On 9/29/11 12:10 AM, Marijn Haverbeke wrote:
I see two potential problems with this... We can't use references for the yielded values, which might be a major penalty in some cases.
I'm assuming that the issue is that alias analysis will prevent you from returning a reference due to it not being able to see through the closure? Sounds like more of a problem with the alias analysis, if so.
And I somewhat doubt that it is easy to optimize. Firstly, our objects are heap-allocated, so you have a malloc/free for every loop, and secondly, inlining things from vtables is not trivial (and not currently happening, I think). Even if the object is defined in the same crate, and the object constructor is inlined, there's some rather obtuse pointer arithmetic and casting used to fetch the code pointer from the vtable. LLVM doesn't currently see through that.
We really shouldn't be casting that much, but yeah. Having iterators just be a closure would fix this.
I was thinking in another direction. We could do what Python does and compile the stack frames for iter functions in a special way. Instead of a function pointer, an iterator would be given a pointer to space it can use for its frame. Allocas within the iterator would go there. The body would have to be split up into several functions, where each 'put' starts a new function (some non-trivial transformations would be needed, but nothing hard, as far as I can see). A 'put' would involve storing the next function into the frame and returning. LLVM rather gets in our way here, but I think we could pull it off. Cleanup of such frames is tricky, but also doable (a 'current cleanup glue' would have to be stored in the frame, and updated at every 'put'). The user of an iterator could choose to allocate it on the stack (in a for-each style construct), or on the heap if it wants to use the iterator as a first-class value. The size of an iter's frame would have to be exported along with the iter, because the code that allocates it has to be generated on the side of the user. I agree this sounds pretty scary. It'd make for versatile, efficient iterators though. Also, since their frame would be alive during the iteration, values can be yielded by reference, although the loop body lives in the function that contains the for-each (and can thus return/break/cont as normal).
This is the kind of complexity that I was hoping to avoid. I would prefer to do some sort of stack-jumping protocol (i.e. just jump back to the previous frame on a |put|) before this. Most iterators are going to be used for very simple things, like vec::iteri, int::range, and so forth, and the #1 goal is for LLVM to be able to optimize these into something as efficient as a for loop.
Patrick _______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
