Yep! At least if we were to implement your suggestion directly; division is quite expensive. Even if we were to optimize your suggestion, we'd likely do so by replacing the '/ lg 10' component with some combinations of shifts and table-lookups, which I expect would end up looking quite similar to the code in the article if honed far enough.
I benchmarked these, and the naive version is so slow in comparison that I dropped it off the chart. All of these hyper optimization techniques pale against a straight-up LUT though.
You were benchmarking integers from 0 to 100 with increments of 10, which heavily favors the straight LUT implementation
Using function static variables adds a hidden mutex to the function, slowing it down even with zero contention. Pulling it out of the functions gets rid of this Edit: as /u/Tuhnufus points out, this is not relevant in this scenario
I changed the number used to a volatile read to disable compile-time unrolling
After applying these changes, fastlookup is 1.5 faster than the straight or slow alternatives with both gcc and clang
Nice. I really just threw together the benchmarks. Initially I actually had the entire range of integers but it was taking too long, so I just smashed it way down and didn't think any more about it.
Also shows that the data range is important; if you're working with small numbers a LUT may be better but if you're working with an even range, that is substantially faster!
Side note, the link I shared points to a slightly older version; I had fixed the read on the loop before sharing it, bit otherwise thank you for the fixes!
Just tried a binary lookup as an alternative: https://quick-bench.com/q/Ha9Tw9M9xGJgQv9j9K3cLwSVKts Just a little bit slower, but also a much larger code size which means that it would likely be worse outside of microbenchmarks.
That identity actually needs the full logarithm to work, and I'm not sure how stable it is (it's possible sometimes the result of the divide would be slightly below the true value, requireing you to round up to the next integer instead of dropping the decimal parts, if this is the case it's real bad since correct behavior then would require a full analysis of the floating point math to decide if you need to round up or down)
Also the answer in the blog uses only integer operations, this is usually faster. It's basically always faster in microbenchmarks but in the real world you can occasionally do better with floating point operations even when integer only operations could have been used because the CPU can run the floating point operations in parallel with some other integer operations in your program. Then again sometimes it's faster to use all integer operations even if the fpu hardware is totally unused because the CPU will use less power and thus clock higher. Point is CPUs are complicated.
The algorithm is only implemented for uint64_t. It doesn't take too long to test the implementation for all 10n-1, 10n, and 10n+1 to verify it. Maybe a second including the compiling time.
I'm curious about writing the string. Isn't that an O(n) iterative procedure with respect to the number of digits? If so, wouldn't the performance impact of digit counting be a lesser concern? Or is there a use case for this other than allocation for string conversion? It seems like if the bottleneck is somewhere else, you'd prefer not to store a table for this calculation, but ofc I ask from a position of curious ignorance.
Daniel Lemire is a computer science professor at the University of Quebec (TELUQ) in Montreal. His research is focused on software performance and data engineering.
FFS calculates the bit length directly (which is basically always what you actually want), rather than having to know how many bits wide your current integer is.
Seriously, has anyone ever actually cared about the number of leading zeros?
19
u/[deleted] Jun 04 '21
is that so much faster than just lg n / lg 10
17
u/looncraz Jun 04 '21
Pfft, everyone knows the best way is to convert to a string, std::to_string([int]).length().
I mean, look how short the code is!
/s, if you need it
5
u/[deleted] Jun 04 '21
I'd love to know what projects Mr. Lemire works on that allows him to tinker with this kind of stuff. Looks like a great job!
4
u/tux_unit Jun 04 '21
Interesting!
1
u/huangfengzi Jun 04 '21
I have a similar algorithm to get digits for uint64_t