<< Back to previous view

[CLJ-1443] reduce docstring partly incorrect with reducers. Created: 10/Jun/14  Updated: 10/Jun/14

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

Type: Defect Priority: Minor
Reporter: Greg Chapman Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: docstring, reducers


The docstring for reduce includes this: "If val is not supplied, returns the result of applying f to the first 2 items in coll". This is true if coll is a sequence, but not if it is a reducer. For example:

user=> (->> (range 0 10 2) (reduce (fn[x y] (+ x y))))
user=> (->> (range 0 10 2) (r/map #(/ % 2)) (reduce (fn[x y] (+ x y))))
ArityException Wrong number of args (0)

The docstring should be updated to make it clear that reducers (used without an initial seed value) require the reducing function to support a 0 arity overload returning the identity value for the reduction operation.

[CLJ-1250] Reducer (and folder) instances hold onto the head of seqs Created: 03/Sep/13  Updated: 29/Aug/14

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

Type: Defect Priority: Critical
Reporter: Christophe Grand Assignee: Unassigned
Resolution: Unresolved Votes: 9
Labels: memory, reducers

Attachments: Text File after-change.txt     Text File before-change.txt     Text File CLJ-1250-08-29.patch     Text File CLJ-1250-20131211.patch     Text File CLJ-1250-AllInvokeSites-20140204.patch     Text File CLJ-1250-AllInvokeSites-20140320.patch    
Patch: Code and Test
Approval: Vetted


Problem Statement
A shared function #'clojure.core.reducers/reducer holds on to the head of a reducible collection, causing it to blow up when the collection is a lazy sequence.

Cause: #'reducer closes over a collection when in order to reify CollReduce, and the closed-over is never cleared. When code attempts to reduce over this anonymous transformed collection, it will realize the tail while the head is stored in the closed-over.

Reproduction steps:
Compare the following calls:

(time (reduce + 0 (map identity (range 1e8))))
(time (reduce + 0 (r/map identity (range 1e8))))

The second call should fail on a normal or small heap.

(If reducers are faster than seqs, increase the range.)

Current Patch

Chosen Approach
Approach #2, clearing the 'this' reference at all tail calls.


1) Reimplement the #'reducer (and #'folder) transformation fns similar to the manner that Christophe proposes here:

(defrecord Reducer [coll xf])

      (coll-reduce [r f1]
                   (clojure.core.protocols/coll-reduce r f1 (f1)))
      (coll-reduce [r f1 init]
                   (clojure.core.protocols/coll-reduce (:coll r) ((:xf r) f1) init)))

(def rreducer ->Reducer) 

(defn rmap [f coll]
  (rreducer coll (fn [g] 
                   (fn [acc x]
                     (g acc (f x))))))

Advantages: Relatively non-invasive change.
Disadvantages: Not evident code. Additional protocol dispatch, though only incurred once

2) Clear the reference to 'this' on the stack just before a tail call occurs

When a callee is in return position, clear the local variable reference to 'this' in the caller's stack frame, which will make the caller and all its closed-overs eligible for reclamation.

Patch 1211 takes this approach for InvokeExpr call sites in return position. Patch 1214 takes the same approach for InvokeExprs and also static and instance interop calls.

Here is the code that performs the clearing excerpted from the 1214 patch:

void emitClearThis(GeneratorAdapter gen) {
		gen.visitVarInsn(Opcodes.ASTORE, 0);

Tail calls wrapped inside a try/catch/finally clause cannot have 'this' cleared, because closed-overs/locals may need to be emitted for exception handling blocks. Both patches consider and handle this edge case.

Advantages: Fixes this case with no user code changes. Enables GC to do reclaim closed-overs references earlier.
Disadvantages: A compiler change.

3) Alternate approach

from Christophe Grand:
Another way would be to enhance the local clearing mechanism to also clear "this" but it's complex since it may be needed to keep a reference to "this" for caches long after obvious references to "this" are needed.

Advantages: Fine-grained
Disadvantages: Complex, invasive, and the compiler is hard to hack on.

Avoid reducing on lazy-seqs and instead operate on vectors / maps, or custom reifiers of CollReduce or CollFold. This could be easier with some implementations of common collection functions being available (like iterate and partition).

See https://groups.google.com/d/msg/clojure-dev/t6NhGnYNH1A/2lXghJS5HywJ for previous discussion.

Comment by Gary Fredericks [ 03/Sep/13 8:53 AM ]

Fixed indentation in description.

Comment by Ghadi Shayban [ 11/Dec/13 11:08 PM ]

Adding a patch that clears "this" before tail calls. Verified that Christophe's repro case is fixed.

Will upload a diff of the bytecode soon.

Any reason this juicy bug was taken off 1.6?

Comment by Ghadi Shayban [ 11/Dec/13 11:17 PM ]

Here's the bytecode for the clojure.core.reducers/reducer reify before and after the change... Of course a straight diff isn't useful because all the line numbers changed. Kudos to Gary Trakhman for the no.disassemble lein plugin.

Comment by Christophe Grand [ 12/Dec/13 6:58 AM ]

Ghadi, I'm a bit surprised by this part of the patch: was the local clearing always a no-op here?

-		if(context == C.RETURN)
+		if(shouldClear)
-			ObjMethod method = (ObjMethod) METHOD.deref();
-			method.emitClearLocals(gen);
+                            gen.visitInsn(Opcodes.ACONST_NULL);
+                            gen.visitVarInsn(Opcodes.ASTORE, 0);

The problem with this approach (clear this on tail call) is that it adds yet another special case. To me the complexity stem from having to keep this around even if the user code doesn't refer to it.

Comment by Ghadi Shayban [ 12/Dec/13 7:19 AM ]

Thank you - I failed to mention this in the commit message: it appears that emitClearLocals() belonging to both ObjMethod and FnMethod (its child) are empty no-ops. I believe the actual local clearing is on line 4855.

I agree re: another special case in the compiler.

Comment by Alex Miller [ 12/Dec/13 8:56 AM ]

Ghadi re 1.6 - this ticket was never in the 1.6 list, it has not yet been vetted by Rich but is ready to do so when we open up again after 1.6.

