我在设计一个带前缀的可变长度整数。Rust有计算前导和尾随1和0的方法：https://doc.rust-lang.org/std/primitive.u64.html#method.leading_zeros这些方法在x86_64、arm32和arm64上的效率是否存在差异？例如，如果计数尾随1比计数尾随0快，我将使用xxxx0111而不是xxxx1000作为长度编码字节（在本例中，用于三个后续字节）。
ee7vknir1#
在所有3个ISA上，计算尾随零比计算尾随1快：x86*、ARM、AArch 64。它们都提供零计数指令，如x86 bsf（查找最低设置位）或x86 BMI 1 tzcnt（尾随零计数）。对运行时变量中的前导/尾随1进行计数需要对输入求反。ARM /AArch 64提供了前导零计数，但对于尾随零的最佳选择是rbit/clz，以进行位反转（自ARMv 6 t2或ARMv7以来）.https://godbolt.org/z/Yr7eac。在此之前，编译器必须将最低设置位与x & -x隔离，对其中的前导零进行计数，并取31-clz(x&-x)。(On x86，使用BMI 1计算前导零的效率最高。如果没有BMI 1，bsr可以给予最高设置位的位置，因此编译器需要31-bsr(x)来实现clz。在AMD CPU上，bsf / bsr比它们的tzcnt / lzcnt对应项要慢得多，因此如果可能，最好使用-march=native或任何Rust等效项进行编译。）在AMD Zen上，lzcnt是1个uop，tzcnt是2个uop。https://uops.info/假定额外的uop是位反转或与x & -x隔离最低设置位，但无论哪种方式都生成一些东西以馈送到lzcnt硬件。相关有趣事实：在设置位上循环以找到它们的位置通常最好使用x = blsr(x)作为循环进位依赖x &= x-1，并独立地对设置位的每个结果进行位扫描。因此，在循环的关键路径延迟中不存在位扫描和移位。相关：在历史x86 CPU上设置任意大小整数C++ bsr/bsf和tzcnt中的前导零位。
bsf
tzcnt
rbit
clz
x & -x
31-clz(x&-x)
bsr
31-bsr(x)
-march=native
lzcnt
x = blsr(x)
x &= x-1
1条答案
按热度按时间ee7vknir1#
在所有3个ISA上，计算尾随零比计算尾随1快：x86*、ARM、AArch 64。它们都提供零计数指令，如x86
bsf（查找最低设置位）或x86 BMI 1tzcnt（尾随零计数）。对运行时变量中的前导/尾随1进行计数需要对输入求反。ARM /AArch 64提供了前导零计数，但对于尾随零的最佳选择是
rbit/clz，以进行位反转（自ARMv 6 t2或ARMv7以来）.https://godbolt.org/z/Yr7eac。在此之前，编译器必须将最低设置位与x & -x隔离，对其中的前导零进行计数，并取31-clz(x&-x)。(On x86，使用BMI 1计算前导零的效率最高。如果没有BMI 1，
bsr可以给予最高设置位的位置，因此编译器需要31-bsr(x)来实现clz。在AMD CPU上，bsf / bsr比它们的tzcnt / lzcnt对应项要慢得多，因此如果可能，最好使用-march=native或任何Rust等效项进行编译。）在AMD Zen上，
lzcnt是1个uop，tzcnt是2个uop。https://uops.info/假定额外的uop是位反转或与x & -x隔离最低设置位，但无论哪种方式都生成一些东西以馈送到lzcnt硬件。相关有趣事实：在设置位上循环以找到它们的位置通常最好使用
x = blsr(x)作为循环进位依赖x &= x-1，并独立地对设置位的每个结果进行位扫描。因此，在循环的关键路径延迟中不存在位扫描和移位。相关：在历史x86 CPU上设置任意大小整数C++ bsr/bsf和tzcnt中的前导零位。