From: William Rutiser <wruyahoo05@...>
Date: 2010-03-20T03:38:12+09:00
Subject: [ruby-core:28805] Re: [Feature #2065] An ancestors iterator

If I understand this discussion correctly, objects have an #ancestors 
method which returns an array of the object's ancestors. This method is 
an atomic action within the Ruby interpreter.

It is proposed to add an #each_ancestor iterator that conceptually 
iterates over the object's ancestors without the overhead of building an 
array. Such an iterator is thought to provide a small syntactic 
convenience and an arguable performance improvement

To achieve the performance improvement, an implementor might be tempted 
to yield to the block passed to the iterator as soon as each ancestor is 
found in the system's internal data structures. Yielding immediately 
when the ancestor is discovered requires only remembering the address of 
the current or next ancestor over the yield. Not yielding immediately 
requires somehow storing the set of ancestors until all are found. 
Storing the ancestors may have almost as much overhead as returning an 
array.

One possible use for these features would be to modify the object's set 
of ancestors in some way dependent on exactly which ancestors are 
present, perhaps by adding new ancestors. This means the internal 
ancestor structure could change WHILE the non-atomic iterator is 
suspended over the yield.

Concurrent modification of structures of linked pointers is hard to get 
right even when all parties know what is happening. Also, it is hard to 
explain or document these problems in a way that they can be understood 
by a programmer having little experience with the deep internals of an 
interpreter for a very dynamic language like Ruby. Not getting it 
exactly right means weird interpreter crashs. The documentation problem 
means programmers puzzled, confused, or maybe angry when the interpreter 
gives results different then they expect.

My intuition suggests that the proposed feature's limited benefits do 
not justify the effort required to safely implement it.

Please note that I am in not, in any way, an experienced Ruby programmer 
nor do I have any knowledge of the MRI interpreter. I do have quite a 
bit of experience with the design and implementation of other languages.

My thanks to all those responsible for Ruby.

-- Bill




Roger Pack wrote:
>> For DSLs that want to have method-like inheritance, the lack of an ancestors iterator is a potential and unnecessary bottleneck.  An each_ancestor iterator would, as per the benchmarks, significantly speed up a useful programming pattern that I think would be used more frequently if it were inherently faster. I hope that clarifies the purpose of this request.
>>     
>
> Potentially a bottleneck but is it actually? You could instead use
> #ancestors.each or roll your own...
>
>  class Module
>    def each_ancestor
>      ancestors.each{|a| yield(a)}
>    end
>  end
>
>
> or a faster version (if you can cache)
>
>  class Module
>    def each_ancestor
>      @ancestors ||= ancestors
>      @ancestors.each{|a| yield(a)}
>    end
>  end
>
> Cheers.
>
> -rp