[jira] [Updated] (ARROW-9029) [C++] Implement BitmapScanner interface to accelerate processing of mostly-not-null data

["Wes McKinney (Jira)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/ARROW-9029?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Wes McKinney updated ARROW-9029:
--------------------------------
    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 popcount to accumulate consecutive 64-bit words from a bitmap where all values are set, up to some limit (e.g. anywhere from 8 to 128 words or more -- we can use benchmarks to determine what is a good limit). The length of this "all-on" run is returned to the caller in a single function call, so that this "run" of data can be processed without any bit-by-bit bitmap checking
* If words containing unset bits is encountered, the scanner will similarly accumulate non-full words until the next full word is encountered or a limit is hit. The length of this "has nulls" run is returned to the caller, which then proceeds bit-by-bit to process the data

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

  was:
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 might, our {{BitmapReader}} class which allows iteration of each bit in a bitmap can be wasteful 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 popcount to accumulate consecutive 64-bit words from a bitmap where all values are set, up to some limit (e.g. anywhere from 8 to 128 words -- we can use benchmarks to determine what is a good limit). The length of this "all-on" run is returned to the caller in a single function call, so that this "run" of data can be processed without any bit-by-bit bitmap checking
* If words containing unset bits is encountered, the scanner will similarly accumulate non-full words until the next full word is encountered or a limit is hit. The length of this "has nulls" run is returned to the caller, which then proceeds bit-by-bit to process the data

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


> [C++] Implement BitmapScanner interface to accelerate processing of mostly-not-null data
> ----------------------------------------------------------------------------------------
>
>                 Key: ARROW-9029
>                 URL: https://issues.apache.org/jira/browse/ARROW-9029
>             Project: Apache Arrow
>          Issue Type: Improvement
>          Components: C++
>            Reporter: Wes McKinney
>            Assignee: Wes McKinney
>            Priority: Major
>             Fix For: 1.0.0
>
>
> 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 popcount to accumulate consecutive 64-bit words from a bitmap where all values are set, up to some limit (e.g. anywhere from 8 to 128 words or more -- we can use benchmarks to determine what is a good limit). The length of this "all-on" run is returned to the caller in a single function call, so that this "run" of data can be processed without any bit-by-bit bitmap checking
> * If words containing unset bits is encountered, the scanner will similarly accumulate non-full words until the next full word is encountered or a limit is hit. The length of this "has nulls" run is returned to the caller, which then proceeds bit-by-bit to process the data
> 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



--
This message was sent by Atlassian Jira
(v8.3.4#803005)