Best way to speed up iterations?

[matthias314]

There are several PRs about slow iterations over subarrays (views), for example #27535, #40397, #43295 and presently #48720. The issue could be fixed by adding @inbounds to iterate for AbstractArray. However, the conclusion of #40397 (as I understand it) was that that's not safe because users may pass invalid states to iterate. I see two ways to address this, and I'm wondering if what we are doing in #48720 is going in the commonly accepted direction.

The first idea is to use iterate with @propagate_inbounds as suggested in #27535. To me as a non-expert this appears to be a clean solution, in line with getindex and setindex!. It seems to give optimal performance and is not restricted to views. While one would have to annotate quite a few iterate methods and calls in Base to realize this idea completely, changing only a handful of lines would already go a long way. @Keno said in #27535 (comment) that this approach "is a bit odd since iterate is not getindex". It's unclear to me whether this is a just a naming issue or something more fundamental. I also note that many iterate methods in iterators.jl are already defined with @propagate_inbounds.

A variant of this idea (maybe a hack) would be to create a new "unsafe array" wrapper around arrays in functions that do iteration. This wrapper, invisible to the user, would turn bounds checking off for the given array. This again gives optimal performance. For a full solution it requires code to deal with many iterators (Generator, Zip etc.) and each function one wants to speed up. Again, doing it only for AbstractArray and foldl_impl would already change a lot.

The second approach I see is to find better iterate methods for each type suffering from slowdown. For views (more precisely, FastSubArray) this is currently done in #48720, with surprisingly good performance (at most 30% slower than a version without views, compared to a factor of 60 for Int8 on master). Finding the right code that does the trick has not been obvious, and of course it only works for views. For other arrays one would have to start from scratch. That's why I feel that we are not addressing the root problem, but the positive side is that we don't need @inbounds for this.

Any opinions on which way is the way to go?

EDIT: #48720 has been merged. It speeds up iteration for FastContiguousSubArray only by defining new methods for checkindex. Still I wonder if there is any interest in pursuing the first approach mentioned above.

[N5N3]

I think rewaking #27535 is the best solution for now, because of the following trues:

1. iterate for Iterators.reverse(::AbstractArray) has been marked as @propagate_inbounds.
2. Array wrappers in Base usually trust the parent implement. e.g. SubArray checks the index on it's own axes and the getindex on parent is marked as @inbound.

[matthias314]

I have noticed that @inbounds is already used for reduce, which can lead to out-of-bounds access. I've started a Discourse thread to see if that's considered acceptable. If it is, then I don't see a problem doing the same for foldl, foldr and maybe even for the lowering of for loops.

[matthias314]

In case anybody is interested: I've created the branch matthias314@ea64de2 where @inbounds is used for mapfoldl and friends and also in the lowering of for loops. See #48803 (comment) for a benchmark.