Java 的速度几乎是 Rust 的两倍？!？我错过了什么？

Question

这个问题在这里已经有了答案:





Why is my Rust program slower than the equivalent Java program?

(1 个回答)


1年前关闭。




我移植了一个 Java 类，该类循环遍历从 n 个选项中选择 k 个元素到 Rust 的所有可能的无序组合，期望 Rust 能帮助我加快计算速度。但是当两者并驾齐驱时，Java 的速度几乎快了两倍!
因为这对我来说根本不合适，而且我刚刚开始使用 Rust，我一定做错了什么，并且想知道是否有更多 Rust 经验的人会帮助我弄清楚为什么我的 Rust 代码要慢得多。
这是我的通用接口(interface)、实现和测试代码的 Java 代码:

public interface Choice<Type> {

    /**
     * Returns the number of possible options that this choice provides.
     * 
     * @return the number of choices
     */
    public long getChoices();
    
    /**
     * Returns the choice with the given index.
     *
     * @param index - the index of the choice to return
     * @return the choice of the given index
     */ 
    public Type getChoice(long index);
}

public class NChooseK implements Choice<int[]> {
    
    private final int n;
    private final int k;
    
    private final long count;
    
    public NChooseK(int n, int k) {
        if ((n<=0) || (k<0) || (k>n)) throw new IllegalArgumentException();
        this.n     = n;
        this.k     = k;
        this.count = choose(n, k);
    }

    @Override
    public long getChoices() {
        return count;
    }

    @Override
    public int[] getChoice(long m) {
        if (k==0) return new int[0];
        
        long  count = this.count;
        int[] result = new int[this.k];
        int   n = this.n;
        int   k = this.k;
        long  x = (count-1) - m;
        
        while (true) {
            if (n == k) {
                while (true) {
                    result[this.k - k] = this.n - k;
                    if (k==1) return result;
                    k--;
                }
            }
            
            count = count * (n-k) / n;
            if (x >= count) {
                result[this.k - k] = this.n - n;
                if (k==1) return result;
                
                x -= count;
                count = count * k / (n-k);

                k--;
            }
            n--;
        }
    }

    private long choose(int n, int k) {
        if (n<k) return 0;
        if (k>n-k) k=n-k;
        
        long b=1;
        for (int i=1, m=n; i<=k; i++, m--)
            b = b*m/i;
        return b;
    }
}

public class Test {
    public static void main(String[] args) {

        NChooseK nck = new NChooseK(26, 13);
        long choices = nck.getChoices();
        System.out.println("Running ("+choices+" choices)...");
        long start = System.currentTimeMillis();
        for (long index = 0; index<choices; index++) {
            int[] choice = nck.getChoice(index);
            //System.out.println(ArrayTools.toString(choice));
        }
        long end = System.currentTimeMillis();
        System.out.println("Done ("+((end - start)/1000.0)+"s)!");
    }
}

这是我认为最接近 Rust 的翻译:

pub trait Choice<Type> {
    
    /// Returns the number of possibilities for this choice.
    fn get_choices(&self) -> u32;
    
    /// Returns the posibility of the given index.
    fn get_choice(&self, index: u32) -> Type;
}

use super::choice::Choice;

pub struct NChooseK {
    n: u32,
    k: u32,
    count: u32,
}

impl NChooseK {
    pub fn new(n: u32, k: u32) -> Result<NChooseK, &'static str> {
        if k > n {
            Err("invalid parameters: k cannot be larger than n")
        } else {
            Ok(NChooseK {
                n: n,
                k: k,
                count: choose(n, k).unwrap() as u32,
            })
        }
    }
}

impl<'a> Choice<Vec<u32>> for NChooseK {
        
    fn get_choices(&self) -> u32 {
        self.count
    }
    
    fn get_choice(&self, m: u32) -> Vec<u32> {
        
        if self.k == 0 {
            return vec![];
        }
        
        let mut count = self.count;
        let mut result:Vec<u32> = Vec::with_capacity(self.k as usize);
        let mut n = self.n;
        let mut k = self.k;
        let mut x = (count-1) - m;
        
        loop {
            if n == k {
                loop {
                    result.push(self.n - k);
                    if k == 1 {
                        return result;
                    }
                    
                    k -= 1;
                }
            }

            count = count * (n - k) / n;
            if x >= count {
                result.push(self.n - n);
                if k == 1 {
                    return result;
                }
                
                x -= count;
                count = count * k / (n - k);

                k -= 1;
            }

            n -= 1;
        }
    }
}


fn choose(n: u32, mut k: u32) -> Option<u64> {
    
    if k > n-k {
        k = n-k;    
    }
    
    let mut b : u64 = 1;
    let mut m = n;
    for i in 1..=k {
        if b > 0xFFFFFFFFFFFFFFFF / (m as u64) {
            return None;
        }
        b  = b * (m as u64) / (i as u64);
        m -= 1;
    }
        
    Some(b)
}

fn main() {
    let nck = NChooseK::new(26, 13).unwrap();
    let choices = nck.get_choices();
    println!("Running ({} choices)...", choices);
    let start = time::precise_time_s();
    for index in 0..choices {
        let choice = nck.get_choice(index);
        //println!("{:?}", choice);
    }
    let end = time::precise_time_s();
    println!("Done ({}s)!", end - start);
}

Rust 代码需要大约 12 到 12.5 秒来运行约 1000 万次 get_choice 调用，而 Java 代码需要 6.5 到 7 秒! WTF?!?!?
这是在 Windows 7 64 位上使用 rustc v1.45.2 和 OpenJDK v1.8.0_212-3-redhat。
笔记:

我最初让 get_choices 在 Rust 中也返回一个 u64，但将其更改为 u32 以尝试尽可能多地消除类型转换(但实际上并没有什么不同)。

我还尝试用 i32s 替换所有 u32s。也没什么区别。

注释掉 result.push(...)语句将运行时间降低到 9 到 9.5 秒。这是一个很大的区别(比我预期的要大!)，但仍然比 Java 慢!

如果我取消注释内部循环内的打印语句并将参数更改为更合理的参数(例如 NChooseK(7, 3))，两个版本都会产生相同的精确输出值(ArrayTools.toString(...) 只是一个简单的辅助函数，它连接用逗号将 int 数组的组件转换为字符串；决定将其省略，因为这里已经有很多代码)

Answer 1

始终使用 cargo build --release或 cargo run --release拥有rustc/llvm当您尝试压缩性能时优化您的代码:

$ cargo build 2>/dev/null && time cargo -q run 2>/dev/null

Running (10400600 choices)...
Done (9.487796306610107s)!

real    0m9,512s
user    0m9,500s
sys     0m0,000s

$ cargo build --release 2>/dev/null && time cargo -q run --release 2>/dev/null
    
Running (10400600 choices)...
Done (3.2046568393707275s)!

real    0m3,229s
user    0m3,222s
sys     0m0,008s