Looking for the fastest way of counting bits
dag...@my-deja.com
1, 3 -> 2, 255 -> 8) While using 8bit lookup table is quite fast, I
wonder if there's any even faster way of doing this. My command of
assemly langauge is quite limited with a lot of instructions totally
unbeknownst to me.
Thanks for any tips.
Sent via Deja.com http://www.deja.com/
Before you buy.
Olaf
<dag...@my-deja.com> wrote in message news:384e...@news.iglou.com...
> I want to count the number of 1 bit in a large array of data. (ie. 2 ->
> 1, 3 -> 2, 255 -> 8) While using 8bit lookup table is quite fast, I
> wonder if there's any even faster way of doing this. My command of
> assemly langauge is quite limited with a lot of instructions totally
> unbeknownst to me.
>
> Thanks for any tips.
>
This is dependent on your data. Given even random distribution of byte data,
a lookuptable is the best. If your data deviates from this (very sparsely
populated with 1's or 0's) some tricks may be applied to avoid some of the
LUT lookups......
Regards,
- Olaf
Danjel McGougan
>
> I want to count the number of 1 bit in a large array of data. (ie. 2 ->
> 1, 3 -> 2, 255 -> 8) While using 8bit lookup table is quite fast, I
> wonder if there's any even faster way of doing this. My command of
> assemly langauge is quite limited with a lot of instructions totally
> unbeknownst to me.
>
The "AMD Athlon Processor x86 Code Optimization guide" contains an
interesting implementation concerning bit-counting. On page 91 this code
is given for counting the number of one-bits in a 32-bit register:
input in EAX
MOV EDX,EAX
SHR EAX,1
AND EAX,055555555h
SUB EDX,EAX
MOV EAX,EDX
SHR EDX,2
AND EAX,033333333h
AND EDX,033333333h
ADD EAX,EDX
MOV EDX,EAX
SHR EAX,4
ADD EAX,EDX
AND EAX,00F0F0F0Fh
IMUL EAX,001010101h
SHR EAX,24
result in EAX
It divides the 32-bit value into sections and counts the number of bits
in each section summing them up and forming larger sections.
Danjel McGougan
NowhereMan
> I want to count the number of 1 bit in a large array of data. (ie. 2 ->
> 1, 3 -> 2, 255 -> 8) While using 8bit lookup table is quite fast, I
> wonder if there's any even faster way of doing this. My command of
> assemly langauge is quite limited with a lot of instructions totally
> unbeknownst to me.
This has been discussed in detail here a few weeks (months?) ago... try
searching with your question in www.deja.com or something.
TK
Daniel M. Pfeffer
The method that is (probably) fastest is to completely unroll the binary
search tree. This gives you the number of bits in a 32-bit integer in 5
comparisons, but the ASM code would take up most of the L1 cache :-)
Daniel Pfeffer
<dag...@my-deja.com> wrote in message news:384e...@news.iglou.com...
> I want to count the number of 1 bit in a large array of data. (ie. 2 ->
> 1, 3 -> 2, 255 -> 8) While using 8bit lookup table is quite fast, I
> wonder if there's any even faster way of doing this. My command of
> assemly langauge is quite limited with a lot of instructions totally
> unbeknownst to me.
>
Terje Mathisen
>
> There was a similar discussion in comp.lang.c.moderated a few months ago.
> The method that is (probably) fastest is to completely unroll the binary
> search tree. This gives you the number of bits in a 32-bit integer in 5
> comparisons, but the ASM code would take up most of the L1 cache :-)
Ouch!!!
Please don't do this!
This code would be guaranteed to miss the branch predictors about 5
times each time you call it, resulting in something like 50-100 cycles
just for the branch misses.
I've just posted in reply to the same query over in
comp.arch.arithmetic, there's no need to repeat all of it here.
Terje
--
- <Terje.M...@hda.hydro.com>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
Terje Mathisen
James Van Buskirk
dag...@my-deja.com wrote in message <384e...@news.iglou.com>...
>I want to count the number of 1 bit in a large array of data. (ie. 2 ->
>1, 3 -> 2, 255 -> 8) While using 8bit lookup table is quite fast, I
>wonder if there's any even faster way of doing this. My command of
>assemly langauge is quite limited with a lot of instructions totally
>unbeknownst to me.
I was just about to cut and paste my population count subroutine from
my sieve of Erastosthenes program, which is likely the fastest way to
do it on a processor that has no population count instruction (does
SSE or 3DNow! include such an instruction?) but noticed that it was
243 lines of uncommented Fortran, so I decided not to. Instead I
will give some highlights and explain what I am doing (I think
someone may have already coded this method in MMX.
I'm gonna use four 64-bit (e.g. MMX) registers as 64 4-bit counters
so I zero them out at the start of the algorithm. With only 8 64-bit
registers one may have to curtail one's ambitions and use only 3-bit
counters.
s0 = 0
s1 = 0
s2 = 0
s3 = 0
!Now we have a loop which gobbles up 16 quadwords (maybe 8 if you use
!3-bit counters) per trip and converts them into a single quadword
!each bit of which represents 16 bits of the original input array.
do i = 1, blocksize-15, 16
! t0 is the next quadword of data
t0 = block(i)
! Now we add the bit of data to the low bit of the counters.
! t1 will be the carry and s0 will be the resulting low bit.
t1 = iand(t0, s0)
s0 = ieor(t0, s0)
! Fetch the next quadword of data
t0 = block(i+1)
! We add the bit of data to the low bit of the counters.
! carry will be the carry and s0 will be the resulting low bit.
carry = iand(t0, s0)
s0 = ieor(t0, s0)
! If you think about it, no bit can be set simultaneously in
! both t1 and carry at this point, so when t1 and carry are
! added there will be no carry.
t1 = ior(t1,carry)
! Now there is no special relationship between t1 and s0
! any more, so we have to add t1 to the counters in the
! twos' (=2**1) place. t2 will be the resulting carry to the
! fours' (=2**2) place and s1 will be the result of the addition
! in the twos' place.
t2 = iand(t1, s1)
s1 = ieor(t1, s1)
! Fetch the next quadword of data
t0 = block(i+2)
Hopefully you can see where this is going now. Just keep going
until you run out of 64-bit registers. At this point you need
an algorithm to add up the overflow from the above counters.
One way to do this is:
function count8(r)
use stuff ! Defines ik8 as the kind of a 64-bit integer
implicit none
integer(ik8) count8
integer(ik8), intent(in) :: r
integer(ik8) m1, m2, m4, mbyte
data m1, m2, m4, mbyte / Z'5555555555555555', Z'3333333333333333',
&
Z'0f0f0f0f0f0f0f0f', Z'00000000000000ff' /
count8 = iand(r, m1)+ishft(iand(r, not(m1)), -1)
count8 = iand(count8, m2)+ishft(iand(count8, not(m2)), -2)
count8 = iand(count8, m4)+ishft(iand(count8, not(m4)), -4)
count8 = count8+ishft(count8, -8)
count8 = count8+ishft(count8, -16)
count8 = count8+ishft(count8, -32)
count8 = iand(count8, mbyte)
end function count8
Hope this helps and that someone can show how to do this in MMX.
The above method can count the bits at about 900 MB/sec in cache
on my 21164, probably slower due to register shortages on MMX,
but still it could be pretty fast I believe.
James Van Buskirk
Terje Mathisen wrote in message <3850...@news.iglou.com>...
>I've just posted in reply to the same query over in
>comp.arch.arithmetic, there's no need to repeat all of it here.
But I couldn't figure out how you got your operation counts.
Not knowing much MMX, it seems like it would take
7*(2**2-n) MMX instructions to compress 2**n-1 qwords into
n qwords by the build up from empty counter and count up
the results method, while it takes 7*(2**n-1) instructions
to compress 2**n qwords into 1 qword by the extract overflow
from running counter method. What is the smallest n for which
you have code that does significantly better than this and
could you post the code or tell me what I'm missing?
Terje Mathisen
The number of operations are for a genereic 3-operand machine, so MMX
needs come copy operations as well.
If counting bits is the only thing you do, then a 256-entry lookup table
is actually very hard to beat, and a 2K table, which still fits in L1
cache, _can_ be even better.
The bitslice version is definitely a win on a machine with more
registers, it is very hard (but not impossible, only non-optimal) to
make it work for more than 7-wide blocks on x86 cpus.
The normal shift & mask counting code will also have scaling benefits,
as you note the later stages can be combined.
Jon Kirwan
On 10 Dec 1999 16:36:01 -0500, "James Van Buskirk"
<tor...@ix.netcom.com> wrote:
>
>Terje Mathisen wrote in message <3850...@news.iglou.com>...
>
>>I've just posted in reply to the same query over in
>>comp.arch.arithmetic, there's no need to repeat all of it here.
>
>
>But I couldn't figure out how you got your operation counts.
>Not knowing much MMX, it seems like it would take
>7*(2**2-n) MMX instructions to compress 2**n-1 qwords into
>n qwords by the build up from empty counter and count up
>the results method, while it takes 7*(2**n-1) instructions
>to compress 2**n qwords into 1 qword by the extract overflow
>from running counter method. What is the smallest n for which
>you have code that does significantly better than this and
>could you post the code or tell me what I'm missing?
I decided to take a quick shot at what Terje was suggesting, writing
my own test code for it. I did have to make some "interpretations" of
what was said, since I've never attempted this before. But the
description made sense to me and the resulting code works quite well,
so I think I got the idea.
If 2^N (2**N for FORTRAN types) is the number of original words to
process, it requires ([2^N]-1) half-adder operations and ([2^N]-1-N)
full-adder operations to complete a set of (N+1) final words, with bit
values of 1, 2, ..., 2^(N-1) for bits in these final words. So, 8
input words (2^3) would require 7 half-adders and 4 full-adders and
produce 4 output words (the last output word of which we wouldn't
really need unless every bit of some given bit position in all the
words was 1.) 16384 input words (2^14) would require 16383
half-adders and 16369 full-adders.
As the number of input words gets large, it approximates one
half-adder plus one full-adder required per word of input. Since a
half adder takes two logical operations and a full adder takes five
logical operations, this suggests that large sets of numbers will
require a total of seven logical operations per input word. Or just
slightly under. (The final bit count of the few output words is
trivial.)
For example, 16384 input words require 2*16383+5*16369=114611 logical
operations, or an average of 114611/16384=6.9953 logical operations
per word. For small 2^N, such as 8, it's 7*2+4*5=34 logical
operations for 8 input words -- an average of 34/8=4.25 logical
operations.
I'd be interested in the details for a significantly better algorithm,
too.
Jon
Terje Mathisen
Jon Kirwan wrote:
> As the number of input words gets large, it approximates one
> half-adder plus one full-adder required per word of input. Since a
> half adder takes two logical operations and a full adder takes five
> logical operations, this suggests that large sets of numbers will
> require a total of seven logical operations per input word. Or just
> slightly under. (The final bit count of the few output words is
> trivial.)
In real life you would split the input aray into 7-wide or 15-wide
blocks, using only full adders to reduce this to 3 or 4 blocks, before
counting the bits in those blocks and accumulate.
This is to avoid having to make special code for each possible input
length, besides the 15-wide versin is close to theoretically optimal
even for really large arrays, since it never has any problems keeping
all temps in registers.
Jon Kirwan
>
>Jon Kirwan wrote:
>> As the number of input words gets large, it approximates one
>> half-adder plus one full-adder required per word of input. Since a
>> half adder takes two logical operations and a full adder takes five
>> logical operations, this suggests that large sets of numbers will
>> require a total of seven logical operations per input word. Or just
>> slightly under. (The final bit count of the few output words is
>> trivial.)
>
>In real life you would split the input aray into 7-wide or 15-wide
>blocks, using only full adders to reduce this to 3 or 4 blocks, before
>counting the bits in those blocks and accumulate.
Can I assume that the reason for using 7-wide or 15-wide, and not
8-wide or 16-wide, is that it saves the need for an extra output word
(7 to 3, rather than 8 to 4, etc?)
>This is to avoid having to make special code for each possible input
>length, besides the 15-wide versin is close to theoretically optimal
>even for really large arrays, since it never has any problems keeping
>all temps in registers.
Sounds good and makes sense. I'll play with it tonight.
------PS------
In converting 16383 words without the splitting process, you get to
count bits in just 14 words. If that were split into blocks of 15,
that would require counting bits in:
4*INT(16383/15) + (16383-15*INT(16383/15)) words
or 4371 words.
The logical operations for 15 input words amounts to 15 half-adders
and 10 full-adders or 15*2+10*5=80 logical operations. So breaking
this up means:
349440 [4*INT(16383/15)*(15*2+10*5) logical operations]
17475 [4*INT(16383/15)*4+(16383-15*INT(16383/15)) word bit counts]
16383 [word memory reads]
(or more logical operations if you consider using only full-adders as
you suggest) as compared approximately against:
114609 [16382*2+16369*5 logical operations]
14 [word bit counts]
65518 [word memory reads]
49134 [word memory writes]
It trades off register operations for memory access, which makes sense
with the newer x86 chips. Is this about what you figure?
Jon
Terje Mathisen
> It trades off register operations for memory access, which makes sense
> with the newer x86 chips. Is this about what you figure?
Yes, all algorithms are moving in the direction of 'memory is slow,
registers are infinitely faster'.
I.e. after finally getting the data into a registers, you can do almost
anything except writing it back out to a temp variable.
James Van Buskirk
Terje Mathisen wrote in message ...
>James Van Buskirk wrote:
>> But I couldn't figure out how you got your operation counts.
>> Not knowing much MMX, it seems like it would take
>> 7*(2**2-n) MMX instructions to compress 2**n-1 qwords into
>> n qwords by the build up from empty counter and count up
>> the results method,
Whoops. The third line should have read "7*(2**n-n)-6 MMX..."
>The number of operations are for a genereic 3-operand machine, so MMX
>needs come copy operations as well.
Or logical negations. It's unfortunate for this algorithm that
PANDN negates the wrong register. Your counts in c.a.a. still
don't agree with mine for Alpha.
>If counting bits is the only thing you do, then a 256-entry lookup table
>is actually very hard to beat, and a 2K table, which still fits in L1
>cache, _can_ be even better.
Counting 11 bits at a time, for 6 lookups per qword? Shift & mask
would be faster on Alpha than even a 65536 byte LUT, even neglecting
the fact that cache couldn't hold it and anything else at the same
time (see appended code).
>The bitslice version is definitely a win on a machine with more
>registers, it is very hard (but not impossible, only non-optimal) to
>make it work for more than 7-wide blocks on x86 cpus.
The discussion later in the thread about 2**n-1 wide blocks doesn't
seem as sensible as 2**n wide blocks. Even though they achieve the
same amount of compression per (work per input register) the two
approches differ in code bloat by quite a bit, the 2**n wide version
being much smaller.
>The normal shift & mask counting code will also have scaling benefits,
>as you note the later stages can be combined.
Yes, I just implemented a little code that does this. It's compressed
enough that the moderator may pass it because it seems to me to shed
some light on the thread even though it isn't in assembler. Further
on in the thread Jon keeps referring to 7 logical operations per
input register to do the compression work, but as you say it only
takes 5 logical operations as can be seen in the code. (Perhaps he
means MMX operations?) This code implements compression by 16 which
should lead to only one spill in MMX (I think.) The F77 version
is > 6X as fast for bit counting; the compiler doesn't seem to inline
the entire recursion tree as we would in this forum, but it's much
longer and harder to read than this F95 code. I was a little confused
by the post I am responding to but just recoding the algorithm in this
style helped clarify many of your statements. The function counts an
array (block) with n 64-bit elements. Hopefully those following this
discussion will find the code clear enough.
function FastCount(block, n)
implicit none
integer, parameter :: ik8 = selected_int_kind(18)
integer(ik8) FastCount
integer, intent(in) :: n
integer(ik8), intent(in) :: block(n)
integer i, j
integer(ik8) subtotal
integer(ik8) counter(4)
integer(ik8) mask0, mask1, mask2, mask3, mask5
data mask0, mask1, mask2, mask3, mask5 / Z'5555555555555555', &
Z'3333333333333333',Z'f0f0f0f0f0f0f0f',Z'ff00ff00ff00ff',Z'ffff'/
FastCount = 0
counter = 0
do i = 1, n, 31*16
subtotal = 0
do j = 1, min(31*16, n-i-14), 16
subtotal = subtotal+count8(combine(i+j-1, 4))
end do
subtotal = iand(subtotal, mask3)+ishft(iand(subtotal, not(mask3)), -8)
subtotal = subtotal+ishft(subtotal, -16)
FastCount = FastCount+iand(subtotal+ishft(subtotal, -32), mask5)
end do
subtotal = dot_product((/1,2,4,8/)+0_ik8, count8(counter))+ &
sum(count8(block(i-31*16+j-1:n)))
subtotal = iand(subtotal, mask3)+ishft(iand(subtotal, not(mask3)), -8)
subtotal = subtotal+ishft(subtotal, -16)
FastCount = 16*FastCount+iand(subtotal+ishft(subtotal, -32), mask5)
contains
recursive function combine(i, n) result(retval)
integer(ik8) retval
integer, intent(in) :: i, n
integer(ik8) a(2)
if(n == 1) then
a = block(i:i+1)
else
a = (/combine(i, n-1),combine(i+2**(n-1), n-1)/)
end if
retval = iand(counter(n), a(1))
counter(n) = ieor(counter(n), a(1))
a(1) = iand(counter(n), a(2))
counter(n) = ieor(counter(n), a(2))
retval = ior(retval, a(1))
end function combine
elemental function count8(x)
integer(ik8) count8
integer(ik8), intent(in) :: x
count8 = x-ishft(iand(x, not(mask0)), -1)
count8 = iand(count8, mask1)+ishft(iand(count8, not(mask1)), -2)
count8 = iand(count8+ishft(count8, -4), mask2)
end function count8
end function FastCount