[ARROW-5760] [C++] Optimize Take implementation

• Type: New Feature
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 1.0.0
• Component/s: C++
• Labels: pull-request-available
• External issue URL: https://github.com/apache/arrow/issues/22185
• Assignee: Wes McKinney
• Reporter: Ben Kietzman
• Created: 27/Jun/19 17:23
• Updated: 11/Jan/23 07:42
• Resolved: 11/Jun/20 16:45

Description

There is some question of whether these kernels allocate optimally- for example when Filtering or Taking strings it might be more efficient to pass over the filter/indices twice, first to determine how much character storage will be needed then again into allocated memory: https://github.com/apache/arrow/pull/4531#discussion_r297160457

Additionally, these kernels could probably make good use of scatter/gather SIMD instructions.

Furthermore, Filter's bitmap is currently lazily expanded into the indices of elements to be appended to the output array. It would probably be more efficient to expand to indices in batches, then gather using an index batch.

Issue Links

• is related to: ARROW-9045 [C++] Improve and expand Take/Filter benchmarks
• is related to: ARROW-9075 [C++] Optimize Filter implementation
• relates to: ARROW-8894 [C++] C++ array kernels framework and execution buildout (umbrella issue)
• relates to: ARROW-8500 [C++] Use selection vectors in Filter implementation for record batches, tables
• links to: GitHub Pull Request #7382