** Fri 12 October 2018
This blog posts discusses the design and performance implications of using
bitmaps to mark null values instead of sentinel values (or special values like
NaN).
Depending on who you talk to, one controversial aspect of the Apache Arrow columnar format is the fact that it uses a validity bitmap to mark value as null or not null. Here’s the basic idea:
The number of nulls is a property of an array, generally computed once then stored
- If an array has any null values at all, then a bitmap must be allocated
If the value at bit i is 0, then the value is null, otherwise it is not null
There’s some nice benefits of the bitmap approach:
If an array has no nulls, then the bitmap can be ignored or simply not allocated at all Nulls can be propagated in algorithms by using word-wise AND or OR operations, processing 32 or 64 values at a time
Still, for systems like R which use special values to mark nulls, bitmaps can
be controversial. The argument sometimes centers on the performance
implications of having to check bits rather than comparing a value with
INT32_MIN or checking if it is NaN. It is also noted that NaN values are
propagated automatically by the CPU in arithmetic operations, so propagating
nulls in the bitmap case will be necessarily slower.
From the perspective of databases and data warehousing, reserving certain
values to mark a null (or NA) is widely considered unacceptable. NaN is valid
data, as is INT32_MIN and other common values used as sentinels.
Most SQL systems store the null-ness of value using an extra bit or byte. File formats like Apache Avro and Parquet have a separate null/not-null encoding.
To show that the performance argument against bitmaps is not persuasive, I
wrote some in-memory performance benchmarks (I would like to do some
experiments with large memory-mapped datasets). To keep things simple, let’s
consider the sum operation which must aggregate all of the non-null values in
an array. We also will track the non-null count.
We are interested in a few typical cases:
-
Data with no nulls
-
Data with a small percentage of nulls, say 10%
-
Data with a high percentage of nulls, say 50%
To keep track of the results of a sum, I use a simple struct, templated on the type of the values:
The naive sum looks like this
Let’s consider double precision floating point values, where NaN is a common
sentinel value. So a sum function for double is:
If we represent nulls with bits, we could write the sum naively like so:
It’s possible to go much faster using bitmaps with a few optimization techniques:
Eliminate the “if” statements by using floating point operations to conditionally add the non-null values
- “Unroll” part of the for loop to sum 8 values at a time
Skip null checking for groups of 8 values with no nulls. This is made faster
still by generating a pre-populated table of bit popcounts for uint8_t
values.
Here’s the meat of this new vectorized sum algorithm:
To give a fair comparison with a sum without nulls, I also wrote similar
versions of this that sums 8 values at a time in the non-nullable case and
NaN sentinel value case. I also added the same benchmark with int64 values
using INT64_MIN as the sentinel value in case integer operations perform
differently from floating point operations.
Complete benchmarking code is here. Here are the performance results for the 3 cases there there are 0%, 10%, and 50% nulls, respectively. The size of the array being summed is 10 million values. The machine is my Xeon E3-1505M Linux laptop.
It’s definitely possible that I’m doing something suboptimal in my implementations. I would love to hear from algorithms experts!
Some observations on these benchmark results:
The “no nulls” sum functions, both vectorized and not, perform the same for all 3 cases, since it does no null checking at all When there are no nulls, there is no performance penality with the optimized bitmap sum When there are 10% nulls, the bitmap sum is about 30% faster than the sentinel-based sum. The performance gap widens when the percentage of nulls is higher. The vectorized bitmap sum is faster when there are 50% nulls than when there are 10% nulls. I am not sure why this is; I would speculate that because on average many of the terms in the sum are 0 that the processor is able to avoid some floating point operations. It might be possible to further optimize by reducing the number of possible FP operations using a “binary tree” sum.
- Vectorization / batching brings little benefit to the sentinel-based algorithm
Using a bit- or byte-based masked null representation is a requirement for a common memory format to be accepted by database systems as well as data science libraries, so using sentinel values at all is not really an option in a project like Apache Arrow. But, in many cases, using bitmaps allows faster algorithms to be developed that are not possible with the sentinel value-based null representation used in pandas and R.
I’m not a perfect programmer, so I’ll be interested to see what other kinds of optimizations others can cook up. Take a look at the benchmark code!