[ARROW-10058] [C++] Investigate performance of LevelsToBitmap without BMI2

• Type: Sub-task
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 2.0.0
• Component/s: C++
• Labels: pull-request-available
• External issue URL: https://github.com/apache/arrow/issues/26079
• Assignee: Antoine Pitrou
• Reporter: Antoine Pitrou
• Created: 21/Sep/20 18:52
• Updated: 11/Jan/23 08:10
• Resolved: 07/Oct/20 04:49

Description

Currently, when some Parquet nested data involves some repetition levels, converting the levels to bitmap goes through a slow scalar path unless the BMI2 instruction set is available and efficient (the latter using the PEXT instruction to process 16 levels at once).

It may be possible to emulate PEXT for 5- or 6-bit masks by using a lookup table, allowing to process 5-6 levels at once.

(also, it would be good to add nested reading benchmarks for non-trivial nesting; currently we only benchmark one-level struct and one-level list)

Issue Links

• links to: GitHub Pull Request #8320