Path: utzoo!utgpu!watmath!clyde!att!ulysses!andante!alice!andrew
From: andrew@alice.UUCP (Andrew Hume)
Newsgroups: comp.lang.c
Subject: Re: Bit counting
Summary: tain't necessarily so
Message-ID: <8730@alice.UUCP>
Date: 11 Jan 89 05:42:47 GMT
References: <1208@ncar.ucar.edu>
Organization: AT&T Bell Laboratories, Murray Hill NJ
Lines: 33



i admired the futzy but clever-looking algorithm to do parallel addition
to determine bit counts reported by rich neitzel. i myself had guessed
that table lookup by bytes was an appropriate space/time tradeoff.
i present times for 300K calls on a mips 120-5 below (8 is table lookup
for 8 bit chunks, 4 is for 4bit chunks and s is the parallel aaddition alg).
note that on the mips, the 3x speedup for 's' found on the vax isn't.
tuttle=; timex a.out 8
real        4.01
user        3.98
sys         0.03
tuttle=; timex a.out 4
real       11.61
user       11.59
sys         0.01
tuttle=; timex a.out s
real       11.33
user       11.24
sys         0.03
this was without optimising; -O3 gains a bit more:
tuttle=; timex a.out 8
real        3.64
user        3.62
sys         0.01
tuttle=; timex a.out 4
real       11.13
user       11.05
sys         0.02
tuttle=; timex a.out s
real       10.34
user       10.32
sys         0.02