7
\$\begingroup\$

I saw a simple method to calculate Log2(N), where N is the power of 2:

unsigned int Log2(unsigned int N)
{
    unsigned int n = 0;
    while (N >>= 1)
    {
        ++n;
    }
    return n;
}

It would be not likely very necessary, but I try to improve it in a simple way, the idea comes from binary search.

unsigned int Log2New(unsigned int N)
{
    unsigned int bits = sizeof(N) * 4;
    unsigned int n = 0;
    while (N > 1)
    {
        if (N >> bits)
        {
            N >>= bits;
            n += bits;
        }
        bits >>= 1;
    }
    return n;
}

I run the test in Visual Studio 2013, 32 bits release build and fully optimized. When I look into generated disassembly, both methods are inlined, and there are nothing special in both function. There is only one shr command as expected in

if (N >> bits) { N >>= bits; ... }

I test both of the method by sending 1 << n, n from 0 to 31 to them, and repeat for 1000000 times, and count the time separately.

The new method is about 1.66 times faster than the old one,

Then I make a further change, expand the while loop in the new method. (There was a word for this 'expand', but I don't remember it exactly 8-| )
To make it clear, I make a new define, and the method become:

#define CountShift(bits)  if ((N)>>(bits)) { (N)>>=(bits); (n) += (bits); }
unsigned int Log2NewExpand(unsigned int N)
{
    unsigned int n = 0;    
    CountShift(16);
    CountShift(8);
    CountShift(4);
    CountShift(2);
    CountShift(1);

    return n;
}

Looking into the disassembly again, as expected, it's fully serialized, only 5 test, je shr and add commands.

Timing again, the expanded method is again about 1.66 times faster then the new one, and about 2.8 times faster than the original method.

I think there must be some more space for improvement. Any suggestion are welcome.

\$\endgroup\$
  • 3
    \$\begingroup\$ You will probably interested in this: stackoverflow.com/q/11376288/667648 \$\endgroup\$ – Dair Dec 31 '16 at 5:08
  • 1
    \$\begingroup\$ I believe the word you're trying to think of is unroll. \$\endgroup\$ – Cody Gray Dec 31 '16 at 8:07
  • \$\begingroup\$ That is great. I will try it when I have time, maybe next year :-; \$\endgroup\$ – Tiger Hwang Dec 31 '16 at 8:38
6
\$\begingroup\$

I was initially skeptical of your benchmarking results because of your testing methodology:

I test both of the method by sending 1 << n, n from 0 to 31 to them, and repeat for 1000000 times, and count the time separately.

When you're benchmarking code that contains conditional branches, it is generally not a good idea to use a predictable sequence of inputs, since this tends to ensure that branch prediction will be successful, mitigating something that is potentially one of the most significant costs in performance-sensitive code. Unless you're actually going to be using this function in a setting where the inputs (and thus the direction of the branches) are predictable, you run the risk of skewing the benchmark results. And even if the real-world inputs aren't purely random, you're testing here in a tight loop, which improves branch prediction even more.

To verify for myself, I used the outstanding Google Benchmark library. This automates most of the dirty work of creating a good benchmark. In my test harness, I just defined the necessary functions and prepared some arrays of randomly-generated numbers. The random number generation is done "off the clock" so it won't affect the measurement. Despite my earlier admonitions, though, it appears that your findings were valid; here are the results from my machine, using inputs randomly selected from a large array of randomly-generated values:

Benchmark                     Time           CPU Iterations
-----------------------------------------------------------
Log2                         21 ns         21 ns   29866667
Log2New                      10 ns         10 ns   74666667
Log2NewUnrolled               6 ns          6 ns  112000000

(As you can see from my function names, the word you were trying to think of when composing the question is "unroll". You've unrolled (or unwound) the while loop, which attempts to gain execution speed in exchange for code size, primarily by reducing the overhead of the loop itself. In this case, you've completely unwound the loop, allowing it to be eliminated entirely. This is a very common low-level optimization, although the customary caveat is that it significantly bloats the size of the code. That is true here as well, so it rarely makes sense to go to this extreme when optimizing unless the code is going to be called in a tight loop.)

I see essentially the same thing when compiling for 64-bit. Each improvement roughly corresponds to a doubling in overall performance, which is actually pretty impressive. Although it is almost certainly possible to squeeze more speed out of your code by iterative improvements, it will become increasingly difficult to do so. The magnitude of improvement will become a lot less significant, and you'll very quickly hit up against the limitations of writing code in a compiled language, where you can't manually tweak the generated assembly.

I would also advise you to consider whether it is really necessary. The benchmarks above suggest that on a mobile Haswell processor, you can compute the base-2 logarithm of in ~6 nanoseconds. Do you really need an implementation that is faster than that? Is it really worth the time it takes to develop one, test it, and maintain it?


Well, let's suppose either that you do need something faster, or perhaps that it's worth the time simply because it's fun. One possible tack is to seek out a way to completely eliminate branches. Rather than doing the shift-and-test-and-maybe-add dance each time, we'll simply do all of the shifts and bitwise-OR the results together. Then, the final answer is obtained by doing a population count (i.e., computing the Hamming weight). The code looks like this:

unsigned int Log2Fast(unsigned int N)
{
   N |= (N >> 1);
   N |= (N >> 2);
   N |= (N >> 4);
   N |= (N >> 8);
   N |= (N >> 16);
   return (PopCount(N) - 1);
}

The nice thing about a population count is that there are several highly-efficient ways to do it. The accepted answer to the linked question shows one possibility, a clever bit-twiddling trick that counts in parallel, also shown on Sean Eron Anderson's Bit-Twiddling Hacks page. This is a good general-purpose implementation. If you have a processor that supports it, you can use the POPCNT instruction (available on Intel Nehalem, AMD Barcelona, and later generations). On MSVC, the __popcnt intrinsic allows you to force this instruction to be emitted.

This gets compiled to beautiful, efficient, completely branchless code:

Log2Fast PROC
    mov ecx, DWORD PTR [N]

    mov    eax, ecx       // N |= (N >> 1)
    shr    eax, 1
    or     ecx, eax

    mov    eax, ecx       // N |= (N >> 2)
    shr    eax, 2
    or     ecx, eax

    mov    eax, ecx       // N |= (N >> 4)
    shr    eax, 4
    or     ecx, eax

    mov    eax, ecx       // N |= (N >> 8)
    shr    eax, 8
    or     ecx, eax

    mov    eax, ecx       // N |= (N >> 16)
    shr    eax, 16
    or     eax, ecx

    popcnt eax, eax       // return (PopCount(N) - 1)
    dec    eax
    ret    4
Log2Fast ENDP
Benchmark                            Time           CPU Iterations
------------------------------------------------------------------
Log2                                21 ns         20 ns   34461538
Log2New                             10 ns         10 ns   64000000
Log2NewUnrolled                      6 ns          6 ns  112000000
Log2Fast                             5 ns          5 ns   89600000
Log2Fast_Intrinsic                   4 ns          4 ns  179200000

Notice that the POPCNT instruction (the _Intrinsic variant shown here) is slightly faster than the hand-optimized bit-twiddling code. In fact, this single snapshot of the results is a bit of a lie. Log2Fast takes anywhere from 5–8 ns, varying slightly each time I run the benchmark. The version that uses the POPCNT instruction is consistently fast. If you can't guarantee that your target system supports this instruction, this implementation may not be any better than what you already have. It almost certainly would not be worth it except in a tight loop, when all of the required code is guaranteed to be hot in the cache. The POPCNT version, on the other hand, is actually shorter than your previous implementation, and that, combined with its lack of conditional branches, would make it a better general-case algorithm and possibly faster.


Can we do even better? Maybe. It's extremely hard to tell at this point, because our performance is already so good that the benchmark has virtually reached its limits. The performance differences we'll see will be almost exclusively due to noise. You'd say we need to improve our benchmark, but I'd say that we need to stop optimizing because we're done!

Some people have proposed an approach that uses a look-up table. The look-up table is implemented as an array, filled statically and compiled directly into the executable, with the intention of saving us from having to do expensive computations at runtime, since we can just index into the array and retrieve the precomputed value. The same solution also appears on the previously-linked Bit Twiddling Hacks page. What you'll notice, though, is that the look-up table is only being used to do the population count. Specifically, the look-up table contains a DeBruijn sequence, which is a well-known way to speed up various bit-counting operations, including finding the MSB, finding the LSB, and, of course, finding the total number of set bits.

We cannot reasonably use a look-up table for the shifting operations, because it would be ginormous. And, unfortunately, the population-count code we have is already so fast that it cannot be sped up with a look-up table. This is actually so interesting (and counter-intuitive) that it warrants a bit of further commentary. I tested this extensively a while back when I needed to find the position of the least-significant set bit (as part of an optimized implementation for strlen). I assumed that a look-up table would be the fastest solution, but it wasn't. Even as far back as a Pentium III, it turned out to be faster (or at least equally as fast) to simply compute the value at runtime. Sometimes, modern processors are like this—they are so fast, that it can be faster to recompute something than to store it and/or look it up. It is also a good demonstration of the fact that (micro-)optimization is often counter-intuitive, and can only be done correctly with the aid of a good benchmark test case!


I know I already said that we're pushing the limits of performance and that the code is already fast enough, but maybe there is a way to push it just a little bit faster? Or at least, maybe we can gain some style points for a truly efficient algorithm!

Let's stop and think for a moment about what we're actually trying to do. What is the log base-2 of a number? Well, it is the binary logarithm—the power to which you must raise 2 in order to obtain that number. The lightbulb might have already flashed on here, after seeing that word "binary". Computers work in binary. More specifically, numbers are stored using a binary representation. That's why your bit-shifting algorithm worked. Since binary is fundamentally based on log2, it turns out that the position of the most-significant set bit is the same as the binary logarithm of the represented value. For example, consider the number 21658123. Its binary logarithm is 24, and its binary representation is:

0001 0100 1010 0111 1010 0000 1011
↑  ↑                             ↑
|  └————— bit 24                 |
bit 31                           bit 0

The index of the first set bit, when searching from most-significant bit (MSB) to least-significant bit (LSB), is 24—exactly the same as the binary logarithm. This hints at an exceptionally simple algorithm (at least conceptually): scan through the binary representation of the number looking for the most significant set bit! As luck would have it, there is an instruction on x86 to do precisely what we want to do, and it's been available since the 386 way back in 1986. That is the BSR instruction (Bit Scan Reverse), usable in MSVC via the _BitScanReverse intrinsic and on Gnu compilers (i.e., GCC and Clang) via the __builtin_clz intrinsic (although you'll need to XOR the result with 32). And even if you're not targeting the x86, the intrinsic will likely still work for you, causing the compiler to use an architecture-provided instruction if available, or emit code to generate the equivalent result.

