hg: lambda/lambda/jdk: Modify the conc-Node spliterator forEach and tryAdvance from using the call

[Paul Sandoz]

On Feb 18, 2013, at 7:44 PM, Edward Harned <edharned at gmail.com> wrote:
> Is the stack problem for serial, parallel or both?
> 

It can be both. A conc-Node is an intermediate result produced from a parallel computation which can be input to a another parallel or serial computation. It all depends at which Node in in the conc-Node tree traversal occurs at and the distance from that Node to the leaf Nodes.


> Do you have an example for where the problem lies? (a little stack trace maybe)
> 

The code to traverse the Spliterator of a conc-Node was recursive for both tryAdvance and forEach. For trees of large depth this can result in a stack overflow, especially on smaller memory configurations.

Consider a right-balanced tree such as that of a spliterator from an iterator. 

For large input, say 10^6 elements, this can result in a tree depth of at least 1024 (it's gonna be marginally higher soon when we change the way that spliterator works) and the stack depth will be proportional to that, for tryAdvance it was 4x e.g.:

"java.lang.StackOverflowError
	at java.util.stream.Nodes$InternalNodeSpliterator.internalTryAdvance(Nodes.java:559)
	at java.util.stream.Nodes$InternalNodeSpliterator$OfDouble.tryAdvance(Nodes.java:732)
	at java.util.stream.Nodes$InternalNodeSpliterator$OfDouble.tryAdvance(Nodes.java:737)
	at java.util.stream.Nodes$InternalNodeSpliterator$OfDouble.tryAdvance(Nodes.java:723)
	at java.util.stream.Nodes$InternalNodeSpliterator.internalTryAdvance(Nodes.java:566)
	at java.util.stream.Nodes$InternalNodeSpliterator$OfDouble.tryAdvance(Nodes.java:732)
	at java.util.stream.Nodes$InternalNodeSpliterator$OfDouble.tryAdvance(Nodes.java:737)
	at java.util.stream.Nodes$InternalNodeSpliterator$OfDouble.tryAdvance(Nodes.java:723)
	at java.util.stream.Nodes$InternalNodeSpliterator.internalTryAdvance(Nodes.java:562)

It is possible to reduce that 4x factor but that is not solving the underlying problem. Also tryAdvance was rather inefficient creating n wrapping Spliterators. So overall i think it a reasonable tradeoff.

The general aim is that a conc-Node represents the shape of the computation producing output elements i.e. it is already split for you for the next computation. The expectation is that splitting should occur all the way down to, or very close to, the leaf nodes. Note that operations like filter or flatMap (replace an element with zero or more elements) can distort the shape of the tree so it will not always be the case and it may be possible to create edge cases especially with right-balanced trees where things could blowup [*].

So this is really fixing for edge cases where those expectations do not hold, while still being efficient for the expected fast path of using forEach traversal close to or at the leaf nodes.

Hth,
Paul.

[*] Infact i should also update the count implementation to pre-compute the size when creating conc-Nodes, it any needs to be used so pre-calculating is more efficient.

> 
> On Mon, Feb 18, 2013 at 9:10 AM, <paul.sandoz at oracle.com> wrote:
> Changeset: 66c0dd07e288
> Author:    psandoz
> Date:      2013-02-18 15:09 +0100
> URL:       http://hg.openjdk.java.net/lambda/lambda/jdk/rev/66c0dd07e288
> 
> Modify the conc-Node spliterator forEach and tryAdvance from using the call
> stack to using an explicit (Deque) stack and a depth first search to
> find leaf nodes. This avoids stack overflow expceptions with tryAdvance
> and forEach for right-balanced or degenerate treess. This also avoids
> the internal creation of n spliterators when using tryAdvance, where n is the
> depth of the tree.
> 
> ! src/share/classes/java/util/stream/Nodes.java
> 
> 
>