Ok so I just an implementation for a doubly linked list in Julia and I think it answers my question. Basically, you avoid heap allocation during iteration passing around something's that has already been allocated, like a node. Therefore, the start function should be called directly on the "container" or whatever iterates. So, a container typically has to provide a default iteration method to answer "start".
On Thursday, June 12, 2014 2:26:04 PM UTC-4, Philippe Lavoie wrote: > > Yes I agree to the heap allocated thing. That is indeed what Java does but > I think in C++ you usually wrap it in a struct and pass it by value to > function templates, so no real overhead. > > What do I have to do in Julia to avoid heap allocation in such a case? > Does the "state" value have to be a primitive type, like Int? > Is the "start" function supposed to be applied to a container type or to > an iterator. In the former case, does that mean container should provide > one default iteration way. In the latter case, does returning an iterator > uses heap allocation? > > Thanks, > Phil > > On Thursday, June 12, 2014 1:54:17 PM UTC-4, Stefan Karpinski wrote: >> >> I'm saying that using a heap-allocated mutable object to store your >> iterator state is going to be slow no matter what language you use. Where >> "slow" means "not fast enough to be how you count from 1 to n" – which is a >> very high performance requirement. In Java, C++, for loops are fast but >> require you to explicitly manage state, whereas iterators hide state >> management inside a mutable object but are relatively slow. In particular, >> they have quite different interfaces and syntax. We wanted a single >> protocol that could be fast enough to be how your basic `for k = 1:n` loop >> works, but general enough to implement all kinds of iterable things. The >> way to do this is to use external state in a functional way, allowing state >> to be kept in registers instead of having it live in a mutable, >> heap-allocated object like C++ and Java do. The for loop syntax hides this >> explicit state, so that you don't actually have to be aware of it, but the >> for loop is just sugar for calling start, done and next in the appropriate >> ways. >> >> >> On Thu, Jun 12, 2014 at 1:37 PM, Philippe Lavoie <[email protected]> >> wrote: >> >>> Hi, >>> Thanks for you answer. I am still hung up on a couple of details: >>> Are you saying that, in Julia, in order for an iterator to be efficient, >>> it has to be an immutable type? >>> Would it be possible to just use it like this: >>> iter = getacomplicatediter(myCollection) >>> (elt, current ) = next(myImmutableIter) >>> stopCondition = done(iter) >>> >>> I guess I don't understand what the additional argument/return value >>> "state" is for? >>> >>> Thanks, >>> Phil >>> >>> >>> On Thursday, June 12, 2014 12:09:22 PM UTC-4, Stefan Karpinski wrote: >>> >>>> Mutable state is lousy for performance. Since the iteration protocol is >>>> used for things as basic as a for loop count up from 1 to n, it has to be >>>> very fast. If it used a mutable iterator object, getting that to be fast >>>> enough would be a nightmare. Using explicit external state makes it easy >>>> to >>>> translate a for loop into very fast, efficient code, equivalent to what >>>> you >>>> would write by hand with a while loop. >>>> >>>> >>>> On Thu, Jun 12, 2014 at 11:59 AM, Philippe Lavoie < >>>> [email protected]> wrote: >>>> >>>>> Hi, >>>>> So I was seduced by a lot of things Julia had to offer and I found the >>>>> documentation really fun and helping. >>>>> >>>>> However, I do have some questions, one of them would be: "why iterator >>>>> functions pass state?". >>>>> In a more traditional language, you would address an iterator as such: >>>>> iter.next(), iter.done(), iter.popFront(), iter.front(), iter.empty(), >>>>> etc... >>>>> >>>>> I am curious to know why, in Julia, iterator functions pass around >>>>> state: >>>>> init = start(iter) >>>>> (i, current) = next(iter, init) >>>>> done = (iter, current) >>>>> >>>>> First of all, I am not sure why a method called "start" would exist, >>>>> given the iterator might be provided by another function, like >>>>> "ascendingValues(myRedBlackTree)", which would return an iterator for >>>>> values in ascending order for example. >>>>> Second, given you have an iterator, why pass its state around instead >>>>> of just modifying it at every functional call, like traditionally (java, >>>>> c++, etc...). IMHO, the iterator interface should/could borrow from other >>>>> programming languages and could be something like: >>>>> done = isDone(iter) >>>>> next = next(iter) >>>>> >>>>> >>>>> >>>> >>