Comment by Ghadi Shayban [ 12/Dec/13 8:59 AM ]

Sorry I confused the critical list with the Rel1.6 list.

Comment by Ghadi Shayban [ 14/Dec/13 11:16 AM ]

New patch 20131214 that handles all tail invoke sites (InvokeExpr + StaticMethodExpr + InstanceMethodExpr). 'StaticInvokeExpr' seems like an old remnant that had no active code path, so that was left as-is.

The approach taken is still the same as the original small patch that addressed only InvokeExpr, except that it is now using a couple small helpers. The commit message has more details.

Also a 'try' block with no catch or finally clause now becomes a BodyExpr. Arguably a user error, historically accepted, and still accepted, but now they are a regular BodyExpr, instead of being wrapped by a the no-op try/catch mechanism. This second commit can be optionally discarded.

With this patch on my machine (4/8 core/thread Ivy Bridge) running on bare clojure.main:
Christophe's test cases both run i 3060ms on a artificially constrained 100M max heap, indicating a dominant GC overhead. (But they now both work!)

When max heap is at a comfortable 2G the reducers version outpaces the lazyseq at 2100ms vs 2600ms!

Comment by Ghadi Shayban [ 13/Jan/14 10:48 AM ]

Updating stale patch after latest changes to master. Latest is CLJ-1250-AllInvokeSites-20140113

Comment by Ghadi Shayban [ 04/Feb/14 3:50 PM ]

Updating patch after murmur changes

Comment by Tassilo Horn [ 13/Feb/14 4:52 AM ]

Ghadi, I suffer from the problem of this issue. Therefore, I've applied your patch CLJ-1250-AllInvokeSites-20140204.patch to the current git master. However, then I get lots of "java.lang.NoSuchFieldError: array" errors when the clojure tests are run:

     [java] clojure.test-clojure.clojure-set
     [java] java.lang.NoSuchFieldError: array
     [java] 	at clojure.core.protocols$fn__6026.invoke(protocols.clj:123)
     [java] 	at clojure.core.protocols$fn__5994$G__5989__6003.invoke(protocols.clj:19)
     [java] 	at clojure.core.protocols$fn__6023.invoke(protocols.clj:147)
     [java] 	at clojure.core.protocols$fn__5994$G__5989__6003.invoke(protocols.clj:19)
     [java] 	at clojure.core.protocols$seq_reduce.invoke(protocols.clj:31)
     [java] 	at clojure.core.protocols$fn__6017.invoke(protocols.clj:48)
     [java] 	at clojure.core.protocols$fn__5968$G__5963__5981.invoke(protocols.clj:13)
     [java] 	at clojure.core$reduce.invoke(core.clj:6213)
     [java] 	at clojure.set$difference.doInvoke(set.clj:61)
     [java] 	at clojure.lang.RestFn.invoke(RestFn.java:442)
     [java] 	at clojure.test_clojure.clojure_set$fn__1050$fn__1083.invoke(clojure_set.clj:109)
     [java] 	at clojure.test_clojure.clojure_set$fn__1050.invoke(clojure_set.clj:109)
     [java] 	at clojure.test$test_var$fn__7123.invoke(test.clj:704)
     [java] 	at clojure.test$test_var.invoke(test.clj:704)
     [java] 	at clojure.test$test_vars$fn__7145$fn__7150.invoke(test.clj:721)
     [java] 	at clojure.test$default_fixture.invoke(test.clj:674)
     [java] 	at clojure.test$test_vars$fn__7145.invoke(test.clj:721)
     [java] 	at clojure.test$default_fixture.invoke(test.clj:674)
     [java] 	at clojure.test$test_vars.invoke(test.clj:718)
     [java] 	at clojure.test$test_all_vars.invoke(test.clj:727)
     [java] 	at clojure.test$test_ns.invoke(test.clj:746)
     [java] 	at clojure.core$map$fn__2665.invoke(core.clj:2515)
     [java] 	at clojure.lang.LazySeq.sval(LazySeq.java:40)
     [java] 	at clojure.lang.LazySeq.seq(LazySeq.java:49)
     [java] 	at clojure.lang.Cons.next(Cons.java:39)
     [java] 	at clojure.lang.RT.boundedLength(RT.java:1655)
     [java] 	at clojure.lang.RestFn.applyTo(RestFn.java:130)
     [java] 	at clojure.core$apply.invoke(core.clj:619)
     [java] 	at clojure.test$run_tests.doInvoke(test.clj:761)
     [java] 	at clojure.lang.RestFn.applyTo(RestFn.java:137)
     [java] 	at clojure.core$apply.invoke(core.clj:617)
     [java] 	at clojure.test.generative.runner$run_all_tests$fn__527.invoke(runner.clj:255)
     [java] 	at clojure.test.generative.runner$run_all_tests$run_with_counts__519$fn__523.invoke(runner.clj:251)
     [java] 	at clojure.test.generative.runner$run_all_tests$run_with_counts__519.invoke(runner.clj:251)
     [java] 	at clojure.test.generative.runner$run_all_tests.invoke(runner.clj:253)
     [java] 	at clojure.test.generative.runner$test_dirs.doInvoke(runner.clj:304)
     [java] 	at clojure.lang.RestFn.applyTo(RestFn.java:137)
     [java] 	at clojure.core$apply.invoke(core.clj:617)
     [java] 	at clojure.test.generative.runner$_main.doInvoke(runner.clj:312)
     [java] 	at clojure.lang.RestFn.invoke(RestFn.java:408)
     [java] 	at user$eval564.invoke(run_tests.clj:3)
     [java] 	at clojure.lang.Compiler.eval(Compiler.java:6657)
     [java] 	at clojure.lang.Compiler.load(Compiler.java:7084)
     [java] 	at clojure.lang.Compiler.loadFile(Compiler.java:7040)
     [java] 	at clojure.main$load_script.invoke(main.clj:274)
     [java] 	at clojure.main$script_opt.invoke(main.clj:336)
     [java] 	at clojure.main$main.doInvoke(main.clj:420)
     [java] 	at clojure.lang.RestFn.invoke(RestFn.java:408)
     [java] 	at clojure.lang.Var.invoke(Var.java:379)
     [java] 	at clojure.lang.AFn.applyToHelper(AFn.java:154)
     [java] 	at clojure.lang.Var.applyTo(Var.java:700)
     [java] 	at clojure.main.main(main.java:37)
