Small Optimizations

A couple of months ago I posted an entry titled Rust Faster Than C? Not So Fast. It was simple analysis of the k-nucleotide benchmark game, my interest piqued by Rust taking the lead over C.

After a brief period of profiling I proposed some very simple changes to the C entrant, or rather to the hash code that it leverages (klib) that would allow C to retake the lead. It was pursued purely in a lighthearted fashion, and certainly wasn’t a dismissal of Rust, but instead was just a curiosity given how simple that particular benchmark was (versus other benchmarks like the regex benchmark where Rust’s excellent regular expression library annihilates the Boost regex implementation, which itself eviscerates the stdlib regex implementation in most environments).

The changes were simple, and I take absolutely no credit for the combined work of others, but given that a number of people have queried why I didn’t publish it in a normal fashion, here it is.

Original Performance
3.9s clock time. 11.0s user time.

[on the same hardware Rust yields 3.6s clock time, 9.8s of user time, taking the lead]

Remove a single-line pre-check that while ostensibly for speed-ups, actually was a significant net negative.

Updated Performance
3.3s clock time. 9.55s user time.

Such a trivial change, removing what was assumed to be a performance improvement, yielded a 15% performance improvement. This particular change has zero positive negative impact so I have submitted a pull request.

Switch the flags from bit-packing into 32-bit integers to fixed-position byte storage

Updated Performance
2.9s clock time. 7.4s user time.

As mentioned in the prior post, the implementation used a significant amount of bit packing, necessitating significant bitshifting. By moving to a byte storage it remains incredibly efficient for a hash table, but significantly reduces high-usage overhead.

If the first pull request is accepted, C will take the lead again. Does it matter? Not at all. But it’s the fun of the spirit of the game.

Regardless, as I finally start contributing to public projects it was an opportunity to share the notion of profiling and the high impact of incredibly simple changes.