<< Back to previous view

[CLJ-1546] Widen vec to take Iterable/IReduce Created: 02/Oct/14  Updated: 24/Oct/14

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

Type: Enhancement Priority: Critical
Reporter: Alex Miller Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: None

Attachments: Text File clj-1546-2.patch     Text File clj-1546-3.patch     Text File clj-1546.patch    
Patch: Code and Test
Approval: Vetted


These examples should work but does not:

Something Iterable but not IReduce:

user> (def i (eduction (map inc) (range 100)))
user> (instance? java.util.Collection i)
user> (instance? Iterable i)
user> (vec i)
RuntimeException Unable to convert: class clojure.core.Iteration to Object[]

Something IReduceInit but not Iterable:

user=> (vec
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
RuntimeException Unable to convert: class user$reify__15 to Object[]

Proposal: Add PersistentVector.create(Iterable) and PersistentVector.create(IReduceInit) to efficiently create PVs from those. Add a number of cases to vec to support different cases.

Patch: clj-1546-3.patch

Screened by:

Comment by Timothy Baldridge [ 02/Oct/14 9:44 AM ]

Is there a reason the final case for (vec something) can't just be a call to (into [] coll)? It seems a bit odd to do (to-array) on anything thats not a java collection or Iterable, when we have IReduce.

Comment by Rich Hickey [ 02/Oct/14 10:02 AM ]

re: Tim - yes, this needs to support IReduce (and thereby educe) as well

Comment by Alex Miller [ 14/Oct/14 9:56 AM ]

Added new patch that handles Iterable and IReduceInit in vec. It also makes calling with a vector much faster due to the first check. into is still faster for chunked seqs (due to special InternalReduce handling of chunking).

It would be possible to move more of the variant checking into LazilyPersistentVector or PersistentVector so it could be used in more contexts. I'm not sure how much to do with that.

It would also be possible to instead lean on reduce more from the Java side if there was a Java version of reduce (as defined in mikera's branch for http://dev.clojure.org/jira/browse/CLJ-1192 at https://github.com/mikera/clojure/compare/clj-1192-vec-performance. Something like that is the only way I can see of leveraging that same InternalReduce logic that makes into faster than vec.

[CLJ-1554] Need to expand tests to cover transducers Created: 07/Oct/14  Updated: 24/Oct/14

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

Type: Defect Priority: Critical
Reporter: Alex Miller Assignee: Alex Miller
Resolution: Unresolved Votes: 0
Labels: transducers

Attachments: Text File clj-1554-2.patch     Text File clj-1554-3.patch     Text File clj-1554.patch    
Patch: Code and Test
Approval: Vetted


Attached patch contains both some generative and example tests for transducers. The generative tests build a series of sequence functions (take 5, filter odd?, etc) and apply them to a random vector of numbers as seq transformations, sequence of transducer, into of transducer, and transduce of transducer. The results are compared.

Note: these tests depend on the patch in CLJ-1349 to run as tests.

Patch: clj-1554-3.patch

Comment by Fogus [ 24/Oct/14 1:44 PM ]

I downloaded and applied this patch and its dependent patch (1349) and ran the tests. The coverage is a good start and the approach of verifying results against results gathered from other approaches is important. One note of style is that the use of `doall` is inconsistent in the `apply-as-*` functions. i would recommend that at least one other person screen this patch as my grasp of test.check is tenuous.

Comment by Alex Miller [ 24/Oct/14 2:52 PM ]

Updated patch slightly to clean up the doall stuff.

[CLJ-1529] Significantly improve compile time by reducing calls to Class.forName Created: 21/Sep/14  Updated: 24/Oct/14

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

Type: Enhancement Priority: Critical
Reporter: Zach Tellman Assignee: Unassigned
Resolution: Unresolved Votes: 27
Labels: compiler, performance

Attachments: File class-for-name.diff     PNG File clj-1529.png     Text File maybe-class-cache-2.patch     Text File maybe-class-cache.patch    
Patch: Code
Approval: Incomplete


Compilation speed has been a real problem for a number of my projects, especially Aleph [1], which in 1.6 takes 18 seconds to load. Recently I realized that Class.forName is being called repeatedly on symbols which are lexically bound. Hits on Class.forName are cached, but misses are allowed to go through each time, which translates into tens of thousands of calls after calling `(use 'aleph.http)`.

This patch improves compilation time from 18 seconds to 7 seconds. The gain is exaggerated by the number of macros I use, but I would expect at least 50% improvements across a wide variety of codebases.

This patch does introduce a slight semantic change by privileging lexical scope over classnames. Consider this code:

(let [String "foo"]
(. String substring 0 1))

Previously, this would be treated as a static call to 'java.lang.String', but with the patch would be treated as a call to the lexical variable 'String'. Since the new semantic is what I (and I think everyone else) would have expected in the first place, it's probably very likely that no one is shadowing classes with their variable names, since someone would have complained about this. If anyone feels this is at all risky, however, I'm happy to discuss it further.

[1] https://github.com/ztellman/aleph

Comment by Ghadi Shayban [ 21/Sep/14 4:30 PM ]

One of our larger projects (not macro-laden) just went from 36 seconds to 23 seconds to start with this patch.

Comment by Ramsey Nasser [ 03/Oct/14 12:34 PM ]

I ported this patch to Clojure-CLR for the Unity integration project and we have seen significant speedups as well. I too agree that this is the behavior I expect as a user.

Comment by Alex Miller [ 06/Oct/14 12:19 PM ]

I ran this on a variety of open-source projects. I didn't find that it produced any unexpected behavior or test errors. Most projects were about 10% faster to run equivalent of "lein test" with a few as high as 35% faster.

Comment by Alex Miller [ 07/Oct/14 12:52 PM ]

We're interested in comparing this and the class caching in fastload branch to get something in for 1.7. Next step is to extract a patch of the stuff in fastload so we can compare them better.

Comment by Alex Miller [ 07/Oct/14 4:06 PM ]

Add maybe class cache patch from fastload branch

Comment by Alex Miller [ 08/Oct/14 8:57 AM ]

Times below to run "time lein test" on a variety of projects with columns:

  • master = current 1.7.0 master
  • maybe-cache = maybe-class-cache.patch extracted from Rich's fastload branch
  • class-for-name = class-for-name.diff from Zach
  • % maybe-cache = % improvement for maybe-cache over master
  • % class-for-name = % improvement for class-for-name patch over master (sorted desc)

project,master,maybe-cache,class-for-name,% maybe-cache,% class-for-name

The summary is that both patches improve times on all projects. In most cases, the improvement from either is <10% but the first few projects have greater improvements. The class-for-name patch has a bigger improvement in all projects than the maybe-cache patch (but maybe-cache has no change in semantics).

Comment by Nicola Mometto [ 08/Oct/14 9:03 AM ]

Are the two patches mutually exclusive?

Comment by Alex Miller [ 08/Oct/14 9:35 AM ]

They are non-over-lapping. I have not considered whether they could both be applied or whether that makes any sense.

Comment by Alex Miller [ 08/Oct/14 9:53 AM ]

The two patches both essentially cut off the same hot code path, just at different points (class-for-name is earlier), so applying them both effectively should give you about the performance of class-for-name.

Comment by Alex Miller [ 08/Oct/14 2:14 PM ]

Added a picture of the data for easier consumption.

Comment by Deepak Giridharagopal [ 10/Oct/14 4:35 PM ]

One of our bigger projects saw a reduction of startup time of 16% with class-for-name, 14% with maybe-cache, and a whopping 23% with both patches applied. This was actually starting up the program, as opposed to running "lein test", FWIW.

Maybe it's worth re-running the benchmarks with a "both-patches" variant?

Comment by Alex Miller [ 10/Oct/14 5:28 PM ]

Hey Deepak, I did actually run some of them with both patches and saw times similar to class-for-name.

Were your times consistent across restarts? The times in the data above are the best of 3 trials for every data point (although they were relatively consistent).

Comment by Deepak Giridharagopal [ 10/Oct/14 6:08 PM ]

Hi Alex, the tests I ran did 20-iteration loops, and I took the mean (though it was pretty consistent between restarts). I can redo stuff and upload the raw data for you if that will help.

Comment by Deepak Giridharagopal [ 10/Oct/14 6:43 PM ]

So repeating the experiment several times does in fact behave as you suspected...apologies for my previous LOLDATA.

Comment by Alex Miller [ 24/Oct/14 3:01 PM ]

maybe-class-cache-2.patch removes some debugging stuff

[CLJ-1501] LazySeq switches to equiv when using equals Created: 11/Aug/14  Updated: 08/Oct/14

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

Type: Defect Priority: Major
Reporter: Jozef Wagner Assignee: Jozef Wagner
Resolution: Unresolved Votes: 0
Labels: collections, ft, interop, seq

Attachments: File clj-1501.diff    
Patch: Code and Test
Approval: Screened


When comparing lazy seqs with java equality operator .equals, the implementation switches to the Clojures .equiv comparison. This switch is not present in any other Seq or ordered collection type.

user> (.equals '(3) '(3N))
user> (.equals [3] [3N])
user> (.equals (seq [3]) (seq [3N]))
user> (.equals (lazy-seq [3]) (lazy-seq [3N]))

Screened by: Alex Miller

Comment by Jozef Wagner [ 11/Aug/14 9:32 AM ]

Patch clj-1501.diff with tests added

Comment by Andy Fingerhut [ 08/Oct/14 5:50 PM ]

This ticket has no Fix Version/s, but is Screened, so at least in some code I have it is 'off the JIRA workflow state diagram'. Not sure if it shows up that way in your filters, Alex.

Comment by Alex Miller [ 08/Oct/14 7:45 PM ]

Yup thanks.

[CLJ-1424] Feature Expressions Created: 15/May/14  Updated: 13/Oct/14

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

Type: Enhancement Priority: Major
Reporter: Ghadi Shayban Assignee: Alex Miller
Resolution: Unresolved Votes: 0
Labels: reader

Attachments: File CLJ-1424-2.diff     File clojure-feature-expressions.diff    
Approval: Incomplete


Feature expressions based directly on Common Lisp. See Clojure design docs, which includes discussion and links to Common Lisp documentation for feature expressions here: http://dev.clojure.org/display/design/Feature+Expressions

#+ #- and or not
are supported. Unreadable tagged literals are suppressed through the *suppress-read* dynamic var. For example, with *features* being #{:clj}, which is the default, the following should read :foo

#+cljs #js {:one :two} :foo

The initial *features* set can be augmented (clj will always be included) with the clojure.features System property:


Patch: CLJ-1424-2.diff

Questions: Should *suppress-read* override *read-eval*?

Related: CLJS-27, TRDR-14

Comment by Jozef Wagner [ 16/May/14 2:19 AM ]

Has there been a decision that CL syntax is going to be used? Related discussion can be found at design page, google groups discussion and another discussion.

Comment by Alex Miller [ 16/May/14 8:34 AM ]

No, no decisions on anything yet.

Comment by Ghadi Shayban [ 19/May/14 7:25 PM ]

Just to echo a comment from TRDR-14:

This is WIP and just one approach for feature expressions. There seem to be at least two couple diverging approaches emerging from the various discussion (Brandon Bloom's idea of read-time splicing being the other.)

In any case having all Clojure platforms be ready for the change is probably essential. Also backwards compatibility of feature expr code to Clojure 1.6 and below is also not trivial.

Comment by Kevin Downey [ 04/Aug/14 1:39 PM ]

if you have ever tried to do tooling for a language where the "parser" tossed out information or did some partial evaluation, it is a pain. this is basically what the #+cljs style feature expressions and bbloom's read time splicing both do with clojure's reader. I think resolving this at read time instead of having the compiler do it before macro expansion is a huge mistake and makes the reader much less useful for reading code.

Comment by Ghadi Shayban [ 04/Aug/14 2:00 PM ]

Kevin, what kind of tooling use case are you alluding to?

Comment by Kevin Downey [ 04/Aug/14 3:24 PM ]

any use case that involves reading code and not immediately handing it off to the compiler. if I wanted to write a little snippet to read in a function, add an unused argument to every arity then pprint it back, reader resolved feature expressions would not round trip.

if I want to write snippet of code to generate all the methods for a deftype (not a macro, just at the repl write a `for` expression) I can generate a clojure data structure, call pprint on it, then paste it in as code, reader feature expressions don't have a representation as data so I cannot do that, I would have to generate strings directly.

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

Changing Patch setting so this is not in Screenable yet (as it's still a wip).

[CLJ-1349] update to latest test.generative and prep for test.check Created: 10/Feb/14  Updated: 14/Oct/14

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

Type: Enhancement Priority: Major
Reporter: Stuart Halloway Assignee: Stuart Halloway
Resolution: Unresolved Votes: 1
Labels: None

Attachments: Text File clj-1349-1.patch     Text File clj-1349-2.patch     Text File clj-1349-3.patch    
Patch: Code and Test
Approval: Screened


This patch updates build to use the latest test.generative, and organizes build.xml so test.check can be dropped in next.

Patch: clj-1349-3

Screeners: note that the elapsed time reported at the end of an Ant build is not wall clock time. Even though the generative tests run for 60 seconds, it will report less. You can see that the tests are running for the correct duration by timing with a stopwatch if you care.

Comment by Alex Miller [ 10/Feb/14 5:16 PM ]

1) The (System/setProperty "clojure.test.generative.msec" "60000") was removed from run_tests.clj but not added to the new src/script/run_test_generative.clj. Because of this, the generative tests don't run as long and the overall build time (from generative tests) is shorter. I do not know if that was intentional.


[java] Framework clojure.test.generative
     [java] {:assert/pass 1282219, :test/group 6, :test/test 120, :test/iter 10025545}


[java] Framework clojure.test.generative
     [java] {:assert/pass 118974, :test/group 6, :test/test 120, :test/iter 998991}

2) The new (non-generative) part of the test lists many more namespaces being tested in the output, including gensym-ish ones like "Testing G__25228". However, both before and after the same number of tests and assertions are printed at the end. Not sure why these differ.

3) The all target could depend on test-all instead of both test and test-generative, but ok as is.

Comment by Alex Miller [ 07/Oct/14 12:51 PM ]

Patch needs some freshening...

Comment by Alex Miller [ 08/Oct/14 10:35 AM ]

Freshen patch and made some mods

Comment by Alex Miller [ 08/Oct/14 10:37 AM ]

New patch applies properly to master. I also:

  • added calls to set java.awt.headless per patches that have been added in the meanwhile
  • rejiggered the ant build targets so that "ant test" still does the same thing it did before but now there are test-example and test-generative. I think this is a smaller change and removes any need to change what we already have doc'ed for developers and screeners (just adds new sub-flavors)
  • added test.check to the dependencies

[CLJ-1515] Reify the result of range Created: 29/Aug/14  Updated: 24/Oct/14

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

Type: Enhancement Priority: Major
Reporter: Timothy Baldridge Assignee: Unassigned
Resolution: Unresolved Votes: 1
Labels: None

Attachments: File patch.diff     File range-patch3.diff    
Patch: Code and Test
Approval: Incomplete


Currently range simply returns a lazy seq. If the return value of range were reified into a type (as it is in ClojureScript) we could optimize many functions on that resulting type. Some operations such as count and nth become O(1) in this case, while others such as reduce could receive a performance boost do to the reduced number of allocations.

Approach: this patch revives the unused (but previously existing) clojure.lang.Range class. This class acts as a lazy seq and implements several other appropriate interfaces such as Counted and Indexed. This type is implemented in Java since range is needed fairly on in core.clj before deftype is defined. The attached patch uses Numbers.* methods for all math due to the input types to range being unknown. The class also supplies a .iterator() method which allows for allocation free reducing over range.

Note: this code keeps backwards compatibility with the existing range code. This means some parts of the class (mostly relating to a step size of 0) are a bit more complex than desired, but these bits were needed to get all the tests to pass.

Note: this code does not preserve the chunked-seq nature of the original range. The fact that range used to return chunked seqs was not published in the doc strings and so it was removed to allow for simpler code in Range.java.

(timings done at the repl run via java -jar)

(dotimes [x 100] (time (dotimes [x 1] (count (range (* 1024 1024))))))
master => 80-110ms
patch => 0.014ms

(dotimes [x 100] (time (dotimes [x 1] (reduce + (map inc (range (* 1024 1024)))))))
master => 76-87ms
patch => 340-360ms

(dotimes [x 100] (time (dotimes [x 1] (reduce + (map inc (map inc (range (* 1024 1024))))))))
master => 97-123ms
patch=> 490-577ms

(dotimes [x 100] (time (dotimes [x 1] (count (filter odd? (range (* 1024 1024)))))))
master => 87-104ms
patch => 370-330ms

(dotimes [x 100] (time (dotimes [x 1] (transduce (comp (map inc) (map inc)) + (range (* 1024 1024))))))
patch => 44ms-59ms

Patch: range-patch3.diff

Comment by Alex Miller [ 29/Aug/14 3:19 PM ]

1) Not sure about losing chunked seqs - that would make older usage slower, which seems undesirable.
2) RangeIterator.next() needs to throw NoSuchElementException when walking off the end
3) I think Range should implement IReduce instead of relying on support for CollReduce via Iterable.
4) Should let _hash and _hasheq auto-initialize to 0 not set to -1. As is, I think _hasheq always would be -1?
5) _hash and _hasheq should be transient.
6) count could be cached (like hash and hasheq). Not sure if it's worth doing that but seems like a win any time it's called more than once.
7) Why the change in test/clojure/test_clojure/serialization.clj ?
8) Can you squash into a single commit?

