<< Back to previous view

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

Status: Closed
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: Completed Votes: 4
Labels: None
Environment:

1.5.1


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

 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).

Cause: The implementation of reduce can bounce back and forth between CollReduce and InternalReduce, consuming a stack frame in every transition. Given enough transitions, the stack will overflow.

Approach: 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.

Rejected alternatives:

1) Use clojure.core/trampoline - This would presumably work, but requires wrapping the normal return values from all implementations of internal-reduce.

2) 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.

Patch: CLJ-1237f.patch

Screened by: Alex Miller



 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.

Comment by Alex Miller [ 31/May/15 1:15 PM ]

I had another thought about this based on some other variants of the reduce stuff I've played with - what if in the cases where we currently were calling back into coll-reduce, we made an explicit check for IReduceInit and in that case invoked .reduce directly (similar to what we do in transduce), otherwise degrade to naive. In that case, we'd get fast reduce on a persistent collection tail in the quite possibly real case of something like (cons 3 (vec (range 10000))).

Comment by Gary Fredericks [ 31/May/15 8:00 PM ]

Okay so in particular I should not do the simplification of the Object impl (where it's only naive), and still have it do its class equality checks, but then add in this IReduceInit check at the end once the class equality check fails.

Sounds reasonable to me at first glance.

Comment by Gary Fredericks [ 01/Jun/15 7:27 PM ]

Uploaded CLJ-1237f.patch containing the latest tactic that Alex Miller cooked up.

Comment by Alex Miller [ 05/Jun/15 9:14 AM ]

Removing incomplete for re-screening

Generated at Sat Aug 01 08:53:21 CDT 2015 using JIRA 4.4#649-r158309.