<< Back to previous view

[CLJ-1598] Make if forms compile directly to the appropriate branch expression if the test is a literal Created: 24/Nov/14  Updated: 24/Nov/14

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: 1
Labels: compiler, performance, primitives

Attachments: Text File 0001-if-test-expr-of-an-if-statement-is-a-literal-don-t-e.patch    
Approval: Triaged

 Description   

This allows expressions like `(cond (some-expr) 1 :else 2)` to be eligible for unboxed use, which is not currently possible since the cond macro always ends up with a nil else branch that the compiler currently takes into account.

With the attached patch, the trailing (if :else 2 nil) in the macroexpansion will be treated as 2 by the Compiler, thus allowing the unboxed usage of the cond expression.






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

Status: Closed
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: Completed Votes: 28
Labels: compiler, performance

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

 Description   

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

Proposed: Avoid calling Class.forName() on non-namespaced symbols that do not contain "." or start with "[", don't map to a Class in the ns, and are names in the current local env. Also, adjust the ordering of checks in tagToClass to check for hints before checking for class.

[Note that the latest variant of the patch moves the check from the original patch farther down in the logic to avoid changing the semantics. This still yields virtually all of the performance gains. See comments for details.]

Patch: clj-1529-no-cache-2.diff

Screened by: Stu Halloway. Note that for this change the patch ended up being so small it is easier follow the code than the prose description.

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



 Comments   
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
aleph,25.605,16.572,14.460,35.278,43.527
riemann,40.550,27.656,24.734,31.798,39.004
lamina,37.247,30.072,29.045,19.263,22.021
trapperkeeper,11.979,11.158,10.3,6.854,14.016
plumbing,73.777,68.388,66.922,7.304,9.292
cheshire,5.583,5.089,5.086,8.848,8.902
tools.analyzer,5.411,5.289,5.023,2.255,7.171
core.async,19.161,18.090,17.942,5.589,6.362
tools.reader,4.686,4.435,4.401,5.356,6.082
clara-rules,43.964,42.140,41.542,4.149,5.509
core.typed,158.885,154.954,151.445,2.474,4.683
instaparse,9.286,8.922,8.859,3.920,4.598
schema,45.3,43.914,43.498,3.060,3.978
mandoline,76.295,74.831,74.425,1.919,2.451

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

Comment by Alex Miller [ 27/Oct/14 4:41 PM ]

I've done more testing and made mods to both patches and moved them closer together.

On the maybe-class-cache patch (new version = clj-1529-with-cache.diff):
1) I found that adding a final else branch that returned null was an improvement - this avoids caching things that will never hit in the future (Cons, PersistentList, Symbols with namespaces, etc). That's both a perf improvement (avoids hashing those things) and a memory improvement.
2) The tagToClass improvement from Zach's patch is orthogonal and also valid here so I added it.
3) I added Zach's check, but moved the placement lower so that it doesn't alter semantics. It helps avoid caching locals that aren't classes.

On the class-for-name patch (new version = clj-1529-no-cache.diff):
1) Same change as #3 above - moved check lower to avoid semantics change.

With these changes, both patches have tagToClass and local checks, neither patch changes semantics, and the only difference is whether to keep or remove the cache.

aleph timings (for "lein test"):

  • 1.7 master = 25.415 s
  • 1.7 + clj-1529-with-cache.diff = 14.329 s
  • 1.7 + clj-1529-no-cache.diff = 14.808 s

lamina timings (for "lein test"):

  • 1.7 master = 37.340 s
  • 1.7 + clj-1529-with-cache.diff = 28.680 s
  • 1.7 + clj-1529-no-cache.diff = 28.759 s

The cache helps slightly in both cases, but it does not seem worth adding the new dynamic var and unbounded memory use inherent in the cache.

Comment by Alex Miller [ 05/Nov/14 11:40 AM ]

Talked to Rich, focusing on no-cache patch. Added new version that fixes tabbing and restores Zach's name to the patch, which seems appropriate.





[CLJ-1517] unrolled small collections Created: 01/Sep/14  Updated: 13/Nov/14

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

Type: Enhancement Priority: Major
Reporter: Zach Tellman Assignee: Unassigned
Resolution: Unresolved Votes: 12
Labels: collections, performance

Attachments: File unrolled-collections-2.diff     File unrolled-collections.diff    
Patch: Code
Approval: Vetted

 Description   

As discussed on the mailing list [1], this patch has two unrolled variants of vectors and maps, with special inner classes for each cardinality. Currently both grow to six elements before spilling over into the general versions of the data structures, which is based on rough testing but can be easily changed. At Rich's request, I haven't included any integration into the rest of the code, and there are top-level static create() methods for each.

The sole reason for this patch is performance, both in terms of creating data structures and performing operations on them. This can be seen as a more verbose version of the trick currently played with PersistentArrayMap spilling over into PersistentHashMap. Based on the benchmarks, which can be run by cloning cambrian-collections [2] and running 'lein test :benchmark', this should supplant PersistentArrayMap. Performance is at least on par with PAM, and often much faster. Especially noteworthy is the creation time, which is 5x faster for maps of all sizes (lein test :only cambrian-collections.map-test/benchmark-construction), and on par for 3-vectors, but 20x faster for 5-vectors. There are similar benefits for hash and equality calculations, as well as calls to reduce().

This is a big patch (over 5k lines), and will be kind of a pain to review. My assumption of correctness is based on the use of collection-check, and the fact that the underlying approach is very simple. I'm happy to provide a high-level description of the approach taken, though, if that will help the review process.

I'm hoping to get this into 1.7, so please let me know if there's anything I can do to help accomplish that.

[1] https://groups.google.com/forum/#!topic/clojure-dev/pDhYoELjrcs
[2] https://github.com/ztellman/cambrian-collections



 Comments   
Comment by Zach Tellman [ 01/Sep/14 10:13 PM ]

Oh, I forgot to mention that I didn't make a PersistentUnrolledSet, since the existing wrappers can use the unrolled map implementation. However, it would be moderately faster and more memory efficient to have one, so let me know if it seems worthwhile.

Comment by Nicola Mometto [ 02/Sep/14 5:23 AM ]

Zach, the patch you added isn't in the correct format, they need to be created using `git format-patch`

Comment by Nicola Mometto [ 02/Sep/14 5:31 AM ]

Also, I'm not sure if this is on-scope with the ticket but those patches break with *print-dup*, as it expects a static create(x) method for each inner class.

I'd suggest adding a create(Map x) static method for the inner PersistentUnrolledMap classes and a create(ISeq x) one for the inner PersistentUnrolledVector classes

Comment by Alex Miller [ 02/Sep/14 8:14 AM ]

Re making patches, see: http://dev.clojure.org/display/community/Developing+Patches

Comment by Jozef Wagner [ 02/Sep/14 9:16 AM ]

I wonder what is the overhead of having meta and 2 hash fields in the class. Have you considered a version where the hash is computed on the fly and where you have two sets of collections, one with meta field and one without, using former when the actual metadata is attached to the collection?

Comment by Zach Tellman [ 02/Sep/14 12:13 PM ]

I've attached a patch using the proper method. Somehow I missed the detailed explanation for how to do this, sorry. I know the guidelines say not to delete previous patches, but since the first one isn't useful I've deleted it to minimize confusion.

I did the print-dup friendly create methods, and then realized that once these are properly integrated, 'pr' will just emit these as vectors. I'm fairly sure the create methods aren't necessary, so I've commented them out, but I'm happy to add them back in if they're useful for some reason I can't see.

I haven't given a lot of thought to memory efficiency, but I think caching the hashes are worthwhile. I can see an argument for creating a "with-meta" version of each collection, but since that would double the size of an already enormous patch, I think that should probably wait.

Comment by Zach Tellman [ 03/Sep/14 4:31 PM ]

I found a bug! Like PersistentArrayMap, I have a special code path for comparing keywords, but my generators for collection-check were previously using only integer keys. There was an off-by-one error in the transient map implementation [1], which was not present for non-keyword lookups.

I've taken a close look for other gaps in my test coverage, and can't find any. I don't think this substantively changes the risk of this patch (an updated version of which has been uploaded as 'unrolled-collections-2.diff'), but obviously where there's one bug, there may be others.

[1] https://github.com/ztellman/cambrian-collections/commit/eb7dfe6d12e6774512dbab22a148202052442c6d#diff-4bf78dbf5b453f84ed59795a3bffe5fcR559

Comment by Zach Tellman [ 03/Oct/14 2:34 PM ]

As an additional data point, I swapped out the data structures in the Cheshire JSON library. On the "no keyword-fn decode" benchmark, the current implementation takes 6us, with the unrolled data structures takes 4us, and with no data structures (just lexing the JSON via Jackson) takes 2us. Other benchmarks had similar results. So at least in this scenario, it halves the overhead.

Benchmarks can be run by cloning https://github.com/dakrone/cheshire, unrolled collections can be tested by using the 'unrolled-collections' branch. The pure lexing benchmark can be reproduced by messing around with the cheshire.parse namespace a bit.

Comment by Zach Tellman [ 06/Oct/14 1:31 PM ]

Is there no way to get this into 1.7? It's an awfully big win to push off for another year.

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

Hey Zach, it's definitely considered important but we have decided to drop almost everything not fully done for 1.7. Timeframe for following release is unknown, but certainly expected to be significantly less than a year.

Comment by John Szakmeister [ 30/Oct/14 2:53 PM ]

You are all free to determine the time table, but I thought I'd point out that Zach is not entirely off-base. Clojure 1.4.0 was released April 5th, 2012. Clojure 1.5.0 was released March 1st, 2013 with 1.6.0 showing up March 25th, 2014. So it appears that the current cadence is around a year.

Comment by Alex Miller [ 30/Oct/14 3:40 PM ]

John, there is no point to comments like this. Let's please keep issue comments focused on the issue.

Comment by Zach Tellman [ 13/Nov/14 12:23 PM ]

I did a small write-up on this patch which should help in the eventual code review: http://blog.factual.com/using-clojure-to-generate-java-to-reimplement-clojure





[CLJ-1493] Fast keyword intern Created: 06/Aug/14  Updated: 11/Sep/14

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

Type: Enhancement Priority: Major
Reporter: dennis zhuang Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: keywords, performance
Environment:

Mac OS X 10.9.4 / 2.6 GHz Intel Core i5 / 8 GB 1600 MHz DDR3
java version "1.7.0_17"
Java(TM) SE Runtime Environment (build 1.7.0_17-b02)
Java HotSpot(TM) 64-Bit Server VM (build 23.7-b01, mixed mode)


Attachments: File fast_keyword_intern.diff    
Patch: Code
Approval: Triaged

 Description   

Keyword's intern(Symbol) method uses recursive invocation to get a valid keyword instance.I think it can be rewrite into a 'for loop'
to reduce method invocation cost.
So i developed this patch, and make some simple benchmark.Run the following command line three times after 'ant jar':

java -Xms64m -Xmx64m -cp test:clojure.jar clojure.main -e "(time (dotimes [n 10000000] (keyword (str n))))"

Before patched:

"Elapsed time: 27343.827 msecs"
"Elapsed time: 26172.653 msecs"
"Elapsed time: 25673.764 msecs"

After patched:

"Elapsed time: 24884.142 msecs"
"Elapsed time: 23933.423 msecs"
"Elapsed time: 25382.783 msecs"

It looks the patch make keyword's intern a little more fast.

The patch is attached and test.

Thanks.

P.S. I've signed the contributor agreement, and my email is killme2008@gmail.com .



 Comments   
Comment by Alex Miller [ 07/Aug/14 9:01 AM ]

Looks intriguing (and would be a nice change imo). I ran this on a json parsing benchmark I used for the keyword changes and saw ~3% improvement.

Comment by dennis zhuang [ 07/Aug/14 9:54 PM ]

Updated the patch, remove the 'k == null' clause in for loop,it's not necessary.

Comment by Andy Fingerhut [ 11/Aug/14 1:29 AM ]

Dennis, while JIRA can handle multiple patches with the same name, it can be confusing for people discussing the patches, and for some scripts I have to evaluate them. Please consider giving the patches different names (e.g. with version numbers in them), or removing older ones if they are obsolete.

Comment by dennis zhuang [ 11/Aug/14 9:19 AM ]

Hi,andy

Thank you for reminding me.I deleted the old patch.

Comment by dennis zhuang [ 11/Sep/14 10:34 AM ]

I am glad to see it is helpful.I benchmark the patch with current master branch,it's fine too.





[CLJ-1458] Use transients in merge and merge-with Created: 04/Jul/14  Updated: 14/Sep/14

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

Type: Enhancement Priority: Minor
Reporter: Yongqian Li Assignee: Unassigned
Resolution: Unresolved Votes: 5
Labels: newbie, performance

Attachments: File transient-merge.diff    
Patch: Code
Approval: Triaged

 Description   

It would be nice if merge used transients.



 Comments   
Comment by Jason Wolfe [ 13/Sep/14 5:09 PM ]

I will take a crack at a patch today.

Comment by Jason Wolfe [ 13/Sep/14 5:42 PM ]

This patch (transient-merge.diff) makes merge, merge-with, and zipmap (since it was right there and could obviously benefit from transients as well) use transients.

Three potential issues:

  • I had to move the functions, since they depend on transient and friends. I assume this is preferable to a forward declaration. This was the best place I could find, but happy to move them elsewhere.
  • I added multiple arities, to avoid potential performance cost of transient-ing a single argument. Happy to undo this if desired.
  • I had to slightly alter the logic in merge-with, since transient maps don't support contains? (or find).
Comment by Michał Marczyk [ 14/Sep/14 12:43 PM ]

I posted a separate ticket for zipmap, with patch, on 30/May/12: CLJ-1005.

Comment by Jason Wolfe [ 14/Sep/14 5:28 PM ]

Ah, sorry if I overstepped then. Happy to remove that change from this patch then if that will simplify things – just let me know.





[CLJ-1439] Reduce keyword cache lookup cost Created: 05/Jun/14  Updated: 07/Oct/14  Resolved: 01/Aug/14

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

Type: Enhancement Priority: Minor
Reporter: Kyle Kingsbury Assignee: Unassigned
Resolution: Completed Votes: 1
Labels: keywords, performance

Attachments: Text File 0001-Improve-Keyword.intern-performance.patch    
Patch: Code
Approval: Ok

 Description   

Background: Symbol is composed of name and namespace strings. Symbol construction interns both of these strings - this reduces memory usage and allows for string == checks inside Symbol. Keywords wrap a Symbol and have an additional cache to reuse Keyword instances.

Problem: Certain applications make heavy use of keywords (in particular the case of parsing or transforming JSON, XML, or other data into Clojure maps with keyword keys). Constructing the same keyword from a string over and over again will cause the string to be interned, a symbol constructed, and the lookup to occur in the keyword cache. In the case where the keyword already exists, this is more work than is necessary, making this path slower than it can be.

Reproduce: The following test simulates rounds of creating many keywords - the unique? flag indicates whether to use new or the same set of keywords each rep. unique?=false should be more similar to parsing a similar JSON record format over and over.

(set! *unchecked-math* true)

(defn kw-new [n unique?]
  (let [base (if unique? (str (rand)) "abcdef")]
    (loop [i 0
           kws (transient [])]
      (if (< i n)
        (recur (inc i) (conj! kws (keyword (str base i))))
        (persistent! kws)))))

(defn bench-kw [reps n unique?]
  (dotimes [_ reps]
    (let [begin (System/nanoTime)]
        (kw-new n unique?)
        (let [end (System/nanoTime)
              elapsed (/ (- end begin) 1000000.0)]
          (println elapsed "ms")))))

(bench-kw 50 10000 false)  ;; expected similar to JSON use case
(bench-kw 50 10000 true)   ;; for comparison

On 1.6, we see about 5.5 ms for repeated and 134 ms for unique after warmup.
With the patch, we see about 2.2 ms for repeated and 120 ms for unique after warmup.

Cause: Keyword construction based on a string involves:

  • Interning string(s) in new kw
  • Constructing Symbol with interned strings
  • Clearing Keywords from the Keyword cache if GC has reclaimed them
  • Constructing a new Keyword
  • Wrapping the Keyword in a WeakReference
  • CHM putIfAbsent on the cache
  • If new, return. If exists, get the old one and return.
  • In the event the Keyword is reclaimed by GC between the last 2 steps, retry.

This process involves a fair amount of speculative interning and object creation if the keyword already exist.

Proposal: Streamline the keyword construction process by reworking the cache implementation and the Keyword.intern() process. The patch changes the cache to key by string name instead of symbol, deferring interning and symbol creation on lookup to when we know the keyword construction is needed. The various Keyword.intern() methods are also reworked to take advantage if called with an existing Symbol to avoid re-creating it.

Patch: 0001-Improve-Keyword.intern-performance.patch

Related: CLJ-1415



 Comments   
Comment by Alex Miller [ 01/Aug/14 11:48 AM ]

Alternate changes were committed today to improve both symbol and keyword creation times.

https://github.com/clojure/clojure/commit/c9e70649d2652baf13b498c4c3ebb070118c4573

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

related patch was applied





[CLJ-1437] Keyword cache lookup could be faster Created: 05/Jun/14  Updated: 05/Jun/14  Resolved: 05/Jun/14

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

Type: Enhancement Priority: Major
Reporter: Alex Miller Assignee: Unassigned
Resolution: Duplicate Votes: 0
Labels: keywords, performance


 Description   

Breaking this piece out from CLJ-1415. Keyword cache lookup includes symbol creation and interning which could be avoided, making cache lookup faster.






[CLJ-1430] Improve performance of partial Created: 23/May/14  Updated: 05/Sep/14  Resolved: 29/Aug/14

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

Type: Enhancement Priority: Minor
Reporter: Timothy Baldridge Assignee: Unassigned
Resolution: Completed Votes: 0
Labels: performance

Attachments: File partial-perf.diff    
Patch: Code
Approval: Ok

 Description   

This patch improves performance of partial by only using apply when needed. The code structure follows that of juxt.

Performance benchmark:

(ns partial-test.core
  (:require [criterium.core :refer [bench]])
  (:gen-class))

