Re: Population count in SSE2, again

"Terje Mathisen" <spamtrap@[EMAIL PROTECTED]
> wrote in message 
news:B5mdncw9LPFJmJ_VnZ2dnUVZ8qLinZ2d@[EMAIL PROTECTED]
> James Van Buskirk wrote:
>> But the big difference lies in implementation of the Carry-Save
>> Adder (CSA) compression scheme.  You will recall that the
>> fundamental sequence of operations, starting with inputs A, B,
>> and C is:

> [snipped bitslice adder logic using negated input bits]

> Nice!!

> OTOH, POPCNT is turning up as a regular x86 opcode these days, and I do 
> assume this will be _very_ hard to beat?

As written, it's getting about 32768/6950 = 4.7 bytes per clock.
In 32-bit mode it may still be above 4 bytes per clock, but you
would have to be able to perform 2 loads per clock (Core 2 Duo only
has one load ****t) and 2 POPCNTs per clock (Phenom only has one
POPCNT-capable ALU) to do better than this.  Also there may simply
be some not-well-do***ented throughput limitation on Core 2 Duo
which impairs performance by 33% (see the thread I started entitled
'Throughput of PXOR'.)  A processor without that limitation might be
50% faster or about 7 bytes per clock.  Also if a processor had
256-bit wide registers available, the speed could double, even
outstripping a POPCNT unit with throughput of 1 per clock cycle in
64-bit mode.  Of course, if a POPCNT instruction were available for
256-bit wide registers, it would be game over.

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