<< Back to previous view

[CLJ-1237] reduce gives a SO for pathological seqs Created: 27/Jul/13  Updated: 29/May/15

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.5
Fix Version/s: Release 1.7

Type: Defect Priority: Major
Reporter: Gary Fredericks Assignee: Unassigned
Resolution: Unresolved Votes: 4
Labels: None
Environment:

1.5.1


Attachments: Text File CLJ-1237c.patch     Text File CLJ-1237d.patch     Text File CLJ-1237e.patch     File reduce.svg    
Patch: Code and Test
Approval: Incomplete

 Description   

reduce gives a StackOverflowError on long sequences that contain many transitions between chunked and unchunked:

(->> (repeat 50000 (cons :x [:y]))
     (apply concat)
     (reduce (constantly nil)))
;; throws StackOverflowError

Such a sequence is well behaved under most other sequence operations, and its underlying structure can even be masked such that reduce succeeds:

(->> (repeat 50000 (cons :x [:y]))
     (apply concat)
     (take 10000000)
     (reduce (constantly nil)))
;; => nil

I don't think Clojure developers normally worry about mixing chunked and unchunked seqs, so the existence of such a sequence is not at all unreasonable (and indeed this happened to me at work and was very difficult to debug).

It seems obvious what causes this given the implementation of reduce – it bounces back and forth between the chunked impl and the unchunked impl, consuming more and more stack as it goes. Without proper tail call optimization, it's not obvious to me what a good fix would be.

Presumed bad solutions

Degrade to naive impl after first chunk

In the IChunkedSeq implementation, instead of calling internal-reduce when the
sequence stops being chunked, it could have an (inlined?) unoptimized implementation,
ensuring that no further stack space is taken up. This retains the behavior that a
generic seq with a chunked tail will still run in an optimized fashion, but a seq with
two chunked portions would only be optimized the first time.

Use clojure.core/trampoline

This would presumably work, but requires wrapping the normal return values from all
implementations of internal-reduce.

Proposed Solution

(attached as CLJ-1237c.patch)

Similar to using trampoline, but create a special type (Unreduced) that signals
an implementation change. The two implementation-change points in internal-reduce
(in the IChunkedSeq impl and the Object impl) are converted to return an instance
of Unreduced instead of a direct call to internal-reduce.

Then seq-reduce is converted to check for instances of Unreduced before returning,
and recurs if it finds one.

Pros

  • Only requires one additional check in most cases
  • Reduces stack usage for existing heterogeneous reductions that weren't extreme enough to crash
  • Should be compatible with 3rd-party implementations of internal-reduce, which can still use the old style (direct recursive calls to internal-reduce) or the optimized style if desired.

Cons

  • internal-reduce is slightly more complicated
  • There's an extra check at the end of seq-reduce – is that a performance worry?


 Comments   
Comment by Gary Fredericks [ 25/Aug/13 4:13 PM ]

Added patch.

Comment by Gary Fredericks [ 24/Mar/15 11:33 AM ]

My coworker just ran into this, independently.

Comment by Jason Wolfe [ 22/May/15 5:13 PM ]

In Clojure 1.7, this is now happening for more cases, such as:

(->> (repeat 10000 (java.util.ArrayList. (range 10)))
     (apply concat) 
     (reduce (constantly nil)))
Comment by Alex Miller [ 22/May/15 7:39 PM ]

Pulling into 1.7 just so we don't lose it.

Comment by Alex Miller [ 27/May/15 12:16 PM ]

Rich would prefer to degrade to naive impl for this.

Comment by Gary Fredericks [ 27/May/15 4:32 PM ]

Is this still aimed at 1.7? I'm happy to work on a patch, just wanted to know if it was relatively urgent (compared to 1.8).

Comment by Alex Miller [ 27/May/15 6:12 PM ]

Yes, would like a patch.

Comment by Gary Fredericks [ 27/May/15 10:27 PM ]

Attached CLJ-1237d.patch, which contains the naive-impl-degradation implementation, and two tests – one for my original case, and the other as reported by Jason Wolfe on the mailing list in response to more recent clojure changes.

Comment by Alex Miller [ 28/May/15 7:28 AM ]

I think we also need to do this same change in the Object case of InternalReduce (the other place where coll-reduce is called) which you can trip simply with something like:

(reduce + (concat (repeat 2 2) (range 5)))

I couldn't quickly come up with an easy large case that demonstrated this though. It needs to be some interleaving of different kinds of non-chunked sequences I think?

Comment by Gary Fredericks [ 28/May/15 9:43 AM ]

Yeah, I had thought to try to analyze the call graph to see if there are other routes to a stackoverflow, but hadn't done that yet. I hereby begin intending to do that more vigorously.

Comment by Alex Miller [ 28/May/15 10:34 AM ]

That Object case is the only other place that loops back to coll-reduce, creating the potential for arbitrary stack usage.

Comment by Gary Fredericks [ 28/May/15 10:16 PM ]

Yeah after analyzing this a bit more I think "some interleaving of different kinds of non-chunked sequences" is accurate – however, I haven't been able to figure out a way to produce such a thing. concat (when no chunking is in play) converts everything but the tail into Cons, and I don't think LazySeq is a plausible way of affecting the behavior of reduce either (since it normally just gets seq'd into whatever is underneath it).

Another thing that I might be overattributing importance to is that rerouting the Object impl like you suggest would remove even the first phase of optimization for some seqs. E.g., I think (cons 3 (vec (range 10000))) would no longer be optimized since the cons would push it right into the Object impl from whence no further optimization could follow.

Working on the patch anyhow in case neither of these points is sufficiently dissuasive. It looks like the entire impl for Object is actually equivalent to naive-seq-reduce once you remove the possibility of optimization.

Comment by Gary Fredericks [ 28/May/15 10:23 PM ]

Attached CLJ-1237e.patch, which removes optimizations from the Object case as well.

Comment by Gary Fredericks [ 28/May/15 10:36 PM ]

It also occurred to me that there might be another option for the chunked case, where instead of degrading to a naive impl you simply continue inside the same loop/recur but only using first/rest rather than chunk-first/chunk-next. The main difference would be you can convert back to optimized if further chunked portions occur (though not for other kinds of optimizable seqs, like a StringSeq). The tradeoff is that you have to check if the seq is chunked at each step, while the fully naive impl doesn't do that.

Comment by Gary Fredericks [ 29/May/15 6:52 AM ]

Attaching the call diagram I made while analyzing the code, in case it's helpful to anybody.





Generated at Fri May 29 17:48:59 CDT 2015 using JIRA 4.4#649-r158309.