Comment by Ghadi Shayban [ 13/Feb/14 8:23 AM ]

Can you give some details about your JVM/environment that can help reproduce? I'm not encountering this error.

Comment by Tassilo Horn [ 13/Feb/14 9:41 AM ]

Sure. It's a 64bit ThinkPad running GNU/Linux.

% java -version
java version "1.7.0_51"
OpenJDK Runtime Environment (IcedTea 2.4.5) (ArchLinux build 7.u51_2.4.5-1-x86_64)
OpenJDK 64-Bit Server VM (build 24.51-b03, mixed mode)
Comment by Ghadi Shayban [ 13/Feb/14 10:19 AM ]

Strange, that is exactly my mail env, OpenJDK7 on Arch, 64-bit. I have also tested on JDK 6/7/8 on OSX mavericks. Are you certain that the git tree is clean besides the patch? (Arch users unite!)

Comment by Tassilo Horn [ 14/Feb/14 1:13 AM ]

Yes, the tree is clean. But now I see that I get the same error also after resetting to origin/master, so it's not caused by your patch at all. Oh, now the error vanished after doing a `mvn clean`! So problem solved.

Comment by Nicola Mometto [ 19/Feb/14 12:32 PM ]

Ghandi, FnExpr.parse should bind IN_TRY_BLOCK to false before analyzing the fn body, consider the case

(try (do something (fn a [] (heap-consuming-op a))) (catch Exception e ..))

Here in the a function the this local will never be cleared even though it's perfectly safe to.
Admittedly this is an edge case but we should cover this possibility too.

Comment by Ghadi Shayban [ 19/Feb/14 2:06 PM ]

You may have auto-corrected my name to Ghandi instead of Ghadi. I wish I were that wise =)

I will update the patch for FnExpr (that seems reasonable), but maybe after 1.6 winds down and the next batch of tickets get scrutiny. It would be nice to get input on a preferred approach from Rich or core after it gets vetted – or quite possibly not vetted.

Comment by Nicola Mometto [ 19/Feb/14 6:11 PM ]

hah, sorry for the typo on the name

Seems reasonable to me, in the meantime I just pushed to tools.analyzer/tools.emitter complete support for "this" clearing, I'll test this a bit in the next few days to make sure it doesn't cause unexpected problems.

Comment by Andy Fingerhut [ 24/Feb/14 12:13 PM ]

Patch CLJ-1250-AllInvokeSites-20140204.patch no longer applies cleanly to latest master as of Feb 23, 2014. It did on Feb 14, 2014. Most likely some of its context lines are changed by the commit to Clojure master on Feb 23, 2014 – I haven't checked in detail.

Comment by Ghadi Shayban [ 20/Mar/14 4:39 PM ]

Added a patch that 1) applies cleanly, 2) binds the IN_TRY_EXPR to false initially when analyzing FnExpr and 3) uses RT.booleanCast

Comment by Alex Miller [ 22/Aug/14 9:31 AM ]

Can you squash the patch and add tests to cover all this stuff?

Comment by Ghadi Shayban [ 22/Aug/14 9:47 AM ]

Sure. Have any ideas for how to test proper behavior of reference clearing? Know of some prior art in the test suite?

Comment by Alex Miller [ 22/Aug/14 10:25 AM ]

Something like the test in the summary would be a place to start. I don't know of any test that actually inspects bytecode or anything but that's probably not wise anyways. Need to make that kind of a test but get coverage on the different kinds of scenarios you're covering - try/catch, etc.

Comment by Ghadi Shayban [ 22/Aug/14 12:13 PM ]

Attached new squashed patch with a couple of tests.

Removed (innocuous but out-of-scope) second commit that analyzed try blocks missing a catch or finally clause as BodyExprs

Comment by Ghadi Shayban [ 29/Aug/14 11:43 AM ]

Rebased to latest master. Current patch CLJ-1250-08-29

Comment by Jozef Wagner [ 29/Aug/14 2:40 PM ]

CLJ-1250-08-29.patch is fishy, 87k size and it includes many unrelated commits

Comment by Alex Miller [ 29/Aug/14 2:44 PM ]

Agreed, Ghadi that last rebase looks wrong.

Comment by Ghadi Shayban [ 29/Aug/14 3:06 PM ]

Oops. Used format-patch against the wrong base. Updated.

Apologies that ticket is longer than War & Peace

[CLJ-1221] Should repackage jsr166 and include known version with Clojure Created: 20/Jun/13  Updated: 03/Sep/13

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

Type: Enhancement Priority: Major
Reporter: Alex Miller Assignee: Alex Miller
Resolution: Unresolved Votes: 0
Labels: reducers


Clojure 1.5 reducers work with either the JDK version of forkjoin (JDK 1.7+) or with an external jsr166 jar. This causes complexity for users and complexity in the build to deal with the two options.

jsr166 code is public domain and it is common for other projects to repackage the handful of files and ship it with the project (similar to what we do with asm). This would allow us just use a known existing version of jsr166 across all jdks and we could get rid of the custom build wrangling we introduced in Clojure 1.5.

jsr166y is compatible with JDK 1.6+ and is the version that (for example) Scala currently repackages. That's the best choice for JDK 1.6 and 1.7. In JDK 1.8, the best choice will (temporarily) be the built-in version in java.util.concurrent which tracks jsr166e but then as soon as there are updates will become jsr166e. Many fork/join fixes are ported to both y and e right now.

Some choices here for JDK 1.8:

  • go for maximal compatibility just use repackaged jsr166y regardless of JDK (simplest)
  • check for jdk version # and use java.util.concurrent instead
  • check for jdk version # and repackage jsr166e and use it instead

Not sure yet which of these is best choice right now.

[CLJ-1197] Allow fold to parallelize over lazy sequences Created: 10/Apr/13  Updated: 27/Sep/13  Resolved: 27/Sep/13

