高效计算汉明权重
Efficiently calculate hamming weight
我使用的是 apple m1 处理器。
我想做的是有效地计算 rust 中大型 char 数组中的 1 位。我查找了 arm neon 指令，我想我可以通过 cnt 指令（每 8 位块计数 1）然后使用 addv 来添加每个 8 位块。
首先我想我会输入 64 位 uint。
fn aarch64_hamming_weight(inp: u64) -> u64 {
let mut outp: u64;
unsafe {
asm!(
"dup v0.2d, {input}",
"cnt v0.16b, v0.16b",
"addv b1, v0.16b",// this adds all the bytes of the vector, how do i get the result?!
//"fmov {output2}, b1",
"fmov {output}, v0.d[1]",
input = in(reg) inp,
output = out(reg) outp,
)
}
return outp;
}
这几乎可以工作，但如果您的数字大于 8 位，则结果不太正确；
225的二进制数是4
425的二进制数是260
所以
- 我需要一种获取 addv 输出的方法
- 我需要一种方法让它与任意字符数组一起工作（这需要一个循环，一次提取 128 位）
当我开始写答案时，我认为它会表明内联 asm 完全没有意义，而 RustC 会很好地向量化 u8.count_ones()。不幸的是，情况并非如此，但如果您要编写一个完整的循环，您应该只使用 asm，而不是一次 u64 一个。 （可能仍然是内联汇编，但写一个完整的函数可能是合理的。）
如果 Rust 具有 ARM/AArch64 的 SIMD 内在函数，那将是比内联 asm 更好的选择，并且绝对值得使用。
为了对整个数组进行计数，您不想将每个 cnt 结果分别缩减为标量，尤其是不要一直缩减到 general-purpose 整数寄存器。特别是一次 u64 而不是完整的 128 位。添加到您只在最后减少的计数向量中。
clang/LLVM 知道如何 auto-vectorize 在 C 中对数组进行 __builtin_popcount() 弹出计数，所以我希望 LLVM-based RustC 对 AArch64 没问题。对于 u64 来说还可以，但不幸的是 u8 就很糟糕了。如果您可以 安全地 将 u64 跨度指向您的数据（或引用或 Rust 做的事情？），那么您可以获得很大一部分的好处，而且没有脆弱性内联汇编并且在某种程度上，未来的编译器版本有望改进。
pub fn hamming_weight_arr(inp: &[u64]) -> u64 {
let mut sum : u64 = 0;
for v in inp {
sum += v.count_ones() as u64; // maybe not terrible but a lot of hsumming.
// doing ldp q2, q3 to load 32 bytes per iteration
}
return sum;
}
使用 -O --target aarch64-unknown-linux-gnu 在 https://godbolt.org/z/7qP7cK6bv 上编译（默认 -C --opt-level=3）。
... some setup
.LBB1_5: // inner loop
ldp q2, q3, [x8, #-16] // load pair of 16-byte vectors = unroll by 4x u64
add x8, x8, #32 // pointer increment by 32 bytes
subs x12, x12, #4
cnt v2.16b, v2.16b
cnt v3.16b, v3.16b
uaddlp v2.8h, v2.16b // hsum byte pairs to u16 halfwords
uaddlp v3.8h, v3.16b
uaddlp v2.4s, v2.8h // hsum u16 pairs to u32 words
uaddlp v3.4s, v3.8h
uadalp v0.2d, v2.4s // sum u32 pairs into accumulator u64 vectors (doublewords)
uadalp v1.2d, v3.4s
b.ne .LBB1_5
add v0.2d, v1.2d, v0.2d // combine pair of accumulators
cmp x10, x11
addp d0, v0.2d // and reduce to one 64-bit
fmov x8, d0
b.eq .LBB1_9
.LBB1_7:
add x10, x0, x1, lsl #3
.LBB1_8:
ldr d0, [x9], #8 // scalar cleanup loop, one u64 at a time
cmp x9, x10
cnt v0.8b, v0.8b
uaddlv h0, v0.8b // slow instruction, as Jake mentioned. Or at least high latency
fmov w11, s0
add x8, x11, x8
b.ne .LBB1_8
.LBB1_9:
mov x0, x8
ret
您认为 sum: u32 会有所帮助，因为它需要较少的循环内部加宽。 （如果您有可能溢出的巨大数组，请使用外部循环）。但实际上，我认为 RustC 仍然扩大到 64 位，但随后做了更多工作将这些计数截断为 32 位。几乎可以肯定是 missed-optimization。 （也许是一种围绕 x86 psadbw 构建的策略，它可以一步将字节求和到 u64 块中；LLVM auto-vectorizes popcount with pshufb 以及 x86 上的 AVX2。）
而且您认为对 u8 数组做同样的事情应该矢量化为相同的代码，只是一些额外的标量清理，对吧？ 嗯，它应该，但实际上它仍然只能像 LLVM 喜欢做的那样展开 4 个，但那是 4 个 u8 个元素，内部循环变成了完全垃圾:
// &[u8] version inner loop is a disaster
LBB2_5:
ldurb w12, [x8, #-2] // scalar zero-extending byte load
subs x11, x11, #4
ldrb w13, [x8] // scalar sign-extending byte load
fmov d2, x12 // copy it into vector reg
ldurb w12, [x8, #-1]
fmov d3, x13
ldrb w13, [x8, #1]
add x8, x8, #4
mov v2.d[1], x12 // get two more bytes into the high 64 bits of a vector
mov v3.d[1], x13
cnt v2.16b, v2.16b // same cnt / uaddlp sequence as before
cnt v3.16b, v3.16b
uaddlp v2.8h, v2.16b
uaddlp v3.8h, v3.16b
uaddlp v2.4s, v2.8h
uaddlp v3.4s, v3.8h
uadalp v0.2d, v2.4s
uadalp v1.2d, v3.4s
b.ne .LBB2_5
所以它正在矢量化 (v as u64).count()，并使用它不知道如何优化的罐装食谱。 （例如，如果 cnt 结果为零，除了每个 64 位块的低字节外，uaddlp 加宽是没有意义的，他们可以只对 64 位块使用垂直 add。）
与您从 C 编译器获得的来自 https://github.com/WojciechMula/sse-popcount/ 的手动矢量化 ARM 代码进行比较。如果 ARM Neon 代码与同一存储库中的 x86 代码一样 well-tuned，那么就编译器的最终 asm 输出而言，这就是您应该瞄准的目标，无论您到达那里。
我猜想一个只将 per-byte 计数加宽到 16 位的内部循环会很好，运行 直到在不溢出 [= 的情况下可能的迭代次数32=] 和 +=16 从在输入它的一对字节中看到 all-ones。即 65535/16 向下舍入 = 4095 个向量，然后扩展到 64 位块。
Mula's version does only 31 inner loop iterations, accumulating into 8-bit elements with vaddq_u8. But uadalp v0.16b, v2.8h horizontal-pair u8 字节到 u16 半字元素的累积不适用于 32 位 NEON，仅适用于 AArch64 ASIMD。
关键是要在 inner-most 循环中做最少的工作，理想情况下每个 cnt 结果向量只使用一条廉价指令。 如果你可以在积累时免费获得一些扩展（或者便宜到不会成为瓶颈），那么执行就会在内部循环中停留更长的时间而不会溢出。 （并且意味着外循环中后面的水平缩减步骤更便宜。）
uadalp 在某些 CPU 上与 pure-vertical add 的性能有些不同，但很可能值得使用。 Cortex-A57 optimization guide 表示它有 4 (1) 个周期延迟，1/时钟吞吐量。 (1) 部分是目标操作数的累积延迟；它允许在 horizontal-pair 添加源元素之后，从相同类型的先前操作进行延迟转发。因此在使用 sum += pairs 和 uadalp 的循环中，loop-carried 依赖链只有 1 个循环长。这是理想的。
整数向量上的常规 add 是 3 周期延迟，2/时钟吞吐量，因此它具有更好的吞吐量但创建了 3 周期 loop-carried 依赖链。 （并且没有完成水平累加工作的一步，并且会更快溢出，因为它只使用 8 位和。）
在 Cortex-A57 上，cnt 也只有 1/clock 吞吐量，因此 uadalp 的 1/clock 吞吐量不是整体瓶颈。除非他们竞争同一个执行端口。 uadalp 在 F1 上运行，SIMD-integer add 在 F0/F1 上运行，cnt 在 F0/F1 上运行。因此，无论哪种方式，加法操作都需要窃取一些 cnt 吞吐量，问题就变成了当 F1 有一堆未来的 uadalp 操作时，cnt 是否可以有效地调度到大多数端口 F0排队。 （在尚未准备好的数据上；out-of-order exec 向前看。在大多数 CPU 上，操作作业被安排到端口，因为它们 rename/allocate 从 front-end 到 back-end。 CPU 不知道什么订单数据将准备就绪，但它可以看到端口的队列长度不同。
可以做到（伪代码）
// Probably not a good idea
c1 = cnt(load1)
c2 = cnt(load2)
c1 += c2 // plain SIMD vertical add
uadalp accumulator, c1
这意味着循环中只有一个 uadalp，以防出现吞吐量瓶颈，同时仍然仅将 uadalp 用于累加器，从而通过累加器保持 loop-carried 依赖链短的。 （假设其他 AArch64 CPUs 也为累积指令做早期转发）。
并且它使得在一次迭代中短的独立依赖链略长（从加载到积累的输入），而不是将其保持为两个独立的依赖链。）Low-end ARM CPUs通常具有非常有限的 out-of-order 执行能力（小的调度程序缓冲区）来找到 instruction-level 跨循环迭代的并行性和重叠工作。保持非 loop-carried 的 dep 链较短使得 CPU 更容易。对于像 Cortex-A53 这样的 in-order AArch64 来说，它完全糟透了，除非你展开了很多。
我使用的是 apple m1 处理器。
我想做的是有效地计算 rust 中大型 char 数组中的 1 位。我查找了 arm neon 指令，我想我可以通过 cnt 指令（每 8 位块计数 1）然后使用 addv 来添加每个 8 位块。
首先我想我会输入 64 位 uint。
fn aarch64_hamming_weight(inp: u64) -> u64 {
let mut outp: u64;
unsafe {
asm!(
"dup v0.2d, {input}",
"cnt v0.16b, v0.16b",
"addv b1, v0.16b",// this adds all the bytes of the vector, how do i get the result?!
//"fmov {output2}, b1",
"fmov {output}, v0.d[1]",
input = in(reg) inp,
output = out(reg) outp,
)
}
return outp;
}
这几乎可以工作，但如果您的数字大于 8 位，则结果不太正确； 225的二进制数是4 425的二进制数是260
所以
- 我需要一种获取 addv 输出的方法
- 我需要一种方法让它与任意字符数组一起工作（这需要一个循环，一次提取 128 位）
当我开始写答案时，我认为它会表明内联 asm 完全没有意义，而 RustC 会很好地向量化 u8.count_ones()。不幸的是，情况并非如此，但如果您要编写一个完整的循环，您应该只使用 asm，而不是一次 u64 一个。 （可能仍然是内联汇编，但写一个完整的函数可能是合理的。）
如果 Rust 具有 ARM/AArch64 的 SIMD 内在函数，那将是比内联 asm 更好的选择，并且绝对值得使用。
为了对整个数组进行计数，您不想将每个 cnt 结果分别缩减为标量，尤其是不要一直缩减到 general-purpose 整数寄存器。特别是一次 u64 而不是完整的 128 位。添加到您只在最后减少的计数向量中。
clang/LLVM 知道如何 auto-vectorize 在 C 中对数组进行 __builtin_popcount() 弹出计数，所以我希望 LLVM-based RustC 对 AArch64 没问题。对于 u64 来说还可以，但不幸的是 u8 就很糟糕了。如果您可以 安全地 将 u64 跨度指向您的数据（或引用或 Rust 做的事情？），那么您可以获得很大一部分的好处，而且没有脆弱性内联汇编并且在某种程度上，未来的编译器版本有望改进。
pub fn hamming_weight_arr(inp: &[u64]) -> u64 {
let mut sum : u64 = 0;
for v in inp {
sum += v.count_ones() as u64; // maybe not terrible but a lot of hsumming.
// doing ldp q2, q3 to load 32 bytes per iteration
}
return sum;
}
使用 -O --target aarch64-unknown-linux-gnu 在 https://godbolt.org/z/7qP7cK6bv 上编译（默认 -C --opt-level=3）。
... some setup
.LBB1_5: // inner loop
ldp q2, q3, [x8, #-16] // load pair of 16-byte vectors = unroll by 4x u64
add x8, x8, #32 // pointer increment by 32 bytes
subs x12, x12, #4
cnt v2.16b, v2.16b
cnt v3.16b, v3.16b
uaddlp v2.8h, v2.16b // hsum byte pairs to u16 halfwords
uaddlp v3.8h, v3.16b
uaddlp v2.4s, v2.8h // hsum u16 pairs to u32 words
uaddlp v3.4s, v3.8h
uadalp v0.2d, v2.4s // sum u32 pairs into accumulator u64 vectors (doublewords)
uadalp v1.2d, v3.4s
b.ne .LBB1_5
add v0.2d, v1.2d, v0.2d // combine pair of accumulators
cmp x10, x11
addp d0, v0.2d // and reduce to one 64-bit
fmov x8, d0
b.eq .LBB1_9
.LBB1_7:
add x10, x0, x1, lsl #3
.LBB1_8:
ldr d0, [x9], #8 // scalar cleanup loop, one u64 at a time
cmp x9, x10
cnt v0.8b, v0.8b
uaddlv h0, v0.8b // slow instruction, as Jake mentioned. Or at least high latency
fmov w11, s0
add x8, x11, x8
b.ne .LBB1_8
.LBB1_9:
mov x0, x8
ret
您认为 sum: u32 会有所帮助，因为它需要较少的循环内部加宽。 （如果您有可能溢出的巨大数组，请使用外部循环）。但实际上，我认为 RustC 仍然扩大到 64 位，但随后做了更多工作将这些计数截断为 32 位。几乎可以肯定是 missed-optimization。 （也许是一种围绕 x86 psadbw 构建的策略，它可以一步将字节求和到 u64 块中；LLVM auto-vectorizes popcount with pshufb 以及 x86 上的 AVX2。）
而且您认为对 u8 数组做同样的事情应该矢量化为相同的代码，只是一些额外的标量清理，对吧？ 嗯，它应该，但实际上它仍然只能像 LLVM 喜欢做的那样展开 4 个，但那是 4 个 u8 个元素，内部循环变成了完全垃圾:
// &[u8] version inner loop is a disaster
LBB2_5:
ldurb w12, [x8, #-2] // scalar zero-extending byte load
subs x11, x11, #4
ldrb w13, [x8] // scalar sign-extending byte load
fmov d2, x12 // copy it into vector reg
ldurb w12, [x8, #-1]
fmov d3, x13
ldrb w13, [x8, #1]
add x8, x8, #4
mov v2.d[1], x12 // get two more bytes into the high 64 bits of a vector
mov v3.d[1], x13
cnt v2.16b, v2.16b // same cnt / uaddlp sequence as before
cnt v3.16b, v3.16b
uaddlp v2.8h, v2.16b
uaddlp v3.8h, v3.16b
uaddlp v2.4s, v2.8h
uaddlp v3.4s, v3.8h
uadalp v0.2d, v2.4s
uadalp v1.2d, v3.4s
b.ne .LBB2_5
所以它正在矢量化 (v as u64).count()，并使用它不知道如何优化的罐装食谱。 （例如，如果 cnt 结果为零，除了每个 64 位块的低字节外，uaddlp 加宽是没有意义的，他们可以只对 64 位块使用垂直 add。）
与您从 C 编译器获得的来自 https://github.com/WojciechMula/sse-popcount/ 的手动矢量化 ARM 代码进行比较。如果 ARM Neon 代码与同一存储库中的 x86 代码一样 well-tuned，那么就编译器的最终 asm 输出而言，这就是您应该瞄准的目标，无论您到达那里。
我猜想一个只将 per-byte 计数加宽到 16 位的内部循环会很好，运行 直到在不溢出 [= 的情况下可能的迭代次数32=] 和 +=16 从在输入它的一对字节中看到 all-ones。即 65535/16 向下舍入 = 4095 个向量，然后扩展到 64 位块。
Mula's version does only 31 inner loop iterations, accumulating into 8-bit elements with vaddq_u8. But uadalp v0.16b, v2.8h horizontal-pair u8 字节到 u16 半字元素的累积不适用于 32 位 NEON，仅适用于 AArch64 ASIMD。
关键是要在 inner-most 循环中做最少的工作，理想情况下每个 cnt 结果向量只使用一条廉价指令。 如果你可以在积累时免费获得一些扩展（或者便宜到不会成为瓶颈），那么执行就会在内部循环中停留更长的时间而不会溢出。 （并且意味着外循环中后面的水平缩减步骤更便宜。）
uadalp 在某些 CPU 上与 pure-vertical add 的性能有些不同，但很可能值得使用。 Cortex-A57 optimization guide 表示它有 4 (1) 个周期延迟，1/时钟吞吐量。 (1) 部分是目标操作数的累积延迟；它允许在 horizontal-pair 添加源元素之后，从相同类型的先前操作进行延迟转发。因此在使用 sum += pairs 和 uadalp 的循环中，loop-carried 依赖链只有 1 个循环长。这是理想的。
整数向量上的常规 add 是 3 周期延迟，2/时钟吞吐量，因此它具有更好的吞吐量但创建了 3 周期 loop-carried 依赖链。 （并且没有完成水平累加工作的一步，并且会更快溢出，因为它只使用 8 位和。）
在 Cortex-A57 上，cnt 也只有 1/clock 吞吐量，因此 uadalp 的 1/clock 吞吐量不是整体瓶颈。除非他们竞争同一个执行端口。 uadalp 在 F1 上运行，SIMD-integer add 在 F0/F1 上运行，cnt 在 F0/F1 上运行。因此，无论哪种方式，加法操作都需要窃取一些 cnt 吞吐量，问题就变成了当 F1 有一堆未来的 uadalp 操作时，cnt 是否可以有效地调度到大多数端口 F0排队。 （在尚未准备好的数据上；out-of-order exec 向前看。在大多数 CPU 上，操作作业被安排到端口，因为它们 rename/allocate 从 front-end 到 back-end。 CPU 不知道什么订单数据将准备就绪，但它可以看到端口的队列长度不同。
可以做到（伪代码）
// Probably not a good idea
c1 = cnt(load1)
c2 = cnt(load2)
c1 += c2 // plain SIMD vertical add
uadalp accumulator, c1
这意味着循环中只有一个 uadalp，以防出现吞吐量瓶颈，同时仍然仅将 uadalp 用于累加器，从而通过累加器保持 loop-carried 依赖链短的。 （假设其他 AArch64 CPUs 也为累积指令做早期转发）。
并且它使得在一次迭代中短的独立依赖链略长（从加载到积累的输入），而不是将其保持为两个独立的依赖链。）Low-end ARM CPUs通常具有非常有限的 out-of-order 执行能力（小的调度程序缓冲区）来找到 instruction-level 跨循环迭代的并行性和重叠工作。保持非 loop-carried 的 dep 链较短使得 CPU 更容易。对于像 Cortex-A53 这样的 in-order AArch64 来说，它完全糟透了，除非你展开了很多。