优化 64 位模数运算，以实现重复使用的运行时模数

Question

我有数十亿个无符号 64 位数字 (x)，我需要找到它们x % m。 m对所有人来说都是相同的，但不是编译时常量。 m大于一。

和x都m同样可能保存任何 64 位值。

（如果m是编译时常量，我可以相信编译器会尽力而为。）

由于m所有这些操作都是相同的，并且我有可用的存储空间，是否有一种优化可以让我x % m比m每个操作都不同时更快地计算所有结果x？

（我受到常量除法优化的启发，它将除法转换为乘法、移位和加法。C、Rust 或伪代码中的说明性代码会很棒。）

我看过该文档，但他们在不计算商的情况下计算模数的优化仅适用于 的除数2^n +/- 1。

Answer 1

下面是我将测试的方法，因为对该问题的评论已经清楚地表明 和 的分布x很m重要。

我没有意识到的是，这种可能性有 50% m > x。

未经测试的伪代码：

fn mod(x: u64, m: u64) -> u64 {
    if m > x {
        x
    } else if 2*m > x {
        x - m
    } else {
        x % m
    }
}

这很可能是编译器产生的结果。我没有测试过。

更新：我在我的 i5 2500K 上测试了此优化，处理 1 GiB 的数据。

结果是速度稳定提高了 67%：

opt: 713.113926ms
plain: 1.195687298s

基准测试代码是：

use std::time::Instant;
use rand::Rng;

const ARR_LEN: usize = 128 * 1024;
const ROUNDS: usize = 1024;

fn plain_mod_test(x: &[u64; ARR_LEN], m: u64, result: &mut [u64; ARR_LEN]) {
    for i in 0..ARR_LEN {
        result[i] = x[i] % m;
    }
}

fn opt_mod_test(x: &[u64; ARR_LEN], m: u64, result: &mut [u64; ARR_LEN]) {
    for i in 0..ARR_LEN {
        result[i] = if m > x[i] {
            x[i]
        } else if m > x[i] / 2 {
            x[i] - m
        } else {
            x[i] % m
        }
    }
}

fn main() {
    // 1 MiB of pseudo-random values x
    let mut rng = rand::thread_rng();
    let mut x = [0u64; ARR_LEN];
    for i in 0..ARR_LEN {
        x[i] = rng.gen();
    }

    // 1 KiB of pseudo-random modulii m
    let mut m = [0u64; ROUNDS];
    for r in 0..ROUNDS {
        m[r] = rng.gen(); // there's only a 1 in 2^64 chance that 0 will be generated
    }

    // 1 GiB of output each, use Vec to avoid stack overflow
    let mut plain_results = vec![[0u64; ARR_LEN]; ROUNDS];
    let mut opt_results = vec![[0u64; ARR_LEN]; ROUNDS];

    // These loops modulus 1GB of data each.
    let start_opt = Instant::now();
    for r in 0..ROUNDS {
        opt_mod_test(&x, m[r], &mut opt_results[r]);
    }
    let stop_opt = Instant::now();
    println!("opt: {:?}", stop_opt - start_opt);

    let start_plain = Instant::now();
    for r in 0..ROUNDS {
        plain_mod_test(&x, m[r], &mut plain_results[r]);
    }
    let stop_plain = Instant::now();
    println!("plain: {:?}", stop_plain - start_plain);


    // Stop the results from being optimised away, by using them.
    let mut plain_sum = 0;
    let mut opt_sum = 0;
    for r in 0..ROUNDS {
        for i in 0..ARR_LEN {
            plain_sum += plain_results[r][i];
            opt_sum += opt_results[r][i];
        }
    }

    println!("opt_sum: {:?}", opt_sum);
    println!("plain_sum: {:?}", plain_sum);

}