I have a function named
grid
which is from the dynamic programming problem "grid Traveler". I wrote the same function twice in JavaScript and Rust and benchmarked 10 million calculations whilst memoizing both functions.
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)
Rust:
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());
}
Benchmark results with commands:
node index.js = 9
cargo run --release = 1614
I thought maybe using a hashmap is not such a great idea, so I tried the #[memoize] macro from this crate.
Results were yet disappointing:
node index.js = 9
cargo run --release = 254
Why is this happening and what’s the optimal solution to generally memoize this function in Rust?
Also benchmark results without memoization:
node index.js = 15424
cargo run --release = 2400
(Changes from Chayim Friedman) + (Switching to 100 million calls):
Rust:
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());
}
It is still around four times slower than Node.js.
node index.js = 54
cargo run --release = 236
The problem is solved and details are in comments.
Since you only ever invoke grid() with one key (18, 18), the inline cache optimization kicks in, and V8 transforms the map lookup in memo (which dominates the time) into a field offset access in object, which is basically free, while the Rust code still has to perform full map lookup.
If you use Map in JS instead of an object, the JS code executes in about 20 seconds on my computer, so Rust is a lot faster. Alternatively, use variable m and n, so that the runtime is dominated by the calculation and not by the lookup.