A Practical Look at Bitmaps

With product launch imminent, a colleague ran into an API performance issue and came to discuss it with me:

Our product’s built-in explorer has a GraphQL API that returns N non-empty blocks. The API can be called like this: starting from the latest block, skip N non-empty blocks and return the next M non-empty blocks.

In API design, skipping N records (for pagination) and returning M results that satisfy some filter is a very common but not particularly easy requirement—especially when the data filter cannot be done with a simple DB query. In our case, block data is stored in a kv-based state DB, so filtering is an O(n) operation. From a product perspective, blocks without transactions only have meaning on the clock; they are not very meaningful to show users. So we want to collapse empty blocks in the UI, which requires the API to return a list of non-empty blocks.

Initially, we reasoned that in actual deployment, non-empty blocks would far outnumber empty ones. So the design simply read blocks from the State DB, filtered out empty blocks, and returned N non-empty blocks to the user.

However, in the past two days, our internal test network was not running simulations, so no transactions were produced, and empty blocks accumulated by the tens of thousands. At that point, accessing the API required filtering tens of thousands of records, making timeouts very likely.

This is a classic problem that can be sped up quickly and effectively with a bitmap. Wikipedia defines a bitmap as follows:

In computing, a bitmap is a mapping from some domain (for example, a range of integers) to bits. It is also called a bit array or bitmap index.

For our requirement, if we map block height to whether the block has any transactions, we get a bitmap, and returning N non-empty blocks reduces to finding N MSBs (Most Significant Bits) in the bitmap. As shown in the figure:

API Design

Following this idea, we can define the following interface for the bitmap:

• new(): Initialize a bitmap
• set(bitmap, index): Set the bit at height index to 1. For example, if block 50 has transactions, call this function.
• unset(bitmap, index): Set the bit at height index to 0.
• set?(bitmap, index): Test whether the bit at height index is 1.
• msb(bitmap): Get the index of the highest set bit. For example, msb(0b1011) = 3.
• msb(bitmap, m): Get the indexes of the top m set bits. For example, msb(0b1011, 3) = [3, 1, 0].

This lets us optimize the business logic as follows:

1. When a block at height h is created, if its number of transactions > 0, call set(bitmap, h).
2. To fetch N non-empty blocks, first get the heights of N non-empty blocks: msb(bitmap, N).
3. Then, with the list of heights, fetch the corresponding data from the state DB one by one.

At this point, in theory, our API performance should improve by several orders of magnitude. However, this bitmap differs slightly from a traditional fixed-length bitmap: it keeps expanding over time. Here we exploit Elixir/Erlang’s support for arbitrary-precision large integers and take a shortcut—our bitmap is represented by a single integer.

Note: Erlang’s large integers do have a limit—when an integer exceeds 35 million bits, the system errors out. In other words, Erlang cannot create or process an integer occupying more than 4 MB of memory. Considering that a 128-bit integer (IPv6) can “assign an IP address to every grain of sand on Earth,” 35 million bits is effectively an infinitely large integer.

Therefore:

• set(bitmap, index) is an bitmap ||| 1 <<< index operation;
• unset(bitmap, index) is an bitmap &&& ~~~(1 <<< index) operation;
• set?(bitmap, index) is an (bitmap >>> index &&& 1) === 1 operation;

These operations map directly to CPU bit-manipulation instructions and are extremely efficient.

MSB

msb(bitmap) is a little more involved. I drew a diagram to illustrate it:

First, we can convert the integer representing the bitmap into its binary form. Then finding the MSB index of the whole bitmap becomes: the MSB of the highest byte of the bitmap’s binary representation, plus the number of remaining bytes × 8. To get the MSB of a single byte, we can do:

defp get_msb(0, 0), do: 0
defp get_msb(0, r), do: r - 1
defp get_msb(i, r), do: get_msb(i >>> 1, r + 1)

And getting the MSB of a bitmap with the algorithm just described is simple:

def msb(bitmap) do
  <<first::size(8), rest::binary>> = to_binary(bitmap)
  size = byte_size(rest) <<< 3
  get_msb(first, 0) + size
end

To get the indexes of the highest N set bits in a bitmap, we just need to get its MSB, unset that MSB, and repeat in a loop:

defp do_msb(_bitmap, 0, result), do: Enum.reverse(result)

defp do_msb(bitmap, length, result) do
  pos = msb(bitmap)
  do_msb(do_unset(bitmap, pos), length - 1, [pos | result])
end

Following the same pattern, if we want to skip M values and get the next MSBs, it seems we can fetch M + N MSBs and strip off the first M. That is simple but inefficient, especially when M >> N. For example, with a 1M-bit bitmap, if we want to skip 1,000 MSBs and then take 10, we waste 1,000 MSB computations. Each operation is very fast, but small costs accumulate.

In fact, when skipping M MSBs, we do not need to know the indexes of the skipped MSBs. In theory, we can simply keep shifting right, discarding the shifted-out bits; if a discarded bit is 1, increment r by 1. When r === M, we have skipped M MSBs. In Erlang, we can do this with pattern matching:

The code is simple—two lines:

defp do_skip(bin, n, acc) when n === acc, do: bin
defp do_skip(<<bit::integer-size(1), rest::bitstring>>, n, acc), do:
  do_skip(rest, n, acc + bit)

With this, the msb interface mentioned earlier can be extended:

# skip 10 MSBs, get the indexes of the next 5 MSBs
def msb(bitmap, 5, skip: 10)