Comment by Timothy Baldridge [ 29/Aug/14 3:40 PM ]

1) I agree, adding chunked seqs to this will dramatically increase complexity, are we sure we want this?
2) exception added
3) I can add IReduce, but it'll pretty much just duplicate the code in protocols.clj. If we're sure we want that I'll add it too.
4) fixed hash init values, defaults to -1 like ASeq
5) hash fields are now transient
6) at the cost of about 4 bytes we can cache the cost of a multiplication and an addition, doesn't seem worth it?
7) the tests in serialization.clj assert that the type of the collection roundtrips. This is no longer the case for range which starts as Range and ends as a list. The change I made converts range into a list so that it properly roundtrips. My assumption is that we shouldn't rely on all implementations of ISeq to properly roundtrip through EDN.
8) squashed.

Comment by Alex Miller [ 29/Aug/14 3:49 PM ]

6) might be useful if you're walking through it with nth, which hits count everytime, but doubt that's common
7) yep, reasonable

Comment by Andy Fingerhut [ 18/Sep/14 6:52 AM ]

I have already pointed out to Edipo in personal email the guidelines on what labels to use for Clojure JIRA tickets here: http://dev.clojure.org/display/community/Creating+Tickets

Comment by Timothy Baldridge [ 19/Sep/14 10:02 AM ]

