Uploaded image for project: 'Apache Arrow'
  1. Apache Arrow
  2. ARROW-9029

[C++] Implement BitBlockCounter interface for blockwise popcounts of validity bitmaps

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Resolved
    • Major
    • Resolution: Fixed
    • None
    • 1.0.0
    • C++

    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

          Activity

            People

              wesm Wes McKinney
              wesm Wes McKinney
              Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved:

                Time Tracking

                  Estimated:
                  Original Estimate - Not Specified
                  Not Specified
                  Remaining:
                  Remaining Estimate - 0h
                  0h
                  Logged:
                  Time Spent - 4h 40m
                  4h 40m