search

amaembo / streamex

Enhancing Java Stream API
Apache License 2.0
2.18k stars 250 forks source link

Make StreamEx.ofTree and friends stackoverflow-safe #202

Closed amaembo closed 4 years ago

amaembo commented 4 years ago

Currently, StreamEx.ofTree for non-short-circuiting op eats the stack at the rate of two frames per tree level, so it could end up with StackOverflowError. We can fix it at the cost of reduced performance. The older version should be available as ofTreeFast.

amaembo commented 4 years ago

An alternative fix is applied which switches the algorithm once the stack depth reaches 128 levels. A benchmark:

StreamEx.ofTree(0, n -> StreamEx.constant(n + 1, n > depth ? 0 : n % (depth / 5) == 0 ? 2 : 1)).mapToInt(x -> x).sum();

Results (ops/s):

Depth 0.7.0 First patch Adaptive
5 428888 243956 415603
10 293785 152853 283709
50 78307 42723 72037
100 41142 22393 39140
500 7835 4789 3622
1000 3772 2350 1821

It's much better for not-so-deep trees (depth <128), but even worse for deep trees. However, I still believe it's a good solution.