Details
-
Improvement
-
Status: Resolved
-
Major
-
Resolution: Fixed
-
None
Description
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.
Attachments
Issue Links
- is a child of
-
ARROW-8894 [C++] C++ array kernels framework and execution buildout (umbrella issue)
-
- Open
-
- links to
