Ste*_*ven 7 optimization cpu-architecture bigint rust
为了好玩，我正在用 Rust 编写一个 bignum 库。我的目标（与大多数 bignum 库一样）是尽可能提高效率。我希望它即使在不寻常的架构上也能高效。
在我看来，CPU 将在具有架构的本机位数的整数上更快地执行算术运算（即，u64对于 64 位机器，u16对于 16 位机器等）因此，因为我想创建一个在所有架构上都有效的库，我需要考虑目标架构的本机整数大小。这样做的明显方法是使用cfg 属性 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;
但是，在调查此问题时，我遇到了此评论。它给出了一个架构示例，其中原生 int 大小与指针宽度不同。因此，我的解决方案不适用于所有架构。另一个潜在的解决方案是编写一个构建脚本，它编码一个LargeInt基于 a 的大小定义的小模块usize（我们可以像这样获取：）std::mem::size_of::<usize>()但是，这与上面有相同的问题，因为usize它基于指针宽度以及。最后一个明显的解决方案是简单地为每个架构保留一个本地 int 大小的映射。但是，此解决方案不够优雅且无法很好地扩展，因此我想避免使用它。
所以，我的问题是：有没有办法找到目标的本机 int 大小，最好在编译之前，以减少运行时开销？这种努力是否值得？也就是说，使用本机 int 大小与指针宽度之间是否可能存在显着差异？
通常很难（或不可能）让编译器为 BigNum 的东西发出最佳代码，这就是为什么https://gmplib.org/有其低级原始函数 ( mpn_... docs ) 为各种目标体系结构手工编写的低级原始函数 ( 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 for mpn_add_nand mpn_sub_n (Add OR Sub = aors)，针对没有部分标志摊位的 SandyBridge 系列进行了调整所以它可以循环dec/jnz。
在使用高级语言编写代码时，了解哪种 asm 是最佳的可能会有所帮助。虽然在实践中你甚至不能接近它，所以有时使用不同的技术是有意义的，比如在 32 位整数中只使用高达 2^30 的值（就像 CPython 在内部所做的那样，通过右移，请参阅此中有关 Python 的部分）。在 Rust 中，您确实可以访问以add_overflow获取结转，但使用它仍然很困难。
对于实际使用，为 GMP 编写 Rust 绑定可能是你最好的选择，除非它已经存在。
使用尽可能大的块非常好；在所有当前 CPU 上，add reg64, reg64具有与add reg32, reg32或相同的吞吐量和延迟reg8。因此，每单位完成的工作量是原来的两倍。并在 1 个延迟周期内通过 64 位结果进行传播。
（有其他存储 BigInteger 数据的方法可以使 SIMD 有用；@Mysticial 在长整数例程可以从 SSE 中受益吗？例如，每 32 位 int 30 个值位，允许您推迟规范化，直到几个添加步骤之后。但是每次使用这些数字都必须注意这些问题，因此它不是一个简单的替代品。）
在 Rust 中，您可能只想使用u64而不管目标，除非您真的关心 32 位目标上的少量（单肢）性能。让编译器用add/ adc（加进位）为你构建 u64 操作。
唯一可能需要特定于 ISA 的是 ifu128在某些目标上不可用。您想使用 64 * 64 => 128 位全乘法作为乘法的构建块；如果编译器可以为您做到这一点，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 for 来避免至少成对的情况u128.overflowing_add。希望这不会花费任何 asm 指令，因为 au128已经必须存储在两个单独的 64 位寄存器中，就像两个单独的u64值一样。
因此，组合 tou128可能只是对添加u64元素数组的函数的局部优化，以使编译器少吸。