1

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.
  • 3
    "How can I implement" -- are you asking for an algorithm or for source code? In what programming language (or assembly language)? Can it be any solution, e.g. a simple solution (or are you looking for a "fastest" solution, or "most readable", or "smallest", or what)? What's the maximum size of W you need to support? Do your integers respect byte boundaries (e.g. W is 2 or 4 or 8), or not (e.g. W is 3 or 5)? – ChrisW Feb 26 '18 at 23:37
  • 3
    Or look at nanopb - an alternative implementation of protocol buffers targeting embedded solutions. All said and done - protobufs varints dont seem that helpful here. All said and done - Bloom filter arrays seem to have relatively low number of elements and since time is very important why even bother using bitfields? – Jan Dorniak Feb 27 '18 at 2:17
  • 2
    Not quite sure why there's so much talk of protocol buffers here: protocol buffers is a serialization format. While it may well support packing values into structures using sub-byte allocations (or not - I don't actually see anything relevant at all in the description of it), it doesn't manipulate them in this format, but rather unpacks them into traditional byte- or word- aligned variables so that they can be accessed using standard compiler techniques. This is entirely different from the kind of approach you'd want to take to perform direct update of such fields. – Jules Feb 27 '18 at 2:24
  • 2
    For allocation-free it depends entirely on whether or not the array is resized - if it is, no can do. If the size is constant thats simple then. All method-local prinitives are allocated on the stack which is basically free. As for branch-free I don,t believe it is possible packing it this way - it could be if you gave up the remainder bits, that is for W=7 you give up one bit in every uint64, storing 9 values in every uint64. This might work for you. Since Im a C++ guy Id template this at least on W if possible. – Jan Dorniak Feb 27 '18 at 16:40
  • 1
    Also sometimes (gcc) you can mark which bramch is more likely so that the compiler kniws how to optimize better. This technique is used for e.g. in the Linux kernel – Jan Dorniak Feb 27 '18 at 16:42
2

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).

  • Thanks for the detailed answer. Re "Maybe you should though, unless you're doing this for fun or homework, take someone's advice and search for some existing implementation": while not exactly homework, I do want to implement this myself, for personal edification. I think I'll begin by supporting only int-widths that align to the int64 boundary, and then (possibly) iterate on that. – blz Feb 27 '18 at 12:06
1

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.

  • I guess you're referring to "The INSERTPS and PINSR instructions read 8, 16 or 32 bits from an x86 register etc." on e.g. this page. – ChrisW Feb 27 '18 at 2:28
  • @ChrisW - that'd be one approach. Another: in order to increment/decrement a value, you could load a constant vector that contains a 1 or -1 in the appropriate field into one register, then use PADDB to update the stored vector. If you can collate a number of updates together (which seems likely for this kind of application) it can be much more efficient than extracting single values. – Jules Feb 27 '18 at 2:39
  • @Jules collation seems unlikely - lookinh at the description of the algorithm at any given step the fields to change should ideally be almost random. And collating between steps is not always an option. – Jan Dorniak Feb 27 '18 at 9:15
  • I guess this is a good reason to dive into assembly :) Thanks very much for the suggestion. I'll probably accept @ChrisW's answer because I can immediately apply it, but I'm bookmarking yours as something to come back to at a later date. – blz Feb 27 '18 at 11:59
-4

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.

  • 1
    BTW in certain programming languages (like c++) && and || are logical operations, while & and | are the bitwise ones. – πάντα ῥεῖ Feb 26 '18 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.