Seriously though, this commit adds support for doing exhaustive testing using Rust.
By exhaustive testing, I mean that I try all possible starting words and see how many guesses it takes for me to get to each other word.
This is an O(n^2) search by definition, so for 2047 words that is 4.2 million calculations.
Exhaustive testing was always possible in index.test.ts but running it takes easily over an hour even if you manually parallelize it with running multiple Node workers. I ran it once to gather results but didn't ever want to do it again since I basically have to run it overnight, or when I'm not using the computer.
Now, it runs in about 137s, or about 2 minutes. I can leave it running while I go do some chores, and it's done when I get back. It can test 2047 end words starting with a single word, in 60ms.
Details:
Rewriting this in Rust was not nearly enough to make it fast. My first cut took over 3500ms to run a single round (aka, with a single starting word). I had to profile the code with WPA to find that HashMap access was bottlenecking my code. That's why you see that the Rust code uses custom implementation of statically allocated hash maps, so that I don't have memory access problems. I'll probably do a writeup on this at another time, but the code is in src/tables.rs
Seriously though, this commit adds support for doing exhaustive testing using Rust. By exhaustive testing, I mean that I try all possible starting words and see how many guesses it takes for me to get to each other word. This is an O(n^2) search by definition, so for 2047 words that is 4.2 million calculations.
Exhaustive testing was always possible in index.test.ts but running it takes easily over an hour even if you manually parallelize it with running multiple Node workers. I ran it once to gather results but didn't ever want to do it again since I basically have to run it overnight, or when I'm not using the computer.
Now, it runs in about 137s, or about 2 minutes. I can leave it running while I go do some chores, and it's done when I get back. It can test 2047 end words starting with a single word, in 60ms.
Details: Rewriting this in Rust was not nearly enough to make it fast. My first cut took over 3500ms to run a single round (aka, with a single starting word). I had to profile the code with WPA to find that HashMap access was bottlenecking my code. That's why you see that the Rust code uses custom implementation of statically allocated hash maps, so that I don't have memory access problems. I'll probably do a writeup on this at another time, but the code is in src/tables.rs