Heads.

[SoniEx2]

I'd like a head. With a lifetime bound to the main array, it provides efficient moving around in an arbitrary array.

For example, on an array, .move(axis, amount) moves the head on axis by amount. If the array is a linear 2D array, and you're moving vertically, this is a multiply and sum. If it's a Z-order-curve 2D array, moving always uses bitwise tricks and never multiplication.

[bluss]

Interesting ideas. Are you thinking of arbitrary movements (a random access iterator)? Just as a musing, I don't know a way to do those in Rust that really make for nice performant code, due to the need for bounds checking.

[SoniEx2]

With simple gets that do x+y*width you have to do one multiplication and one addition per position, not counting the 2 bounds checks. With a head, you do a single bounds check and a single addition per movement.

See also this Kotlin code: http://sprunge.us/PRjW (note that current versions of rust cannot handle such heads, see rust-lang/rust#8995, rust-lang/rust#17307, rust-lang/rust#17842)

Considering you'd go from 1 multiply, 1 add, 2 bounds check to 1 or 2 adds (2 adds are still faster than 1 multiply) and 1 bound check, it's a huge performance improvement. The optimal iteration mode for linear heads is probably either circular/spiral iteration or zig-zag iteration.

However, if you just wanna iterate everything and you don't care about order/position, the best way to go about it is probably to just treat the whole thing as a linear array and you still get 1 add and 1 bound check for each operation, but now you don't run into cache locality issues.