Node.js 与 Rust，但 Node.js 更快 [已关闭]

Question

我有一个名为

的函数

网格

来自动态规划问题“grid Traveler”。我用 JavaScript 和 Rust 编写了两次相同的函数，并在记住这两个函数的同时对 1000 万次计算进行了基准测试。

JavaScript：

const grid = (m, n, memo) => {
    const key = m + ',' + n;
    if (key in memo) return memo[key]
    const max = Math.max(m, n)
    const min = Math.min(m, n)
    const d = Array.from({ length: max }, () => 1)
    for (let i = 1; i < min; i++) {
        for (let j = i; j < max; j++) {
            const index = j
            if (i === j) {
                d[index] *= 2
            } else {
                d[index] = d[index] + d[index - 1]
            }
        }
    }
    memo[key] = d[max - 1]
    return d[max - 1]
}


let start = new Date().getTime()
const memo = {}
for (let i = 0; i < 10_000_000; i++) {
    // grid(18, 18)
    grid(18, 18, memo)
}
console.log(new Date().getTime() - start)

铁锈：

use std::collections::hash_map::Entry;
use std::collections::HashMap;
use std::time::SystemTime;

fn grid(m: &usize, n: &usize, memo: &mut HashMap<String, u64>) -> u64 {
    let key = m.to_string() + "," + &n.to_string();
    match memo.entry(key) {
        Entry::Occupied(x) => *x.get(),
        Entry::Vacant(v) => {
            let max: &usize;
            let min: &usize;
            if m > n {
                max = &m;
                min = &n;
            } else {
                max = &n;
                min = &m;
            }
            let mut d = Vec::<u64>::with_capacity(*max);
            for _ in 0..*max {
                d.push(1);
            }
            for i in 1..*min {
                for j in i..*max {
                    if i == j {
                        d[j] *= 2;
                    } else {
                        d[j] = d[j] + d[j - 1];
                    }
                }
            }
            v.insert(d[*max - 1]);
            return d[*max - 1];
        }
    }
}

fn main() {
    let start = SystemTime::now();
    let mut memo = HashMap::<String, u64>::new();
    let m = 18;
    let n = 18;
    for _ in 0..10_000_000 {
        grid(&m, &n, &mut memo);
        // grid(&m, &n);
    }

    println!("{}", start.elapsed().unwrap().as_millis());
}

使用命令对结果进行基准测试：

节点索引.js = 9

货物运行--release = 1614

我想也许使用 hashmap 并不是一个好主意，所以我尝试了 this crate 中的 #[memoize] 宏。

结果仍然令人失望：

节点索引.js = 9

货物运行--release = 254

为什么会发生这种情况？在 Rust 中一般记住这个函数的最佳解决方案是什么？

还可以在不记忆的情况下对结果进行基准测试：

节点索引.js = 15424

货物运行--release = 2400

（Chayim Friedman 的更改）+（切换到 1 亿个调用）：

铁锈：

use std::collections::hash_map::Entry;
use std::time::Instant;
use rustc_hash::FxHashMap;

fn grid(m: usize, n: usize, memo: &mut FxHashMap<(usize, usize), u64>) -> u64 {
    let key: (usize, usize) = (m, n);
    match memo.entry(key) {
        Entry::Occupied(x) => *x.get(),
        Entry::Vacant(v) => {
            let max: &usize;
            let min: &usize;
            if m > n {
                max = &m;
                min = &n;
            } else {
                max = &n;
                min = &m;
            }
            let mut d = Vec::<u64>::with_capacity(*max);
            for _ in 0..*max {
                d.push(1);
            }
            for i in 1..*min {
                for j in i..*max {
                    if i == j {
                        d[j] *= 2;
                    } else {
                        d[j] = d[j] + d[j - 1];
                    }
                }
            }
            v.insert(d[*max - 1]);
            return d[*max - 1];
        }
    }
}

fn main() {
    let start = Instant::now();
    let mut memo = FxHashMap::<(usize, usize), u64>::default();
    for _ in 0..100_000_000 {
        grid(18, 18, &mut memo);
    }
    println!("{}", start.elapsed().as_millis());
}

它仍然比 Node.js 慢 四倍。

节点索引.js = 54

货物运行--release = 236

---

问题已解决，详情见评论。

Answer 1

由于您只用一键 (

grid()

) 调用

18, 18

，内联缓存优化就会启动，V8 将

memo

中的映射查找（主导时间）转换为对象中的字段偏移访问，这基本上是免费的，而 Rust 代码仍然需要执行完整的映射查找。

如果在 JS 中使用

Map

而不是对象，JS 代码在我的电脑上执行大约 20 秒，所以 Rust 快很多。或者，使用变量

m

和

n

，以便运行时间由计算主导，而不是由查找主导。