[jira] [Comment Edited] (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:comment-tabpanel&focusedCommentId=17125430#comment-17125430 ] 

Wes McKinney edited comment on ARROW-9029 at 6/4/20, 12:58 AM:
---------------------------------------------------------------

After writing this JIRA I wrote an initial implementation which tried to find the longest consecutive run of all-set words. This turned out to be much, much slower than simply running popcount on every word and returning the popcounts 4-words at a time.  I'll rewrite the JIRA to explain what my PR actually does


was (Author: wesmckinn):
After writing this JIRA I wrote an initial implementation which tried to find the longest consecutive run of all-set words. This turned out to be much, much slower than simplify running popcount on every word and returning the popcounts 4-words at a time.  I'll rewrite the JIRA to explain what my PR actually does

> [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
>              Labels: pull-request-available
>             Fix For: 1.0.0
>
>          Time Spent: 1h 20m
>  Remaining Estimate: 0h
>
> 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)