For a static bitmap, this interface works well. But for a dynamically expanding bitmap, skip becomes problematic. For example, the first request asks for 10 MSBs; the second skips 10 and asks for 10 more. If the bitmap has grown by a few bits between the two requests, the second request will return incorrect data. In this scenario, we need a cursor to record the last value returned by the previous request, then pass it into the next call:

# skip to after the bit at index 137, get the indexes of the next 5 MSBs
def msb(bitmap, 5, cursor: 137)

Supporting a cursor is simple; I will leave it as an exercise for readers (after thinking it through, you can refer to the code I wrote).

After this series of clever tricks, we had essentially implemented the requirement.

Population Count

Of course, a complete bitmap implementation should ideally also have population count—i.e., how many bits are set to 1 in total. This is a classic problem; see Wikipedia’s Hamming Weight. For example, the show-off code that often appears on Stack Overflow:

const uint64_t m1  = 0x5555555555555555; //binary: 0101...
const uint64_t m2  = 0x3333333333333333; //binary: 00110011..
const uint64_t m4  = 0x0f0f0f0f0f0f0f0f; //binary:  4 zeros,  4 ones ...
const uint64_t m8  = 0x00ff00ff00ff00ff; //binary:  8 zeros,  8 ones ...
const uint64_t m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64_t m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
const uint64_t h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...

//This is a naive implementation, shown for comparison,
//and to help in understanding the better functions.
//This algorithm uses 24 arithmetic operations (shift, add, and).
int popcount64a(uint64_t x)
{
    x = (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits
    x = (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits
    x = (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits
    x = (x & m8 ) + ((x >>  8) & m8 ); //put count of each 16 bits into those 16 bits
    x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits
    x = (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits
    return x;
}

However, if you understand the skip-MSB algorithm above, population count is a piece of cake. Interestingly, Wikipedia has this algorithm:

//This is better when most bits in x are 0
//This is algorithm works the same for all data sizes.
//This algorithm uses 3 arithmetic operations and 1 comparison/branch per "1" bit in x.
int popcount64d(uint64_t x)
{
  int count;
  for (count=0; x; count++)
    x &= x - 1;
  return count;
}

The gist is that when a bitmap contains many 0s, this algorithm is more efficient. But do not be fooled by that sentence—it assumes a 64-bit integer. For a 1-million-bit integer, this algorithm is about 30% worse than the skip-MSB-like population count algorithm above (see the benchmark at the end). This is the meaning of “believing everything in books is worse than having no books at all”: performance is measured in real application scenarios, not guessed at off the top of one’s head.

Storing the Bitmap

Finally, once a bitmap is generated, storage inevitably comes into play. Storing the entire bitmap on disk is inefficient: a 1M-bit bitmap needs 128 KB of disk space. Wasting space is one thing, but the real issue is poor write efficiency. So we can gzip it; for a relatively sparse bitmap, compression can reduce it to just a few hundred bytes. When writing this bitmap module, I originally spent a lot of thought on using RAM and delayed writes to reduce disk writes. Later, after gzipping and benchmarking, I found that the straightforward write path was quite efficient. For our use case, writing the bitmap to disk once per block is no burden at all, so I did not keep optimizing further.

Performance

Having said all this, it is time to trot out the results—benchmark results below (note: the initial bitmap I used was a 1-million-bit bitmap, so do not compare these with benchmark results for a 64-bit bitmap):

$ make bench
Benchmark the simple bitmap...
Operating System: macOS
CPU Information: Intel(R) Core(TM) i7-7820HQ CPU @ 2.90GHz
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.8.1
Erlang 21.2.4

Name                                      ips        average  deviation         median         99th %
set random bits                      94140.89      0.0106 ms   ±110.23%     0.00900 ms      0.0330 ms
unset random bits                    46012.36      0.0217 ms    ±57.87%      0.0210 ms      0.0580 ms
load bitmap                           2433.74        0.41 ms    ±27.38%        0.39 ms        0.72 ms
save bitmap                           1132.84        0.88 ms    ±41.45%        0.84 ms        1.38 ms
get msb list                           651.70        1.53 ms    ±14.33%        1.48 ms        2.52 ms
get msb list with random cursor        511.99        1.95 ms    ±26.43%        1.84 ms        3.39 ms
get msb list skip N                    189.12        5.29 ms    ±32.41%        5.35 ms        8.62 ms
population count                        74.11       13.49 ms     ±5.06%       13.34 ms       16.19 ms
population count 1                      50.11       19.96 ms     ±3.97%       19.80 ms       23.25 ms

The performance is actually quite good. This is currently an unoptimized version, written over a few scattered hours. For the problem we encountered at the beginning of the article, the performance from these benchmarks is more than sufficient (the bottleneck has since moved elsewhere). It supports a bitmap upper limit of roughly 35 million bits. Given that a block is produced every few seconds—say every 10 seconds—350 million seconds is about 11 years, enough to last for quite a while. Of course, there is still plenty of room for optimization. Given the special nature of blockchains, a block is read-only once generated, and a bit is never unset after being set; many (specialized) optimizations are possible here. In addition, block height—i.e., the index—grows linearly, so older bitmaps (cold data) can live on disk and be loaded on demand, while only a very small amount of hot data needs to remain in memory; this could improve time and space by one to several orders of magnitude. Furthermore, the GraphQL API layer can add caching to further improve performance.

Readers interested in the source code can visit github.com/tyrchen/simple_bitmap. The code is simple—about two hundred lines including comments.