是否有可能在 Rust 中获得整数的本机 CPU 大小？

Question

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

在我看来，直觉上 CPU 将以架构的本机位数更快地对整数执行算术运算（即，u64 对于 64 位机器，u16 对于 16 位机器等）因此，由于我想创建一个在所有体系结构上都有效的库，因此我需要考虑目标体系结构的本机整数大小。显而易见的方法是使用 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;

然而，在调查这个问题时，我也遇到了 . It gives an example of an architecture where the native int size is different from the pointer width. Thus, my solution will not work for all architectures. Another potential solution would be to write a build script which codegens a small module which defines LargeInt based on the size of a usize (which we can acquire like so: std::mem::size_of::<usize>().) However, this has the same problem as above, since 。最后一个明显的解决方案是简单地为每个体系结构保留一个本地 int 大小的映射。但是，此解决方案不够优雅且无法很好地扩展，因此我想避免使用它。

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

Answer 1

通常很难（或不可能）让编译器为 BigNum 的东西发出最佳代码，这就是为什么 https://gmplib.org/ has its low level primitive functions (mpn_... docs) hand-written in assembly for various target architectures with tuning for different micro-architecture, e.g. https://gmplib.org/repo/gmp/file/tip/mpn/x86_64/core2/mul_basecase.asm for the general case of multi-limb * multi-limb numbers. And https://gmplib.org/repo/gmp/file/tip/mpn/x86_64/coreisbr/aors_n.asm 用于 mpn_add_n 和 mpn_sub_n（Add OR Sub = aors），针对没有部分标志停顿的 SandyBridge 系列进行了调整，因此它可以使用 dec/jnz.

循环

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

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

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

（有其他方法可以存储 BigInteger 数据，这可以使 SIMD 变得有用；@Mysticial 在 Can long integer routines benefit from SSE? 中进行了解释。例如，每个 32 位 int 有 30 个值位，允许您将规范化推迟到一些加法之后步骤。但每次使用此类数字都必须注意这些问题，因此它不是一个简单的替代品。）

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

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

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

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

说服像 LLVM 这样的编译器后端发出一串 adc 指令真的很难（可能是不可能的）。当您不需要来自 adc 的结转时，add/adc 是可行的。或者如果编译器正在为你做 u128.overflowing_add

编译器通常会将进位标志转换为寄存器中的 0 / 1，而不是使用 adc。您可以希望通过将 u128.overflowing_add 的输入 u64 值组合到 u128 来至少对 u64 避免这种情况。希望这不会花费任何 asm 指令，因为 u128 已经必须存储在两个单独的 64 位寄存器中，就像两个单独的 u64 值一样。

因此，最多合并 u128 可能只是对添加 u64 元素数组的函数的局部优化，以减少编译器的性能。

Answer 2

在我的图书馆ibig我做的是：

Select 特定于体系结构的大小基于 target_arch。
如果我没有架构值，select 16、32 或 64 基于 target_pointer_width。
如果 target_pointer_width 不是这些值之一，则使用 64。

是否有可能在 Rust 中获得整数的本机 CPU 大小？

Is it possible to get the native CPU size of an integer in Rust?

optimization

cpu-architecture

bigint

rust