Status: Resolved
Project: Clojure
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Major
Reporter: Paul Butcher Assignee: Unassigned
Resolution: Declined Votes: 0
Labels: reducers

Attachments: File foldable-seq.diff    
Patch: Code


This patch implements foldable-seq, which allows fold to parallelize over a lazy sequence. See this conversation on the Clojure mailing list:


The patch is code only, sadly. No tests because I've not been able to find any existing tests for fold:


However, I have tested it in a separate project successfully.

Comment by Stuart Halloway [ 27/Sep/13 3:12 PM ]

Hi Paul,

Seqs are fundamentally not foldable. That said, what you seem to be trying to do (partition a seq into foldable subjobs) is straightforward in Clojure, see


That said, if the input is truly arriving sequentially, pmap or some variant may do as well or better, e.g.


[CLJ-1113] `reductions` reducer Created: 23/Nov/12  Updated: 03/Sep/13

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

Type: Enhancement Priority: Minor
Reporter: Marshall T. Vandegrift Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: reducers

Attachments: File reductions-reducer.diff    
Patch: Code and Test


It would be nice to have a reducers implementation of the core `reductions` function.

Initial implementation attempt included. This version requires an initial reduction value parameter (vs using (f)) and includes that initial value in the final reduction. I'm not certain either of these decisions is optimal, but results in a function which most closely mimics `clojure.core/reductions`.

[CLJ-1058] StackOverflowError on exception in reducef for PersistentHashMap fold Created: 02/Sep/12  Updated: 07/Feb/14  Resolved: 07/Feb/14

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.5
Fix Version/s: Release 1.6

Type: Defect Priority: Major
Reporter: Tom Jack Assignee: Bruce Adams
Resolution: Completed Votes: 1
Labels: reducers

Clojure 1.5.0-alpha4, Sun Java 1.6.0_35, with [org.codehaus.jsr166-mirror/jsr166y "1.7.0"]

Attachments: File sneakyThrow-clj-1058.diff    
Patch: Code and Test
Approval: Ok


If reducef throws an exception, the exception is swallowed sometimes (that is: not propagated up to the caller of r/fold). This can lead to infinite recursion, causing a stack overflow which masks the problem.