(defn -main []
  (let [f (partial + 1 1)]
    (println "Starting")
    (bench (f 1 1))
    (println "Done")))

Results for 1.6.0:

Evaluation count : 228751140 in 60 samples of 3812519 calls.
             Execution time mean : 266.700063 ns
    Execution time std-deviation : 2.966851 ns
   Execution time lower quantile : 262.641023 ns ( 2.5%)
   Execution time upper quantile : 274.207916 ns (97.5%)
                   Overhead used : 1.610513 ns

Found 3 outliers in 60 samples (5.0000 %)
	low-severe	 3 (5.0000 %)
 Variance from outliers : 1.6389 % Variance is slightly inflated by outliers

Results for 1.7.0 with this patch:

 Evaluation count : 348208140 in 60 samples of 5803469 calls.
              Execution time mean : 171.210533 ns
     Execution time std-deviation : 2.011660 ns
    Execution time lower quantile : 168.819526 ns ( 2.5%)
    Execution time upper quantile : 176.015584 ns (97.5%)
                    Overhead used : 2.644128 ns

 Found 3 outliers in 60 samples (5.0000 %)
 	low-severe	 3 (5.0000 %)
  Variance from outliers : 1.6389 % Variance is slightly inflated by outliers

Benchmarks performed via lein uberjar + running via the commandline.

Patch: partial-perf.diff

Screened by: Alex Miller



 Comments   
Comment by Alex Miller [ 23/May/14 10:46 AM ]

Screened, looks as expected.

Comment by Andy Fingerhut [ 02/Jun/14 10:50 AM ]

Timothy, just a nit that I would not have noticed except for my program that checks for name and email address of patch authors, to see if they are on my contributor's list, but do you really have both of the email addresses tbaldridge@gmail.com and tbaldidge@gmail.com (note the spelling difference)? The latter is the one on this patch.

Comment by Timothy Baldridge [ 02/Jun/14 11:04 AM ]

fixed email

Comment by Timothy Baldridge [ 02/Jun/14 11:05 AM ]

nice catch! it was a typeo in my .gitconfig defaults. I've fixed the patch.

Comment by Alex Miller [ 02/Jun/14 11:19 AM ]

Tim (and anyone really) - please let someone know if you need to change a screened patch! Looks fine here, but screener should be notified so they can re-screen.

Comment by Alex Baranosky [ 05/Sep/14 9:11 PM ]

Very nice patch. I've gotten into the habit of not using partial anymore for performance sensitive code. Perhaps this change means I need to rethink that.





[CLJ-1429] Cache unknown multimethod value default dispatch Created: 22/May/14  Updated: 29/Aug/14  Resolved: 29/Aug/14

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

Type: Enhancement Priority: Major
Reporter: Alex Miller Assignee: Unassigned
Resolution: Completed Votes: 2
Labels: performance

Attachments: Text File clj-1429.patch    
Patch: Code
Approval: Ok

 Description   

Multimethods maintain a cache from dispatch value (result of the dispatch function) to dispatch method. If the dispatch value does not find a match in the available methods, it falls through to a lookup using the default dispatch value and returns that method. This default dispatch case is NOT recorded in the cache. This means that every case that falls through to the default case incurs a scan of the methodTable (and the class inheritance checks that involves).

Perf test:

(defmulti mm class)
(defmethod mm String [s] s)
(defmethod mm Long [l] l)
(defmethod mm :default [v] v)

(defn perf [reps size]
  (let [data (take size (cycle ["abc" 5 :k]))]
    (dotimes [_ reps]
      (time (doall (map mm data))))))

And results:

;; Without patch:
user=> (perf 5 100000)
"Elapsed time: 1301.262 msecs"
"Elapsed time: 928.888 msecs"
"Elapsed time: 942.905 msecs"
"Elapsed time: 858.513 msecs"
"Elapsed time: 832.314 msecs"

;; With patch:
user=> (perf 5 100000)
"Elapsed time: 134.169 msecs"
"Elapsed time: 28.859 msecs"
"Elapsed time: 45.452 msecs"
"Elapsed time: 13.189 msecs"
"Elapsed time: 13.42 msecs"

Attached patch caches the mapping of unknown value -> default dispatch method and significantly improves the performance for this case.

Patch: clj-1429.patch
Screened by: Stu






[CLJ-1422] Recur around try boxes primitives Created: 14/May/14  Updated: 28/Jul/14

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

Type: Enhancement Priority: Minor
Reporter: Kyle Kingsbury Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: compiler, performance, typehints


 Description   

Primitive function and recur variables can't pass through a (try) cleanly; they're boxed to Object instead. This causes reflection warnings for fns or loops that use primitive types.

user=> (set! *warn-on-reflection* true)
true
 
user=> (fn [] (loop [t 0] (recur t)))
#<user$eval676$fn__677 user$eval676$fn__677@3d80023a>
 
user=> (fn [] (loop [t 0] (recur (try t))))
NO_SOURCE_FILE:1 recur arg for primitive local: t is not matching primitive, had: Object, needed: long
Auto-boxing loop arg: t
#<user$eval680$fn__681 user$eval680$fn__681@5419323a>

user=> (fn [^long x] (recur (try x)))
NO_SOURCE_FILE:1 recur arg for primitive local: x is not matching primitive, had: Object, needed: long

CompilerException java.lang.IllegalArgumentException:  recur arg for primitive local: x is not matching primitive, had: Object, needed: long, compiling:(NO_SOURCE_PATH:1:1)


 Comments   
Comment by David James [ 15/Jun/14 10:27 PM ]

Without commenting on the most desirable behavior, the following code does not cause reflection warnings:

user=> (set! *warn-on-reflection* true)
true
user=> (fn [] (loop [t 0] (recur (long (try t)))))
#<user$eval673$fn__674 user$eval673$fn__674@4e56c411>
Comment by Nicola Mometto [ 16/Jun/14 6:33 AM ]

Similar ticket http://dev.clojure.org/jira/browse/CLJ-701

Comment by Kevin Downey [ 21/Jul/14 6:59 PM ]

try/catch in the compiler only implements Expr, not MaybePrimitiveExpr, looking at extending TryExpr with MaybePrimitiveExpr it seems simple enough, but it turns out recur analyzes it's arguments in the statement context, which causes (try ...) to essentially wrap itself in a function like ((fn [] (try ...))), at which point it is an invokeexpr which is much harder to add maybeprimitiveexpr too and it reduces to the same case as CLJ-701

Comment by Kevin Downey [ 22/Jul/14 9:27 PM ]

http://dev.clojure.org/jira/browse/CLJ-701 has a patch that I think solves this

Comment by Alex Miller [ 28/Jul/14 1:56 PM ]

Should I dupe this to CLJ-701?

Comment by Kevin Downey [ 28/Jul/14 5:22 PM ]

if you want the fixes for try out of the return context to be part of CLJ-701 then yes it is a dupe, if you are unsure or would prefer 701 to stay more focused (my patch may not be acceptable, or may be too large and doing too much) then no it wouldn't be a dupe. I sort of took it on myself to solve both in the patch on CLJ-701 because I came to CLJ-701 via Nicola's comment here, and the same compiler machinery can be used for both.

I think the status is pending on the status of CLJ-701.





[CLJ-1420] ThreadLocalRandom instead of Math/random Created: 11/May/14  Updated: 29/Aug/14

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

Type: Enhancement Priority: Minor
Reporter: Linus Ericsson Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: math, performance
Environment:

Requires Java >=1.7!


Attachments: Text File 0001-rand-using-ThreadLocalRandom-and-tests-for-random.patch    
Patch: Code
Approval: Vetted

 Description   

The standard Math.random() is thread-safe through being declared as a synchronized static method.

The patch uses java.util.concurrent.ThreadLocalRandom which actually seems to be two times faster than the ordinary Math.random() in a simple single threaded criterium.core/bench:

The reason I investigated the function at all was to be sure random-number generation was not a bottleneck when performance testing multithreaded load generation.

If necessary, one could of course make a conditional declaration (like in fj-reducers) based on the existence of the class java.util.concurrent.ThreadLocalRandom, if Clojure 1.7 is to be compatible with Java versions < 1.7



 Comments   
Comment by Linus Ericsson [ 11/May/14 11:05 AM ]

Benchmark on current rand (clojure 1.6.0), $ java -version
java version "1.7.0_51"
OpenJDK Runtime Environment (IcedTea 2.4.4) (7u51-2.4.4-0ubuntu0.13.10.1)
OpenJDK 64-Bit Server VM (build 24.45-b08, mixed mode)

:jvm-opts ^:replace [] (ie no arguments to the JVM)

(bench (rand 10))
Evaluation count : 1281673680 in 60 samples of 21361228 calls.
Execution time mean : 43.630075 ns
Execution time std-deviation : 0.420801 ns
Execution time lower quantile : 42.823363 ns ( 2.5%)
Execution time upper quantile : 44.456267 ns (97.5%)
Overhead used : 3.194591 ns

Found 1 outliers in 60 samples (1.6667 %)
low-severe 1 (1.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers

Clojure 1.7.0-master-SNAPSHOT.

(bench (rand 10))
Evaluation count : 2622694860 in 60 samples of 43711581 calls.
Execution time mean : 20.474605 ns
Execution time std-deviation : 0.248034 ns
Execution time lower quantile : 20.129894 ns ( 2.5%)
Execution time upper quantile : 21.009303 ns (97.5%)
Overhead used : 2.827337 ns

Found 2 outliers in 60 samples (3.3333 %)
low-severe 2 (3.3333 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers

I had similar results on Clojure 1.6.0, and ran several different tests with similar results. java.util.Random.nextInt is suprisingly bad. The ThreadLocalRandom version of .nextInt is better, but rand-int can take negative integers, which would lead to some argument conversion for (.nextInt (ThreadLocalRandom/current) n) since it need upper and lower bounds instead of a simple multiplication of a random number [0,1).

CHANGE:

The (.nextDouble (ThreadLocalRandom/current) argument) is very quick, but cannot handle negative arguments. The speed given a plain multiplication is about 30 ns.

Comment by Linus Ericsson [ 11/May/14 12:44 PM ]

Added some simplistic tests to be sure that rand and rand-int accepts ratios, doubles and negative numbers of various kinds. A real test would likely include repeated generative testing, these tests are mostly for knowing that various arguments works etc.

Comment by Linus Ericsson [ 11/May/14 1:38 PM ]

0001-rand-using-ThreadLocalRandom-and-tests-for-random.patch contains the changed (rand) AND the test cases.

Comment by Alex Miller [ 11/May/14 5:45 PM ]

Clojure requires Java 1.6.0 so this will need to be reconsidered at a later date. We do not currently have any plans to bump the minimum required JDK in Clojure 1.7 although that could change of course.

Comment by Gary Fredericks [ 11/May/14 5:54 PM ]

I've always thought that the randomness features in general are of limited utility due to the inability to seed the PRNG, and that a clojure.core/rand dynamic var would be a reasonable way to do that.

Maybe both of these problems could be partially solved with a standard library? I started one at https://github.com/fredericksgary/four, but presumably a contrib library would be easier for everybody to standardize on.

Comment by Linus Ericsson [ 12/May/14 2:17 AM ]

Gary, I'm all for creating some well-thought out random-library, which could be a candidate for some library clojure.core.random if that would be useful.

Please have a look at http://code.google.com/p/javarng/ since that seems to do what you library four does (and more). Probably we could salvage either APIs, algorithms or both from this library.

I'll contact you via mail!

Comment by Gary Fredericks [ 20/Jun/14 10:21 AM ]

Come to think of it, a rand var in clojure.core shouldn't be a breaking change, so I'll just make a ticket for that to see how it goes. That should at the very least allow solving the concurrency issue with binding. The only objection I can think of is perf issues with dynamic vars?

Comment by Gary Fredericks [ 20/Jun/14 10:42 AM ]

New issue is at CLJ-1452.

Comment by Andy Fingerhut [ 29/Aug/14 4:50 PM ]

Patch 0001-rand-using-ThreadLocalRandom-and-tests-for-random.patch dated May 11 2014 no longer applied cleanly to latest master after some commits were made to Clojure on Aug 29, 2014. It did apply cleanly before that day.

I have not checked how easy or difficult it might be to update this patch. See section "Updating Stale Patches" on this wiki page for some tips on updating patches: http://dev.clojure.org/display/community/Developing+Patches





[CLJ-1415] Keyword cache cleanup incurs linear scan of cache Created: 06/May/14  Updated: 07/Oct/14  Resolved: 01/Aug/14

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

Type: Enhancement Priority: Minor
Reporter: Kyle Kingsbury Assignee: Alex Miller
Resolution: Not Reproducible Votes: 6
Labels: keywords, performance

Attachments: File faster-keywords.diff     File keyword-cache.diff     Text File kw-clean-future.patch     File unified-kw-patch.diff    
Patch: Code
Approval: Vetted

 Description   

If the GC reclaims a keyword, any subsequent attempt to create a keyword requires an O(n) scan over the entire keyword table via Util.clearCache. This is a significant performance cost in keyword-heavy operations; e.g. JSON parsing.

Patch: keyword-cache.diff - patch to defer cleaning till portion of the table is dead and avoid multiple threads cleaning simultaneously.

Patch: kw-clean-future.patch - patch to spin cache cleaning into a future. Found that 1) this introduces some ordering constraints and circularity between Agent and Keyword (fixable) and 2) using the future pool for this means shutdown-agents would always need to be called (in the patch I avoided this by changing agent's soloExecutor to use daemon threads.

Patch: unified-kw-patch.diff - Alternative to keyword-cache and clean-future.patch. Combines all keyword-perf changes, including the EDN kw parser improvement, improved table lookup performance, and has threads cooperate to empty the table refqueue with a minimum of contention.



 Comments   
Comment by Alex Miller [ 06/May/14 5:53 PM ]

Any perf-related ticket will need some clear before/after timings (with good methodology and how to repro) and also a consideration of cases where the change may introduce any perf degradation in normal usage.

Comment by Kyle Kingsbury [ 07/May/14 9:54 PM ]

I've experimented with a patch reducing the cache clearing cost and removing the need for String.intern. Preliminary results are good, but I want to try a few alternative approaches for cache keys. For instance, could we use pure strings like "foo" and "clojure.core/foo" as the cache keys, removing a level of memory indirection? If we're being really sneaky, we could share those same strings with the Symbol _str field to halve our memory use, assuming it's OK to reach in and mutate it.

https://gist.github.com/aphyr/f72e72992dade4578232
http://imgur.com/a/YSgUa#2

Comment by Alex Miller [ 08/May/14 12:29 PM ]

Great start on this - having the perf data is hugely important. One thing I don't see you've covered yet is what the corresponding memory increase you're incurring with CacheKey to get the benefit - we need to quantify both sides of the tradeoff here (latency/throughput vs memory) to fully judge.

Questions/comments on your patch...

1) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L101 - do we need the (o instanceof CacheKey) check? If the usage of this is constrained then we might be able to skip it (and it will blow up on the next line if something is wrong).

2) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L110 - shouldn't we precompute and save the hash code!? The only thing we're making this for is fast hash comparisons. That hash computation is string length dependent - it ain't cheap.

3) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L126 - have you tested with other values here? Should have some justification for this.

4) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L126 - have you tested with other values here? Should have some justification that this is a reasonable number.

5) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L169 - there is a race here (actually more than one if you include getting the tableSize):

Th1: orphansCount = orphans.get()
Th2: orphansCount = orphans.get()
Th2: orphansNew = orphans.getAndSet(0)
Th2: orphansNew > orphansCount -> start cleaning
<huge gc, 10 zillion orphans are created>
Th1: orphansNew = orphans.getAndSet(0)
Th1: orphansNew > orphansCount -> start cleaning

but I guess this is "safe"; we just have multiple threads cleaning in that case.

6) In general it seems pretty sloppy (I don't mean that pejoratively) how the orphans, rq, and cleaning thread are working together and may be out of sync. I get it and I even believe it will work (usually) but I worry about timing issues that I am too dumb to think of.

Is there a simpler strategy? What if every Nth call to intern() cleaned M entries (or up to M% of table)?

7) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L177 - if you made the iterator explicit in this loop, it would be safe to call iterator.remove() instead of table.remove() and I believe that would be faster on CHM.

8) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L198 - could have two versions of this with/without the symbol. Not sure if that would be faster but they might both inline better into their callers then?

9) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L242 - what's the use case for finding an external CacheKey? Fast re-lookup for specialized use? Do we want to commit to this in the API?

Comment by Kyle Kingsbury [ 08/May/14 2:41 PM ]

1) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L101 - do we need the (o instanceof CacheKey) check? If the usage of this is constrained then we might be able to skip it (and it will blow up on the next line if something is wrong).

I'm usually wary of violating equality/hashCode contracts, and this doesn't even appear as a blip on the radar in profiling. I think we could drop it

2) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L110 - shouldn't we precompute and save the hash code!? The only thing we're making this for is fast hash comparisons. That hash computation is string length dependent - it ain't cheap.

It's less memoizable than you might think; each CacheKey is only indexed a few times, and only at query time; it also doesn't help us for equality checks, since those only occur after hashing. I can add a memoizing field for it at the cost of another 32 bits/kw; we'll see how it impacts performance.

3) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L126 - have you tested with other values here? Should have some justification for this.

I experimented with several values on the Clojure test suite, benchmarks, and some real-world hadoop code. Diminishing returns, as you'd expect. 0.1 and 0.5 are essentially identical in runtime tradeoff. We could drop to 0.01 if desired; it'll only make a difference in large (10-100K) extant keyword benchmarks, as far as I can tell.

4) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L126 - have you tested with other values here? Should have some justification that this is a reasonable number.

Same question as #3?

5) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L169 - there is a race here (actually more than one if you include getting the tableSize):

Th1: orphansCount = orphans.get()
Th2: orphansCount = orphans.get()
Th2: orphansNew = orphans.getAndSet(0)
Th2: orphansNew > orphansCount -> start cleaning
<huge gc, 10 zillion orphans are created>
Th1: orphansNew = orphans.getAndSet(0)
Th1: orphansNew > orphansCount -> start cleaning

