[LLVMbugs] [Bug 1488] NEW: bithacks: optimize code that counts bits

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.org/bugs/show_bug.cgi?id=1488

           Summary: bithacks: optimize code that counts bits
           Product: libraries
           Version: trunk
          Platform: All
               URL: http://graphics.stanford.edu/~seander/bithacks.html#Coun
                    tBitsSetKernighan
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Scalar Optimizations
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: nicholas at mxc.ca


The common idiom for counting the number of bits set can be optimized.

unsigned countbits_slow(unsigned v)
{
  unsigned c;
  for (c = 0; v; v >>= 1)
  {
    c += v & 1;
  }
  return c;
}

This can be rewritten as such:

unsigned countbits_fast(unsigned v)
{
  unsigned c;
  for (c = 0; v; c++)
  {
    v &= v - 1; // clear the least significant bit set
  }
  return c;
}

There are other ways to rewrite the bit-counting code, but they involve other
tradeoffs such as constant arrays. Also, the naive method may be written such
that it starts with the high bit or low bit for performance, if the programmer
happens to know about the distribution of the bits in advance. countbits_fast
will equal or outperform either implementation.

With stock GCC, countbits_slow has a 63% longer run-time in a tight loop, while
with llvm-gcc, countbits_slow has a 45% longer run-time. (Sadly, llvm-gcc is
slower than GCC at either function on x86 Linux, but that's another bug.)



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.