如何解决指针数组中的数据依赖性？
How can I resolve data dependency in pointer arrays?
如果我们有一个整型指针数组，它们都指向同一个 int，并循环执行 ++ 操作，它会比那些指向两个不同 int 的指针慢 100%。这是一个具体的例子
int* data[2];
int a, b;
a = b = 0;
for (auto i = 0ul; i < 2; ++i) {
// Case 3: 2.5 sec
data[i] = &a;
// Case 2: 1.25 sec
// if (i & 1)
// data[i] = &a;
// else
// data[i] = &b;
}
for (auto i = 0ul; i < 1000000000; ++i) {
// Case 1: 0.5sec
// asm volatile("" : "+g"(i)); // deoptimize
// ++*data[0];
++*data[i & 1];
}
总而言之，观察结果是：（描述了循环体）
案例 1（快速）：++*指针[0]
情况 2（中等）：++*指针[i]，一半指针指向一个 int，另一半指针指向另一个 int。
情况 3（慢）：++*pointer[i]，所有指针都指向同一个 int
这是我目前的想法。案例 1 很快，因为现代 CPU 知道我们在 read/write 相同的内存位置，从而缓冲操作，而在案例 2 和案例 3 中，我们需要在每次迭代中写出结果。情况 3 比情况 2 慢的原因是因为当我们通过指针 a 写入内存位置，然后尝试通过指针 b 读取它时，我们必须等待写入完成。这会停止超标量执行。
我的理解正确吗？有什么方法可以在不更改指针数组的情况下使案例 3 更快？ （也许添加一些 CPU 提示？）
您发现了导致直方图中出现瓶颈的影响之一。该问题的解决方法是保留多个计数器数组并在它们之间循环，因此相同索引的重复 运行 分布在内存中的 2 或 4 个不同的计数器上。
（然后遍历计数器数组，将它们求和为一组最终计数。这部分可以受益于 SIMD。）
Case 1 is fast because modern CPU knows we are read/write the same memory location, thus buffering the operation
不，这不是 CPU，它是 编译时 优化。
++*pointer[0] 很快，因为编译器可以将 store/reload 提升到循环之外，实际上只是递增一个寄存器。 （如果您不使用结果，它甚至可能会优化掉。）
没有数据争用 UB 的假设让编译器假设没有其他任何东西正在修改 pointer[0] 所以它肯定是每次递增的同一个对象。 as-if 规则让它将 *pointer[0] 保存在寄存器中，而不是实际执行内存目标增量。
所以这意味着增量有 1 个周期延迟，当然它可以将多个增量合并为一个并执行 *pointer[0] += n 如果它完全展开并优化了循环。
when we write to a memory location by pointer a, and then trying to read it by pointer b, we have to wait the write to finish. This stops superscalar execution.
是的，通过该内存位置的数据依赖性是问题所在。在编译时不知道指针都指向同一个位置的情况下，编译器将生成实际上增加指向内存位置的 asm。
不过，"wait for the write to finish" 并不严格准确。 CPU 有一个存储缓冲区，用于将存储执行与缓存未命中以及实际上提交给 L1d 并对其他内核可见的存储的乱序推测执行分离。重新加载最近存储的数据不必等待它提交到缓存； 存储转发 从存储缓冲区到重新加载是一旦 CPU 检测到的事情。
在现代英特尔 CPUs 上，存储转发延迟约为 5 个周期，因此内存目标添加具有 6 个周期延迟。 （1 个用于添加，5 个用于 store/reload，如果它在关键路径上。）
是的，乱序执行让这些 6 周期延迟依赖链中的两个 运行 并行。并且循环开销隐藏在该延迟下，再次由 OoO 执行。
相关：
- x86 处理器中的存储到加载转发和内存消歧
在 stuffedcow.net
- How does store to load forwarding happens in case of unaligned memory access?
（在 Sandybridge 系列上，如果您不尝试立即重新加载，存储转发延迟可以减少。）
Is there any way to make Case 3 faster without changing the pointer array?
是的，如果这种情况是预期的，也许 branch 就可以了:
int *current_pointer = pointer[0];
int repeats = 1;
...
loop {
if (pointer[i] == current_pointer) {
repeats++;
} else {
*current_pointer += repeats;
current_pointer = pointer[i];
repeats = 1;
}
}
我们通过 计算重复相同指针的 运行 长度来优化 。
这完全被情况 2 打败了，如果长 运行 是 不 常见的，则表现会很差。
短运行s可以被乱序执行隐藏；只有当 dep 链变得足够长以填充 ROB（重新排序缓冲区）时，我们才真正停止。
如果我们有一个整型指针数组，它们都指向同一个 int，并循环执行 ++ 操作，它会比那些指向两个不同 int 的指针慢 100%。这是一个具体的例子
int* data[2];
int a, b;
a = b = 0;
for (auto i = 0ul; i < 2; ++i) {
// Case 3: 2.5 sec
data[i] = &a;
// Case 2: 1.25 sec
// if (i & 1)
// data[i] = &a;
// else
// data[i] = &b;
}
for (auto i = 0ul; i < 1000000000; ++i) {
// Case 1: 0.5sec
// asm volatile("" : "+g"(i)); // deoptimize
// ++*data[0];
++*data[i & 1];
}
总而言之，观察结果是：（描述了循环体）
案例 1（快速）：++*指针[0]
情况 2（中等）：++*指针[i]，一半指针指向一个 int，另一半指针指向另一个 int。
情况 3（慢）：++*pointer[i]，所有指针都指向同一个 int
这是我目前的想法。案例 1 很快，因为现代 CPU 知道我们在 read/write 相同的内存位置，从而缓冲操作，而在案例 2 和案例 3 中，我们需要在每次迭代中写出结果。情况 3 比情况 2 慢的原因是因为当我们通过指针 a 写入内存位置，然后尝试通过指针 b 读取它时，我们必须等待写入完成。这会停止超标量执行。
我的理解正确吗？有什么方法可以在不更改指针数组的情况下使案例 3 更快？ （也许添加一些 CPU 提示？）
您发现了导致直方图中出现瓶颈的影响之一。该问题的解决方法是保留多个计数器数组并在它们之间循环，因此相同索引的重复 运行 分布在内存中的 2 或 4 个不同的计数器上。
（然后遍历计数器数组，将它们求和为一组最终计数。这部分可以受益于 SIMD。）
Case 1 is fast because modern CPU knows we are read/write the same memory location, thus buffering the operation
不，这不是 CPU，它是 编译时 优化。
++*pointer[0] 很快，因为编译器可以将 store/reload 提升到循环之外，实际上只是递增一个寄存器。 （如果您不使用结果，它甚至可能会优化掉。）
没有数据争用 UB 的假设让编译器假设没有其他任何东西正在修改 pointer[0] 所以它肯定是每次递增的同一个对象。 as-if 规则让它将 *pointer[0] 保存在寄存器中，而不是实际执行内存目标增量。
所以这意味着增量有 1 个周期延迟，当然它可以将多个增量合并为一个并执行 *pointer[0] += n 如果它完全展开并优化了循环。
when we write to a memory location by pointer a, and then trying to read it by pointer b, we have to wait the write to finish. This stops superscalar execution.
是的，通过该内存位置的数据依赖性是问题所在。在编译时不知道指针都指向同一个位置的情况下，编译器将生成实际上增加指向内存位置的 asm。
不过，"wait for the write to finish" 并不严格准确。 CPU 有一个存储缓冲区，用于将存储执行与缓存未命中以及实际上提交给 L1d 并对其他内核可见的存储的乱序推测执行分离。重新加载最近存储的数据不必等待它提交到缓存； 存储转发 从存储缓冲区到重新加载是一旦 CPU 检测到的事情。
在现代英特尔 CPUs 上，存储转发延迟约为 5 个周期，因此内存目标添加具有 6 个周期延迟。 （1 个用于添加，5 个用于 store/reload，如果它在关键路径上。）
是的，乱序执行让这些 6 周期延迟依赖链中的两个 运行 并行。并且循环开销隐藏在该延迟下，再次由 OoO 执行。
相关：
- x86 处理器中的存储到加载转发和内存消歧 在 stuffedcow.net
- How does store to load forwarding happens in case of unaligned memory access?
Is there any way to make Case 3 faster without changing the pointer array?
是的，如果这种情况是预期的，也许 branch 就可以了:
int *current_pointer = pointer[0];
int repeats = 1;
...
loop {
if (pointer[i] == current_pointer) {
repeats++;
} else {
*current_pointer += repeats;
current_pointer = pointer[i];
repeats = 1;
}
}
我们通过 计算重复相同指针的 运行 长度来优化 。
这完全被情况 2 打败了，如果长 运行 是 不 常见的，则表现会很差。
短运行s可以被乱序执行隐藏；只有当 dep 链变得足够长以填充 ROB（重新排序缓冲区）时，我们才真正停止。