but I guess this is "safe"; we just have multiple threads cleaning in that case.

Yep. This check is only there as an optimization--and note that if a huge GC occurs, it's likely we want to schedule a followup traversal of the table anyway, because the thread that's already cleaned some of the table has probably missed some subsequently GC'ed elements. The number of concurrently cleaning threads is bounded by the rate of GC churn, and in the most pathological case (sadly, I haven't been able to produce this race experimentally), this degenerates to the old Clojure behavior of every thread doing a full scan.

6) In general it seems pretty sloppy (I don't mean that pejoratively) how the orphans, rq, and cleaning thread are working together and may be out of sync. I get it and I even believe it will work (usually) but I worry about timing issues that I am too dumb to think of.

Is there a simpler strategy? What if every Nth call to intern() cleaned M entries (or up to M% of table)?

Every nth call is just fine, but it degrades more poorly for large tables. In general, I try to lean towards scale-invariant solutions, which is why I aimed to reclaim roughly a tenth of the entries in the map every time. Maybe more, maybe less, depending on CAS retries, delayed threads resetting the counter to zero, etc.

Doing M entries or M% is more tricky; gotta figure out which threads collect what fraction when, how you efficiently access that subsection of the hash, make sure elements don't fall through the cracks, etc.

7) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L177 - if you made the iterator explicit in this loop, it would be safe to call iterator.remove() instead of table.remove() and I believe that would be faster on CHM.

I agree. I figured Rich had a good reason for doing it this way, but if you concur I'll change it.

8) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L198 - could have two versions of this with/without the symbol. Not sure if that would be faster but they might both inline better into their callers then?

I agree. We can do that dispatch statically and cut down on branch misprediction, too.

9) https://gist.github.com/aphyr/f72e72992dade4578232#file-gistfile1-diff-L242 - what's the use case for finding an external CacheKey? Fast re-lookup for specialized use? Do we want to commit to this in the API?

Keep forgetting Java's obsession with encapsulation. I'll privatize.

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

On several of these - 2, 7, 8 - I think those are worth a test. If faster, we should consider.

On 9, I thought maybe you were opening it up so it would be possible to save off a CacheKey and reuse it or something else. If it's not needed externally, then might be good to private-ize CacheKey itself so we can change it later.

Comment by Kyle Kingsbury [ 09/May/14 6:04 PM ]

http://imgur.com/a/1bv3P#0
https://gist.github.com/aphyr/f72e72992dade4578232

These charts show the performance impact of several changes. In order, they are:

1.7                 baseline
kw                  initial patch
kw-static-paths     Separate codepaths for interning symbols vs strings. Iterator
                    .remove for cache cleaning. Fix a bug for null comparisons
                    in CacheKey namespaces. Internal functions now protected, not
                    public. Not much performance impact.
kw-memo-hash        Memoize hashcodes for CacheKeys. Performance is a wash.
kw-string-cachekeys Observing that String.indexOf('/') consumed a significant 
                    fraction of interning time, use a combined "ns/name" string for
                    Cachekeys instead of separate strings. Significant performance 
                    boost in all tests; 40% reduction in median latencies in 1000-
                    kw allocation test, for instance.
kw-string-keys      Use raw strings for CacheKeys. Improves performance by removing
                    a level of memory indirection, even without cached hashcodes.
kw-interned-keys    Intern those strings to reduce memory consumption, sharing
                    them with the underlying symbol's strings. Slightly slower.

Performance is even better now. Creating 1000 keywords median latency changed from 900 to 200 micros; .999s lower, throughput from 4000 to 20,000/second. JSON parsing median latency fell from 170 micros to 100 micros; throughput doubled from 17500 docs/sec to 36,000 docs/sec.

We're still suffering from poor dispersal in ConcurrentHashmap's use of the string hashCode on JDK7/8, but maybe that's a subject for a different patch.

Memory impact is now minimal. We intern every key string in the table, and those strings are interned by the symbols anyway, so they're essentially the same object. For namespaced symbols, we pay a slightly higher cost--forcing the interning of the "ns/name" string instead of deferring it to Symbol.toString() time. For non-namespaced symbols, these strings are interned as a part of the symbol creation process so there's no memory overhead.

At the repl, I tested by allocating and retaining a million keywords:

(def x (mapv keyword (map (partial str "test-kw-") (range 1e6))))

Retained size (bytes)             1.7   string-kw
----------------------------------------------------
Total retained heap        221.    MB  221.    MB
clojure.lang.Symbols       104.820 MB   32.900 MB
clojure.lang.Keywords       24.021 MB   56.049 MB
java.lang.Strings           89.537 MB   81.786 MB
clojure.lang.Keyword class  72.447 MB   72.451 MB

Total memory use is unchanged, but note that clojure.lang.Symbol retains less, since its strings are now shared by the Keyword table. Keywords, by contrast, retains more. Strings and the keyword table are essentially unchanged.

Comment by Kyle Kingsbury [ 09/May/14 6:08 PM ]

I can't figure out how to edit the ticket description, but I updated the same gist with the cumulative changes. Comments welcome!

Comment by Alex Miller [ 09/May/14 9:51 PM ]

Excellent, thanks for the data. I added a group to your auth so I think you should be able to edit descriptions now. If not, let me know. I'll re-review the patch next week. It would be good either at this point or after that to turn this into an actual patch file instead of a gist.

Comment by Kyle Kingsbury [ 12/May/14 4:24 PM ]

I've attached a cumulative patch. It's comprised of 8 commits; one for each stage we've discussed. I can rebase into a single commit if you'd like.

Comment by Alex Miller [ 13/May/14 7:31 AM ]

I would like a single cumulative rebased patch. I hope to have some time to look at it today.

Comment by Alex Miller [ 13/May/14 12:39 PM ]

On another look, I think it would be useful to separate this ticket into two parts - the first is about optimizing keyword creation and lookup to avoid unnecessary work (avoiding symbol creation and interning, using Strings as keys in the cache). The second part is really about optimizing cache clearing. Do you think these can be separated into two tickets?

Regarding the cache clearing part, have you tested a simpler strategy of just counting calls to clearCache() and running the clean scan every N calls? If that was almost as good, I'd be in favor of that over what is in the patch.

The kw-static paths version did not seem to be an improvement - perhaps you should try pulling them back together to simplify the code? Only worth it if there is a real improvement from it.

On the various find methods - if you could retain their ordering and minimize noise in the diffs that would really help make it easier to screen.

Finally, we need to do some tests to verify that we have not altered the performance of using keywords and symbols as keys in a map for lookup.

Comment by Kyle Kingsbury [ 05/Jun/14 2:36 PM ]

> On another look, I think it would be useful to separate this ticket into two parts - the first is about optimizing keyword creation and lookup to avoid unnecessary work (avoiding symbol creation and interning, using Strings as keys in the cache). The second part is really about optimizing cache clearing. Do you think these can be separated into two tickets?

Created dev.clojure.org/jira/browse/CLJ-1439 for reduced intern cost

> Regarding the cache clearing part, have you tested a simpler strategy of just counting calls to clearCache() and running the clean scan every N calls? If that was almost as good, I'd be in favor of that over what is in the patch.

I'm not confident that this work will be merged, so I'm kinda reticent to go off and spend another N hours doing benchmarks.

> The kw-static paths version did not seem to be an improvement - perhaps you should try pulling them back together to simplify the code? Only worth it if there is a real improvement from it.

It was obsoleted by a later commit; only included it in the benchmark because you asked about the perf impact.

> On the various find methods - if you could retain their ordering and minimize noise in the diffs that would really help make it easier to screen.

Done.

> Finally, we need to do some tests to verify that we have not altered the performance of using keywords and symbols as keys in a map for lookup.

This doesn't touch the lookup path; costs are equivalent.

Comment by Alex Miller [ 09/Jun/14 1:53 PM ]

reduced patch with only the keyword cache clearing changes

Comment by Alex Miller [ 09/Jun/14 8:53 PM ]

Patch that spins cache cleaning into a future

Comment by Kyle Kingsbury [ 21/Jul/14 2:20 PM ]

Just as a followup: got bit by this issue again in a data analysis project today: JSON parsing thrashes the reference queue really hard. Merging this patch would definitely be appreciated. Yourkit screenshot here: http://aphyr.com/media/clojure-keyword-refqueue.png

Comment by Kyle Kingsbury [ 21/Jul/14 4:58 PM ]

Oh yeah, once these two are merged, here's a patch that speeds up my EDN parsing-heavy hadoop jobs by 2-3x. Avoids constructing the symbol every time.

--- a/src/jvm/clojure/lang/EdnReader.java
+++ b/src/jvm/clojure/lang/EdnReader.java
@@ -299,10 +299,9 @@ private static Object matchSymbol(String s){
                        return null;
                        }
                boolean isKeyword = s.charAt(0) == ':';
-               Symbol sym = Symbol.intern(s.substring(isKeyword ? 1 : 0));
                if(isKeyword)
-                       return Keyword.intern(sym);
-               return sym;
+                       return Keyword.intern(s.substring(1));
+               return Symbol.intern(s);
                }
        return null;
 }
Comment by Kyle Kingsbury [ 21/Jul/14 6:33 PM ]
public static void clearCache() {
  if(rq.poll() != null) {
    Agent.soloExecutor.submit(new Runnable() {
      public void run() {
        Util.clearCache(rq,table);
      }
    });
  }
}

This spawns literally hundreds of new threads – 30-40 at a time in my workload – which fight over the referencequeue. Also it causes a fair bit of contention on the executor itself during keyword-heavy allocation-all threads have to synchronize on the executor's queue-but that seems secondary to the cost of the cache-clearing threads themselves.

How about adding a single-thread executor to Agent for these sorts of housekeeping jobs?

Comment by Alex Miller [ 21/Jul/14 8:14 PM ]

I actually built another patch that did exactly that but never got around to attaching it; a single-threaded executor reserved solely for cache clearing. I tried actually making it completely independent but I found it was pretty easy for it to fall behind - it needs to be connected into the construction process to avoid blowing the queue up too big.

