Support for-loop iteration over 1-dim memory views

[scoder]

Currently, efficient iteration over a memory views axis requires indexing. Iterating with a for-in-loop should result in the same code.

Convert the loop in IterationTransform._optimise_for_loop() in Optimize.py, similar to the range optimisation.

Additional idea: for multi-dimensional views, the iteration could yield borrowed slices, with their lifetime bound to the current loop iteration. That would avoid the refcounting overhead for them, which can hurt for very small slices (as found in #2987). Iteration seems to provide a natural frame for this.

[NicolasHug]

Just to make sure I get it right:

We're trying to convert

for e in the_view:
	# do whatever on e

into

for (i = 0; i < length_of_the_view; i++) {
	// do whatever on some_view[i]
}

And in the case that e is actually another view, we convert it into a "borrowed slice" (I don't know what that means yet but I'll look into it)

Is this correct?

[scoder]

Yes. If the_view is a memoryview (which is the case that I'd like to support here), then you wouldn't have to type e, it would just be a view on the same buffer with one dimension less (or a simple item value for 1D views).

With "borrowed slice" I mean a slice that is not refcounted (a "borrowed" reference) and thus relies on the main view to keep the buffer alive. But that seems safe in this specific case, since we're holding tight to it while we're iterating over it.

An unclear issue is: What happens on re-assignments to the loop variable? Can/should we allow that at all? Should we switch back to ref-counting if we detect that? (That seems the best way out for this.)

I think the semantics would be like this:

for x in a_view:
    …
else:
    …

would translate into (rough pseudo-code)

try:
    x = borrowed(None)
    for i in range(len(a_view)):
         x = borrowed(a_view[i])
        …
    else:
        …
finally:
    del x  # or incref(x), maybe?

And then, there could be a way to get prange() loops by saying

for x in cython.parallel.piter(a_view):
    …

as noted in #2628.

[da-woods]

I've had an go at the easy bit of this (optimized iteration over memoryviews), not the "borrowed reference" side of it, which I think it quite a bit more involved. To work well it requires some changes to type inference of memoryviews, which could probably do with some more thought.

I think the borrowed reference side is potentially a mess - you have to worry about reassignment (as you observe) but it's also inconsistent with the rest of Python if you can't access the loop target after the loop has finished.

[scoder]

Closing through #3617. Created #3715 as a follow-up regarding borrowed slices.