优化64位取模运算，以适应经常使用的运行时模数。

Question

优化64位取模运算，以适应经常使用的运行时模数。

coptimizationrustmodulo

6

我有数十亿个无符号64位数字（x），需要找到x％m。 m对于所有数字都相同，但不是编译时常量。 m大于1。

无论是x还是m，都可能持有任何64位值。

（如果m是编译时常量，我可以相信编译器尽其所能。）

由于m对于所有这些操作都是相同的，并且我有可用的存储空间，是否有一种优化方法可以让我计算x％m的所有结果比m为每个x不同的情况下更快？

（我受到了除以常数优化的启发，它将除法转换为乘法、移位和加法。C、Rust或伪代码中的示例代码将非常棒。）

我已经查看了文档，但他们对于计算模数而不计算商的优化只适用于2^n +/- 1的除数。

- fadedbee

1

“m” 可以是任何 64 位数字吗？ - Alberto Sinigaglia

1

你是否测量了取模运算是（疑似）性能问题的原因？目前需要多长时间？ - Bodo

1

m的分布未被指定。实际上，整体上下文也没有被指定。提供更大的背景可能有助于改善性能，而不仅仅是这种狭隘的方法。祝好运。 - chux - Reinstate Monica

1

实际上，对于任何 m，您可以执行很多操作，类似于编译时发生的情况，但是您会在运行时执行它。顺便问一下，你会如何使用它？或者你只是“普遍地”感兴趣？有各种特殊解决方案的情况，例如使用蒙哥马利模乘法（如果适用）或使用模乘逆元素进行乘法来检查可除性。 - harold

1

libdivide 是专门为此目的而用 C 和 C++ 编写的。 - phuclv

显示剩余10条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fadedbee · Accepted Answer

以下是我将要测试的一种方法，因为问题的评论已经明确了x和m的分布很重要。

我没有意识到的是，m > x的概率是50%。

未经测试的伪代码：

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);

}