search

dsharlet / array

C++ multidimensional arrays in the spirit of the STL
Apache License 2.0
198 stars 15 forks source link

Consider adding "flat iterators" for arrays #22

Open dsharlet opened 4 years ago

dsharlet commented 4 years ago

It would be great to have "flat iterators" for arrays. Among other things, this could enable the standard <algorithm> algorithms to work on arrays where it makes sense, and we could get rid of our subset of these mirroring the STL. However, it is difficult to implement a performant flat iterator, due to the branchiness at each iteration required in the implementation.

dsharlet commented 4 years ago

Added a start of this in https://github.com/dsharlet/array/tree/flat-iterators, I am concerned performance will be bad though.

Peter-McLean-Altera commented 1 year ago

Is this enhancement still under consideration?

dsharlet commented 1 year ago

@jiawen was looking at it a while back, but I'm not sure about now.

The problem is this isn't really hard to implement, but the performance of it is going to be bad, and I'm not sure how that can be avoided. This can only be fast if you assume the array can be flattened to a contiguous 1D array, which is a hard assumption to make.

Peter-McLean-Altera commented 1 year ago

The issue I have (had?) is that there is no 'iterator' for shape index_type. I want to take an index_type, add to the lowest dimension, and increment the index across the shape.

I've prototyped something that works by recursively adding to each dimension of the index_type up to extent and then breaking if there is no carry over to higher dimension. Performance likely isn't great but in my application that is not a problem.

dsharlet commented 1 year ago

That sounds lot like the increment function here: https://github.com/dsharlet/array/compare/master...flat-iterators#diff-f5f78d116bcb84f7507c786fd0f8264f9e4b0d72b8412e112b1731c982983c34R756 in the branch I linked in a previous comment on this issue.

It’s definitely doable, I’m just hesitant to provide it because the performance will be terrible compared to for_each_index/for_each_value even if it doesn’t matter in some cases, I think it will still leak into cases where it does.