Re: Population count in SSE2, again

"Terence" <spamtrap@[EMAIL PROTECTED]
> wrote in message 
news:25562a29-faf9-4899-9acf-bff6e19075a2@[EMAIL PROTECTED]
> Someone tell me why 21 instructions and a branch, per word, is somehow
> better/faster than

I think you may be referring to Maarten Kronenburg's example, which
has 24 instructions+branch.  The point you are missing is that
these complicated methods are counting several words per loop
trip.  Well, MK's method is a naive version, and is surely slower
than a well-optimized 8-bit LUT would be.  But the point is that
counting 64 bits could be done in just two more operations than
counting 32 bits (actually the same number in a more sophisticated
implementation) whereas the LUT method requires about twice as
many operations to count up twice the bits.  The limitation of
LUTs is that they can only get so big before every access is a
cache miss, so the number of bits that can be handled in
parallel is quite limited.  Parallel methods are limited by
register width which is up to 128 bits in x86 just now.

A good explanation of Maarten Kronenburg's code may be found
in the Wikipedia entry on Hamming weight,

http://en.wikipedia.org/wiki/Hamming_weight

The compression stage is explained in the old thread referenced
in my original post,

http://groups.google.com:80/group/comp.lang.asm.x86/msg/54d29f732e51de93

Not to mention

http://www.icis.ntu.edu.sg/scs-ijit/91/91-1.pdf

Well, there's so much available that if you're really interested
these references should keep you busy for a while.

-- 
write(*,*) transfer((/17.392111325966148d0,6.5794487871554595D-85, &
6.0134700243160014d-154/),(/'x'/)); end