59

我一直在阅读有关新的 C++11 内存模型的信息，并且遇到了该std::kill_dependency功能（第 29.3/14-15 节）。我很难理解为什么我会想要使用它。

我在N2664 提案中找到了一个示例，但没有多大帮助。

它首先显示没有std::kill_dependency. 在这里，第一行将依赖项携带到第二行中，第二行将依赖项携带到索引操作中，然后将依赖项携带到do_something_with函数中。

r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(a[r2]);

还有一个例子std::kill_dependency用来打破第二行和索引之间的依赖关系。

r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(a[std::kill_dependency(r2)]);

据我所知，这意味着索引和调用do_something_with不是在第二行之前排序的依赖项。根据 N2664：

这允许编译器重新排序对 的调用do_something_with，例如，通过执行预测 的值的推测优化a[r2]。

为了调用do_something_with该值a[r2]是必需的。如果，假设，编译器“知道”数组被零填充，它可以优化该调用do_something_with(0);并根据其他两条指令重新排序该调用。它可以产生以下任何一种：

// 1
r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(0);
// 2
r1 = x.load(memory_order_consume);
do_something_with(0);
r2 = r1->index;
// 3
do_something_with(0);
r1 = x.load(memory_order_consume);
r2 = r1->index;

我的理解正确吗？

如果do_something_with通过其他方式与另一个线程同步，那么这对于x.load调用和另一个线程的顺序意味着什么？

假设我的理解是正确的，还有一件事困扰着我：当我编写代码时，什么原因会导致我选择杀死依赖项？

4

3 回答 3

39

memory_order_consume 的目的是确保编译器不会进行某些可能破坏无锁算法的不幸优化。例如，考虑以下代码：

int t;
volatile int a, b;

t = *x;
a = t;
b = t;

符合标准的编译器可以将其转换为：

a = *x;
b = *x;

因此，a 可能不等于 b。它还可以：

t2 = *x;
// use t2 somewhere
// later
t = *x;
a = t2;
b = t;

通过 using load(memory_order_consume)，我们要求正在加载的值的使用不会在使用点之前移动。换句话说，

t = x.load(memory_order_consume);
a = t;
b = t;
assert(a == b); // always true

标准文档考虑了一种情况，您可能只对排序结构的某些字段感兴趣。例子是：

r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(a[std::kill_dependency(r2)]);

这指示编译器允许它有效地执行以下操作：

predicted_r2 = x->index; // unordered load
r1 = x; // ordered load
r2 = r1->index;
do_something_with(a[predicted_r2]); // may be faster than waiting for r2's value to be available

甚至这样：

predicted_r2 = x->index; // unordered load
predicted_a  = a[predicted_r2]; // get the CPU loading it early on
r1 = x; // ordered load
r2 = r1->index; // ordered load
do_something_with(predicted_a);

如果编译器知道这do_something_with不会改变 r1 或 r2 的加载结果，那么它甚至可以一直向上提升：

do_something_with(a[x->index]); // completely unordered
r1 = x; // ordered
r2 = r1->index; // ordered

这允许编译器在优化方面有更多的自由。

于 2011-08-22T19:02:41.087 回答
11

除了其他答案之外，我还要指出 C++ 社区的权威领导者之一 Scott Meyers 非常强烈地抨击 memory_order_consume。他基本上说他认为它在标准中没有位置。他说有两种情况 memory_order_consume 有任何影响：

  • 旨在支持 1024+ 核心共享内存机器的奇特架构。
  • DEC 阿尔法

是的，再一次，DEC Alpha 通过使用一种直到多年后在荒谬的专业机器上才出现在任何其他芯片中的优化，再次陷入了臭名昭著的境地。

特别的优化是那些处理器允许在实际获取该字段的地址之前取消引用该字段（即它可以在它甚至查找x之前查找x->y，使用x的预测值）。然后它返回并确定 x 是否是它预期的值。成功后，它节省了时间。失败时，它必须返回并再次获取 x->y。

Memory_order_consume 告诉编译器/架构这些操作必须按顺序发生。然而，在最有用的情况下，人们最终会想要做 (x->yz)，其中 z 不会改变。memory_order_consume 将强制编译器保持 xy 和 z 的顺序。kill_dependency(x->y).z 告诉编译器/架构它可能会继续执行这种邪恶的重新排序。

99.999% 的开发人员可能永远不会在需要此功能（或根本没有任何效果）的平台上工作。

于 2013-09-03T05:51:43.743 回答
2

的通常用例kill_dependency来自以下情况。假设您想要对重要的共享数据结构进行原子更新。一个典型的方法是非原子地创建一些新数据并原子地从数据结构中摆动指针到新数据。一旦你这样做了，你不会改变新数据，直到你把指针从它移到别的东西上（并等待所有读者腾出）。这种范式被广泛使用，例如 Linux 内核中的 read-copy-update。

现在，假设读取器读取了指针，读取了新数据，稍后返回并再次读取指针，发现指针没有改变。硬件无法判断指针没有再次更新，因此从consume语义上讲，他不能使用数据的缓存副本，而是必须从内存中再次读取它。（或者换一种说法，硬件和编译器不能在读取指针之前推测性地移动数据的读取。）

这就是kill_dependency救援的地方。通过将指针包装在 a 中kill_dependency，您可以创建一个不再传播依赖关系的值，从而允许通过指针进行访问以使用新数据的缓存副本。

于 2013-11-07T14:18:24.640 回答