In analytics, it is common for data to be all not-null or mostly not-null. Data with > 50% nulls tends to be more exceptional. In this light, our BitmapReader class which allows iteration of each bit in a bitmap can be computationally suboptimal for mostly set validity bitmaps.

I propose instead a new interface for use in kernel implementations, for lack of a better term BitmapScanner. This works as follows:

• Uses hardware popcount to compute the number of set values in 256 bits at a time (or whatever is the right window size).

• Code can use the returned "run" (length + # of set bits) to switch between nullable/non-nullable code paths

  For data with a lot of nulls, this may degrade performance somewhat but probably not that much empirically. However, data that is mostly-not-null should benefit from this.

  This BitmapScanner utility can probably also be used to accelerate the implementation of Filter for mostly-not-null data

  I tried some other things that were slower (like trying to find the largest consecutive run of all-set words) before doing the simple 256-bit popcount solution.

Reporter: Wes McKinney / @wesm
Assignee: Wes McKinney / @wesm

Related issues:

• [C++] C++ array kernels framework and execution buildout (umbrella issue) (is a child of)

PRs and other links:

• GitHub Pull Request #7346

_{Note: This issue was originally created as ARROW-9029. Please see the migration documentation for further details.}