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

Question

我移植了一个 Java 类，该类将所有可能的从 n 个选项中选择 k 个元素的无序组合循环到 Rust，希望 Rust 帮助我加快计算速度。但是当两者并肩运行时，结果发现 Java 快了几乎两倍！

由于这对我来说根本不合适，而且我刚刚开始使用 Rust，我一定是做错了什么，想知道是否有更多 Rust 经验的人能帮助我弄清楚为什么我的 Rust 代码慢得多。

这是我的通用接口、实现和测试代码的 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 秒来运行对 get_choice 的约 1000 万次调用，而 Java 代码需要 6.5 到 7 秒！卧槽？！？！？

这是在 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(...)只是一个简单的辅助函数，它连接了一个整数数组的组件将逗号转换为字符串；决定将其省略，因为这里已经有太多代码了）

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