[C++] Optimize Take and Filter on fixed-size list of primitives

[pitrou]

Describe the enhancement requested

Currently, calling the Take and Filter functions on a fixed-size list of primitive types will use the following algorithm:

1. generate an array of child indices into the values array (for example, taking indices [1, 2] on a fixed_size_list<T, 3> array will generate child indices [3, 4, 5, 6, 7, 8])
2. call Take on the values array and the child indices

But, when the fixed-size list's value type is a fixed-width primitive type such as numbers or even fixed-size binary (example : a fixed-shape tensor), then we could simply Take or Filter directly on the values array, using the appropriate byte width. For example, filtering a fixed_size_list<int32, 3> can use the same algorithm as filtering a fixed_size_binary<12>. This should be much faster.

Component(s)

C++

[pitrou]

cc @felipecrv @js8544 @rok

[rok]

That seems like a worth-while optimization. Can we reuse fixed-size binary codepath?

[pitrou]

Yes, that would be the idea. (related: #39795)

[felipecrv]

A generic "gather" primitive could take the base indices and length of each contiguous run and then dispatch (based on template-params) the appropriate buffer writes for the type.

[pitrou]

A generic "gather" primitive could take the base indices and length of each contiguous run and then dispatch (based on template-params) the appropriate buffer writes for the type.

That's a separate avenue, though.

[felipecrv]

As I'm looking into optimizing take on chunked arrays, I will do this together.

[felipecrv]

I got this working locally for Take

[felipecrv]

A change to FizedSizeListBuilder that makes it more likely that the optmization proposed here is possible in more case, simple, more effective -> #41189