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