I have not been able to build an isolated test that actually showed any significant performance difference with just your cache-clearing change (what's currently attached as keyword-cache.diff) and not the other changes. I had many problems getting your test code to run but when I did get something to run I was not able to see any significant difference with just the keyword-cache.diff.

Comment by Kyle Kingsbury [ 22/Jul/14 6:43 PM ]

Managed to eliminate the refqueue contention by having only one thread involved in GCing at a time. Also doesn't require messing with background threads, and is less susceptible to the queue-overflow problem. Since the various extant patches don't apply cleanly on top of each other, I've re-written them in unified-kw-patch.diff, attached. Roughly doubles throughput compared to your patch, at least on a 24-core xeon running openjdk7.

http://aphyr.com/media/clojure-reduced-kw-refqueue-contention.png

Can you please reconsider merging? I've put over a hundred hours into writing, testing, and refining this patchset; it's been stable in production for months and has made a dramatic difference in several of our data-heavy Clojure programs.

Comment by Alex Miller [ 23/Jul/14 10:58 AM ]

Hey Kyle, I appreciate the time you've put into this. However, having a big giant patch tuned on a single use case is not an effective way to evolve the language. We need to separate and describe problems, then explore the solution space for each one, as independently as possible, while considering the impacts on all other use cases.

This particular ticket is concerned solely with the linear cleanup of the reference queue. Can you split out just a patch that deals with this issue? It would be helpful to have a test that demonstrates the performance problem and how this patch address the problem. My testing so far with the prior patch did not demonstrate any improvement.

It would also be helpful to have a squashed version of the complement of the changes related to interning on CLJ-1439 for consideration of that as a separate problem. (And maybe there is further splitting that could be done; I have not looked closely at the interning changes.)

Comment by Alex Miller [ 23/Jul/14 11:00 AM ]

The EdnReader changes, for example, should be a separate ticket.

Comment by Kyle Kingsbury [ 23/Jul/14 12:30 PM ]

Could you at least merge dev.clojure.org/jira/browse/CLJ-1439 first? I split it into a separate ticket over a month ago and these changes depend on it.

Comment by Alex Miller [ 23/Jul/14 1:27 PM ]

I would be happy to consider CLJ-1439 first. Can you update the patch there to be current and focused on the intern/cache?

Comment by Kyle Kingsbury [ 23/Jul/14 2:35 PM ]

The patch is current, and it is focused on the intern/cache.

Comment by Andy Fingerhut [ 01/Aug/14 9:31 PM ]

Kyle, CLJ-1439 was completed today via a commit to Clojure master. That also had the side effect of making all of the currently attached patches no longer apply cleanly. I haven't checked how easy or difficult it might be to update them to apply cleanly.

Comment by Alex Miller [ 01/Aug/14 11:35 PM ]

I am not able to reproduce a performance issue due to a linear scan of the reference queue cache. Obviously the scan occurs but in most cases the scan is comparatively fast and does not seem to be a bottleneck in the tests I've run.

If there is a test that can reproduce this issue (on current master) and demonstrates an improvement with this patch, please reopen the ticket for investigation.





[CLJ-1410] Optimization: allow `set`/`vec` to pass through colls that satisfy `set?`/`vector?` Created: 26/Apr/14  Updated: 05/May/14

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

Type: Enhancement Priority: Minor
Reporter: Peter Taoussanis Assignee: Unassigned
Resolution: Unresolved Votes: 2
Labels: performance

Attachments: File benchmarks.clj     Text File clj1410-bench.txt     Text File CLJ-1410.patch    
Patch: Code
Approval: Triaged

 Description   

set and vec currently reconstruct their inputs even when they are already of the requested type. Since it's a pretty common pattern to call set/vec on an input to ensure its type, this seems like an easy performance win in a common case.

Proposed: Check for set? in set and vec? in vec and return the coll as is if already of the requested type.

Performance:

See attached clj1410-bench.txt for test details :

Input/size Function Original Patched Comment
set/10 set 1.452 µs 0.002 µs 726x faster
set/1000 set 248.842 µs 0.006 µs 41473x faster
vector/10 set 1.288 µs 1.323 µs slightly slower
vector/1000 set 222.992 µs 221.116 µs ~same
set/10 vec 0.614 µs 0.592 µs ~same
set/1000 vec 56.876 µs 55.920 µs ~same
vector/10 vec 0.252 µs 0.007 µs 36x faster
vector/1000 vec 24.428 µs 0.007 µs 3500x faster

As expected, if an instance of the correct type is passed, then the difference is large (with bigger savings for sets which do more work for dupe checking). In cases where the type is different, there is an extra instance? check (which looks to be jit'ed away or negligible). We only see a slower time in the case of passing a small vector to the set function - 3% slower (35 ns). The benefit seems greater than the cost for this change.

Screened by:

More info:

Group discussion: https://groups.google.com/forum/#!topic/clojure-dev/fg4wtqzu0eY



 Comments   
Comment by Alex Miller [ 26/Apr/14 10:18 AM ]

Re:

*Open question*
Would it be better to pass-through arguments that satisfy the general (`set?`,`vec?`) or concrete (`PersistentHashSet`,`PersistentVector`) type?

I don't think there is any question that relying on abstractions via set?/vec? is better than referring to concrete types.

Comment by Alex Miller [ 26/Apr/14 10:20 AM ]

Please add perf difference info in the description. Please also combine the patches into a single patch.

Comment by Peter Taoussanis [ 26/Apr/14 10:52 AM ]

Combined earlier patches, removed docstring changes.

Comment by Peter Taoussanis [ 26/Apr/14 11:39 AM ]

Attached some simple benchmarks. These were run with HotSpot enabled, after a 100k lap warmup.

Google Doc times: http://goo.gl/W7EACR

The `set` benefit can be substantial, and the overhead in non-benefitial cases is negligible.

The effect on `vec` is subtler: the benefit is relatively smaller and the overhead relatively larger.

Comment by Reid McKenzie [ 04/May/14 12:01 PM ]

Patch looks good to me, and I've reproduced the claimed low "worst case" overhead and significant potential savings numbers to within 1ms. +1.

Comment by Alex Miller [ 05/May/14 10:21 AM ]

I added a more extensive set of tests performed using Criterium which should give better insight into single operation performance.





[CLJ-1402] sort-by calls keyfn more times than is necessary Created: 11/Apr/14  Updated: 11/Apr/14

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

Type: Enhancement Priority: Minor
Reporter: Steve Kim Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: performance


 Description   

clojure.core/sort-by evaluates keyfn for every pairwise comparison. This is wasteful when keyfn is expensive to compute.

user=> (def keyfn-calls (atom 0))
#'user/keyfn-calls
user=> (defn keyfn [x] (do (swap! keyfn-calls inc) x))
#'user/keyfn
user=> @keyfn-calls
0
user=> (sort-by keyfn (repeatedly 10 rand))
(0.1647483850582695 0.2836687590331822 0.3222305842748623 0.3850390922996001 0.41965440953966326 0.4777580378736771 0.6051704988802923 0.659376178201709 0.8459820304223701 0.938863131161208)
user=> @keyfn-calls
44


 Comments   
Comment by Steve Kim [ 11/Apr/14 11:46 AM ]

CLJ-99 is a similar issue





[CLJ-1384] clojure.core/set should use transients Created: 15/Mar/14  Updated: 29/Aug/14  Resolved: 29/Aug/14

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

Type: Enhancement Priority: Major
Reporter: Gary Fredericks Assignee: Unassigned
Resolution: Completed Votes: 4
Labels: performance

Attachments: Text File CLJ-1384-p1.patch     Text File CLJ-1384-p2.patch     File set-bench.tar    
Patch: Code
Approval: Ok

 Description   

CLJ-1384-p2 uses transients for both create and createWithCheck. This is consistent with the current implementation for map.

clojure.core/vec calls (more or less) PersistentVector.create(...), which uses a transient vector to build up the result.

clojure.core/set on the other hand, calls PersistentHashSet.create(...), which repeatedly calls .cons on a PersistentHashSet, with all the associated speed/GC issues.

Operation count now w/transients
set 5 1.771924 µs 1.295637 µs
into 5 1.407925 µs 1.402995 µs
set 1000000 2.499264 s 1.196653 s
into 1000000 0.977555 s 1.006951 s

Patch: CLJ-1384-p2.patch
Screened by: Stu



 Comments   
Comment by Gary Fredericks [ 15/Mar/14 10:13 PM ]

PersistentHashSet has six methods for creating sets – one for each combination of {with check, without check} and {array (varargs), List, ISeq}. Each of them does not use transients but could.

I believe clojure.core/set only depends on the (without check, ISeq) version.

Should all of these be changed? Three of them? One of them?

Comment by Andy Fingerhut [ 15/Mar/14 10:21 PM ]

I believe that the 'with check' versions are only intended to be used when reading set literals in Clojure source code, and give an error if there are duplicate elements. If you find examples where those set creation functions are called in other situations, I would be interested to learn about them to find out where my misunderstanding lies, or whether that is a problem with the current code.

If the belief above is correct, I would suggest not changing the 'with check' versions, since their speed isn't as critical.

Comment by Gary Fredericks [ 15/Mar/14 10:23 PM ]

Thanks Andy, I'll submit a patch that changes the three non-checked methods.

Comment by Gary Fredericks [ 15/Mar/14 10:46 PM ]

Attached CLJ-1384-p1.patch, which updates the three non-check create methods.

I also added benchmarks. It's about 2-3 times faster for large collections.

Comment by Ambrose Bonnaire-Sergeant [ 11/Apr/14 11:15 AM ]

Added benchmark suite (set-bench.tar).

FWIW results are similar to gfrederick's on my machine:

Clojure 1.6

Small collections (5 elements)

set averages 1.220601 µs
into averages 1.597991 µs

Large collections (1,000,000 elements)

set averages 2.429066 sec
into averages 1.006249 sec

After transients

Small collections (5 elements)

set averages 999.248325 ns
into averages 1.162889 µs

Large collections (1,000,000 elements)

set averages 1.003792 sec
into averages 889.993185 ms

Add full output to the tar.

Comment by Ghadi Shayban [ 11/Apr/14 11:35 AM ]

CLJ-1192 is related to this, but and Andy seems to be indicating the use of reduce as the means to better performance there.

Comment by Gary Fredericks [ 11/Apr/14 11:41 AM ]

Oh that's a good point about reduce. The difference should only apply to chunked seqs, right? It's worth noting that the benchmarks above used range which creates chunked seqs, so that might be why into looks faster on the large collections?

So this change only makes set act like vec; I think whether either/both of them should use reduce is a different question.





[CLJ-1376] Initialize internal maps to more efficient version Created: 11/Mar/14  Updated: 11/Mar/14

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

Type: Enhancement Priority: Major
Reporter: Alex Miller Assignee: Unassigned
Resolution: Unresolved Votes: 1
Labels: performance


 Description   

In reviewing some hashing stuff, I noticed that there are many places internal to Clojure that use maps initialized with PersistentHashMap.EMPTY. Many of these maps are likely to have a small number of entries such that a PersistentArrayMap might be more efficient.

These are the candidates:

src/jvm/clojure/lang/ARef.java
19:private volatile IPersistentMap watches = PersistentHashMap.EMPTY;

src/jvm/clojure/lang/Compiler.java
3009:				IPersistentMap m = PersistentHashMap.EMPTY;
3819:					       KEYWORDS, PersistentHashMap.EMPTY,
3820:					       VARS, PersistentHashMap.EMPTY,
3964:	IPersistentMap closes = PersistentHashMap.EMPTY;
3977:	IPersistentMap keywords = PersistentHashMap.EMPTY;
3978:	IPersistentMap vars = PersistentHashMap.EMPTY;
5121:                            ,CLEAR_SITES, PersistentHashMap.EMPTY
7259:			       KEYWORDS, PersistentHashMap.EMPTY,
7260:			       VARS, PersistentHashMap.EMPTY
7418:			IPersistentMap opts = PersistentHashMap.EMPTY;
7475:			IPersistentMap fmap = PersistentHashMap.EMPTY;
7522:					       KEYWORDS, PersistentHashMap.EMPTY,
7523:					       VARS, PersistentHashMap.EMPTY,
7912:                            ,CLEAR_SITES, PersistentHashMap.EMPTY

src/jvm/clojure/lang/LispReader.java
755:					RT.map(GENSYM_ENV, PersistentHashMap.EMPTY));

src/jvm/clojure/lang/MultiFn.java
39:	this.methodTable = PersistentHashMap.EMPTY;
41:	this.preferTable = PersistentHashMap.EMPTY;
49:		methodTable = methodCache = preferTable = PersistentHashMap.EMPTY;

src/jvm/clojure/lang/Var.java
48:	final static Frame TOP = new Frame(PersistentHashMap.EMPTY, null);
175:	setMeta(PersistentHashMap.EMPTY);
341:	IPersistentMap ret = PersistentHashMap.EMPTY;

Approach: Two possible approaches - initialize to PersistentArrayMap.EMPTY or call RT.map(). The latter requires function invocation so is slightly slower, but has the benefit of localizing map construction into a single place.






[CLJ-1373] LazySeq should utilize cached hash from its underlying seq. Created: 09/Mar/14  Updated: 20/Mar/14

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

Type: Enhancement Priority: Major
Reporter: Jozef Wagner Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: collections, performance
Environment:

1.6.0 master SNAPSHOT


Attachments: File clj-1373.diff    
Patch: Code
Approval: Triaged

 Description   

Even if underlying seq contains a cached hash, LazySeq computes it every time.

user=> (def a (range 100000))
#'user/a
user=> (time (hash a))
"Elapsed time: 46.904273 msecs"
375952610
user=> (time (hash a)) ;; RECOMPUTE
"Elapsed time: 10.879098 msecs"
375952610
user=> (def b (seq a))
#'user/b
user=> (time (hash b))
"Elapsed time: 10.572522 msecs"
375952610
user=> (time (hash b)) ;; CACHED HASH
"Elapsed time: 0.024927 msecs"
375952610
user=> (def c (lazy-seq b))
#'user/c
user=> (time (hash c))
"Elapsed time: 12.207651 msecs"
375952610
user=> (time (hash c))
"Elapsed time: 10.995798 msecs"
375952610


 Comments   
Comment by Jozef Wagner [ 09/Mar/14 9:20 AM ]

Added patch which checks if underlying seq implements IHashEq and if yes, uses that hash instead of recomputing.





[CLJ-1340] Emit unboxed cohercions from int/long to float/double Created: 05/Feb/14  Updated: 05/Feb/14

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

Type: Enhancement Priority: Minor
Reporter: Christophe Grand Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: enhancement, performance

Attachments: File primitive-cohercion.diff    
Patch: Code

 Description   

Currently when an int or long is used where a float or double is expected, boxed conversion happens instead of emitting [IL]2[FD] instructions.






[CLJ-1334] Improve performance of the bean function with caching Created: 30/Jan/14  Updated: 31/Jan/14  Resolved: 31/Jan/14

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

Type: Enhancement Priority: Minor
Reporter: Ron Pressler Assignee: Unassigned
Resolution: Declined Votes: 0
Labels: performance


 Description   

The bean function is a very useful Java interop feature that provides a read-only view of a Java Bean as a Clojure map.
As it stands, the function performs introspection on the bean's class whenever the function is called. We can, however, cache the mapping from keywords to getters using JDK 7's handy ClassValue. The proposed function will look like this:

(def ^:private ^java.lang.ClassValue bean-class-value
(proxy [java.lang.ClassValue]
[]
(computeValue [c]
(reduce1 (fn [m ^java.beans.PropertyDescriptor pd]
(let [name (. pd (getName))
method (. pd (getReadMethod))
type (.getPropertyType pd)]
(if (and method (zero? (alength (. method (getParameterTypes)))))
(assoc m (keyword name) (fn [x] (clojure.lang.Reflector/prepRet type (. method (invoke x nil)))))
m)))
{}
(seq (.. java.beans.Introspector
(getBeanInfo c)
(getPropertyDescriptors)))))))

(defn bean
"Takes a Java object and returns a read-only implementation of the
map abstraction based upon its JavaBean properties."
{:added "1.0"}
[^Object x]
(let [c (. x (getClass))
pmap (.get bean-class-value c)
v (fn [k] ((pmap k) x))
snapshot (fn []
(reduce1 (fn [m e]
(assoc m (key e) ((val e) x)))
{} (seq pmap)))]
(proxy [clojure.lang.APersistentMap]
[]
(containsKey [k] (contains? pmap k))
(entryAt [k] (when (contains? pmap k) (new clojure.lang.MapEntry k (v k))))
(valAt ([k] (when (contains? pmap k) (v k)))
([k default] (if (contains? pmap k) (v k) default)))
(cons [m] (conj (snapshot) m))
(count [] (count pmap))
(assoc [k v] (assoc (snapshot) k v))
(without [k] (dissoc (snapshot) k))
(seq [] ((fn thisfn [plseq]
(lazy-seq
(when-let [pseq (seq plseq)]
(cons (new clojure.lang.MapEntry (first pseq) (v (first pseq)))
(thisfn (rest pseq)))))) (keys pmap))))))



 Comments   
Comment by Jozef Wagner [ 30/Jan/14 9:25 AM ]

associated discussion

Comment by Alex Miller [ 31/Jan/14 8:45 AM ]

Curious if anyone is using this inside production code? I use it at the REPL when exploring Java stuff sometimes but have never used it inside my actual code.

Comment by Stuart Halloway [ 31/Jan/14 12:28 PM ]

This is a cool idea, but doesn't need to be in core. How about https://github.com/clojure/java.data ?

Comment by Ron Pressler [ 31/Jan/14 12:48 PM ]

This might be good for java.data, and I'm certainly not saying it should be in the core except for the fact that it already is. This is a proposal for a performance improvement of a core function.





[CLJ-1296] locking expressions cause vars to be dereferenced, even if not executed, unless wrapped in let Created: 17/Nov/13  Updated: 18/Apr/14

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

Type: Enhancement Priority: Minor
Reporter: Andy Fingerhut Assignee: Unassigned
Resolution: Unresolved Votes: 1
Labels: performance


 Description   

Description of one example with poor performance discovered by Michał Marczyk in the discussion thread linked below.

The difference between the compiled versions of:

(defn foo [x]
  (if (> x 0)
    (inc x)
    (locking o
      (dec x))))

and

(defn bar [x]
  (if (> x 0)
    (inc x)
    (let [res (locking o
                (dec x))]
      res)))

is quite significant. foo gets compiled to a single class, with invocations handled by a single invoke method; bar gets compiled to a class for bar + an extra class for an inner function which handles the (locking o (dec x)) part – probably very similar to the output for the version with the hand-coded locking-part (although I haven't really looked at that yet). The inner function is a closure, so calling it involves an allocation of a closure object; its ctor receives the closed-over locals as arguments and stores them in two fields (lockee and x). Then they get loaded from the fields in the body of the closure's invoke method etc.

Note: The summary line may be too narrow a description of the root cause, and simply the first example of a case where this issue was noticed and examined. Please make the summary and this description more accurate if you diagnose this issue.

See discussion thread on Clojure group here: https://groups.google.com/forum/#!topic/clojure/x86VygZYf4Y



 Comments   
Comment by Kevin Downey [ 18/Apr/14 2:17 AM ]

maybe it is already clear to others, but this was not immediately clear to me:

the reason

(defn bar [x]
  (if (> x 0)
    (inc x)
    (let [res (locking o
                (dec x))]
      res)))

generates a second class is locking is a macro that contains a try/finally form in it's expansion.

binding the result of a try/finally form to a result (as in the let) would require some real tricky code gen without adding the extra function, so of course the clojure compile adds the extra function.





[CLJ-1295] Speed up dissoc on array-maps Created: 15/Nov/13  Updated: 10/Sep/14

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

Type: Enhancement Priority: Major
Reporter: Andy Fingerhut Assignee: Unassigned
Resolution: Unresolved Votes: 1
Labels: performance

Attachments: File clj-1295-1.diff    
Patch: Code
Approval: Triaged

 Description   

In latest Clojure master as of Nov 15 2013, the method without() in PersistentArrayMap.java first searches for a matching key using indexOf(key) and saves the result in i.

If a matching key was found, the code then copies the old array to the new smaller one, but unnecessarily repeats the comparison of every key in the map to the key being removed, even though its location is already stored in i.



 Comments   
Comment by Andy Fingerhut [ 15/Nov/13 7:05 PM ]

The patch clj-1295-1.diff changes PersistentArrayMap's without() to use System.arraycopy to copy only the necessary parts from the current array to newArray, similar to PersistentHashMap's method removePair().

Benchmark 1 has strings for keys, which are relatively slow to compare to each other.

(def m1 (array-map "abcdef" 1 "abcdeg" 2 "abcdeh" 3 "abcdei" 4))
(time (dotimes [i 100000000] (dissoc m1 "abcdei")))

1.6.0-alpha2 with no changes:
"Elapsed time: 29663.443 msecs"
"Elapsed time: 29490.225 msecs"
"Elapsed time: 29600.138 msecs"
"Elapsed time: 29627.948 msecs"

1.6.0-alpha2 with patch clj-1295-1.diff:
"Elapsed time: 6362.006 msecs"
"Elapsed time: 6121.006 msecs"
"Elapsed time: 6163.377 msecs"
"Elapsed time: 6155.299 msecs"
"Elapsed time: 6395.224 msecs"

Averages about 21% of the run time before the change.

Benchmark 2 has keywords for keys, which are compared via Java ==, so as fast as comparison can get.

(def m2 (array-map :abcdef 1 :abcdeg 2 :abcdeh 3 :abcdei 4))
(time (dotimes [i 100000000] (dissoc m2 :abcdei)))

1.6.0-alpha2 with no changes:
"Elapsed time: 5033.863 msecs"
"Elapsed time: 5028.327 msecs"
"Elapsed time: 5045.019 msecs"
"Elapsed time: 5004.751 msecs"
"Elapsed time: 5039.143 msecs"

1.6.0-alpha2 with patch clj-1295-1.diff:
"Elapsed time: 2874.748 msecs"
"Elapsed time: 2862.878 msecs"
"Elapsed time: 2887.778 msecs"
"Elapsed time: 2874.196 msecs"
"Elapsed time: 2861.807 msecs"

Averages about 57% of the run time before the change.





[CLJ-1289] aset-* and aget perform poorly on multi-dimensional arrays even with type hints. Created: 01/Nov/13  Updated: 14/Feb/14

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

Type: Enhancement Priority: Major
Reporter: Michael O. Church Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: arrays, performance
Environment:

Clojure 1.5.1.

Dependencies: criterium


Attachments: Text File CLJ-1289-p1.patch    
Patch: Code
Approval: Triaged

 Description   

Here's a transcript of the behavior. I don't know for sure that reflection is being done, but the performance penalty (about 1300x) suggests it.

user=> (use 'criterium.core)
nil
user=> (def b (make-array Double/TYPE 1000 1000))
#'user/b
user=> (quick-bench (aget ^"[[D" b 304 175))
WARNING: Final GC required 3.5198021166354323 % of runtime
WARNING: Final GC required 29.172288684474303 % of runtime
Evaluation count : 63558 in 6 samples of 10593 calls.
             Execution time mean : 9.457308 µs
    Execution time std-deviation : 126.220954 ns
   Execution time lower quantile : 9.344450 µs ( 2.5%)
   Execution time upper quantile : 9.629202 µs (97.5%)
                   Overhead used : 2.477107 ns

One workaround is to use multiple agets.

user=> (quick-bench (aget ^"[D" (aget ^"[[D" b 304) 175))
WARNING: Final GC required 40.59820310542545 % of runtime
Evaluation count : 62135436 in 6 samples of 10355906 calls.
             Execution time mean : 6.999273 ns
    Execution time std-deviation : 0.112703 ns
   Execution time lower quantile : 6.817782 ns ( 2.5%)
   Execution time upper quantile : 7.113845 ns (97.5%)
                   Overhead used : 2.477107 ns

Cause: The inlined version only applies to arity 2, and otherwise it reflects.



 Comments   
Comment by Gary Fredericks [ 08/Dec/13 9:28 PM ]

A glance at the source makes it obvious that the hypothesis is correct – the inlined version only applies to arity 2, and otherwise it reflects.

I thought this would be as simple as converting the inline function to be variadic (using reduce), but after trying it I realized this is tricky as you have to generate the correct type hints for each step. E.g., given ^"[[D" the inline function needs to type-hint the intermediate result with ^"[D". This isn't difficult if we're just dealing with strings that begin with square brackets, but I don't know for sure that those are the only possibilities.

Comment by Yaron Peleg [ 13/Feb/14 4:44 AM ]

Bump. I just got bitten bad by this.

There are two seperate issues here:
1) (aget 2d-array-doubles 0 0 ) doesn't emit a reflection warning.
2) It seems like the compiler has enough information to avoid the reflective call here.

Note this gets exp. worse as number of dimensions grows, i.e (get doubles3d 0 0 0)
will be 1M slower, etc' Not true, unless you iterate over all elements. it's
simply n_dims*1000x per lookup.

Nasty surprise, especially considering you often go to primitive arrays for speed,
and a common use case is an inner loop(s) that iterate over arrays.

Comment by Gary Fredericks [ 13/Feb/14 7:08 AM ]

I can probably take a stab at this.

Comment by Gary Fredericks [ 13/Feb/14 8:34 PM ]

I think the reflection warning problem is pretty much impossible to solve without changing code elsewhere in the compiler, because the reflection done in aget is a different kind than normal clojure reflection – it's explicitly in the function body rather than emitted by the compiler. Since the compiler isn't emitting it, it doesn't reasonably know it's even there. So even if aget is fixed for other arities, you still won't get the warning when it's not inlined.

I can imagine some sort of metadata that you could put on a function telling the compiler that it will reflect if not inlined. Or maybe a more generic not-inlined warning?

The global scope of adding another compiler flag seems about balanced by the seriousness of array functions not being able to warn on reflection.

Comment by Gary Fredericks [ 13/Feb/14 8:52 PM ]

Attached CLJ-1289-p1.patch which simply inlines variadic calls to aget. It assumes that if it sees a :tag on the array arg that is a string beginning with [, it can assume that the return value from one call to aget can be tagged with the same string with the leading [ stripped off.

I'm not a jvm expert, but having read through the spec a little bit I think this is a reasonable assumption.

Comment by Alex Miller [ 14/Feb/14 3:34 PM ]

I think this probably is actually true, but a more official way to ask that question would be to get the array class and ask for Class.getComponentType() (and less janky than string munging).

Comment by Gary Fredericks [ 14/Feb/14 3:40 PM ]

How would you get the array class based on the :tag type hint?

Comment by Gary Fredericks [ 14/Feb/14 7:05 PM ]

I see (-> s (Class/forName) (.getComponentType) (.getName)) does the same thing – is that route preferred, or is there another one?





[CLJ-1288] aset-* and aget: on multi-dimensional arrays (e.g. double[][]) these fn reflect (and, thus, perf. poorly) even with type hints. Created: 01/Nov/13  Updated: 01/Nov/13  Resolved: 01/Nov/13

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

Type: Defect Priority: Minor
Reporter: Michael O. Church Assignee: Unassigned
Resolution: Duplicate Votes: 0
Labels: arrays, performance
Environment:

Clojure 1.5.1.

Dependencies: criterium



 Description   

Here's a transcript of the behavior. I don't know for sure that reflection is being done, but the performance penalty (about 1300x) suggests it.

user=> (use 'criterium.core)
nil
user=> (def b (make-array Double/TYPE 1000 1000))
#'user/b
user=> (quick-bench (aget ^"[[D" b 304 175))
WARNING: Final GC required 3.5198021166354323 % of runtime
WARNING: Final GC required 29.172288684474303 % of runtime
Evaluation count : 63558 in 6 samples of 10593 calls.
Execution time mean : 9.457308 µs
Execution time std-deviation : 126.220954 ns
Execution time lower quantile : 9.344450 µs ( 2.5%)
Execution time upper quantile : 9.629202 µs (97.5%)
Overhead used : 2.477107 ns
nil

A (n ugly) workaround is to use multiple agets.

user=> (quick-bench (aget ^"[D" (aget ^"[[D" b 304) 175))
WARNING: Final GC required 40.59820310542545 % of runtime
Evaluation count : 62135436 in 6 samples of 10355906 calls.
Execution time mean : 6.999273 ns
Execution time std-deviation : 0.112703 ns
Execution time lower quantile : 6.817782 ns ( 2.5%)
Execution time upper quantile : 7.113845 ns (97.5%)
Overhead used : 2.477107 ns
nil



 Comments   
Comment by Alex Miller [ 01/Nov/13 1:09 PM ]

Dupe of CLJ-1289.





[CLJ-1277] Speed up printing of time instants by adding type hints Created: 10/Oct/13  Updated: 03/Oct/14

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

Type: Enhancement Priority: Major
Reporter: Andy Fingerhut Assignee: Unassigned
Resolution: Unresolved Votes: 1
Labels: ft, performance

Attachments: Text File clj-1277-1.txt    
Patch: Code
Approval: Triaged

 Description   

There are several occurrences of reflection in instant.clj that slow down the printing of time instants.

Clojure Google group conversation link: https://mail.google.com/mail/u/0/?shva=1#label/clojure/1419e1e6f6cc5b3d

The addition of a few type hints is enough to speed the printing of time instants by a factor of about 3 to 4.5, in a few small benchmarks.

Patch: clj-1277-1.txt
Screened by: Alex Miller



 Comments   
Comment by Andy Fingerhut [ 10/Oct/13 12:07 AM ]

Patch clj-1277-1.txt adds 4 type hints that eliminate all reflection occurrences in source file instant.clj. Benchmarks show that it speeds up printing of java.util.Date and java.sql.Timestamp objects by a factor of about 3 to 4.5.

Latest Clojure master as of Oct 9 2013:

user=> (time (let [d (java.util.Date.)] (dotimes [i 3000000] (pr-str d))))
"Elapsed time: 24094.282 msecs"
user=> (import 'java.sql.Timestamp)
user=> (time (let [d (java.sql.Timestamp. 1300000000000)] (dotimes [i 2000000] (pr-str d))))
"Elapsed time: 20856.957 msecs"

That version of Clojure plus the patch clj-1277-1.txt:

user=> (time (let [d (java.util.Date.)] (dotimes [i 3000000] (pr-str d))))
"Elapsed time: 5085.847 msecs"
user=> (time (let [d (java.sql.Timestamp. 1300000000000)] (dotimes [i 2000000] (pr-str d))))
"Elapsed time: 7582.233 msecs"

Comment by Alexander Kiel [ 10/Oct/13 4:54 AM ]

Thanks for the patch Andy. But I don't like the (set! warn-on-reflection true). I think its better to use it only in the dev profile in leiningen. Not in real production code.

Comment by Andy Fingerhut [ 10/Oct/13 4:06 PM ]

Alexander, Leiningen is not used for building Clojure itself. The two supported choices are Maven and ant. Several Clojure source files, e.g. core/protocols.clj and core/reducers.clj, set warn-on-reflection to true, I believe so that if code is changed in such a way as to introduce a warning, it will be caught more quickly.

If the screeners or Rich think it is inappropriate, it is easy enough to remove.

Comment by Alex Miller [ 10/Oct/13 4:48 PM ]

Setting that is not uncommon in core clojure code and seems fine to me here.





[CLJ-1266] Better primitive support for floats Created: 26/Sep/13  Updated: 05/Feb/14

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

Type: Enhancement Priority: Minor
Reporter: Christophe Grand Assignee: Unassigned
Resolution: Unresolved Votes: 1
Labels: performance

Attachments: File floats.diff     File floats-intrinsics.diff    
Patch: Code

 Description   

Clojure offers optimized arithmetic functions for long, int and doubles but none for floats.
Plus converting from integers (ints or longs) to floating point numbers (float or double) doesn't use the specialized bytecode.
This patch adds float-add/subtract/multiply/divide and more efficient coversion from integers to floating points numbers.



 Comments   
Comment by Alex Miller [ 05/Feb/14 12:29 PM ]

I think it's unlikely the arithmetic float ops will be accepted.
However, the intrinsics changes could be useful - could you split those into a new ticket?

Comment by Christophe Grand [ 05/Feb/14 4:20 PM ]

I attached a new patch with only intrinsics and more comprehensive primitive coercion. Is it the split you expected?

Comment by Alex Miller [ 05/Feb/14 5:22 PM ]

No, but totally my fault for saying the wrong words.

I think the changes in Compiler to get access to I2D, L2D, I2F, and L2F are potentially useful (most particularly L2D) - these would make sense in a new ticket.

The other changes in Intrinsics and Numbers to support float math are unlikely to be accepted.

Comment by Christophe Grand [ 05/Feb/14 5:40 PM ]

Godd thing I had already split coercions in a sparate commit then

See http://dev.clojure.org/jira/browse/CLJ-1340





[CLJ-1259] Speed up pprint Created: 09/Sep/13  Updated: 03/Oct/14

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

Type: Enhancement Priority: Major
Reporter: Andy Fingerhut Assignee: Unassigned
Resolution: Unresolved Votes: 1
Labels: ft, performance, print

Attachments: Text File clj-1259-1.txt    
Patch: Code
Approval: Triaged

 Description   

There are many occurrences of reflection in the pprint implementation.

By eliminating all of them, I ran one benchmark of pprint'ing a Clojure map that resulted in a 300 Kbyte output. After eliminating reflection, the elapsed time to pprint was reduced by 18% (about 14.0 sec down to about 11.5 sec) on a recent model MacBook Pro.

Patch: clj-1277-1.txt
Screened by: Alex Miller



 Comments   
Comment by Andy Fingerhut [ 09/Sep/13 11:36 PM ]

Patch clj-1259-1.txt eliminates all occurrences of reflection in pprint, and all files loaded from pprint.clj. It also sets warn-on-reflection to true for those files, in hopes of making it more obvious if a new use of reflection is added there.





[CLJ-1224] Records do not cache hash like normal maps Created: 24/Jun/13  Updated: 06/Oct/14

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

Type: Enhancement Priority: Major
Reporter: Brandon Bloom Assignee: Unassigned
Resolution: Unresolved Votes: 9
Labels: defrecord, performance

Attachments: Text File 0001-cache-hasheq-and-hashCode-for-records.patch    
Patch: Code
Approval: Vetted

 Description   

Records do not cache their hash codes like normal Clojure maps, which affects their performance. This problem has been fixed in CLJS, but still affects JVM CLJ.

Approach: Cache hash values in record definitions, similar to maps.

Patch: 0001-CLJ-1224-cache-hasheq-and-hashCode-for-records.patch

Also see: http://dev.clojure.org/jira/browse/CLJS-281



 Comments   
Comment by Nicola Mometto [ 14/Feb/14 5:46 PM ]

I want to point out that my patch breaks ABI compatibility.
A possible approach to avoid this would be to have 3 constructors instead of 2, I can write the patch to support this if desired.

Comment by Stuart Halloway [ 27/Jun/14 11:09 AM ]

The patch 0001-CLJ-1224-cache-hasheq-and-hashCode-for-records.patch is broken in at least two ways:

  • The fields __hash and __hasheq are adopted by new records created by .assoc and .without, which will cause those records to have incorrect (and likely colliding) hash values
  • The addition of the new fields breaks the promise of defrecord, which includes an N+2 constructor taking meta and extmap. With the patch, defrecords get an N+4 constructor letting callers pick hash codes.

I found these problems via the following reasoning:

  • Code has been touched near __extmap
  • Grep for all uses of __extmap and see what breaks
Comment by Nicola Mometto [ 27/Jun/14 2:53 PM ]

Patch 0001-cache-hasheq-and-hashCode-for-records.patch fixes both those issues, reintroducing the N+2 arity constructor

Comment by Alex Miller [ 27/Jun/14 4:08 PM ]

Questions addressed, back to Vetted.

Comment by Andy Fingerhut [ 29/Aug/14 4:32 PM ]

All patches dated Jun 7 2014 and earlier no longer applied cleanly to latest master after some commits were made to Clojure on Aug 29, 2014. They did apply cleanly before that day.

I have not checked how easy or difficult it might be to update this patch.

Comment by Alex Miller [ 29/Aug/14 4:40 PM ]

Would be great to get this one updated as it's otherwise ready to screen.

Comment by Nicola Mometto [ 29/Aug/14 4:58 PM ]

Updated patch to apply to lastest master





[CLJ-1192] vec function is substantially slower than into function Created: 06/Apr/13  Updated: 24/Oct/14  Resolved: 24/Oct/14

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

Type: Enhancement Priority: Major
Reporter: Luke VanderHart Assignee: Unassigned
Resolution: Duplicate Votes: 0
Labels: performance

Approval: Incomplete

 Description   

(vec coll) and (into [] coll) do exactly the same thing. However, due to into using transients, it is substantially faster. On my machine:

(time (dotimes [_ 100] (vec (range 100000))))
"Elapsed time: 732.56 msecs"

(time (dotimes [_ 100] (into [] (range 100000))))
"Elapsed time: 491.411 msecs"

This is consistently repeatable.

Since vec's sole purpose is to transform collections into vectors, it should do so at the maximum speed available.



 Comments   
Comment by Andy Fingerhut [ 07/Apr/13 5:50 PM ]

I am pretty sure that Clojure 1.5.1 also uses transient vectors for (vec (range n)) (probably also some earlier versions of Clojure, too).

Look at vec in core.clj. It checks whether its arg is a java.util.Collection, which lazy seqs are, so calls (clojure.lang.LazilyPersistentVector/create coll).

LazilyPersistentVector's create method checks whether its argument is an ISeq, which lazy seqs are, so it calls PersistentVector.create(RT.seq(coll)).

All 3 of PersistentVector's create() methods use transient vectors to build up the result.

I suspect the difference in run times are not because of transients or not, but because of the way into uses reduce, and perhaps may also have something to do with the perhaps-unnecessary call to RT.seq in LazilyPersistentVector's create method (in this case, at least – it is likely needed for other types of arguments).

Comment by Alan Malloy [ 14/Jun/13 2:17 PM ]

I'm pretty sure the difference is that into uses reduce: since reducers were added in 1.5, chunked sequences know how to reduce themselves without creating unnecessary cons cells. PersistentVector/create doesn't use reduce, so it has to allocate a cons cell for each item in the sequence.

Comment by Gary Fredericks [ 08/Sep/13 1:55 PM ]

Is there any downside to (defn vec [coll] (into [] coll)) (or the inlined equivalent)?

Comment by Ghadi Shayban [ 11/Apr/14 5:13 PM ]

While I agree that there are improvements and possibly low-hanging fruit, FWIW https://github.com/clojure/tools.analyzer/commit/cf7dda81a22f4c9c1fe64c699ca17e7deed61db4#commitcomment-5989545

showed a 5% slowdown from a few callsites in tools.analyzer.

This ticket's benchmark is incomplete in that it covers a single type of argument (chunked range), and flawed as it timing the expense of realizing the range. (That could be a legit benchmark case, but it shouldn't be the only one).

Sorry to rain on a parade. I promise like speed too!

Comment by Greg Chapman [ 25/Apr/14 5:23 PM ]

One thing to note is that vec has a subtle difference from into when the collection is an Object array of length <= 32. In that case, vec aliases the supplied array, rather than copying it (this is noted in the warning here: http://clojuredocs.org/clojure_core/clojure.core/vec). I believe I read some place that this behavior is intentional, but I can't find the citation.

Comment by Andy Fingerhut [ 25/Apr/14 10:18 PM ]

Greg, CLJ-893 might be what you remember. That is the ticket that was closed by a patch updating the documentation of vec.

Comment by Mike Anderson [ 18/May/14 7:41 AM ]

I think there are quite a few performance improvements that can be made to vec in general. For example, if given a List it should use PersistentVector.create(List) rather than producing an unnecessary seq, which appears to be the case at the moment. Also it should probably return the same object if passed an existing IPersistentVector.

Basically there are a number of cases that we could be handling more efficiently....

I'm taking a look at this now.... will propose a quick patch if it seems there is a good solution.

Comment by Mike Anderson [ 24/Jul/14 4:01 AM ]

I've looked at this issue and it is quite complex. There are multiple types that need to potentially be converted into vectors, and doing so efficiently will often require making use of reduce-style operations on the source collections.

Doing this efficiently will probably in turn require making use of the IReduce interface, which doesn't yet seem to be fully utilised across the Clojure code based. If we do this, lots of operations (not just vec!) can be made faster but it will be quite a major change.

I have a branch that implements some of this but would appreciate feedback if this is the right direction before I take it any further:
https://github.com/mikera/clojure/tree/clj-1192-vec-performance

Comment by Alex Miller [ 24/Jul/14 9:45 AM ]

Thanks Mike! It may take a few days before I can get back to you about this.

Comment by Mike Anderson [ 25/Jul/14 3:44 AM ]

Basically the approach I am proposing is:

  • Make various collections implement IReduce efficiently (if they don't already). Especially applied to chunked seqs etc.
  • Have RT.reduce(...) methods that implement reduce on the Java side
  • Make the Clojure side use IReduce where relevant (should be as simple as extending the existing protocols)
  • Implement vec (and other similar operations) in terms of IReduce - which will solve this specific issue

If we really care about pushing vector performance even further, we can also consider:

  • Create specialised small vector types where appropriate - e.g. a specialised SmallPersistentVector class for <32 elements. This should outperform the more generic PersistentVector which is better suited for large vectors.
  • Some dedicated construction functions that know how to efficiently exploit knowledge about the data source (e.g. creating a vec from a segment of a big Object array can be done with a bunch of arraycopys into 32-element chunks and then constructing a PersistentVector around these)

This should give us a decent speedup overall (of course it would need benchmarking... but I'd hope to see some sort of measurable improvement on a macro benchmark like building and testing Clojure).

Comment by Alex Miller [ 24/Oct/14 8:36 AM ]

I believe this will be covered by a combination of CLJ-1546 (which makes vec work in more cases and faster on everything but chunked seqs) and CLJ-1515 (which will make the primary chunked seq use case of range faster) so marking as a dupe. After those are done, would consider more targeted ticket for whatever case is left.





[CLJ-1096] Make destructuring emit direct keyword lookups Created: 29/Oct/12  Updated: 06/Jun/14

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

Type: Enhancement Priority: Major
Reporter: Christophe Grand Assignee: Christophe Grand
Resolution: Unresolved Votes: 2
Labels: performance

Attachments: File desctructure-keyword-lookup.diff     File inline-get-keyword.diff    
Patch: Code
Approval: Triaged

 Description   

Currently associative destructuring emits calls to get. The attached patch modify desctruture to emit direct keyword lookups when possible.

Approved here https://groups.google.com/d/msg/clojure-dev/MaYcHQck8VA/nauMus4mzPgJ



 Comments   
Comment by Christophe Grand [ 04/Sep/13 3:40 AM ]

Rethinking about this patch now, it may be too specific: get's inline expansion should be modified when the key is a literal keyword.

Comment by Christophe Grand [ 04/Sep/13 3:41 AM ]

More generic patch (inline-get-keyword.diff): all get calls with literal keywords as keys are inlined to direct keyword lookup.

Comment by John Hume [ 19/May/14 1:14 PM ]

Is this only stalled out of lack of interest?

Comment by Andy Fingerhut [ 19/May/14 6:13 PM ]

There are currently about 50 tickets "triaged", i.e. marked for Rich to look at and decide whether they are things he is interested in seeing a patch for, and another 25 or so that were triaged and he has "vetted" them, and they are in various stages of having patches written for them, screened, etc. That doesn't mean anything for this ticket in particular – just wanted to make it clear that there are a bunch of other tickets that are getting some attention, and a bunch of others that are not.

What gets triaged depends somewhat upon how severe the issue appears. You can vote on the ticket, and try to persuade others to do so as well, if they think this would enhance the performance of some commonly-written types of Clojure code. You could also consider doing some benchmarking with & without these patches to see how much performance they can gain.





[CLJ-1090] Indirect function calls through Var instances fail to clear locals Created: 22/Oct/12  Updated: 25/Oct/13  Resolved: 25/Oct/13

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

Type: Defect Priority: Minor
Reporter: Spencer Tipping Assignee: Unassigned
Resolution: Completed Votes: 0
Labels: performance
Environment:

Probably all, but observed on Ubuntu 12.04, OpenJDK 6


Attachments: File var-clear-locals.diff     File var-clear-locals-patch-v2.diff     Text File var-clear-locals-patch-v2.txt    
Patch: Code
Approval: Ok

 Description   

If you make a function call indirectly by invoking a Var object (which derefs itself and invokes the result), the invocation parameters remain in the thread's local stack for the duration of the function call, even though they are needed only long enough to be passed into the deref'd function. As a result, passing a lazy seq into a function invoked in its Var form may run out of memory if the seq is forced inside that function. For example:

(defn total [xs] (reduce + 0 xs))
(total (range 1000000000))   ; this works, though takes a while
(#'total (range 1000000000)) ; this dies with out of memory error

Solution: Similar to RestFn, wrap each argN in Var inside a Util.ret1(argN, argN = null).

Patch: var-clear-locals-patch-v2.diff

Screened by: Alex Miller



 Comments   
Comment by Spencer Tipping [ 23/Oct/12 1:37 PM ]

Sorry, I typo'd the example. (defn total ...) should be (defn sum ...).

Comment by Timothy Baldridge [ 27/Nov/12 11:45 AM ]

fixed typeo in example

Comment by Timothy Baldridge [ 27/Nov/12 11:47 AM ]

Couldn't reproduce the exception, but the 2nd example did chew through about 4x the amount of memory. Vetting.

Comment by Timothy Baldridge [ 29/Nov/12 2:57 PM ]

adding a patch. Since most of Clojure ends up running this code in one way or another, I'd assert that tests are included as part of the normal Clojure test process.

Patch simply calls Util.ret1(argx, argx=null) on all invoke calls.

Comment by Timothy Baldridge [ 29/Nov/12 3:17 PM ]

And as a note, both examples in the original report now have extremely similar memory usages.

Comment by Spencer Tipping [ 30/Nov/12 2:22 PM ]

Sounds great, and the patch looks good too. Let me know if I need to do anything else.

Comment by Alex Miller [ 22/Aug/13 10:35 PM ]

Switching back to Triaged as afaict Rich has not Vetted this one.

Comment by Andy Fingerhut [ 05/Sep/13 6:18 PM ]

Patch var-clear-locals-patch-v2.txt is identical to var-clear-locals.diff (and preserves credit to its author), except it eliminates trailing whitespace in some added lines that cause git to give warnings when applying the patch.





[CLJ-1087] clojure.data/diff uses set union on key seqs Created: 15/Oct/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: Tom Jack Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: performance

Attachments: Text File clj-1087-diff-perf-enhance-patch-v1.txt    
Patch: Code

 Description   

clojure.data/diff, on line 118, defines:

java.util.Map
(diff-similar [a b]
  (diff-associative a b (set/union (keys a) (keys b))))

Since keys returns a key seq, this seems like an error. clojure.set/union has strange and inconsistent behavior with regard to non-sets, and in this case the two key seqs are concatenated. Based on a cursory benchmark, it seems that this bug is a slight performance gain when the maps have no common keys, and a significant performance loss when the maps have the same keys. The results are still correct because of the merging reduce in diff-associative.

The patch is easy (just call set on each key seq).



 Comments   
Comment by Andy Fingerhut [ 15/Oct/12 2:52 PM ]

clj-1087-diff-perf-enhance-patch-v1.txt dated Oct 15 2012 implements Tom's suggested performance enhancement, although not exactly in the way he suggested. It does calculate the union of the two key sequences.





[CLJ-1080] Eliminate many uses of reflection in Clojure code Created: 30/Sep/12  Updated: 10/Oct/13

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

Type: Enhancement Priority: Minor
Reporter: Andy Fingerhut Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: performance, typehints

Attachments: Text File clj-1080-v5.txt    
Patch: Code

 Description   

There are dozens of uses of reflection in Clojure code that can be eliminated by adding suitable type hints. This patch adds the necessary type hints for most of those.



 Comments   
Comment by Andy Fingerhut [ 30/Sep/12 11:39 AM ]

Patch clj-1080-eliminate-many-reflection-warnings-patch-v1.txt dated Sep 30 2012 adds type hints to eliminate many uses of reflection in Clojure core code.

Comment by Andy Fingerhut [ 14/Nov/12 1:26 PM ]

clj-1080-eliminate-many-reflection-warnings-patch-v2.txt dated Nov 14 2012 is identical to the previous patch (to be removed soon), except it applies cleanly to latest master.

Comment by Andy Fingerhut [ 07/Feb/13 8:54 AM ]

clj-1080-eliminate-many-reflection-warnings-patch-v3.txt dated Feb 7 2013 is identical to the previous patch (to be removed soon), except it applies cleanly to latest master. One type hint in the patch was added due to a different change, and was no longer needed in the patch.

Comment by Andy Fingerhut [ 09/Sep/13 11:37 PM ]

Patch clj-1080-v4.txt eliminates many, but not all, uses of reflection. To avoid overlap with CLJ-1259, it does not touch pprint or any of the files loaded from pprint.clj. See CLJ-1259 for those.

Comment by Andy Fingerhut [ 10/Oct/13 12:22 AM ]

Patch clj-1080-v5.txt eliminates many, but not all, uses of reflection. It does not touch pprint or any of the files loaded from pprint.clj – see CLJ-1259 for those. Similarly see CLJ-1277 for elimination of reflection in instant.clj





[CLJ-1050] Remove a lock in the common case of deref of delay Created: 26/Aug/12  Updated: 18/Sep/12  Resolved: 18/Sep/12

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

Type: Enhancement Priority: Trivial
Reporter: Nicolas Oury Assignee: Unassigned
Resolution: Declined Votes: 0
Labels: enhancement, patch, performance

Attachments: Text File 0001-No-lock-in-the-common-path-for-delays.patch    

 Description   

Currently, when deref is called in Delay.java, a lock on the Delay is always acquired.
This is wasteful as most of the time you just want to read the val.

The attached patch changes this behaviour to the following:

  • val is initialised to a known secret value. (During its constructor so it is visible from any thread).
  • When deref is called, val is checked to the known secret value.
  • If it is not the secret value, then it has to be the value computed by the function and we return it.
  • If it is the secret value, then we lock this object and revert to the current behaviour.

This is faster than what is done currently and can be very much faster if there is contention on the delay.



 Comments   
Comment by Nicolas Oury [ 27/Aug/12 2:37 AM ]

Please close and reject. The patch is not working if val has non final fields.





[CLJ-1005] Use transient map in zipmap Created: 30/May/12  Updated: 26/Sep/14

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

Type: Enhancement Priority: Major
Reporter: Michał Marczyk Assignee: Unassigned
Resolution: Unresolved Votes: 10
Labels: performance

Attachments: Text File 0001-Use-transient-map-in-zipmap.2.patch     Text File 0001-Use-transient-map-in-zipmap.patch     Text File 0002-CLJ-1005-use-transient-map-in-zipmap.patch     Text File CLJ-1005-zipmap-iterators.patch    
Patch: Code
Approval: Vetted

 Description   

The attached patch changes zipmap to use a transient map internally. The definition is also moved so that it resides below that of #'transient. The original definition is commented out (like that of #'into).



 Comments   
Comment by Aaron Bedra [ 14/Aug/12 9:24 PM ]

Why is the old implementation left and commented out? If we are going to move to a new implementation, the old one should be removed.

Comment by Michał Marczyk [ 15/Aug/12 4:17 AM ]

As mentioned in the ticket description, the previously attached patch follows the pattern of into whose non-transient-enabled definition is left in core.clj with a #_ in front – I wasn't sure if that's something desirable in all cases.

Here's a new patch with the old impl removed.

Comment by Andy Fingerhut [ 15/Aug/12 10:37 AM ]

Thanks for the updated patch, Michal. Sorry to raise such a minor issue, but would you mind using a different name for the updated patch? I know JIRA can handle multiple attached files with the same name, but my prescreening code isn't quite that talented yet, and it can lead to confusion when discussing patches.

Comment by Michał Marczyk [ 15/Aug/12 10:42 AM ]

Thanks for the heads-up, Andy! I've reattached the new patch under a new name.

Comment by Andy Fingerhut [ 16/Aug/12 8:24 PM ]

Presumptuously changing Approval from Incomplete back to None after the Michal's updated patch was added, addressing the reason the ticket was marked incomplete.

Comment by Aaron Bedra [ 11/Apr/13 5:32 PM ]

The patch looks good and applies cleanly. Are there additional tests that we should run to verify that this is providing the improvement we think it is. Also, is there a discussion somewhere that started this ticket? There isn't a lot of context here.

Comment by Michał Marczyk [ 11/Apr/13 6:19 PM ]

Hi Aaron,

Thanks for looking into this!

From what I've been able to observe, this change hugely improves zipmap times for large maps. For small maps, there is a small improvement. Here are two basic Criterium benchmarks (transient-zipmap defined at the REPL as in the patch):

;;; large map
user=> (def xs (range 16384))
#'user/xs
user=> (last xs)
16383
user=> (c/bench (zipmap xs xs))
Evaluation count : 13920 in 60 samples of 232 calls.
             Execution time mean : 4.329635 ms
    Execution time std-deviation : 77.791989 us
   Execution time lower quantile : 4.215050 ms ( 2.5%)
   Execution time upper quantile : 4.494120 ms (97.5%)
nil
user=> (c/bench (transient-zipmap xs xs))
Evaluation count : 21180 in 60 samples of 353 calls.
             Execution time mean : 2.818339 ms
    Execution time std-deviation : 110.751493 us
   Execution time lower quantile : 2.618971 ms ( 2.5%)
   Execution time upper quantile : 3.025812 ms (97.5%)

Found 2 outliers in 60 samples (3.3333 %)
	low-severe	 2 (3.3333 %)
 Variance from outliers : 25.4675 % Variance is moderately inflated by outliers
nil

;;; small map
user=> (def ys (range 16))
#'user/ys
user=> (last ys)
15
user=> (c/bench (zipmap ys ys))
Evaluation count : 16639020 in 60 samples of 277317 calls.
             Execution time mean : 3.803683 us
    Execution time std-deviation : 88.431220 ns
   Execution time lower quantile : 3.638146 us ( 2.5%)
   Execution time upper quantile : 3.935160 us (97.5%)
nil
user=> (c/bench (transient-zipmap ys ys))
Evaluation count : 18536880 in 60 samples of 308948 calls.
             Execution time mean : 3.412992 us
    Execution time std-deviation : 81.338284 ns
   Execution time lower quantile : 3.303888 us ( 2.5%)
   Execution time upper quantile : 3.545549 us (97.5%)
nil

Clearly the semantics are preserved provided transients satisfy their contract.

I think I might not have started a ggroup thread for this, sorry.

Comment by Andy Fingerhut [ 03/Sep/14 8:10 PM ]

Patch 0001-Use-transient-map-in-zipmap.2.patch dated Aug 15 2012 does not apply cleanly to latest master after some commits were made to Clojure on Sep 3 2014.

I have not checked whether this patch is straightforward to update. See the section "Updating stale patches" at http://dev.clojure.org/display/community/Developing+Patches for suggestions on how to update patches.

Comment by Michał Marczyk [ 14/Sep/14 12:48 PM ]

Thanks, Andy. It was straightforward to update – an automatic rebase. Here's the updated patch.

Comment by Ghadi Shayban [ 22/Sep/14 9:58 AM ]

New patch using clojure.lang.RT/iter, criterium shows >30% more perf in the best case. Less alloc probably but I didn't measure. CLJ-1499 (better iterators) is related





[CLJ-1000] Performance drop in PersistentHashMap.valAt(...) in v.1.4 -- Util.hasheq(...) ? Created: 21/May/12  Updated: 01/Mar/13  Resolved: 11/Dec/12

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

Type: Enhancement Priority: Major
Reporter: Oleksandr Shyshko Assignee: Timothy Baldridge
Resolution: Completed Votes: 1
Labels: performance
Environment:

Java(TM) SE Runtime Environment (build 1.7.0_04-b21)
Java HotSpot(TM) 64-Bit Server VM (build 23.0-b21, mixed mode)


Attachments: File caching-hasheq-v3.diff     PNG File clj_13.png     PNG File clj_14.png    
Patch: Code
Approval: Ok

 Description   

It seems there is a 30-40% performance degradation of PersistentHashMap.valAt(...) in Clojure 1.4.
Possibly due to references to new CPU-hungry implementation of Util.hasheq(...).

I have created a demo project with more details and some profiling information here:
https://github.com/oshyshko/clj-perf



 Comments   
Comment by Christophe Grand [ 27/Nov/12 8:30 AM ]

I added a patch consisting of three commits:

  • one which adds caching to seqs, sets, maps, vectors and queues
  • one that aligns the shape of Util/hasheq on the one Util/equiv (to have a consistent behavior from the JIT compiler: without that deoptimization was more penalizing for hasheq than for equiv)
  • one that fix hasheq on records (which was non consistent with its equiv impl.) – and this commit relies on a static method introduced in the "caching hasheq" commit
Comment by Timothy Baldridge [ 30/Nov/12 12:10 PM ]

In the process of screening this, I'm not seeing much of a performance difference after applying the patch.

before patch:
user=> (-main)

Version: 1.5.0-master-SNAPSHOT
"Elapsed time: 6373.752 msecs"
"Elapsed time: 6578.037 msecs"
"Elapsed time: 6476.399 msecs"

after patch:
user=> (-main)

Version: 1.5.0-master-SNAPSHOT
"Elapsed time: 6182.699 msecs"
"Elapsed time: 6548.086 msecs"
"Elapsed time: 6496.711 msecs"

clojure 1.4:
user=> (-main)

Version: 1.4.0
"Elapsed time: 6484.234 msecs"
"Elapsed time: 6243.672 msecs"
"Elapsed time: 6248.898 msecs"

clojure 1.3
user=> (-main)

Version: 1.3.0
"Elapsed time: 3584.966 msecs"
"Elapsed time: 3618.189 msecs"
"Elapsed time: 3372.979 msecs"

I blew away my local clojure repo and re-applied the patch just to make sure, but the results are the same. Does this fix not optimize the case given in the original test project?

For reference I'm running this code:

(defn -main
[& args]

(println)
(println "Version: " (clojure-version))

(def mm 10000)

(def str-keys (map str (range mm)))
(def m (zipmap str-keys (range mm)))
(time (dotimes [i mm] (doseq [k str-keys] (m k))))

(def kw-keys (map #(keyword (str %)) (range mm)))
(def m (zipmap kw-keys (range mm)))
(time (dotimes [i mm] (doseq [k kw-keys] (m k))))

(def sym-keys (map #(symbol (str %)) (range mm)))
(def m (zipmap sym-keys (range mm)))
(time (dotimes [i mm] (doseq [k sym-keys] (m k))))

(println))

Comment by Christophe Grand [ 30/Nov/12 2:10 PM ]

Sorry, I was too quick to react on the ML (someone said it was related to hasheq caching and since I had the patch almost ready: on a project I noticed too much time spent computing hasheq on vectors).
So no, my patch doesn't improve anything with kws, syms or strs as keys. However when keys are collections, it fares better.

In 1.4, for a "regular" object, it must fails two instanceof tests before calling .hashCode().
If we make keywords and symbols implement IHashEq and reverse the test order (first IHashEq, then Number) it should improve the performance of the above benchmark – except for Strings.

Comment by Timothy Baldridge [ 30/Nov/12 2:16 PM ]

Marking as incomplete, should we also delete the patch as it seems like it should be in a different ticket?

Comment by Christophe Grand [ 03/Dec/12 10:00 AM ]

In 1.3, #'hash was going through Object.hashCode and thus was simple and fast. Plus collections hashes were cached.
In 1.4 and master, #'hash goes now through two instanceof test (Number and IHasheq in this order) before trying Object.hashCode in last resort. Plus collections hashes are not cached.
As such I'm not sure Util.hasheq inherent slowness (compared to Util.hash) and hasheq caching should be separated in two issues.

The caching-hasheq-v2.diff patchset reintroduces hashes caching for collections/hasheq and reorders the instanceof tests (to test for IHashEq before Number) and makes Keyword and Symbol implement IHashEq to branch fast in Util.hasheq.

I recommend adding a collection test to the current benchmark:

(defn -main
[& args]

(println)
(println "Version: " (clojure-version))

(def mm 10000)

(def str-keys (map str (range mm)))
(def m (zipmap str-keys (range mm)))
(time (dotimes [i mm] (doseq [k str-keys] (m k))))

(def kw-keys (map #(keyword (str %)) (range mm)))
(def m (zipmap kw-keys (range mm)))
(time (dotimes [i mm] (doseq [k kw-keys] (m k))))

(def sym-keys (map #(symbol (str %)) (range mm)))
(def m (zipmap sym-keys (range mm)))
(time (dotimes [i mm] (doseq [k sym-keys] (m k))))

(def vec-keys (map (comp (juxt keyword symbol identity) str) (range mm)))
(def m (zipmap vec-keys (range mm)))
(time (dotimes [i mm] (doseq [k vec-keys] (m k))))

(println))
Comment by Timothy Baldridge [ 03/Dec/12 10:38 AM ]

For some reason I can't get v2 to build against master. It applies cleanly, but fails to build.

Comment by Christophe Grand [ 03/Dec/12 11:30 AM ]

Timothy: I inadvertently deleted a "public" modifier before commiting... fixed in caching-hasheq-v3.diff

Comment by Timothy Baldridge [ 10/Dec/12 11:00 AM ]

I now get the following results:

Version: 1.4.0
"Elapsed time: 6281.345 msecs"
"Elapsed time: 6344.321 msecs"
"Elapsed time: 6108.55 msecs"
"Elapsed time: 36172.135 msecs"

Version: 1.5.0-master-SNAPSHOT (pre-patch)
"Elapsed time: 6126.337 msecs"
"Elapsed time: 6320.857 msecs"
"Elapsed time: 6237.251 msecs"
"Elapsed time: 18167.05 msecs"

Version: 1.5.0-master-SNAPSHOT (post-patch)
"Elapsed time: 6501.929 msecs"
"Elapsed time: 3861.987 msecs"
"Elapsed time: 3871.557 msecs"
"Elapsed time: 5049.067 msecs"

Marking as screened

Comment by Oleksandr Shyshko [ 10/Dec/12 3:53 PM ]

Please, could you add as a comment the bench result using 1.3 vs 1.5-master-post-patch?

Comment by Oleksandr Shyshko [ 11/Dec/12 2:13 PM ]

The performance with 1.5-master is now very close to 1.3 for 3/4 of the benchmark.

However, this code is still showing 43% performance drop (3411 ms VS 6030 ms – 1.3 VS 1.5-master):

(def str-keys (map str (range mm)))
(def m (zipmap str-keys (range mm)))
(time (dotimes [i mm] (doseq [k str-keys] (m k))))

Version: 1.3.0
"Elapsed time: 3411.353 msecs" <---
"Elapsed time: 3459.992 msecs"
"Elapsed time: 3365.182 msecs"
"Elapsed time: 3813.637 msecs"

Version: 1.4.0
"Elapsed time: 5710.073 msecs" <---
"Elapsed time: 5817.356 msecs"
"Elapsed time: 5774.856 msecs"
"Elapsed time: 18754.482 msecs"

Version: 1.5.0-master-SNAPSHOT
"Elapsed time: 6030.247 msecs" <---
"Elapsed time: 3372.637 msecs"
"Elapsed time: 3267.481 msecs"
"Elapsed time: 3852.927 msecs"

To reproduce:
$ git clone https://github.com/clojure/clojure.git
$ cd clojure
$ mvn install -Dmaven.test.skip=true

$ cd ..

$ git clone https://github.com/oshyshko/clj-perf.git
$ cd clj-perf
$ lein run-all





[CLJ-988] the locking in MultiFn.java (synchronized methods) can cause lots of contention in multithreaded programs Created: 08/May/12  Updated: 21/Sep/12  Resolved: 21/Sep/12

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

Type: Enhancement Priority: Major
Reporter: Kevin Downey Assignee: Stuart Sierra
Resolution: Completed Votes: 10
Labels: bug, performance

Attachments: Text File clj-988-tests-only-patch-v1.txt     File issue988-lockless-multifn+tests-120817.diff     File issue988-lockless-multifn+tests.diff    
Patch: Code and Test
Approval: Ok

 Description   

if you call a single multimethod a lot in multithreaded code you get lots of contention for the lock on the multimethod. this contention slows things down a lot.

this is due to getMethod being synchronized. it would be great if there was some fast non-locking path through the multimethod.



 Comments   
Comment by Kevin Downey [ 08/May/12 11:30 AM ]

http://groups.google.com/group/clojure-dev/browse_thread/thread/6a8219ae3d4cd0ae?hl=en

Comment by David Santiago [ 11/May/12 6:38 AM ]

Here's a stab in the dark attempt at rewriting MultiFn to use atoms to swap between immutable copies of its otherwise mutable state.

The four pieces of the MultiFn's state that are mutable and protected by locks are now contained in the MultiFn.State class, which is immutable and contains convenience functions for creating a new one with one field changed. An instance of this class is now held in an atom in the MultiFn called state. Changes to any of these four members are now done with an atomic swap of these State objects.

The getMethod/findAndCacheBestMethod complex was rewritten to better enable the atomic logic. findAndCacheBestMethod was replaced with findBestMethod, which merely looks up the method; the caching logic was moved to getMethod so that it can be retried easily as part of the work that method does.

As it was findAndCacheBestMethod seemingly had the potential to cause a stack overflow in a perfect storm of heavy concurrent modification, since it calls itself recursively if it finds that the hierarchy has changed while it has done its work. This logic is now done in the CAS looping of getMethod, so hopefully that is not even an unlikely possibility anymore.

There is still seemingly a small race here, since the check is done of a regular variable against the value in a ref. Now as before, the ref could be updated just after you do the check, but before the MultiFn's state is updated. Of course, only the method lookup part of a MultiFn call was synchronized before; it could already change after the lookup but before the method itself executed, having a stale method finish seemingly after the method had been changed. Things are no different now in general, with the atom-based approach, so perhaps this race is not a big deal, as a stale value can't persist for long.

The patch passes the tests and Clojure and multimethods seems to work.

Comment by Kevin Downey [ 12/May/12 8:59 PM ]

this patch gets rid of the ugly lock contention issues. I have not been able to benchmark it vs. the old multimethod implementation, but looking at it, I would not be surprised if it is faster when the system is in a steady state.

Comment by Stuart Halloway [ 08/Jun/12 12:11 PM ]

This looks straightforward, except for getMethod. Can somebody with context add more discussion of how method caching works?

Also, it would be great to have tests with this one.

Comment by David Santiago [ 15/Jun/12 4:44 AM ]

Obviously I didn't write the original code, so I'm not the ideal
person to explain this stuff. But I did work with it a bit recently,
so in the hopes that I can be helpful, I'm writing down my
understanding of the code as I worked with it. Since I came to the
code and sort of reverse engineered my way to this understanding,
hopefully laying this all out will make any mistakes or
misunderstandings I may have made easier to catch and correct. To
ensure some stability, I'll talk about the original MultiFn code as it
stands at this commit:
https://github.com/clojure/clojure/blob/8fda34e4c77cac079b711da59d5fe49b74605553/src/jvm/clojure/lang/MultiFn.java

There are four pieces of state that change as the multimethod is either
populated with methods or called.

  • methodTable: A persistent map from a dispatch value (Object) to
    a function (IFn). This is the obvious thing you think it is,
    determining which dispatch values call which function.
  • preferTable: A persistent map from a dispatch value (Object) to
    another value (Object), where the key "is preferred" to the value.
  • methodCache: A persistent map from a dispatch value (Object) to
    function (IFn). By default, the methodCache is assigned the same
    map value as the methodTable. If values are calculated out of the
    hierarchy during a dispatch, the originating value and the
    ultimate method it resolves to are inserted as additional items in
    the methodCache so that subsequent calls can jump right to the
    method without recursing down the hierarchy and preference table.
  • cachedHierarchy: An Object that refers to the hierarchy that is
    reflected in the latest cached values. It is used to check if the
    hierarchy has been updated since we last updated the cache. If it
    has been updated, then the cache is flushed.

I think reset(), addMethod(), removeMethod(), preferMethod(),
prefers(), isA(), dominates(), and resetCache() are extremely
straightforward in both the original code and the patch. In the
original code, the first four of those are synchronized, and the other
four are only called from methods that are synchronized (or from
methods only called from methods that are synchronized).

Invoking a multimethod through its invoke() function will call
getFn(). getFn() will call the getMethod() function, which is
synchronized. This means any call of the multimethod will wait for and
take a lock as part of method invocation. The goal of the patch in
this issue is to remove this lock on calls into the multimethod. It in
fact removes the locks on all operations, and instead keeps its
internal mutable state by atomically swapping a private immutable
State object held in an Atom called state.

The biggest change in the patch is to the
getFn()>getMethod()>findAndCacheBestMethod() complex from the
original code. I'll describe how that code works first.

In the original code, getFn() does nothing but bounce through
getMethod(). getMethod() tries three times to find a method to call,
after checking that the cache is up to date and flushing it if it
isn't:

1. It checks if there's a method for the dispatch value in the
methodCache.

2. If not, it calls findAndCacheBestMethod() on the
dispatch value. findAndCacheBestMethod() does the following:

1. It iterates through every map entry in the method table,
keeping at each step the best entry it has found so far
(according to the hierarchy and preference tables).

2. If it did not find a suitable entry, it returns null.

3. Otherwise, it checks if the hierarchy has been changed since the cache
was last updated. If it has not changed, it inserts the method
into the cache and returns it. If it has been changed, it
resets the cache and calls itself recursively to repeat the process.

3. Failing all else, it will return the method for the default
dispatch value.

Again, remember everything in the list above happens in a call to a
synchronized function. Also note that as it is currently written,
findAndCacheBestMethod() uses recursion for iteration in a way that
grows the stack. This seems unlikely to cause a stack overflow unless
the multimethod is getting its hierarchy updated very rapidly for a
sustained period while someone else tries to call it. Nonetheless, the
hierarchy is held in an IRef that is updated independently of the
locking of the MultiFn. Finally, note that the multimethod is locked
only while the method is being found. Once it is found, the lock is
released and the method actually gets called afterwards without any
synchronization, meaning that by the time the method actually
executes, the multimethod may have already been modified in a way that
suggests a different method should have been called. Presumably this
is intended, understood, and not a big deal.

Moving on now to the patch in this issue. As mentioned, the main
change is updating this entire apparatus to work with a single atomic
swap to control concurrency. This means that all updates to the
multimethod's state have to happen at one instant in time. Where the
original code could make multiple changes to the state at different
times, knowing it was safely protected by an exclusive lock, rewriting
for atom swaps requires us to reorganize the code so that all updates
to the state happen at the same time with a single CAS.

To implement this change, I pulled the implicit looping logic from
findAndCacheBestMethod() up into getMethod() itself, and broke the
"findBestMethod" part into its own function, findBestMethod(), which
makes no update to any state while implementing the same
logic. getMethod() now has an explicit loop to avoid stack-consuming
recursion on retries. This infinite for loop covers all of the logic
in getMethod() and retries until a method is successfully found and a
CAS operation succeeds, or we determine that the method cannot be
found and we return the default dispatch value's implementation.

I'll now describe the operation of the logic in the for loop. The
first two steps in the loop correspond to things getMethod() does
"before" its looping construct in the original code, but we have to do
in the loop to get the latest values.

1. First we dereference our state, and assign this value to both
oldState and newState. We also set a variable called needWrite to
false; this is so we can avoid doing a CAS (they're not free) when
we have not actually updated the state.

2. Check if the cache is stale, and flush it if so. If the cache
gets flushed, set needWrite to true, as the state has changed.

3. Check if the methodCache has an entry for this dispatch
value. If so, we are "finished" in the sense that we found the
value we wanted. However, we may need to update the state. So,

  • If needWrite is false, we can return without a CAS, so just
    break out of the loop and return the method.
  • Otherwise, we need to update the state object with a CAS. If
    the CAS is successful, break out of the loop and return the
    target function. Otherwise, continue on the next iteration
    of the loop, skipping any other attempts to fetch the method
    later in the loop (useless work, at this point).

4. The value was not in the methodCache, so call the function
findBestMethod() to attempt to find a suitable method based on the
hierarchy and preferences. If it does find us a suitable method,
we now need to cache it ourselves. We create a new state object
with the new method cache and attempt to update the state atom
with a CAS (we definitely need a write here, so no need to check
needWrite at this point).

The one thing that is possibly questionable is the check at this
point to make sure the hierarchy has not been updated since the
beginning of this method. I inserted this here to match the
identical check at the corresponding point in
findAndCacheBestMethod() in the original code. That is also a
second check, since the cache is originally checked for freshness
at the very beginning of getMethod() in the original code. That
initial check happens at the beginning of the loop in the
patch. Given that there is no synchronization with the method
hierarchy, it is not clear to me that this second check is needed,
since we are already proceeding with a snapshot from the beginning
of the loop. Nonetheless, it can't hurt as far as I can tell, it
is how the original code worked, and I assume there was some
reason for that, so I kept the second check.

5. Finally, if findBestMethod() failed to find us a method for the
dispatch value, find the method for the default dispatch value and
return that by breaking out of the loop.

So the organization of getMethod() in the patch is complicated by two
factors: (1) making the retry looping explicit and stackless, (2)
skipping the CAS when we don't need to update state, and (3) skipping
needless work later in the retry loop if we find a value but are
unable to succeed in our attempt to CAS. Invoking a multimethod that
has a stable hierarchy and a populated cache should not even have a
CAS operation (or memory allocation) on this code path, just a cache
lookup after the dispatch value is calculated.

Comment by David Santiago [ 15/Jun/12 4:45 AM ]

I've updated this patch (removing the old version, which is entirely superseded by this one). The actual changes to MultiFn.java are identical (modulo any thing that came through in the rebase), but this newer patch has tests of basic multimethod usage, including defmulti, defmethod, remove-method, prefer-method and usage of these in a hierarchy that updates in a way interleaved with calls.

Comment by David Santiago [ 15/Jun/12 6:38 AM ]

I created a really, really simple benchmark to make sure this was an improvement. The following tests were on a quad-core hyper-threaded 2012 MBP.

With two threads contending for a simple multimethod:
The lock-based multifns run at an average of 606ms, with about 12% user, 15% system CPU at around 150%.
The lockless multifns run at an average of 159ms, with about 25% user, 3% system CPU at around 195%.

With four threads contending for a simple multimethod:
The lock-based multifns run at an average of 1.2s, with about 12% user, 15% system, CPU at around 150%.
The lockless multifns run at an average of 219ms, with about 50% user, 4% system, CPU at around 330%.

You can get the code at https://github.com/davidsantiago/multifn-perf

Comment by David Santiago [ 14/Aug/12 10:02 PM ]

It's been a couple of months, and so I just wanted to check in and see if there was anything else needed to move this along.

Also, Alan Malloy pointed out to me that my benchmarks above did not mention single-threaded performance. I actually wrote this into the tests above, but I neglected to report them at the time. Here are the results on the same machine as above (multithreaded versions are basically the same as the previous comment).

With a single thread performing the same work:
The lock-based multifns run at an average of 142ms.
The lockless multifns run at an average of 115ms.

So the lockless multimethods are still faster even in a single-threaded case, although the speedup is more modest compared to the speedups in the multithreaded cases above. This is not surprising, but it is good to know.

Comment by Stuart Sierra [ 17/Aug/12 2:58 PM ]

Screened. The approach is sound.

I can confirm similar performance measurements using David Santiago's benchmark, compared with Clojure 1.5 master as of commit f5f4faf.

Mean runtime (ms) of a multimethod when called repeatedly from N threads:

|            | N=1 | N=2 | N=4 |
|------------+-----+-----+-----|
| 1.5 master |  80 | 302 | 765 |
| lockless   |  63 |  88 | 125 |

My only concern is that the extra allocations of the State class will create more garbage, but this is probably not significant if we are already using persistent maps. It would be interesting to compare this implementation with one using thread-safe mutable data structures (e.g. ConcurrentHashMap) for the cache.

Comment by David Santiago [ 17/Aug/12 7:05 PM ]

I think your assessment that it's not significant compared to the current implementation using persistent maps is correct. Regarding the extra garbage, note that the new State is only created when the hierarchy has changed or there's a cache miss (related, obviously)... situations where you're already screwed. Then it won't have to happen again for the same method (until another change to the multimethod). So for most code, it won't happen very often.

ConcurrentHashMap might be faster, it'd be interesting to see. My instinct is to keep it as close to being "made out of Clojure" as possible. In fact, it's hard to see why this couldn't be rewritten in Clojure itself some day, as I believe Chas Emerick has suggested. Also, I would point out that two of the three maps are used from the Clojure side in core.clj. I assume they would be happier if they were persistent maps.

Funny story: I was going to point out the parts of the code that were called from the clojure side just now, and alarmingly cannot find two of the functions. I think I must have misplaced them while rewriting the state into an immutable object. Going to attach a new patch with the fix and some tests for it in a few minutes.

Comment by David Santiago [ 17/Aug/12 7:44 PM ]

Latest patch for this issue. Supersedes issue988-lockless-multifn+tests.diff as of 08/17/2012.

Comment by David Santiago [ 17/Aug/12 7:49 PM ]

As promised, I reimplemented those two functions. I also added more multimethod tests to the test suite. The new tests should definitely prevent a similar mistake. While I was at it, I went through core.clj and found all the multimethod API functions I could and ensured that there were at least some basic functionality tests for all of them. The ones I found were: defmulti, defmethod, remove-all-methods, remove-method, prefer-method, methods, get-method, prefers (Some of those already had tests from the earlier version of the patch).

Really sorry about catching this right after you vetted the patch. 12771 test assertions were apparently not affected by prefers and methods ceasing to function, but now there are 12780 to help prevent a similar error. Since you just went through it, I'm leaving the older version of the patch up so you can easily see the difference to what I've added.

Comment by Rich Hickey [ 15/Sep/12 9:05 AM ]

https://github.com/clojure/clojure/commit/83ebf814d5d6663c49c1b2d0d076b57638bff673 should fix these issues. The patch here was too much of a change to properly vet.

If you could though, I'd appreciate a patch with just the multimethod tests.

Comment by Andy Fingerhut [ 15/Sep/12 10:59 AM ]

Patch clj-988-tests-only-patch-v1.txt dated Sep 15 2012 is a subset of David Santiago's
patch issue988-lockless-multifn+tests-120817.diff dated Aug 17 2012. It includes only the tests from that patch. Applies cleanly and passes tests with latest master after Rich's read/write lock change for multimethods was committed.

Comment by Rich Hickey [ 17/Sep/12 9:20 AM ]

tests-only patch ok





[CLJ-958] Make APersistentVector.iterator slightly more efficient Created: 23/Mar/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: Chris Gray Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: performance

Attachments: Text File 0001-Make-APersistentVector.iterator-slightly-more-effici.patch    
Patch: Code

 Description   

The attached patch uses a sequence to create an iterator for persistent vectors. It should be slightly more efficient for PersistentVector objects than repeatedly calling nth (for reasons that I outline in the commit message).






[CLJ-910] [Patch] Allow for type-hinting the method receiver in memfn Created: 13/Jan/12  Updated: 01/Sep/12  Resolved: 01/Sep/12

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

Type: Enhancement Priority: Minor
Reporter: Tassilo Horn Assignee: Unassigned
Resolution: Completed Votes: 1
Labels: performance, reflection

Attachments: Text File 0001-Make-memfn-allow-for-type-hinting-the-method-receive.patch    
Patch: Code
Approval: Ok

 Description   

The attached patch copies metadata given to the method name symbol of memfn to the method receiver in the expansion. That way, memfn is able to be used even for type-hinted calls resulting in a big performance win.

user> (time (dotimes [i 1000000] ((memfn intValue) 1)))
Reflection warning, NO_SOURCE_FILE:1 - call to intValue can't be resolved.
"Elapsed time: 2579.229115 msecs"
nil
user> (time (dotimes [i 1000000] ((memfn ^Number intValue) 1)))
"Elapsed time: 12.015235 msecs"
nil


 Comments   
Comment by Tassilo Horn [ 08/Mar/12 3:56 AM ]

Updated patch.

Comment by Aaron Bedra [ 21/Aug/12 6:06 PM ]

Applies properly against d4170e65d001c8c2976f1bd7159484056b9a9d6d. Things look good to me.





[CLJ-858] Improve speed of STM by removing System.currentTimeMillis Created: 17/Oct/11  Updated: 22/Nov/13  Resolved: 22/Nov/13

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

Type: Enhancement Priority: Minor
Reporter: Stefan Kamphausen Assignee: Unassigned
Resolution: Completed Votes: 2
Labels: performance
Environment:

Tested on Ubuntu and OSX


Attachments: File stm-rm-msecs-patch.diff    
Patch: Code
Approval: Ok

 Description   

The inner class TVal in LockingTransaction and Ref has an unused milliseconds field (that is populated with System.currentTimeMillis()).

This patch removes the milliseconds from inner class TVal in LockingTransaction.java and Ref.java. Using a little test suite[1] a increase of performance by up to 25% could be measured.

Original post: https://groups.google.com/d/topic/clojure/kc99LcUK8Tk/discussion

References:
[1] https://github.com/ska2342/clj-stm-perf-test/

Screened by: Alex Miller



 Comments   
Comment by Alex Miller [ 08/Aug/13 2:48 AM ]

Patch applies cleanly. Author is a contributor.

Did not verify performance claims but I can't see how removing fields and calls to System.currentTimeMillis() could do anything but make STM usage smaller and faster.

Marking Screened.





[CLJ-703] Improve writeClassFile performance Created: 04/Jan/11  Updated: 08/Oct/14

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

Type: Enhancement Priority: Critical
Reporter: Jürgen Hötzel Assignee: Unassigned
Resolution: Unresolved Votes: 19
Labels: Compiler, performance

Attachments: Text File 0001-use-File.mkdirs-instead-of-mkdir-every-single-direct.patch     Text File 0002-Ensure-atomic-creation-of-class-files-by-renaming-a-.patch     Text File improve-writeclassfile-perf.patch     Text File remove-flush-and-sync-only.patch     Text File remove-sync-only.patch    
Patch: Code
Approval: Triaged

 Description   

This Discussion about timing issues when writing class files led to the the current implementation of synchronous writes to disk. This leads to bad performance/system-load when compiling Clojure code.

This Discussion questioned the current implentation.

Synchronous writes are not necessary and also do not ensure (crash while calling write) valid classfiles.

These Patches (0001 is just a code cleanup for creating the directory structure) ensures atomic creation of classfiles by using File.renameTo()



 Comments   
Comment by David Powell [ 17/Jan/11 2:16 PM ]

Removing sync makes clojure build much faster. I wonder why it was added in the first place? I guess only Rich knows? I assume that it is not necessary.

If we are removing sync though, I wouldn't bother with the atomic rename stuff. Doing that sort of thing can cause problems on some platforms, eg with search indexers and virus checkers momentarily locking files after they are created.

The patch seems to be assuming that sync is there for some reason, but my initial assumption would be that sync isn't necessary - perhaps it was working around some issue that no longer exists?

Comment by Jürgen Hötzel [ 19/Jan/11 2:05 PM ]

Although its unlikely: there is a possible race condition "loading a paritally written classfile"?:

https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java#L393

Comment by John Szakmeister [ 25/May/12 4:22 AM ]

The new improve-writeclassfile-perf version of the patch combines the two previous patches into a single patch file and brings them up-to-date with master. I can split the two changes back out into separate patch files if desired, but I figured out current tooling is more geared towards a single patch being applied.

Comment by John Szakmeister [ 25/May/12 4:36 AM ]

FWIW, both fixes look sane. The first one is a nice cleanup. The second one is a little more interesting in that uses a rename operation to put the final file into place. It removes the sync call, which does make things faster. In general, if we're concerned about on-disk consistency, we should really have a combination of the two: write the full contents to a tmp file, sync it, and atomically rename to the destination file name.

Neither the current master, nor the current patch will guarantee on-disk consistency across a machine wide crash. The current master could crash before the sync() occurs, leaving the file in an inconsistent state. With the patch, the OS may not get the file from file cache to disk before an OS level crash occurs, and leave the file in an inconsistent state as well. The benefit of the patch version is that the whole file does atomically come into view at once. It does have a nasty side effect of leaving around a temp file if the compiler crashes just before the rename though.

Perhaps a little more work to catch an exception and clean up is in order? In general, I like the patched version better.

Comment by Ivan Kozik [ 05/Oct/12 7:07 PM ]

File.renameTo returns false on (most?) errors, but the patch doesn't check for failure. Docs say "The return value should always be checked to make sure that the rename operation was successful." Failure might be especially likely on Windows, where files are opened by others without FILE_SHARE_DELETE.

Comment by Dave Della Costa [ 23/Jun/14 11:37 PM ]

We've been wondering why our compilation times on linux were so slow. It became the last straw when we walked away from one project and came back after 15 minutes and it was not done yet.

After some fruitless investigation into our linux configuration and lein java args, we stumbled upon this issue via the associated Clojure group thread. Upon commenting out the flush() and sync() lines (https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Compiler.java#L7171-L7172) and compiling Clojure 1.6 ourselves, our projects all started compiling in under a minute.

Point being, can we at least provide some flag to allow for "unsafe compilation" or something? As it is, this is bad enough that we've manually modified all our local versions of Clojure to work around the issue.

Comment by Tim McCormack [ 30/Sep/14 4:10 PM ]

Additional motivation: This becomes really unpleasant on an encrypted filesystem, since write and read latency become higher.

As a partial workaround, I've been using this script to mount a ramdisk over top of target, which speeds up compilation 2-4x: https://gist.github.com/timmc/6c397644668bcf41041f (but removing flush() and sync() entirely would probably speed things up even more, if safe)

Comment by Ragnar Dahlen [ 06/Oct/14 12:30 PM ]

I'd like to explore this issue further as I also don't think the flush and sync calls add any value, but do have a severe impact on performance.

To resurrect the discussion, I've attached a new patch with the following approach:

  • create a temporary file
  • write class bytecode to temporary file, no flush or sync
  • close temporary file
  • atomic rename of temporary file to class file name

It is different to previous patches in that:

  • it applies cleanly to master
  • it checks return value from File.renameTo
  • it omits proposed File.mkdirs change as the current implementation is actually converting from an "internal name", where forward slashes are assumed (splits on "/"), to a platform specific path using File.separator. I'm not convinced that the previous patch is safe on all versions of Windows, and I think it's separate from the main issue here.

I opted for the atomic rename of a temp file to avoid leaving empty class files with a correct expected class file name in case of failure.

It is my understanding that this patch will guarantee that:

  • when writeClassFile returns successfully, a class file with the expected name will exists, and subsequent reads from that file name will return the expected bytecode (possibly from kernel buffers).
  • when writeClassFile fails, a class file with the expected name will not have been created (or updated if it previously existed).

Anything preventing the operating system from flushing its buffers to disk (power failure etc) might leave a corrupt (empty, partially written) class file. It's my opinion that that is acceptable behaviour, and worth the performance improvement (I'm seeing AOT compilation reduced from 1m20s -> 22s on one of our codebases, would be happy to provide more benchmarks if requested).

Would be grateful for feedback/testing of this patch.

Comment by Ragnar Dahlen [ 08/Oct/14 6:00 AM ]

We're testing this patch on various projects/platforms at my company. So far we've seen:

  • Significantly reduced compilation times on Linux (two typical examples: 30s to 15s, 1m30s to 30s)
  • No significant change in compilation times on Mac OSX.
  • File.renameTo consistently failing on a Windows machine.

My understanding is that the performance difference between Linux and OSX is due to differences in how these platforms implement fsync. OSX by default does not actually tell the drive to flush its buffers (requires fcntl F_FULLSYNC for this, not used by JVMs) [1], whereas Linux does [2].

Our very limited test shows (as was previously pointed out) that File.renameTo is problematic on Windows. I've attached a new patch that doesn't use rename, and only has the the sync call removed (flush is a no-op for FileOutputStreams). We're currently testing this patch.

The drawback of this patch is that it may leave correctly named, but empty class files if the write fails. One option would be to try and delete the file in the catch block. Personally, I wouldn't expect a compilation that failed because of OS/IO reasons to leave my classfiles in a consistent state.

[1]: "Note that while fsync() will flush all data from the host to the drive (i.e. the "permanent storage device"), the drive itself may not physically write the data to the platters for quite some time and it may be written in an out-of-order sequence.": https://developer.apple.com/library/mac/documentation/Darwin/Reference/ManPages/man2/fsync.2.html

[2]: "[...] includes writing through or flushing a disk cache if present."
http://man7.org/linux/man-pages/man2/fsync.2.html





[CLJ-669] clojure.java.io/do-copy: use java.nio for Files Created: 01/Nov/10  Updated: 22/Nov/13  Resolved: 22/Nov/13

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

Type: Enhancement Priority: Major
Reporter: Jürgen Hötzel Assignee: Unassigned
Resolution: Completed Votes: 0
Labels: performance

Attachments: Text File 0001-use-java.nio-in-do-copy-method-for-Files.patch     Text File clj-669-use-java.nio-in-do-copy-for-files-patch-v2.txt     File clj-669-use-java.nio-in-do-copy-for-files-patch-v3.diff     Text File clj-669-use-java.nio-in-do-copy-for-files-patch-v3.txt    
Patch: Code
Approval: Ok

 Description   

NIO Channels reduce CPU/Disk load when copying Files (by using syscalls like sendfile internally on Linux/Solaris).

CPU-Load goes from 100% to 0% on my system when copying large files, because no userspace-copying is involved.

Patch: clj-669-use-java.nio-in-do-copy-for-files-patch-v3.diff

Screened by: Alex Miller



 Comments   
Comment by Jürgen Hötzel [ 27/Nov/10 5:05 AM ]

Patch instead of linking to github

Comment by Andy Fingerhut [ 24/May/13 12:45 PM ]

Patch clj-669-use-java.nio-in-do-copy-for-files-patch-v2.txt dated May 24 2013 is identical to patch 0001-use-java.nio-in-do-copy-method-for-Files.patch dated Nov 27 2010 except it applies cleanly to latest master. The older patch conflicts with a recent commit for CLJ-1072 that updates the obsolete #^ syntax for metadata.

Comment by Stuart Sierra [ 02/Aug/13 2:05 PM ]

Marked as incomplete pending a question: do we know that transferTo will always copy the entire file in one call? Nothing in the Javadoc for FileChannel.transferTo guarantees that it will.

Just to be safe, I think we should call transferTo in a loop, keeping track of how many bytes have been copied.

As a side note, I verified that the transferTo method is available in JDK 1.5.

Comment by Andy Fingerhut [ 10/Aug/13 3:37 AM ]

Good catch, Stuart. I verified by testing the -v2.txt patch on a 7 Gbyte file, and at least with a couple of OS/JDK combos transferTo never copied more than just under 2 Gbytes per call. It definitely needs a loop around transferTo calls to be correct.

Patch clj-669-use-java.nio-in-do-copy-for-files-patch-v3.txt dated Aug 10 2013 implements such a loop. I've tested it with OSX10.8.4+OracleJDK1.7.0_15, Ubuntu 12.04.1+OpenJDK1.6.0_27, and Ubuntu 12.04.1+OracleJDK1.7.0_25. In all cases it worked correctly on the 7 Gbyte file, and it reduced CPU load in the Java process as compared to the original version of do-copy.





[CLJ-668] Improve slurp performance by using native Java StringWriter and jio/copy Created: 01/Nov/10  Updated: 03/Oct/14

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

Type: Enhancement Priority: Major
Reporter: Jürgen Hötzel Assignee: Timothy Baldridge
Resolution: Unresolved Votes: 0
Labels: ft, io, performance

Attachments: File slurp-perf-patch.diff    
Patch: Code
Approval: Triaged

 Description   

Instead of copying each character from InputReader to StringBuffer.

Performance improvement:

Generate a 10meg file:
user> (spit "foo.txt" (apply str (repeat (* 1024 1024 10) "X")))

Test code:
user> (dotimes [x 100] (time (do (slurp "foo.txt") 0)))

From:
...
Elapsed time: 136.387 msecs"
"Elapsed time: 143.782 msecs"
"Elapsed time: 153.174 msecs"
"Elapsed time: 211.51 msecs"
"Elapsed time: 155.429 msecs"
"Elapsed time: 145.619 msecs"
"Elapsed time: 142.641 msecs"
...


To:
...
"Elapsed time: 23.408 msecs"
"Elapsed time: 25.876 msecs"
"Elapsed time: 41.449 msecs"
"Elapsed time: 28.292 msecs"
"Elapsed time: 25.765 msecs"
"Elapsed time: 24.339 msecs"
"Elapsed time: 32.047 msecs"
"Elapsed time: 23.372 msecs"
"Elapsed time: 24.365 msecs"
"Elapsed time: 26.265 msecs"
...

Approach: Use StringWriter and jio/copy vs character by character copy. Results from the current patch see a 4-5x perf boost after the jit warms up, with purely in-memory streams (ByteArrayInputStream over a 6MB string).

Patch: slurp-perf-patch.diff
Screened by: Alex Miller



 Comments   
Comment by Alex Miller [ 21/Apr/14 3:28 PM ]

This is double-better with the changes in Clojure 1.6 to improve jio/copy performance by using the NIO impl. Rough timing difference on a 25M file: old= 2316.021 msecs, new= 93.319 msecs.

Filer did not supply a patch and is not a contributor. If someone wants to make a patch (and better timing info demonstrating performance improvements), that would be great.

Comment by Timothy Baldridge [ 10/Sep/14 10:29 PM ]

Fixed the ticket formatting a bit, and added a patch I coded up tonight. Should be pretty close to the old patch, as we both use StringWriter, but I didn't really look at the old patch beyond noticing that it was using StringWriter.

Comment by Alex Miller [ 11/Sep/14 7:01 AM ]

Can you update the perf comparison on latest code and do both a small and big file?





[CLJ-400] A faster flatten Created: 13/Jul/10  Updated: 03/Sep/13

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

Type: Enhancement Priority: Major
Reporter: Anonymous Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: performance


 Description   

As discussed in this thread, I am submitting a more performant version of flatten for review. It has the same semantics as the current core/flatten. I have also updated the doc string to say that "(flatten nil) returns the empty list", because that's what the current version of core/flatten does as well.

I haven't mailed in a CA yet, but I will tomorrow morning.

Edit: Of course I'd mess my first ticket up . I am not immediately seeing an option to edit this to add the "patch" tag or add the "ready to test" action. Sorry folks



 Comments   
Comment by Assembla Importer [ 24/Aug/10 12:19 AM ]

Converted from http://www.assembla.com/spaces/clojure/tickets/400
Attachments:
flatten-enhancement.diff - https://www.assembla.com/spaces/clojure/documents/c5chtAJQir353NeJe5cbLr/download/c5chtAJQir353NeJe5cbLr





[CLJ-15] Incremental hashcode calculation for collections Created: 17/Jun/09  Updated: 05/Sep/14

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

Type: Enhancement Priority: Minor
Reporter: Rich Hickey Assignee: Unassigned
Resolution: Unresolved Votes: 2
Labels: performance

Attachments: File lazy-incremental-hashes.diff    
Patch: Code

 Description   
Reported by richhickey, Dec 17, 2008
So hachCode can be final, more efficient to calc as you go.
Formerly Google Code Issue 11


 Comments   
Comment by Assembla Importer [ 24/Aug/10 3:44 AM ]

Converted from http://www.assembla.com/spaces/clojure/tickets/15

Comment by Christophe Grand [ 08/Mar/13 6:20 AM ]

Wouldn't the naive approach incur realizing lazy sequences when adding them to a list or a vector or as values in a map?

Comment by Christophe Grand [ 26/Aug/13 3:40 AM ]

The lazy-incremental-hashes.diff introduces lazy incremental hashes based on structural sharing.

Comment by Christophe Grand [ 26/Aug/13 3:42 AM ]

Why is this identified as Blocker?

Comment by Christophe Grand [ 26/Aug/13 3:43 AM ]

setting priority to minor

Comment by Andy Fingerhut [ 26/Aug/13 7:46 AM ]

I've seen this "edit a ticket, it changes to Priority=Blocker" behavior before. I believe some of the older tickets have no Priority field at all, and when you edit any of their properties, it creates the priority field with a default value of Blocker.

Comment by Alex Miller [ 26/Aug/13 8:06 AM ]

Yes, concur with Andy's explanation on priority change. I just bulk-edited all open CLJ tickets with null priority and set their priority.

Comment by Andy Fingerhut [ 30/Jan/14 8:01 PM ]

Patch lazy-incremental-hashes.diff still applies cleanly as of Jan 30 2014 latest Clojure master, but now fails tests due to recent commits involving hash changes. I have not checked how difficult or easy it might be to update the patch to pass tests again.

Comment by Andy Fingerhut [ 29/Aug/14 4:25 PM ]

Patch lazy-incremental-hashes.diff dated Aug 26 2013 no longer applied cleanly to latest master after some commits were made to Clojure on Aug 29, 2014. It did apply cleanly before that day.

I have not checked how easy or difficult it might be to update this patch.

Comment by Andy Fingerhut [ 05/Sep/14 11:41 AM ]

Patch lazy-incremental-hashes.diff dated Aug 26 2013 applies cleanly again to latest Clojure master as of Sep 5 2014, even though the patch has not been updated. I haven't checked, but I would guess this is because one of the changes made to Clojure master recently was reverted with this commit: https://github.com/clojure/clojure/commit/46be47c9f51ef10d0082f1bd39ffff1008682861





Generated at Mon Nov 24 14:27:26 CST 2014 using JIRA 4.4#649-r158309.