Here's our updated function:

unsigned int Log2_ViaBSR(unsigned int value)
{
    unsigned long result;
    _BitScanReverse(&result, static_cast<unsigned long>(value));
    return result;
}

(Yes, code that should be a single line looks a little bit bloated here because MSVC's _BitScanReverse intrinsic works only with DWORD values, which is a typedef for unsigned long, not unsigned int, so although on Windows they are both 32-bit types, they are nevertheless different types according to the language standard, so you need to declare and use an additional temporary for the output, instead of simply reusing the input parameter. Fortunately, this does not affect the object code generated by the compiler. Note, also, that the intrinsic returns a Boolean value indicating whether it was successful. This allows you to handle the case where the input is 0 and the result is undefined—see "caveats" below.)

And the updated leaderboard:

Benchmark                            Time           CPU Iterations
------------------------------------------------------------------
Log2                                22 ns         21 ns   32000000
Log2New                             10 ns         10 ns   64000000
Log2NewUnrolled                      6 ns          6 ns  112000000
Log2Fast                             7 ns          6 ns   89600000
Log2Fast_Intrinsic                   4 ns          4 ns  186666667
Log2_ViaBSR                          2 ns          2 ns  298666667

Stop and think about this for a second. We went from an O(log n) algorithm to what is effectively an O(1) algorithm, just by thinking about the problem in a different way, and figuring out how we can leverage the computer's internal binary representation to our advantage. It reminds me of a lesson straight out of Michael Abrash's Zen of Assembly Language. We now have the most efficient algorithm and have earned those style points!

Now, there are a couple of caveats. First off, log2(0) is mathematically undefined, so you have to decide how you want to handle that. I've simply ignored it in all of the code I've written, making it undefined there as well. The BSR instruction and its corresponding intrinsics take the same tack, formally defining the result as "undefined" when the input is 0. And although there is actually a lot more that I could say about this (including possible workarounds for "undefined" inputs, inefficient code generation when this intrinsic is used in MSVC, the similar LZCNT instruction introduced on Intel Haswell, etc.), I probably shouldn't make this answer any longer. Instead, I'll refer you to Peter Cordes's recent answer on the subject, and my comments below it.

\$\endgroup\$
  • \$\begingroup\$ @JS1 Thanks, fixed. I always seem to mix up CTZ and CLZ because they're the opposite of the x86 instruction mnemonics. However, __builtin_clz isn't quite right. That gives you the count of leading zeros, whereas we want the index of the first set zero. There's no __builtin_flz intrinsic, but we can simulate it by simply XORing the result of __builtin_clz by 31, and both Clang and GCC are smart enough to transform this into a single BSR instruction. \$\endgroup\$ – Cody Gray Dec 31 '16 at 11:21
  • \$\begingroup\$ @JS1 You would think, wouldn't you? Clang emits the expected code if you do it that way, but GCC doesn't. \$\endgroup\$ – Cody Gray Dec 31 '16 at 11:24
  • \$\begingroup\$ It can't have anything to do with 0. Intel's documentation for BSR says the destination's contents are undefined if the source contains 0. XORing undefined with 31 isn't going to change that. Besides, the intrinsic itself leaves 0 undefined. There is no legitimate reason for it to be emitting this sequence, it's just bad code generation. The hard-coded definition of the intrinsic for x86 (BSR+XOR) is disrupting its ability to analyze the surrounding code. It is not a regression; the bug has been there virtually forever. Someone should probably submit a defect report. \$\endgroup\$ – Cody Gray Dec 31 '16 at 11:33
  • \$\begingroup\$ Thanks for the long post, it take me a while to read it through. First of all I am not doing it for business, it's holiday and I just do it for fun. In the testing part, I think while using same test framework to compare these methods, as far as they get same data set, the result should be reliable. In the very beginning I was wondering since we need only one line to check IsPowerOf2() { return N&(N-1) == 0; }, maybe there is a simpler way to calculate this. Just now I also saw some other sites provide some magic methods, but need time to check them. Happy New Year! \$\endgroup\$ – Tiger Hwang Dec 31 '16 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.