optimization - 是否有可能在 Rust 中获得整数的 native CPU 大小？

Question

为了好玩，我正在用 Rust 编写一个 bignum 库。我的目标(与大多数 bignum 库一样)是使其尽可能高效。我希望它即使在不寻常的架构上也能高效。

对我来说很直观的是，CPU 将更快地对具有架构的 native 位数的整数执行算术运算(即，u64 用于 64 位机器，u16 用于 16 位机器等)因此，因为我想创建一个对所有架构都有效的库，所以我需要考虑目标架构的 native 整数大小。最明显的方法是使用 cfg attribute target_pointer_width .例如，要定义始终能够容纳超过最大原生 int 大小的最小类型:

#[cfg(target_pointer_width = "16")]
type LargeInt = u32;

#[cfg(target_pointer_width = "32")]
type LargeInt = u64;

#[cfg(target_pointer_width = "64")]
type LargeInt = u128;

然而，在调查这个时，我遇到了 this comment .它给出了一个架构示例，其中 native int 大小与指针宽度不同。因此，我的解决方案不适用于所有架构。另一个可能的解决方案是编写一个构建脚本，该脚本生成一个定义 LargeInt 的小模块。基于 usize 的大小(我们可以像这样获得: std::mem::size_of::<usize>()。)但是，这与上面的问题相同，因为 usize is based on the pointer width也是。最后一个明显的解决方案是简单地为每个架构保留一个原生 int 大小的映射。然而，这个解决方案是不优雅的并且不能很好地扩展，所以我想避免它。

所以，我的问题是:有没有办法找到目标的 native int 大小，最好是在编译之前，以减少运行时开销？这种努力是否值得？也就是说，使用 native int 大小与指针宽度之间是否可能存在显着差异？

Answer 1

通常很难(或不可能)让编译器为 BigNum 的东西发出最佳代码，这就是 https://gmplib.org/ 的原因。有它的低级原始函数 (mpn_... docs) 为各种目标架构手写汇编，并针对不同的微架构进行调整，例如https://gmplib.org/repo/gmp/file/tip/mpn/x86_64/core2/mul_basecase.asm对于多肢*多肢数的一般情况。和https://gmplib.org/repo/gmp/file/tip/mpn/x86_64/coreisbr/aors_n.asm对于 mpn_add_n和 mpn_sub_n (添加 OR Sub = aors)，针对没有部分标志停顿的 SandyBridge 系列进行了调整，因此它可以使用 dec/jnz 循环.

在用高级语言编写代码时，了解哪种 asm 是最佳的可能会有所帮助。虽然在实践中你甚至无法接近它，所以有时使用不同的技术是有意义的，比如在 32 位整数中只使用高达 2^30 的值(就像 CPython 在内部所做的那样，通过右移，见 the section about Python in this)。在 Rust 中，您确实可以访问 add_overflow得到结转，但使用它仍然很困难。

对于实际使用，为 GMP 编写 Rust 绑定(bind)可能是你最好的选择，除非它已经存在。

使用尽可能大的 block 是非常好的；在所有当前 CPU 上，add reg64, reg64具有与 add reg32, reg32 相同的吞吐量和延迟或 reg8 .因此，您每单位完成的工作量是原来的两倍。并在 1 个延迟周期内通过 64 位结果进行传播。

(有其他存储 BigInteger 数据的方法可以使 SIMD 有用；@Mysticial 在 Can long integer routines benefit from SSE? 中解释。例如，每个 32 位 int 有 30 个值位，允许您将规范化推迟到几个添加步骤之后。但是每次使用这样的numbers 必须意识到这些问题，所以它不是一个简单的替代品。)

在 Rust 中，您可能只想使用 u64不管目标是什么 ，除非您真的关心 32 位目标上的小数(单肢)性能。让编译器从 add 中为您构建 u64 操作/adc (加进位)。

唯一可能需要特定于 ISA 的是 u128在某些目标上不可用。您想使用 64 * 64 => 128 位全乘法作为乘法的构建 block ；如果编译器可以使用 u128 为您做到这一点那很好，特别是如果它有效地内联。

另请参阅问题下评论中的讨论。

让编译器发出有效的 BigInt 加法循环(甚至在一个展开循环的主体内)的一个绊脚石是编写一个加法，它接受一个进位输入并产生一个进位输出。请注意 x += 0xff..ff + carry=1即使 0xff..ff + 1 也需要执行回零。所以在 C 或 Rust 中，x += y + carry必须在 y+carry 中检查是否执行和 x+=部分。

说服像 LLVM 这样的编译器后端发出 adc 指令链真的很难(可能是不可能的)。当您不需要从 adc 执行时，可以使用 add/adc。或者如果编译器正在为你做 u128.overflowing_add
通常编译器会将进位标志转换为寄存器中的 0/1，而不是使用 adc。 .你至少可以避免这种情况，至少成对的 u64此外，通过将输入 u64 值与 u128 组合为 u128.overflowing_add .希望这不会花费任何 asm 指令，因为 u128已经必须存储在两个单独的 64 位寄存器中，就像两个单独的 u64值(value)观。

所以结合到 u128可能只是添加 u64 数组的函数的局部优化元素，让编译器少吸一点。