Cutoff Points Matter #
hacking, June 10th 2007
If an operation can be completed using two alternative algorithms, suited to different sizes of input, it can be well worth your time to take a while to tune the cutoff point.
This seems pretty obvious, but it obviously isn't obvious enough for me: I last visited SBCL bignum printing in February 2005, changing the system to use a bisective algrorithm which allowed larger bignums to be printed without running out of stack (courtesy of Harald Hanche-Olsen.) It wasn't until yesterday that I noticed how the algrorithm used to print fixnums was faster for bignums up to 250 bits or so...
The situation is now fixed (and the worst bottleneck of the bisective version has been alleviated by caching), so printing small bignums (upto 87 bits) is now approximately 40% faster. Bignums up to 2048 bits also print significantly faster (~30% improvement), but beyond that the changes are insignificant: the aforementioned cache drops overly large values before each GC — only tight printing loops will see a difference for bignums of over 2048 bits.
Moral of the story: check your cutoff points.