Counting Digits in Rust
The just concluded edition of Advent of Code included a problem that involved the number of digits of an integer. The naive solution many folks reach for is printing the number to a string and checking the length of the string:
But then, while exchanging solutions online, someone1Not sure if they're okay being named, so I'm defaulting to keeping them anonymous. shared their supposedly optimized solution with me:
I was curious if this "hand-rolled" solution was actually faster than either of the other ones, so I put together a quick benchmark, both for inputs of zero and random, non-zero 64-bit integers:
It turns out the match solution is four times slower than the logarithm solution, though the string solution is another six times slower. We can see that both match and logarithm perform much better if the input is zero, the former because it matches early, and the latter because it checks for zero as part of the logarithm. The string solution does not get a similar speedup, because it has to allocate a string either way.
If we look at the assembly for the latter two, we can see that match generates a chain of comparisons for the match arms, as the first matching arm defines the result.2Which is also why the order of arms matters if several arms can match an input. The compiler translates this into the assembly equivalent of a chain of if statements with comparisons. The logarithm solution on the other hand compiles into about 30 instructions that do not make a lot of sense at first glance, mostly bitwise operations but also some additions and multiplications, which apparently add up to a logarithm with base ten.3Further research reveals that the specific logarithm implementation actually varies a lot with the processor targeted. Because checked_ilog10 returns None for zero, there is also the aforementioned check for zero at the very start returning zero and skipping the rest in that case.
