QuickDiv

QuickDiv是一个Rust crate，允许您通过基于libdivide C/C++库的算法来加速通过相同的除数进行的重复除法和取模操作。

在大多数硬件上，整数除法操作比乘法和加法操作执行时间更长。因此，编译器通常通过用更便宜的移位、乘法和加法序列替换它来优化常数的除法。此crate允许您将类似的算法应用于仅在运行时才知道的值进行优化。

性能提升将在各个平台、CPU和整数宽度之间有所不同，但您可以预期，使用预计算的除数除以整数比内置的硬件除法方法快2到10倍。请注意，准备除数的成本高于单次未优化的除法：它将至少需要通过相同的除数进行2次除法才能达到盈亏平衡。

此crate支持所有宽度的原始整数类型，包括有符号和无符号变体。它需要Rust版本1.54或更高。它是#![no_std]和#![forbid(unsafe_code)]。

示例

use quickdiv::DivisorU64;

fn is_quadratic_residue(q: u64, modulus: u64) -> bool {
    // Initializing a divisor is more expensive than a single
    // unoptimized division, to gain a benefit you must divide
    // multiple times by the same divisor.
    let modulus = DivisorU64::new(modulus);

    // The original value can be recovered by using ::get().
    for x in (0..modulus.get()) {
        // A divisor can be used as the second operand with
        // the / and % operators.
        if (x * x) % modulus == q {
            return true;
        }
    }

    false
}

assert!(is_quadratic_residue(152, 169));
assert!(!is_quadratic_residue(51, 111));

性能

以下基准测试应该能给您一个大致的了解，您能期待的速度提升。数字表示每秒处理百万个元素的吞吐量（越大越好），在各个任务上。对于Quotient Sum，我们通过一个固定的除数将一组随机整数除以，在LCG中，我们根据一个固定的模数计算余数，最后，在FizzBuzz中，我们检查随机整数是否能被一个固定的除数整除。

请注意，虽然 QuickDiv 计算余数并检查其是否为零，但编译器使用不同的方法直接检查可除性，这使得在 FizzBuzz 任务上的性能更快。

注意事项

• 这些结果仅适用于 u64。性能可能因位数和符号而异。
• 基准测试是在 AMD Ryzen 5 2600 CPU（即较旧的 x86-64 CPU）上运行的。一些较新的高端处理器，如 Apple M1/M2，具有非常快的硬件除法，因此速度提升可能不太明显。
• 所有任务至少重复使用了 1000 次相同的除数，这使得分支预测变得简单。如果您正在迭代不同除数的集合，则可能会遇到更差的表现。如果您想了解更多信息，请查看 Paul Khuong 关于他的无分支 Rust 整数除法库 Reciprocal 的帖子 Paul Khuong's post。

如果您想自己运行这些基准测试，请查看 GitHub 仓库中的 benchmarks crate。

许可证

许可协议包括以下之一

• Apache License，版本 2.0，(LICENSE-APACHE 或 https://www.apache.org/licenses/LICENSE-2.0)
• MIT 许可证 (LICENSE-MIT 或 https://opensource.org/licenses/MIT)
• zlib 许可证 (LICENSE-ZLIB 或 https://opensource.org/license/zlib/)

由您选择。

贡献

除非您明确声明，否则根据 Apache-2.0 许可证定义的任何贡献，均应按上述方式多重许可，而不附加任何额外条款或条件。