How can I query, increment & decrement arbitrary-length integers encoded into a bit-array?

Question

I'm in the process of implementing a counting Bloom filter. This data structure is defined as a bit-array and a "width" parameter, W.

The bit array stores unsigned integers, whose size is determined by W, into an array of uint64s. Thus, it is expected that the integers' size will not be multiple of 8. For instance, W=4 (max value = 15) is a popular choice. Moreover, it is expected that the integers'size will not necessarily respect byte-boundaries. W=3, is also an acceptable value. The maximum size for W, however is 8.

Thus, a bit array with W=4 should be interpreted as such:

+----+----+----+----+----+----+----+----+----+----+----+----+----+----
|       uint4       |       uint4       |       uint4       |        ...
+----+----+----+----+----+----+----+----+----+----+----+----+----+----

Similarly, a bit array with W=2 should be interpreted as:

+----+----+----+----+----+----+----+----+----+----+----+----+----+----
|  uint2  |  uint2  |  uint2  |  uint2  |  uint2  |  uint2  |        ...
+----+----+----+----+----+----+----+----+----+----+----+----+----+----

This data structure needs to support three distinct operations:

1. Read the i-th uintW
2. Increment the i-th uintW
3. Decrement the i-th uintW

Decrementing a uintW below 0 is undefined behavior. Incrementing a uintW above its maximum value is also undefined behavior.

Questions

1. Which algorithm can implement these operations on a bit array backed by an array of uint64s?
2. Is there a allocation-free and/or branch-free solution? The idea here is to have the most performant solution possible, since Bloom filters have a nasty habit of being called billions of times in tight loops.

Answer 1

Here's the start of a pseudocode solution for W = 4.

// beware: untested code ahead

uint64[] array;

int read(int i)
{
  uint64 loaded = array[i / 16];
  return (loaded >> ((i % 16) * 4)) & 0xF;
}

i / 16 because there are 16 4-bit ints per uint64 (it's 64 / W).

0xF is the bitmask (it's 2**W - 1).

increment could be similar, built on top of that:

1. read
2. increment the resulting integer
3. write

The write is similar to the read (assume the new incremented n value is small and doesn't need masking/truncating):

void write(i, n)
{
  uint64 loaded = array[i / 16];
  shift = ((i % 16) * 4);
  // zero (mask-out) some bits to make a hole into which to OR the new value
  loaded = loaded & ~(0xF << shifted);
  // or-in the new value, suitably shifted
  loaded = loaded | (n << shifted);
  // write the result back into the buffer
  array[i / 16] = loaded;
}

There are micro-optimizations available by combining these (read and write) operations into one function (e.g. loaded and shift need only be calculated once).

I guess the fastest implementation uses a separate/dedicated/hard-coded implementation for each value of W.

---

W values of 3, 5, 6, and 7 introduce complications that I don't want to solve, i.e. "an exercise for the reader". :-(

---

The fastest implementation might be to use lookup tables instead of bit-twiddling; for example, consider this solution for W is 4:

uint8[] array; // not uint64
uint8[256][2] lookup; // precalculated lookup table

increment(i)
{
    uint8 loaded = array[i/2];
    // lookup the incremented value
    // choose the right lookup table to increment either the 1st or 2nd nibble
    loaded = lookup[loaded][i % 2];
    // write the result back
    array[i/2] = loaded;
}

For W is 2 you'd need a lookup table like

uint8[256][4] lookup;

Precalculating the contents of the lookup table is an exercise for the reader (you could do it by machine, using a slower implementation) ... and so is figuring how to implement those less convenient W values (3, 5, 6, and 7).

---

Maybe you should though, unless you're doing this for fun or homework, take someone's advice and search for some existing implementation (because instead of "reinventing the wheel", generally try to use a professional pre-made, optimized, tested, peer-reviewed, supported solution).

---

If you're looking for the fastest (not smallest) implementation, IMO you might consider implementing W=3 and similar by wasting space in the buffer (e.g. implement W=3 using the same code and data layout as W=4).

If you're using a lookup table it's good to align on a byte boundary (so you transform whole bytes, needing only 256 elements in the lookup table).

If you're bit-twiddling it's sufficient to align on a 64-bit boundary, and you can waste less space (e.g. when W=6, instead of fitting each uint6 into a uint8, fit 10 uint6 into a uint64, wasting only 4 bits per uint64).

Answer 2

The fastest approach to accessing integers packed into less than single byte-wide fields, at least on an x86 family processor, is likely to involve using the PDEP and PEXP bit-manipulation instructions. I haven't checked how good current compilers are at generating these instructions, although a brief google suggests that at least as of last year LLVM didn't have any direct support, although it may be supported via intrinsics -- which means that Go is unlikely to use them unless there is an explicit optimization or interface in the compiler that is designed to enable them. LLVM in general is pretty close to being the best available optimizer for x86 machines, so if LLVM doesn't generate these instructions it's a good bet that none of the other major compilers do, either. This suggests that for optimal performance here, assembly language is likely to be your best bet.

Unless you really need the space savings produced by using this packed format, however, you may be better off wasting a bit of space so that you can use the more commonly supported (and faster) SSE* instructions to perform your operations. Most modern compilers can generate these in many circumstances, and they are likely the fastest way to perform operations on a lot of data, but they do require your values to be packed into fields of at least 1 byte per value.

Answer 3

You can do this with a bit of maths and clever use of bitwise operations like and (&), or (|), and shift (>>). I'll leave the actual implementation to the reader.