Re: Population count in SSE2, again

"Maarten Kronenburg" <spamtrap@[EMAIL PROTECTED]
> wrote in message 
news:4805f444$0$717$7ade8c0d@[EMAIL PROTECTED]
> Below is my xmm version, it runs a little under 3 cycles/32-bit.
> It's not as fast as your code (1 cycle/32-bit), but on 32-bit system
there
> are not enough xmm registers to do the CSA trick, so this is how far I 
> get.

> @[EMAIL PROTECTED]
> movdqu xmm1, [esi+4*edi]
> @[EMAIL PROTECTED]
> movdqa xmm2, xmm1
> psrld xmm2, 1
> pand xmm1, xmm4
> pand xmm2, xmm4
> paddd xmm1, xmm2
> movdqa xmm2, xmm1
> psrld xmm2, 2
> pand xmm1, xmm5
> pand xmm2, xmm5
> paddd xmm1, xmm2
> movdqa xmm2, xmm1
> psrld xmm2, 4
> paddd xmm1, xmm2
> pand xmm1, xmm6
> psadbw xmm1, xmm7
> paddd xmm0, xmm1
> sub edi, 4
> jnz short @[EMAIL PROTECTED]
 cycles per 4 bytes is pretty slow.  What kind of processor are you
testing with?  There are some tweaks that can speed up your code.
Firstly, look at how the first stage where 1-bit counters are
combined to form 2-bits counters is performed in the AMD manual.
Notice that they use a subtraction instead of an addition, a
clever optimization that can save you an AND.

You might think that it's a good thing to keep all your constants in
registers, but that is more problematic on Intel processors where
you have only limited ROB read bandwidth.  What that amounts to is
you can only read at most two registers per cycle than aren't "in
flight" or three if the third is used as an index.  See 248966.pdf,
section 3.5.2.1 on ROB read ****t stalls.  Originally my code had all
the constants in registers but I moved some of them to memory with
consequent speed-up.  Also you may consider making edi 4X as big
and addressing as movdqu xmm1, [edi+1*esi] so that your dead
register is the index register.  Thus it won't participate in ROB
read ****t stalls.

Also when you have to perform a movaps to copy a value because of
the 2-register ISA we are laboring under (movaps is one byte shorter
than movdqa which is why it is more freqently seen, even in integer
code) copy a constant rather than the in-flight variable.  This
allows the processor to issue the copy instruction out of order
well in advance of where it's needed so that it can't get in the way
of the critical path instructions.

After you have moved some of the constants from registers to memory
and tweaked your code a little, you may find that as a side effect
of having constants in memory you have now some free registers so
that you may be able to do a little CSA compression after all.

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