user> (require '[clojure.core.reducers :as r])
user> (r/fold (fn ([]) ([ret k v] (+ 3 "foo") ret)) (into {} (map (juxt identity identity) (range 10000))))
StackOverflowError   clojure.lang.Numbers.add (Numbers.java:126)

This results in a stack like: https://raw.github.com/gist/3bab917287a7fd635a84/f38bfe3e270556e467f3fc02062af7ea10781390/gistfile1.txt

Cause: The problem area in the code catches Exception and swallows it - this is commented "aargh" in PersistentHashMap.java line 444 (as of 412a51d).

Approach: Throw the Exception and allow it to propagate instead of swallowing it.

Patch: sneakyThrow-clj-1058.diff

Screened by: Alex Miller

Comment by Timothy Baldridge [ 30/Nov/12 3:40 PM ]

Verified as a bug.

Comment by Dave Sann [ 30/Jul/13 3:41 AM ]

Some comments here:


in short

can be replaced by

throw new RuntimeException(e);

or maybe: Util.sneakyThrow(e);

which will surface the exception rather than swallow it.

I have questions about clean-up - in the thread - I am not very familiar with the fork join framework.

Comment by Bruce Adams [ 17/Sep/13 7:12 AM ]

Don't ignore exceptions thrown by tasks

Comment by Bruce Adams [ 18/Sep/13 11:24 AM ]

This change removes the problematic
try ... catch
and enhances "foldTasks" and "fold" method declarations by adding "throws Exception".

Comment by Andy Fingerhut [ 26/Sep/13 9:28 PM ]

Bruce, others can comment better than I can on this comment, but a large number of places in the Clojure implementation avoid the need for declaring checked exceptions by using Util.sneakyThrow. Search for that in the Java code for examples, and how it is implemented if you are curious. It might be that this is another place this should be done.

Comment by Bruce Adams [ 28/Sep/13 8:38 PM ]

I don't yet know the Clojure code base very well. Doing a quick count, there are slightly more methods with a declared "throws" clause then there are "sneakyThrows" calls. I am assuming (based on other Java experience) that sneakyThrows is only used when declaring a throws clause is problematic. In my proposed fix, throws declarations are needed only on four methods, all in the same module. The actual exceptions appear to be dealt with cleanly.

What I haven't yet figured out is how to write relevant tests for this. The clearly broken thing about the existing code is falling out of the if count==1 block into code that assumes count>1. Even just returning a null at least avoids the infinite recursion problem (and also swallows the exception, which seems wrong). So a test for once-and-only-once seems relevant. Also, a test for exception behavior seems called for.

(Also, I don't know protocol for assigning bugs. I'm tempted to hit the "Assign To Me" button in JIRA, but I'm not sure what it means in the larger scheme of things.)

Comment by Alex Miller [ 11/Oct/13 4:21 PM ]

"Assign to Me" means that you are currently working on something for that ticket and others should probably check with you before investing time. From my perspective, anyone is welcome to assign to themselves with the caveat that someone else may still create a patch and/or interpret non-progress as an invitation to work on it.

Is this ticket in a state where it should be screened or do you feel it is incomplete? I am trying to judge whether I should invest time in screening it.

Comment by Bruce Adams [ 11/Oct/13 4:42 PM ]

I believe that declare-throws-clj-1058.diff correctly deals with the problem. It certainly behaves better than code it replaces. I can imagine you screening, and then Rich accepting, it as is.

However, I think we will all be happier with tests demonstrating behavior. I've been struggling with writing tests, especially tests that cleanly fail on the old code, instead of hard crashing the test suite with a stack overflow.

Comment by Bruce Adams [ 17/Oct/13 1:21 PM ]

The code fix in "patch-with-tests-clj-1058.diff" is identical to my earlier "declare-throws-clj-1058.diff" This new patch includes an additional commit adding a unit test.

This is ready for screening.

Comment by Alex Miller [ 17/Dec/13 11:05 PM ]

I don't think we want to throw Exception out of (at least) fold() and possibly the others as well. Can you rework with sneakyThrow?

Comment by Bruce Adams [ 18/Dec/13 9:21 PM ]

I can use sneakyThrow. The patch I uploaded in September 17 did exactly that. I have since deleted that patch.

I've now had two people I respect, you and Andy Fingerhut, suggest a need for using sneakyThrow in this code. Each of you know the Clojure code far better than I do. I'm very inclined to trust your intuition that sneakyThrow is the right thing here, but I would really like to understand why. In my testing, checked exceptions (non-RuntimeExceptions) out of this code already get wrapped in a RuntimeException. I assume this wrapping happens higher up the Java stack and is implemented via sneakyThrow. Why do we want to add yet another layer of exception wrapping? It adds complexity to this Java code.

I am happy to add tests demonstrating the existing checked exception wrapping behavior.

Can you help me understand why we want sneakyThrow here? I would really appreciate it.

Comment by Alex Miller [ 18/Dec/13 10:01 PM ]

Most of the internal Clojure code eschews checked exceptions (they are an artifact of Java, not a JVM thing) and I think it's unlikely that Rich would accept a patch that explicitly declared it in this case. My expectation is that wrapping the exception at the beginning via sneakyThrow will prevent it from being wrapped again farther up, so I don't know that this change will nest things any more deeply.

Comment by Bruce Adams [ 11/Jan/14 10:57 AM ]

My earlier patch had an extra, unneeded "throws Exception" declaration on a publicly visible "fold" method. This new patch, declarative-clj-1058.diff, only adds "throws Exception" to methods used within src/jvm/clojure/lang/PersistentHashMap.java.

To make this locality clear, I've attached another patch, private-interface-INode.diff, which declares the internal INode interface as "private". I don't think the "private" declaration needs to go into the Clojure code.

These patches do not taking your advice to use sneakyThrow here. Using sneakyThrow still feels wrong to me. I will (attempt to) start a conversation on the Clojure-dev mailing asking people for thoughts about the two approaches.

Comment by Bruce Adams [ 13/Jan/14 5:16 AM ]

I forgot to thank Alex for expressing concerns with my earlier patchset. That got me to think harder about what exactly is happening here and to learn more about the Java code implementing Clojure. I enjoy thinking and learning.

Thank you, Alex!

Comment by Bruce Adams [ 14/Jan/14 5:49 PM ]

Thanks to Kevin Downey on the Clojure-dev mailing list, I now understand sneakyThrow better.

This patch uses sneakyThrow to surface exceptions.

Comment by Alex Miller [ 14/Jan/14 10:08 PM ]

Switching to Vetted so this is available to be screened.

Comment by Alex Miller [ 16/Jan/14 4:16 PM ]

Bruce, what's with the k-fail and def stuff in the tests?

Comment by Alex Miller [ 17/Jan/14 10:16 AM ]

Moving back to Incomplete - I think the tests should be simplified - I don't see why all the internal def stuff is necessary to demonstrate this.

Comment by Bruce Adams [ 17/Jan/14 11:09 AM ]

Yes, I agree. I'll update the patch with simpler tests. It'll take a few days.

Comment by Bruce Adams [ 05/Feb/14 8:10 PM ]

Same fix as before, using sneakyThrow, but with a single, much simpler test.

[CLJ-1047] Simplify the process of requiring fj in clojure.core.reducers Created: 21/Aug/12  Updated: 03/Sep/13

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

Type: Enhancement Priority: Minor
Reporter: Nicola Mometto Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: reducers

Attachments: Text File 001-simplify-fj-importing.patch    
Patch: Code


this patch removes compile-if in favor of import-if, removing code duplication

[CLJ-1046] Drop-while as a reducer Created: 18/Aug/12  Updated: 03/Sep/13

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

Type: Enhancement Priority: Major
Reporter: Alan Malloy Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: reducers

Attachments: Text File drop-while-reducer.patch    
Patch: Code and Test


Implement drop-while as a reducer. Follows the same atom-based strategy as drop and take.

Does not depend on any of my other reducer patches, but there will probably be some minor merge conflicts unless it is merged after CLJ-1045, and before CLJ-992 and CLJ-993.

[CLJ-1045] Generalize/refactor implementation of PersistentVector/coll-fold Created: 18/Aug/12  Updated: 03/Sep/13

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

Type: Enhancement Priority: Major
Reporter: Alan Malloy Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: reducers

Attachments: Text File clj-1045-fold-by-halves-patch-v2.txt     Text File fold-by-halves.patch    
Patch: Code


Vector currently contains a specialized implementation of the folding algorithm "split the collection in half until the pieces are small enough". The attached commit lifts out the general strategy so that it can be reused by other collection types amenable to splitting.

CLJ-993 depends on this patch, as it uses the new fold-by-halves function.

Comment by Andy Fingerhut [ 25/Jan/13 2:29 PM ]

clj-1045-fold-by-halves-patch-v2.txt dated Jan 25 2013 is identical to fold-by-halves.patch dated Aug 18 2012, except it updates one line of context changed by a recent commit to Clojure master.

[CLJ-994] repeat reducer Created: 11/May/12  Updated: 03/Sep/13

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

Type: Enhancement Priority: Major
Reporter: Jason Jackson Assignee: Unassigned
Resolution: Unresolved Votes: 1
Labels: reducers

Attachments: Text File 0001-repeat-for-clojure.core.reducers.patch    
Patch: Code and Test


i'm working on clojure.core/repeat reducer.

Comment by Andy Fingerhut [ 17/May/12 6:18 PM ]

Jason, have you tried to build this using JDK 1.6.0? I've tried on Mac OS X 10.6.8 + Oracle/Apple JDK 1.6.0 and Ubuntu 11.10 + IBM JDK 1.6.0, and on both it compiles, but during the tests fails with a ClassNotFoundException for class jsr166y.ForkJoinTask.

It builds and tests cleanly on Ubuntu 11.10 + Oracle JDK 1.7.0 for me.

Comment by Jason Jackson [ 17/May/12 6:41 PM ]

That's an issue that applies to all of core.reducers. Alan Malloy experienced it as well. I tried fixing it, but eventually just upgraded to JDK 1.7. I don't understand why it's happening.

Comment by Jason Jackson [ 19/May/12 2:55 PM ]

This issue is isolated to mvn test afaik.

When I include clojure inside a leiningen project, and add jsr166y.jar to lib directory, core.reducers works fine with java 1.6.

Comment by Andy Fingerhut [ 20/May/12 3:00 AM ]

Jason, you say it applies to all of core.reducers in your May 17, 2012 comment. I don't understand. Without your patch applied, I can run "./antsetup.sh ; ant" in a freshly-pulled Clojure git repo on either of the JDK 1.6.0 versions mentioned in my earlier comment, and do not get any errors during the tests. Are you saying perhaps that core.reducers currently has no tests that exercise the problem now, but your patch adds such tests that fail, even with no other changes to the code?

Comment by Jason Jackson [ 20/May/12 11:55 AM ]

Yah that's right. Now that you mention it, my patch is the first unit test to call r/fold (the existing tests do non-parallel reductions).

Comment by Andy Fingerhut [ 08/Jun/12 7:11 PM ]

With Stuart Halloway's commit to Clojure master on June 8, 2012 titled "let reducers tests work under ant", patch 0001-repeat-for-clojure.core.reducers.patch dated May 11, 2012 now runs correctly even the new unit tests requiring class jsr166y.ForkJoinTask with Oracle/Apple JDK 1.6 and Linux IBM JDK 1.6.

Comment by Jason Jackson [ 14/Aug/12 1:17 AM ]

I'm on the contributors list. Is this patch still needed?
sorry for long long delay.

Comment by Jason Jackson [ 14/Sep/12 2:37 PM ]

This patch should wait until http://dev.clojure.org/jira/browse/CLJ-993 is committed. I think there's a some shared code.

[CLJ-993] `range` reducer Created: 10/May/12  Updated: 03/Sep/13

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

Type: Enhancement Priority: Major
Reporter: Alan Malloy Assignee: Unassigned
Resolution: Unresolved Votes: 1
Labels: reducers

Attachments: Text File 0001-CLJ-993-implement-range-and-iterate-as-reducers.patch     Text File 0001-CLJ-993-implement-range-and-iterate-as-reducers.patch     Text File 0001-CLJ-993-implement-range-as-a-reducer.patch     Text File 0002-Make-iterate-and-range-Seqable.patch     Text File 0003-Implement-fold-for-Range-objects.patch     Text File just-iseq.patch     Text File range-reducer.patch    
Patch: Code and Test


Rich mentioned in IRC today he'd welcome a reducer implementation of clojure.core/range. Now that I've figured out how to do iterate, I figure I'll knock out range as well by the end of the night. Just opening the issue early to announce my intentions to anyone else interested in doing it.

Comment by Alan Malloy [ 10/May/12 10:45 PM ]

Implemented range. A separate commit is attached, making iterate and range also Seqable, since I'm not sure if that's desired. Apply it or not, as you prefer.

Comment by Jason Jackson [ 11/May/12 11:20 AM ]

Range should be foldable

Comment by Alan Malloy [ 11/May/12 12:53 PM ]

Yep, so it should. Time for me to dig into the folding implementations!

Comment by Alan Malloy [ 11/May/12 2:42 PM ]

Should I fold (har har) all of these commits into one? I don't know what is preferred on JIRA, and I also don't know whether range/iterate should be seqable or if I should just drop the second commit.

Comment by Rich Hickey [ 11/May/12 3:21 PM ]

Yes, please merge these together, it's hard to see otherwise (I can barely read diffs as is . range and iterate shouldn't be novel in reducers, but just enhanced return values of core fns. The enhancement (e.g. protocol extensions) can come by requiring reducers since it can't be leveraged without it. Also, I'm not sure how I feel about an allocating protocol for 'splittable' - I've avoided it thus far.

Comment by Alan Malloy [ 11/May/12 3:30 PM ]

So you want clojure.core/range to return some object (a Range), which implements Counted and Seqable (but isn't just a lazy-seq), and then inside of clojure.core.reducers I extend CollReduce and CollFold to that type? Okay, I can do that.

I don't quite follow what you mean by an allocating protocol. I see your point that my fold-by-halves which takes a function in is analogous to a protocol with a single function, but it doesn't allocate anything more than foldvec already does - I just pulled that logic out so that the fork/join fiddly work doesn't need to be repeated in everything foldable. Do you have an alternative recommendation, or is it just something that makes you uneasy and you're still thinking about?

Comment by Rich Hickey [ 11/May/12 3:52 PM ]

While vector-fold allocs subvecs, the halving-fn must return a new vector, for all implementations. It's ok, I don't think it's likely to dominate (since fj needs new closures anyway). Please proceed, but keep range and iterate in core. They are sources, not transformers, and only transformers (which must be different from their seq-based counterparts) must reside in reducers. Thanks!

Comment by Stuart Sierra [ 11/May/12 5:01 PM ]

One big patch file is preferred, although that file may contain multiple commits if that makes the intent clearer.

When adding a patch, update the description of the ticket to indicate which file is the most recent. Leave old patch files around for historical reference.

Comment by Alan Malloy [ 11/May/12 9:00 PM ]

It's looking harder than I expected to move iterate and range into core.clj. My plan was to just have them implement Seqable, which is easy enough, but currently they are actually instances of ISeq, because they inherit from LazySeq. A bunch of code all over the place (eg, to print them in the repl) depends on them being ISeq, so I can't just ignore it. To implement all of these methods (around thirty) would take a large amount of code, which can't easily be shared between Iteration, Range, and any future reducible sources that are added to core.clj.

I could write a macro like (defseq Range [start end step] Counted (count [this] ...) ...) which takes normal deftype args and also adds in implementations for ISeq, Collection, and so forth in terms of (.seq this), which will be a LazySeq. However, this seems like a somewhat awkward approach that I would be a little embarrassed to clutter up core.clj with. If anyone has a better alternative I will be pleased to hear it. In the mean time, I will go ahead with this macro implementation, in case it turns out to be the best choice.

Comment by Alan Malloy [ 11/May/12 11:52 PM ]

– This patch subsumes all previous patches to this issue and to CLJ-992

In order to create an object which is both a lazy sequence and a
reducible source, I needed to add a macro named defseq to core_deftype.
It is basically a reimplementation of clojure.lang.LazySeq as a clojure
macro, so that I can "mix in" lazy-sequence functions into a new class
with whatever methods are needed for reducing and folding.

If we wanted, we could use this macro to implement lazy-seq in clojure instead of in java, but that's unrelated so I didn't do that in this patch.

As noted in a previous comment, defseq may not be the right approach, but this works until something better is suggested.

Comment by Alan Malloy [ 11/May/12 11:58 PM ]

I accidentally included an implementation of drop-while in this patch, which I was playing around with to make sure I understood how this all works. I guess I'll leave it in for the moment, since it works and is useful, but I can remove it, or move it to a new JIRA ticket, if it's not wanted at this time.

Comment by Rich Hickey [ 12/May/12 10:52 AM ]

Ok, I think this patch is officially off the rails. There must be a better way. Let's start with: touching core/deftype and reimplementing lazy-seq as a macro are off the table. The return value of range doesn't have to be a LazySeq, it has to be a lazy seq, .e.g. implement ISeq (7 methods, not 30) which it can do by farming out to its existing impl. It can also implement some new interface for use by the reducer logic. There is also still clojure.lang.Range still there, which is another approach. Please take an extremely conservative approach in these things.

Comment by Alan Malloy [ 12/May/12 5:53 PM ]

Okay, thanks for the feedback - I'm glad I went into that last patch knowing it was probably wrong . I thought I would need to implement the java collection interfaces that LazySeq does, eg java.util.List, in order to avoid breaking interop functions like (defn range-list [n] (ArrayList. (range n))). If it's sufficient to implement ISeq (and thus IPersistentCollection), then that's pretty manageable.

It's still an unpleasant chunk of boilerplate for each new source, though; would you welcome a macro like defseq if I didn't put it in core_deftype? If so, it seems like it might as well implement the interop interfaces; if not, I can skip them and implement the 7 (isn't it more like 9?) methods in ISeq, IPersistentCollection, and Seqable for each new source type.

Thanks for pointing out clojure.lang.Range to me - I didn't realize we had it there. Of course with implementation inheritance it would be easy to make Range, Iteration, etc inherit from LazySeq and just extend protocols from them. But that means moving functionality out of clojure and into java, which I didn't think we'd want to do.

I'll put together a patch that just implements ISeq by hand for both of these new types, and attach it probably later today.

Comment by Alan Malloy [ 12/May/12 7:49 PM ]

So I've written a patch that implements ISeq, but not the java Collections interfaces, and it mostly works but there are definitely assumptions in some parts of clojure.core and clojure.lang that assume seqs are Collections. The most obvious to me (ie, it shows up when running mvn test) is RT/toArray - it tests for Collection, but never for ISeq, implying that it's not willing to handle an ISeq that is not also a collection. Functions which rely on toArray (eg to-array and vec) now fail.

This patch subsumes all previous patches on this issue, but is not suitable for application because it leaves some failing tests behind - it is intended only for intermediate feedback.

Comment by Rich Hickey [ 13/May/12 8:50 AM ]

It would be a great help if, time permitting, you could please write up the issues, challenges and options you've discovered somewhere on the dev wiki (even a simple table would be fantastic). I realize this has been a challenging task, and at this point perhaps we should opt for the more modest reducers/range and reducers/iterate and leave the two worlds separate. I'd like at some point to unify range, as there are many extant ranges it would be nice to be able to fold, as we can extant vectors.

Comment by Jason Jackson [ 13/May/12 9:24 AM ]

Should r/range return something Seqable and Counted?

If so, I'll do the same for r/repeat.

Comment by Alan Malloy [ 13/May/12 1:59 PM ]

I've sketched out a description of the issues and options. I'm not very familiar with the dev wiki and couldn't figure out where was the right place to put this. "release.next" seems to still be about 1.4 issues, and I don't know if it's "appropriate" to create a whole new category for this. It's available as a gist until a better home can be found for it.

Comment by Alan Malloy [ 23/May/12 7:54 PM ]

Here's a single patch summing up the state Rich suggested "rolling back" to: separate r/range and r/iterate functions. I haven't heard any feedback since doing the writeup Rich asked for, so am not making any further progress at the moment; if something other than this patch is desired just let me know.

Comment by Rich Hickey [ 14/Aug/12 2:07 PM ]

I prefer not to see the use of extend like this for new types. Perhaps this code is too DRY? Also, it does a lot in one patch which makes it hard to parse and accept. This adds Range, switches impl of vector folds etc. Can it be broken up into separate tickets that do each step that builds on the previous, e.g. one ticket could be: capture vector fold impl for reuse by similar things.

Comment by Alan Malloy [ 18/Aug/12 6:19 PM ]

Okay, I should be able to split it up over the weekend. I'll also see about converting fold-by-halves into a function that is used by Range/Vector, rather than a function that gets extended onto them.

Comment by Alan Malloy [ 18/Aug/12 7:18 PM ]

As requested, I have split up the large patch on this issue into four smaller tickets. The other three are: CLJ-1045, CLJ-1046, and CLJ-992.

CLJ-1045 contains the implementation of fold-by-halves, and as such this patch cannot be applied until CLJ-1045 is accepted. This ticket does not depend on the other two, but there will be minor merge conflicts if this is merged before them.

[CLJ-992] `iterate` reducer Created: 10/May/12  Updated: 09/Apr/14

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

Type: Enhancement Priority: Major
Reporter: Alan Malloy Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: reducers

Attachments: Text File 0001-Add-reducers-iterate.patch     Text File iterate-reducer.patch    
Patch: Code and Test
Approval: Vetted


Added a reducer implementation mirroring clojure.core/iterate.

Patch: 0001-Add-reducers-iterate.patch

Screened by:

Comment by Alan Malloy [ 10/May/12 9:50 PM ]

Should I have made this implement Seqable as well? It wasn't clear to me, because as far as I could see this was the only function in clojure.core.reducers that's generating a brand-new sequence rather than transforming an existing one.

Comment by Alan Malloy [ 10/May/12 10:24 PM ]

Previous version neglected to include the seed value of the iteration in the reduce.

Comment by Jason Jackson [ 11/May/12 11:23 AM ]

Currying iterate seems useless, albeit not harmful.

While implementing repeat, I couldn't use currying. Because 1-arity is already reserved for infinite repeat ([n x] and [x], not [n x] and [n] if currying)

How about we just support currying for functions where last param is reducible?

Comment by Alan Malloy [ 18/Aug/12 7:16 PM ]

This new patch replaces the previous patch. As requested, I am splitting up the large issue CLJ-993 into smaller tickets.

Does not depend on any of my other reducer patches, but there will probably be some minor merge conflicts unless it is merged after CLJ-1045 and CLJ-1046, and before CLJ-993.

[CLJ-991] partition-by reducer Created: 10/May/12  Updated: 03/Sep/13

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

Type: Enhancement Priority: Minor
Reporter: Kevin Downey Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: reducers

Attachments: File reducer-partition-by2.diff     File reducer-partition-by3.diff     File reducer-partition-by4.diff     File reducer-partition-by.diff    
Patch: Code and Test

Comment by Rich Hickey [ 14/Aug/12 1:52 PM ]

I'd like to see something much faster than this.

Comment by Kevin Downey [ 15/Aug/12 1:58 AM ]

For reference here is a benchmark of a non-reducers (seq based) process that uses partition-by

user=> (def x (vec (range 1e6)))
user=> (bench (reduce + (map count (partition-by #(or (zero? (mod % 3)) (zero? (mod % 5))) x))))
Evaluation count             : 60
             Execution time mean : 1.072157 sec  95.0% CI: (1.070606 sec, 1.073381 sec)
    Execution time std-deviation : 165.818282 ms  95.0% CI: (163.873585 ms, 168.271261 ms)
         Execution time lower ci : 972.562000 ms  95.0% CI: (972.562000 ms, 973.301850 ms)
         Execution time upper ci : 1.419148 sec  95.0% CI: (1.419148 sec, 1.419148 sec)

Found 7 outliers in 60 samples (11.6667 %)
	low-severe	 2 (3.3333 %)
	low-mild	 5 (8.3333 %)
 Variance from outliers : 85.8489 % Variance is severely inflated by outliers

Same again using r/partition-by from reducer-partition-by.diff

user=> (bench (r/reduce + (r/map count (r/partition-by #(or (zero? (mod % 3)) (zero? (mod % 5))) x))))
Evaluation count             : 60
             Execution time mean : 1.418350 sec  95.0% CI: (1.417738 sec, 1.418948 sec)
    Execution time std-deviation : 66.736477 ms  95.0% CI: (66.186568 ms, 67.610777 ms)
         Execution time lower ci : 1.370419 sec  95.0% CI: (1.370419 sec, 1.370419 sec)
         Execution time upper ci : 1.544151 sec  95.0% CI: (1.544151 sec, 1.544156 sec)

Found 10 outliers in 60 samples (16.6667 %)
	low-severe	 2 (3.3333 %)
	low-mild	 8 (13.3333 %)
 Variance from outliers : 33.5591 % Variance is moderately inflated by outliers

(using https://github.com/hugoduncan/criterium for benchmarking)

Comment by Kevin Downey [ 15/Aug/12 2:17 AM ]

same again for r/partition-by from reducers-partition-by2.diff

user=> (bench (r/reduce + (r/map count (r/partition-by #(or (zero? (mod % 3)) (zero? (mod % 5))) x))))
Evaluation count             : 180
             Execution time mean : 307.596806 ms  95.0% CI: (307.271339 ms, 307.961550 ms)
    Execution time std-deviation : 34.060809 ms  95.0% CI: (33.613169 ms, 34.416837 ms)
         Execution time lower ci : 285.339333 ms  95.0% CI: (285.339333 ms, 285.339333 ms)
         Execution time upper ci : 385.087950 ms  95.0% CI: (385.087950 ms, 385.087950 ms)

Found 10 outliers in 60 samples (16.6667 %)
	low-severe	 4 (6.6667 %)
	low-mild	 6 (10.0000 %)
 Variance from outliers : 73.8053 % Variance is severely inflated by outliers

same again driven using r/fold (for grins) instead of r/reduce

user=> (bench (r/fold + (r/map count (r/partition-by #(or (zero? (mod % 3)) (zero? (mod % 5))) x))))
Evaluation count             : 360
             Execution time mean : 215.214486 ms  95.0% CI: (214.915417 ms, 215.664236 ms)
    Execution time std-deviation : 36.588464 ms  95.0% CI: (36.305548 ms, 36.847846 ms)
         Execution time lower ci : 185.575000 ms  95.0% CI: (185.575000 ms, 185.575000 ms)
         Execution time upper ci : 287.605175 ms  95.0% CI: (286.547833 ms, 287.605175 ms)

Found 6 outliers in 60 samples (10.0000 %)
	low-severe	 3 (5.0000 %)
	low-mild	 3 (5.0000 %)
 Variance from outliers : 87.6303 % Variance is severely inflated by outliers

reducers-partition-by2.diff is faster, but I am not wild about introducing a type and a protocol. also not sure about the CollFold impl.

Comment by Rich Hickey [ 15/Aug/12 6:58 AM ]

Let's leave fold out for this first patch, please.

Comment by Kevin Downey [ 15/Aug/12 2:34 PM ]

reducer-partition-by3.diff is a cleaned up version of reducer-partition-by2.diff without fold

Comment by Devin Walters [ 20/Oct/12 7:07 PM ]

Per Andy Fingerhut's email reducer-partition-by3.diff was failing to apply. This patch should apply cleanly to current master.

Comment by Andy Fingerhut [ 01/Nov/12 6:59 PM ]

Presumptuously changing Approval from Incomplete to None, since the reason for its being marked Incomplete seems to have been addressed with the latest patch.

Comment by Kevin Downey [ 04/Mar/13 2:49 PM ]

should this be assigned to someone?

Generated at Sat Aug 30 11:20:22 CDT 2014 using JIRA 4.4#649-r158309.