New patch with IReduce directly on Range instead of relying on iterators

Comment by Alex Miller [ 01/Oct/14 2:00 PM ]

The new patch looks good. Could you do a test to determine the perf difference from walking the old chunked seq vs the new version? If the perf diff is negligible, I think we can leave as is.

Another idea: would it make sense to have a specialized RangeLong for the (very common) case where start, end, and step could all be primitive longs? Seems like this could help noticeably.

Comment by Timothy Baldridge [ 03/Oct/14 10:00 AM ]

Looks like chunked seqs do make lazy seq code about 5x faster in these tests.

Comment by Ghadi Shayban [ 03/Oct/14 10:22 AM ]

I think penalizing existing code possibly 5x is a hard cost to stomach. Is there another approach where a protocolized range can live outside of core? CLJ-993 has a patch that makes it a reducible source in clojure.core.reducers, but it's coll-reduce not IReduce, and doesn't contain an Iterator. Otherwise we might have to take the chunked seq challenge.

Alex: Re long/float. Old reified Ranged.java in clojure.lang blindly assumes ints, it would be nice to have a long vs. float version, though I believe the contract of reduce boxes numbers. (Unboxed math can be implemented very nicely as in Prismatic's Hiphip array manipulation library, which takes the long vs float specialization to the extreme with different namespaces)

Comment by Timothy Baldridge [ 03/Oct/14 10:38 AM ]

I don't think anyone is suggesting we push unboxed math all the way down through transducers. Instead, this patch contains a lot of calls to Numbers.*, if we were to assume that the start end and step params of range are all Longs, then we could remove all of these calls and only box when returning an Object (in .first) or when calling IFn.invoke (inside .reduce)

Comment by Alex Miller [ 03/Oct/14 10:46 AM ]

I agree that 5x slowdown is too much - I don't think we can give up chunked seqs if that's the penalty.

On the long case, I was suggesting what Tim is talking about, in the case of all longs, create a Range that stores long prims and does prim math, but still return boxed objects as necessary. I think the only case worth optimizing is all longs - the permutation of other options gets out of hand quickly.

Comment by Ghadi Shayban [ 03/Oct/14 11:00 AM ]

Tim, I'm not suggesting unboxed math, but the singular fast-path of all-Longs that you and Alex describe. I mistakenly lower-cased Long/Float.

[CLJ-1572] into does not work with IReduceInit Created: 24/Oct/14  Updated: 24/Oct/14

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

Type: Defect Priority: Major
Reporter: Alex Miller Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: None

Attachments: Text File clj-1572.patch    
Patch: Code
Approval: Incomplete


This should work:

(into []
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
IllegalArgumentException Don't know how to create ISeq from: user$eval5$reify__6
	clojure.lang.RT.seqFrom (RT.java:506)
	clojure.lang.RT.seq (RT.java:487)
	clojure.core/seq--seq--4091 (core.clj:135)
	clojure.core.protocols/seq-reduce (protocols.clj:30)
	clojure.core.protocols/fn--6422 (protocols.clj:42)
	clojure.core.protocols/fn--6369/f--6255--auto----G--6364--6382 (protocols.clj:13)
	clojure.core/reduce (core.clj:6469)
	clojure.core/into (core.clj:6550)

Comment by Alex Miller [ 24/Oct/14 10:40 AM ]

into calls reduce which calls into CollReduce. CollReduce extends to IReduce, but not to IReduceInit. If CollReduce were extended to IReduceInit for the arity it can support, into work as expected in the given example. Patch clj-1572.patch does this.

Generated at Sat Oct 25 12:07:28 CDT 2014 using JIRA 4.4#649-r158309.