Clojure

reduce gives a SO for pathological seqs

Details

  • Type: Defect Defect
  • Status: Closed Closed
  • Priority: Major Major
  • Resolution: Completed
  • Affects Version/s: Release 1.5
  • Fix Version/s: Release 1.7
  • Component/s: None
  • Labels:
    None
  • Environment:
    1.5.1
  • 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

  1. CLJ-1237c.patch
    25/Aug/13 4:13 PM
    3 kB
    Gary Fredericks
  2. CLJ-1237d.patch
    27/May/15 10:27 PM
    3 kB
    Gary Fredericks
  3. CLJ-1237e.patch
    28/May/15 10:23 PM
    3 kB
    Gary Fredericks
  4. CLJ-1237f.patch
    01/Jun/15 7:27 PM
    3 kB
    Gary Fredericks
  5. reduce.svg
    29/May/15 6:52 AM
    17 kB
    Gary Fredericks

Activity

Hide
Alex Miller added a comment -

Removing incomplete for re-screening

Show
Alex Miller added a comment - Removing incomplete for re-screening
Hide
Gary Fredericks added a comment -

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

Show
Gary Fredericks added a comment - Uploaded CLJ-1237f.patch containing the latest tactic that Alex Miller cooked up.
Hide
Gary Fredericks added a comment -

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.

Show
Gary Fredericks added a comment - 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.
Hide
Alex Miller added a comment -

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

Show
Alex Miller added a comment - 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))).
Hide
Gary Fredericks added a comment -

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

Show
Gary Fredericks added a comment - Attaching the call diagram I made while analyzing the code, in case it's helpful to anybody.
Hide
Gary Fredericks added a comment -

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.

Show
Gary Fredericks added a comment - 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.
Hide
Gary Fredericks added a comment -

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

Show
Gary Fredericks added a comment - Attached CLJ-1237e.patch, which removes optimizations from the Object case as well.
Hide
Gary Fredericks added a comment -

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.

Show
Gary Fredericks added a comment - 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.
Hide
Alex Miller added a comment -

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

Show
Alex Miller added a comment - That Object case is the only other place that loops back to coll-reduce, creating the potential for arbitrary stack usage.
Hide
Gary Fredericks added a comment -

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.

Show
Gary Fredericks added a comment - 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.
Hide
Alex Miller added a comment -

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?

Show
Alex Miller added a comment - 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?
Hide
Gary Fredericks added a comment -

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.

Show
Gary Fredericks added a comment - 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.
Hide
Alex Miller added a comment -

Yes, would like a patch.

Show
Alex Miller added a comment - Yes, would like a patch.
Hide
Gary Fredericks added a comment -

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

Show
Gary Fredericks added a comment - 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).
Hide
Alex Miller added a comment -

Rich would prefer to degrade to naive impl for this.

Show
Alex Miller added a comment - Rich would prefer to degrade to naive impl for this.
Hide
Alex Miller added a comment -

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

Show
Alex Miller added a comment - Pulling into 1.7 just so we don't lose it.
Hide
Jason Wolfe added a comment -

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)))
Show
Jason Wolfe added a comment - 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)))
Hide
Gary Fredericks added a comment -

My coworker just ran into this, independently.

Show
Gary Fredericks added a comment - My coworker just ran into this, independently.
Hide
Gary Fredericks added a comment -

Added patch.

Show
Gary Fredericks added a comment - Added patch.

People

Vote (4)
Watch (5)

Dates

  • Created:
    Updated:
    Resolved: