Just out of curiosity I had a look at an asm version of the 'while' method. To cut a long story short, it was not worthwhile. For small bit counts it was the fastest method, but suffered as the bit count increased. Being Ulong based using 32-bit registers it, clearly, was not as versatile as the other methods above.
I checked dodicat's code and found an issue.
With p=popcnt(i) and __popcount(i) 'i' is determined from '#define i int(rnd*20000000)'. We have then a calculation inside the Timer calculation. Goodness knows what effect this will have on the timing, even though 'Randomize 1' is used to use the same random number sequence.
I rewrote the timing code to consider bit counts 1,2,4,8,16,and 32 with three tests each rather than five.
With the same value being calculated within a loop an optimized gcc will, but not always, rip the loop out, so I inserted 'Asm nop' to stop that. That does not always work. gcc have a pragma to stop selected sections being optimized, but fbc isn't using it. IT SHOULD !
So, what do we have now?
The 'while' method gets faster as the bit count reduces. dodicat's methd is not sensitive to the bit count.
dodicat's method is the faster, and noticeably so as the bit count increases.
Don't forget that we are using 'Var lim=10000000'. At a bit count of 32 dodicat's method is 10 times faster than the 'while' method. With a lim of 100 10 times faster is 10 times faster than virtually nothing which is – well – virtually nothing. I am reminded of someone who spent a whole afternoon getting a Function to execute twice as fast. When asked, how much of the application session time did the original take. After a few minutes, I was told: “About one percent”. I told him that he had wasted a whole afternoon, and he should profile and find something else to look at.
Code: Select all
#cmdline "-gen gcc -O 2"
Function popcnt(x As ULongInt) As ULong
If x=18446744073709551615 Then Return 64
x -= ((x Shr 1) And &h5555555555555555ull)
x = (((x Shr 2) And &h3333333333333333ull) + (x And &h3333333333333333ull))
x = (((x Shr 4) + x) And &hf0f0f0f0f0f0f0full)
x += (x Shr 8)
x += (x Shr 16)
x+= (x Shr 32)
Return x And &h0000003full
End Function
Function __popcnt( x As ULongInt ) As ULongInt
Dim As ULongInt c
While x<>0
x And= x-1
c+=1
Wend
Return c
End Function
Dim As Double t
Var lim=10000000
Dim BitCount(...) As ULong = {&b11111111111111111111111111111111, &b11101010001110101010100100101001 _
,&b1110101001100010, &b1010001000000010, &b101, &b010}
Var p=0
For j As Long = LBound(BitCount) To UBound(BitCount)
For k As Long=1 To 3
t=Timer
For n As Long=1 To lim
Asm nop
p=popcnt(BitCount(j))
Next
Print Timer-t,p,"no loop"
t=Timer
For n As Long=1 To lim
Asm nop
p=__popcnt(BitCount(j))
Next
Print Timer-t,p,"loop"
Print
Next
Next
Sleep