The test results are in:
__builtin_popcount(): 12.677 seconds
fast_bitcount(): 7.218 seconds
kr_bitcount(): 33.172 seconds
naive(): 59.345 seconds

also, the patch you committed says for (bits, n, bits++). Notice the
commas are not semicolons.

On Sat, 2009-11-28 at 10:16 -0800, Corbin Simpson wrote:
> Do your test again. I just pushed a fairly fast variable-length
> bitcount. Sorry for not pushing it earlier.
> 
> Posting from a mobile, pardon my terseness. ~ C.
> 
> > On Nov 28, 2009 10:12 AM, "Joakim Sindholt" <b...@zhasha.com> wrote:
> > 
> > I was perusing the commit log for mesa and stumbled upon the
> > recently
> > added util_bitcount. It uses a rather naïve algorithm and I thought
> > I'd
> > look into it as someone mentioned this problem to me before.
> > This is what I found, should anyone be interested:
> > http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
> > 
> > In any case, I wrote a little profiler that I have attached (bc.c).
> > The
> > interesting bit is what result it throws out.
> > [zha...@ztoshiba ~]$ gcc bc.c -O3 -o bc && ./bc
> > 1 billion of __builtin_popcount(), fast_bitcount(), and naive() (in
> > that
> > order)
> > __builtin_popcount(): 12.541 seconds
> > fast_bitcount(): 7.312 seconds
> > naive(): 58.240 seconds
> > 
> > And this is the real reason I'm putting something this
> > unimportant/trivial on the ML. Should the builtin be removed in
> > favor of
> > this wonder-algorithm? and can I even justify pushing this patch
> > considering the requirement of knowing CHAR_BIT (from limits.h,
> > amount
> > of bits in a char)?
> > 
> > ------------------------------------------------------------------------------
> > Let Crystal Reports handle the reporting - Free Crystal Reports 2008
> > 30-Day
> > trial. Simplify your report design, integration and deployment - and
> > focus on
> > what you do best, core application coding. Discover what's new with
> > Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> > _______________________________________________
> > Mesa3d-dev mailing list
> > Mesa3d-dev@lists.sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/mesa3d-dev
> > 
> 

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <limits.h>

/* Templated C++ code (works for ints of up to 128bit)
template<typename T>
int fast_bitcount(T v)
{
    v = v - ((v >> 1) & (T)~(T)0/3);
    v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);
    v = (v + (v >> 4)) & (T)~(T)0/255*15;
    return (T)(v * ((T)~(T)0/255)) >> (sizeof(v) - 1) * CHAR_BIT;    
}
*/

inline int fast_bitcount(unsigned v)
{
    v = v - ((v >> 1) & ~0U/3);
    v = (v & ~0U/15*3) + ((v >> 2) & ~0U/15*3);
    v = (v + (v >> 4)) & ~0U/255*15;
    return (v * (~0U/255)) >> (sizeof(v) - 1) * CHAR_BIT;
}

inline int kr_bitcount(unsigned v)
{
    int c;
    for (c = 0; v; ++c) {
        v &= v - 1;
    }
    return c;
}

inline int naive(unsigned v)
{
    int c = 0;
    while (v) {
        c += v & 1;
        v >>= 1;
    }
    return c;
}

#define TEST(func) \
    gettimeofday(&ts, NULL); \
    for (i = 0; i < 1000000000; i++) { \
        c = func(i); \
    } \
    srand(c); \
    gettimeofday(&te, NULL); \
    t = (te.tv_sec - ts.tv_sec) * 1000 + (te.tv_usec - ts.tv_usec) / 1000; \
    printf(#func "(): %u.%u seconds\n", t / 1000, t % 1000)

int main()
{
    unsigned c, i, t;
    struct timeval ts, te;
    
    printf("1 billion of __builtin_popcount(), fast_bitcount(), and naive() (in that order)\n");
    TEST(__builtin_popcount);
    TEST(fast_bitcount);
    TEST(kr_bitcount);
    TEST(naive);
    return 0;
}
------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day 
trial. Simplify your report design, integration and deployment - and focus on 
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
Mesa3d-dev mailing list
Mesa3d-dev@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mesa3d-dev

Reply via email to