<< Back to previous view

[CLJ-1515] Reify the result of range Created: 29/Aug/14  Updated: 14/Nov/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     File reified-range4.diff    
Patch: Code and Test
Approval: Incomplete

 Description   

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.

Performance:
(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))))))
master=>76-116ms
patch => 44ms-59ms

Patch: reified-range4.diff (some tests fail)



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

Comment by Timothy Baldridge [ 31/Oct/14 11:30 AM ]

Here's the latest work on this, a few tests fail. If someone wants to take a look at this patch feel free, otherwise I'll continue to work on it as I have time/energy.

Comment by Nicola Mometto [ 14/Nov/14 12:51 PM ]

As discussed with Tim in #clojure, the current patch should not change ArrayChunk's reduce impl, that's an error.





[CLJ-1546] Widen vec to take Iterable/IReduce Created: 02/Oct/14  Updated: 14/Nov/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-4.patch     Text File clj-1546.patch    
Patch: Code and Test
Approval: Incomplete

 Description   

These examples should work but does not:

Something Iterable but not IReduce:

user> (def i (eduction (map inc) (range 100)))
#'user/i
user> (instance? java.util.Collection i)
false
user> (instance? Iterable i)
true
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-4.patch

Screened by:



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

Comment by Alex Miller [ 13/Nov/14 4:14 PM ]

Prior comments from Stu removed from description: "Open Question: Which branch should come first, Collection or IReduceInit? Collection reaches the fast path for small collections through LazilyPersistentVector, but IReduceInit should be faster for larger things. Related: Shouldn't the item count in LazilyPersistentVector be a bounded count?"

I have attached a new patch that simplifies the impl to do it in LazilyPersistentVector instead of in vec, which was easier due to "and" not being able yet when vec is implemented to do the length check.

I have also done a considerable amount of analysis on the matrix of incoming collections and best path to follow and also collected some data on what collections are commonly passed into vec. The current patch reflects those findings. Some highlights:

  • vec is called with PersistentVector in all projects I tested. The instanceof check takes that case from typically 100s of nanos to ~5 ns. So I do think it is worth doing.
  • vec is overwhelmingly called with small collections - in most cases the incoming collection is <10 elements. In cases where the collection is not a sequence, the path of creating the Vector with an owning array is the fastest option, beating even IReduce and transient building (as that path has some checks involved).
  • PersistentList is the only IReduce likely to be encountered by vec right now and adding that branch is a significant performance boost from prior impl and vs into. If maps and sets were IReduce, they would gain this as well.
  • chunked seqs will be significantly faster with into than vec as into goes through CollReduce and can leverage many optimizations on reducing through chunks that are not available to vec.
  • seqs in general though are now faster with vec than they were due to leveraging transients.
  • eduction results support IReduce and are also faster with vec than into.
  • range is currently slower with vec, but when range is IReduce, it will probably be faster with vec

In summary, some new conventional wisdom (after this patch) on (into []) vs vec:

  • vec is faster if passed a vector, an IReduce, or an array
  • into is faster when working with seqs, but even vec is better than it used to be and may even be faster for things like range in the future
Comment by Michael Blume [ 13/Nov/14 7:24 PM ]

Latest patch won't build for me when applied to master

compile-clojure:
     [java] Exception in thread "main" java.lang.ExceptionInInitializerError
     [java] 	at clojure.lang.Compile.<clinit>(Compile.java:29)
     [java] Caused by: java.lang.NoSuchMethodError: clojure.lang.LazilyPersistentVector.create(Ljava/util/Collection;)Lclojure/lang/IPersistentVector;, compiling:(clojure/core.clj:14:23)
     [java] 	at clojure.lang.Compiler.load(Compiler.java:7206)
     [java] 	at clojure.lang.RT.loadResourceScript(RT.java:370)
     [java] 	at clojure.lang.RT.loadResourceScript(RT.java:361)
     [java] 	at clojure.lang.RT.load(RT.java:440)
     [java] 	at clojure.lang.RT.load(RT.java:411)
     [java] 	at clojure.lang.RT.doInit(RT.java:448)
     [java] 	at clojure.lang.RT.<clinit>(RT.java:329)
     [java] 	... 1 more
     [java] Caused by: java.lang.NoSuchMethodError: clojure.lang.LazilyPersistentVector.create(Ljava/util/Collection;)Lclojure/lang/IPersistentVector;
     [java] 	at clojure.lang.LispReader$VectorReader.invoke(LispReader.java:1073)
     [java] 	at clojure.lang.LispReader.readDelimitedList(LispReader.java:1138)
     [java] 	at clojure.lang.LispReader$ListReader.invoke(LispReader.java:972)
     [java] 	at clojure.lang.LispReader.read(LispReader.java:183)
     [java] 	at clojure.lang.LispReader$WrappingReader.invoke(LispReader.java:535)
     [java] 	at clojure.lang.LispReader.readDelimitedList(LispReader.java:1138)
     [java] 	at clojure.lang.LispReader$MapReader.invoke(LispReader.java:1081)
     [java] 	at clojure.lang.LispReader.read(LispReader.java:183)
     [java] 	at clojure.lang.LispReader$MetaReader.invoke(LispReader.java:716)
     [java] 	at clojure.lang.LispReader.readDelimitedList(LispReader.java:1138)
     [java] 	at clojure.lang.LispReader$ListReader.invoke(LispReader.java:972)
     [java] 	at clojure.lang.LispReader.read(LispReader.java:183)
     [java] 	at clojure.lang.Compiler.load(Compiler.java:7190)
     [java] 	... 7 more
Comment by Alex Miller [ 13/Nov/14 7:28 PM ]

Did you clean first? I replaced that static method call there with a wider version but if you are cleaning fresh it should be fine.

Comment by Michael Blume [ 13/Nov/14 7:31 PM ]

Apologies, maven just wasn't doing a good job of tracking changes, running mvn clean fixes the build.





[CLJ-1424] Feature Expressions Created: 15/May/14  Updated: 07/Nov/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 clj-1424-3.diff     File clojure-feature-expressions.diff    
Patch: Code
Approval: Incomplete

 Description   

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:

-Dclojure.features=production,embedded

Patch: clj-1424-3.diff

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

Related: CLJS-27, TRDR-14



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

Comment by Alex Miller [ 07/Nov/14 4:39 PM ]

Latest patch brings up to par with related patches in CLJS-27 and TRDR-14 and importantly adds support for loading .cljc files as Clojure files.

Comment by Andy Fingerhut [ 07/Nov/14 5:55 PM ]

Maybe undesirable behavior demonstrated below with latest Clojure master plus patch clj-1424-3.diff, due to the #+cljs skipping the comment, but not the (dec a). I thought it could be fixed simply by moving RT.suppressRead() check after (ret == r) check in read(), but that isn't correct.

user=> (read-string "(defn foo [a] #+clj (inc a) #+cljs ; foo\n (dec a))")
(defn foo [a] (inc a) (dec a))




Generated at Sun Nov 23 10:04:43 CST 2014 using JIRA 4.4#649-r158309.