Fast BitCounting

1

I have a series of UInt64s that I’m using to store an array of booleans. These are to represent tasks that a customer must complete.

I’d like to offer some progress, I already know the number of tasks the customer has to complete, but I need a fast way to display how many have been completed.

The ids of the booleans are stored in an enum (1, 2, 4, 8), so I could loop through all entries of the enum and check to see that bit is set. But I wondering if someone with more experience in this area has a better idea.

2

There are some well known Bit Twiddling Hacks that might be useful. I used those with my Sudoku solver.

1 Like
3

Silly idea… why not also keep an additional
integer variable as a ‘counter of things done so far’?

You know the starting point.
You have code to mark a task as done.
Just add an increment to the ‘make done’ code, and you’re there?

4

But bit set can do a lot more than just a simple counter variable.

5

How many bits/booleans do you have and what is their scope of access?

6

That is something I didn’t think about, I was just hoping there would be an API for counting the number of bits set to 1. Which I think was silly, because how many people need a function to that?

I see that and thank for sharing the page. I was hoping for some magic C function, but like I said above, I think I was expecting too much :slight_smile:

Right now, I’m using 33 of them, they’re controlled via a Toggles and custom binding. I expect before I’ve finished, there will be more, but at this point I couldn’t say exactly, except when I designed this, I knew 32 wasn’t going to be enough :slight_smile:

7

Would you look at that? After some sleuthing and browsing around the web… There is an API in Swift for doing just this! It’s called nonzeroBitCount!

Man, the more I learn Swift, the more I appreciate the well populated function set.

1 Like
8

you could write a little function to count them

something akin to

    Function NonZeroBitCount( value as Uint64) as integer

  Dim count As Integer

  For i As Integer = 1 To 63
  
    Dim currentBitSet As UInt64 = 2 ^ I
  
    If (value And currentBitSet) <> 0 Then
      count = count + 1
    End If
    currentBitSet = currentBitSet * 2
  Next
 
  Return count
end function

insert suitable pragmas

1 Like
9

there are other ways that MIGHT be faster (like a linear list of 64 1 bit checks)

Function NonZeroBitCount( value as Uint64) as integer

  Dim count As Integer

    if (value and &b00000000 00000000 00000000 00000000 000000000 00000000 000000000 00000001) <> 0   Then
      count = count + 1
    End If
    if (value and &b00000000 00000000 00000000 00000000 000000000 00000000 000000000 00000010) <> 0   Then
      count = count + 1
    End If
    if (value and &b00000000 00000000 00000000 00000000 000000000 00000000 000000000 00000100) <> 0   Then   
      count = count + 1
    End If
 
   .... and so on through all the bits ....
  Return count
end function

certainly possible there are other faster ways that might be able to count more bits at once etc

1 Like
10

Probably does what Norm suggested. Just because there is a call, doesn’t mean its the fastest method, although it makes your code smaller.

11

From what I could find online, there is a processor instruction for counting bits popcnt and the Swift framework uses that. Because it’s an on processor instruction, it should be faster than any code you and I can write in a high level language.

Seems like most processors since the 2000s have had a similar instruction.

Xojo could even use it to add the same function to Xojo made apps.

Edit: POPCNT is the Intel instruction, the ARM instruction is VCNT.

2 Likes
12

Still trying to understand the requirement in full. How fast does it have to be? How would an array of elements of type Bool in standard Swift code perform?

13

Pretty simple really, SwiftUI app drawing the value at layout time (so needs to be fast).
Second, I’m using an UInt64 to save on memory, as it can hold 64 booleans, in 8 bytes. I’m now using 50 of 'em already.

14

It takes 1 msec to test a buffer containing 1000 bits without using a processor instruction on my really old computer, so it’s not too bad even without optimizations.

8th can use a buffer as a bitmap of bits:

: bitmap  \ maxbits -- b
  8 n:/mod swap if
    n:1+
  then
  b:new b:clear ;

: app:main
  1000 bitmap
  5 1 b:bit!
  56 1 b:bit
  3 1 b:bit!
  d:msec >r
  0 >r
  ( b:bit@ n:r+ ) 0 999 loop drop d:msec r> . cr r> n:- . cr ;

Result is 3 bits set and took 1 msec:

3
1
1 Like
15

In Xojo it could be:

Public Function NonZeroBitCount(value as Uint64) As integer
  var bits as integer = 0
  
  Do until value = 0
    bits = bits + (value And 1)
    value = ShiftRight(value, 1)
  Loop
  
  Return bits
End Function
1 Like
16

Let’s say 8th makes simple things more complex. But it is a nice timeshredder to use. The 8th :slight_smile:

17

I highly doubt Java could use arbitary sized buffer as a bitmap of bits with simpler code.

Here is a little refactored and commented version:

1000 constant MAXBITS

\ Allocate buffer large enough to store maxbits bits.
: bitmap  \ maxbits -- b
  8 n:/mod swap if  \ How many bytes is needed?
    n:1+
  then
  b:new b:clear ;

: one-bits?  \ b n -- b n
  \ We use the top of r-stack as a counter
  0 >r ( b:bit@ n:r+ ) 0 rot loop r> ;

: app:main
  1000 bitmap   \ Allocate bitmap for 1000 bits.
  30 1 b:bit!   \ Set bit 30 to 1
  50 1 b:bit!   \ Set bit 50 to 1
  840 1 b:bit!  \ Set bit 840 to 1
  MAXBITS n:1- one-bits? . ;
18

I may be wrong but it’s my understanding addressing bits is slower than addressing a whole byte and 50 booleans would only be 50 bytes anyway so what’s the point in packing them like that?

19

Basicly, if the compiler is smart, bits are unbeatable in speed in this context. Because the value can be cached in just one CPU register and ultra fast CPU op codes will solve this in nanoseconds. Many bytes are waaay worse, because you need lots of memory I/O and bus addressing.

20

TBH: I never considered that, in my original design I saw that I would need an array of booleans and immediately thought about using bitMasks instead of booleans. It’s going to be quicker to save and load, and use less memory. I have several pages, but not really enough for it make a major difference.

There is one other advantage. The tasks are grouped, so I can use a groupMask (which contains all the elements of the group) and with one operation I can tell if that entire group is completed or not.

Maybe if my original design had 100s of booleans, I may reconsider, then again I may not have and just used multiple UInt64s… It’s hard to say.