[ARROW-3922] [C++] improve the performance of bitmap operations

• Type: Improvement
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 0.12.0
• Component/s: C++
• Labels: pull-request-available
• External issue URL: https://github.com/apache/arrow/issues/20533
• Assignee: Animesh Trivedi
• Reporter: Animesh Trivedi
• Created: 01/Dec/18 07:59
• Updated: 11/Jan/23 07:30
• Resolved: 02/Dec/18 23:05

Description

C++ bitmap code can be optimized further by using the unsigned integers than "int64_t" for bitmap checks, and eliminating the kBitmap. See here https://godbolt.org/z/deq0_q - compare the size of the assembly code. And the performance measurements in the blog show up to 50% performance gains. 
Alternatively if signed to unsigned upgrade is not possible (perhaps in every language), then in the C++ code, we should use the bitmap operations directory ( `<<3` for division by 8, and ` & 0x7` for modulo by 8 operation), instead of `/` and `%`. 

Issue Links

• links to: GitHub Pull Request #3067