I am on vacation this week, so I decided to dig out a backtracking Sudoku solver I wrote last summer and see what I could do to improve its performance. A couple of changes to the data structures and the algorithm yieled an important speed-up. Previously, I had used a
BTreeSet to store the list of candidates for a cell; I now use a
u32 to represent a set of 9 elements. I used to compute the list of neighbors of a cell everytime it was needed; I now pre-compute the matrix of neighbors and avoid the unnecessary re-computations. With these changes, solving 1000 normal-difficulty problems went down from 33 seconds to 1.5 second; the time to solve 1000 very hard problems went down from 15 minutes to 40 seconds.
I wondered if there was a way that I could improve the performance of my code further. I looked for places in the code where I could avoid vector indexing—and in doing so, avoid Rust’s bounds checking—but I didn’t really feel like changing the way the whole program worked. Somewhat randomly, I stumbled on a forum thread about the implementation of
count_ones() (popcount), and buried in the detailed answer of sorear is a command-line option to have
rustc select the CPU that LLVM should target. By compiling my solver for my particular CPU platform (Intel Skylake), the time to solve the normal problems went down to 0.8 second and the time to solve the very hard problems went down to 20 seconds. Nearly a 2x speed-up by adding an extra flag, not a bad deal!
You can pass flags to
rustc from Cargo by using the
rustc sub-command and giving your extra arguments after a double-dash.
$ cargo build --release Compiling sudoku v0.1.0 (file:///home/vfoley/prog/rust/sudoku) Finished release [optimized + debuginfo] target(s) in 1.66 secs $ time ./target/release/sudoku <very_hard.txt >/dev/null real 0m36.542s user 0m36.530s sys 0m0.008s $ cargo rustc --release -- -C target-cpu=skylake Compiling sudoku v0.1.0 (file:///home/vfoley/prog/rust/sudoku) Finished release [optimized + debuginfo] target(s) in 1.65 secs $ time ./target/release/sudoku <very_hard.txt >/dev/null real 0m17.473s user 0m17.466s sys 0m0.004s
Update: est31 on Reddit mentions that we can replace
native to let the backend figure out the appropriate value.
Update 2: Manisheart on Reddit notes that it is better to use the
RUSTFLAGS="-C target-cpu=native" environment variable instead of the
rustc subcommand as it will apply the native compilation to all dependencies and not just the top crate.