[C++] Optimize Take implementation

[asfimport]

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: #4531 (comment)

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.

Reporter: Ben Kietzman / @bkietz
Assignee: Wes McKinney / @wesm

Related issues:

• [C++] C++ array kernels framework and execution buildout (umbrella issue) (relates to)
• [C++] Use selection vectors in Filter implementation for record batches, tables (relates to)
• [C++] Improve and expand Take/Filter benchmarks (is related to)
• [C++] Optimize Filter implementation (is related to)

PRs and other links:

• GitHub Pull Request #7382

_{Note: This issue was originally created as ARROW-5760. Please see the migration documentation for further details.}

[asfimport]

Wes McKinney / @wesm:
Another problem I noticed with the current implementation of Take and Filter: different x86 is generated for applying these operations on arrays with the same underlying C type. For example, instructions for moving 8-byte-wide values are being generated for Int64Type, UInt64Type, Date64Type, Time64Type, and TimestampType, when only one underlying "data movement function" is needed. As part of improving the performance of Take and Filter we should also ensure that we eliminate this unneeded binary bloat in the shared library

[asfimport]

Wes McKinney / @wesm:
I'd like to work on this next week if it's alright

[asfimport]

Antoine Pitrou / @pitrou:
Issue resolved by pull request 7382
#7382