枚举 n 位所有值的时间

Question

我正在寻找遍历可以用 n 位编码的所有可能值所需的理论时间，其中 n 很大（比如 80）。我知道这需要一些指令，即测试、加法和跳转。但我无法弄清楚 CPU 将如何在这样的数字上管理这些操作，以及每次递增的循环总数。

感谢任何帮助，谢谢！

Answer 1

总结：每个值一个时钟周期，将结果存储到内存中，在乱序执行时非常容易CPU。除了存储结果之外的任何事情都会比递增更多的开销。

指令 throughput/latency 和 CPU 来自 Agner Fog 的执行管道信息。

80 位比普通 64 位 CPU 上的单个寄存器大，因此我们需要一对寄存器来保存这些值。即

uint64_t high, low;  // or a struct, or a 2-element array

无论是单独的变量、结构字段还是数组元素，任何体面的编译器都会将它们保存在寄存器中。 high 可以是 32 位变量。

有两种方法可以将这对数字从 0 增加到 2^80-1：

慢速方式：low+=1, high = add-with-cary(high, 0).
快捷方式：双嵌套循环：

low = 0;
for (high = 0 ; high < 1UL << (80-64) ; high++) {
    do {
        use_value(high,low);  // this point sees all 2^64 values of low
        low++;
    } while (low != 0);
    // low has wrapped to zero, so we don't even have to re-zero it
}

如果必须使用 32 位代码执行此操作，请使用三层嵌套循环。（在 32 位代码中使用 uint64_t 可能会很慢，每次都添加进位。）

这应该编译成一个内部循环，每次迭代只需要一个周期。（Intel Haswell 可以进行每周期一次的循环迭代，但 Intel Sandybridge 的分支吞吐量仅为每 2 个周期一次。）

我把这个 on godbolt 和 store(memory_order_relaxed) 放在原子全局变量中作为我的 use(high,low)，以防止循环优化。存储比函数调用的开销更少，并且不需要 mov 指令将变量放入正确的寄存器中。它实际上编译成一个相当好的循环，应该运行在大多数 CPU 上每个时钟一个。

当我在原子存储之前有 low++ 时，它使用了一个额外的 test 指令，这是愚蠢的。它应该这样做：

loop80:
    xor edx, edx    # high
    xor eax, eax    # low
.Louter_loop:
    mov QWORD PTR global_h[rip], rdx    # or this could just be a 32bit store
.Linner_loop:
    mov QWORD PTR global_l[rip], rax    #,, low
    inc rax     # shorter encoding than add rax, 1
    jne .Linner_loop      # flags set by inc
 # inner loop is 2 fused-domain uops.  Or on AMD, 3 macro-ops since it can't fuse ALU ops with jcc

    inc edx     # only need to use the 32bit reg.
    cmp edx, 65536   # or count down from 65535 to zero, saving the cmp insn
    jne .Louter_loop

    ret

通过循环展开（gcc -O3 -funroll-loops），gcc 和 clang 可以使用 lea 指令并行执行 low+1、low+2、low+3 等，因此循环-携带依赖性仅为low+=8。这大大降低了所需的分支吞吐量，但现在瓶颈变成了存储吞吐量（每个时钟一个）。

如果我们不考虑存储，我们可以在寄存器中每个时钟生成 3 个 low 值。（英特尔 SnB 和 Haswell 可以运行 LEA 在两个执行端口上，并在第三个端口上融合算术+分支。）这使得没有执行资源可以自由地使用值做 任何事情 ，但您所要求的只是列举它们。 LEA 作为非破坏性的 3 操作数加法运算很有用。超过该吞吐量需要更多的 LEA 吞吐量，或不同的 CPU 架构。例如大多数 RISC CPUs（ARM、PowerPC 等）对大多数 ALU 操作都有 3 个操作数指令，而不是 dest = src 操作数之一。我没有查看 POWER 架构上的指令吞吐量（而且我发现指令助记符真的很难读......），但它可能能够并行执行 4 个加法。如果是这样，它可能会在此微基准测试中击败英特尔的 x86 实现。

注意我们是如何不递增全局变量的。在 dep 链中具有 store->load 依赖性将使它至少有 6 个周期长。原子增量（lock inc [mem]）需要相当长的时间。

因此，如果您需要对每个位模式做任何事情，即使只是将其存储在内存中，也会占用运行ning 时间。如果您不需要存储它，乱序执行CPU运行宁好的代码可以在每个时钟并行生成多个值。（英特尔和 AMD 当前的实现每个时钟只能存储一次。）

如果你想开始变傻，可以使用向量指令递增 16（或 32，或 AVX512 为 64）8 位值，并对该向量进行一次 16B（或 32B 或 64B）存储每个时钟。但是，这不会在内存中产生连续的 80 位值，这就是为什么我称它为愚蠢的原因。

枚举 n 位所有值的时间

Time to enumerate all values in n bits

cpu

bits

enumerate