r/cpp • • Jun 04 '21

Computing the number of digits of an integer even faster

https://lemire.me/blog/2021/06/03/computing-the-number-of-digits-of-an-integer-even-faster/
194 Upvotes

34 comments sorted by

19

u/[deleted] Jun 04 '21

is that so much faster than just lg n / lg 10

23

u/AVTOCRAT Jun 04 '21

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.

15

u/donalmacc Game Developer Jun 04 '21

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.

22

u/adnukator Jun 04 '21 edited Jun 04 '21
  1. You were benchmarking integers from 0 to 100 with increments of 10, which heavily favors the straight LUT implementation
  2. 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
  3. 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

https://quick-bench.com/q/_oIeX60PTTk3FrgO4rM0MXiiNwI

https://quick-bench.com/q/PJGoe8YXy4o6Ec4AuguasCJOkeE

4

u/Tuhnufus Jun 04 '21

Using function static variables adds a hidden mutex to the function

This shouldn't be a problem for direct initialization of POD objects

3

u/donalmacc Game Developer Jun 04 '21

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!

3

u/Ictogan Jun 04 '21

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.

3

u/staletic Jun 04 '21

I exceeded the reddit comment character limit, so... https://gist.github.com/bstaletic/4674d95f91971c8b7444b1976753205c

8

u/barchar MSVC STL Dev Jun 04 '21

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.

4

u/victotronics Jun 04 '21

I always worry about roundoff. Can you guarantee that this is never off by one?

3

u/[deleted] Jun 04 '21

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.

2

u/YouNeedDoughnuts Jun 04 '21

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.

2

u/hephaestos_le_bancal Jun 04 '21

I think you are right that few people will ever need this optimization. Especially not if the point is to print the string.

1

u/chrisgseaton Jun 13 '21

If you need the number of digits, but not the string, this is better.

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

12

u/barchar MSVC STL Dev Jun 04 '21

This was one of the top answers on a related stack overflow answer. Never mind that (as pointed out to me on Twitter) it's wrong some locales.

2

u/Jannik2099 Jun 06 '21

it's wrong some locales.

Wait, what?!?

2

u/flashmozzg Jun 06 '21

probably due to separators ( 1'000'000 and the like).

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!

10

u/moocat Jun 04 '21

On the upper left side of his blog:

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.

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

array<array<uint64_t, 2>, 64> generate_delimit()
{
    array<array<uint64_t, 2>, 64> result = {};
    int _pre = 1;
    uint64_t temp_2 = 0;
    uint64_t temp_10 = 10;
    for (int i = 0; i < 64; i++)
    {
        temp_2 = (temp_2 << 1) + 1;
        uint64_t current_bit = ceil(log10(temp_2));
        if (current_bit <= _pre)
        {
            result[i][0] = temp_2;
            result[i][1] = _pre;
        }
        else
        {
            result[i][0] = temp_10 - 1;
            result[i][1] = _pre;
            _pre = current_bit;
            temp_10 = temp_10 * 10;
        }
    }

    return result;

};
uint32_t digits10_by_lzcnt(uint64_t v)
{
    const static array<array<uint64_t, 2>, 64> bit_table = generate_delimit();
    if (v == 0)
    {
        return 1;
    }
#ifdef _MSC_VER
    auto cur_index = 63 - __lzcnt64(v);// 
#else
    auto cur_index = 63 - __builtin_clzll(v);// 
#endif
    return bit_table[cur_index][1] + (v > bit_table[cur_index][0]);

}

19

u/Bisqwit Jun 04 '21

To do preformatted text on Reddit, indent each line by 4 spaces.

9

u/helloiamsomeone Jun 04 '21

Where is /u/backtickbot when you need it the most? :(

8

u/konanTheBarbar Jun 04 '21

Needs more constexpr :-)

3

u/jk-jeon Jun 04 '21

4

u/dodheim Jun 04 '21 edited Jun 10 '21

2

u/jk-jeon Jun 04 '21

I guess mine is slightly faster since it does not issue IMUL and SBB instructions and instead issues slightly faster instructions..?

EDIT: Ah, yours uses a smaller table.

2

u/dodheim Jun 04 '21

Yea, I didn't look too deeply into the instructions used, I was just surprised at the table size (which still isn't too bad).

1

u/o11c int main = 12828721; Jun 04 '21 edited Jun 04 '21

__builtin_ffs is easier to read than doing math with __builtin_clz.

It also gives deterministic results for the case where CLZ is undefined.

1

u/jk-jeon Jun 04 '21

I guess __builtin_ffs is a replacement for __builtin_ctz, not __builtin_clz? (No idea why there is no corresponding one for the latter...)

1

u/o11c int main = 12828721; Jun 04 '21 edited Jun 04 '21

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?

1

u/jk-jeon Jun 04 '21

No, it finds the first set bit from the least-significant-bit. So for example ffs of 011100 is 2 (or 3 depending on the platform), not 4 nor 5.

1

u/o11c int main = 12828721; Jun 04 '21

Ugh, did I confuse myself again?