Re: Request for help optimising a Clojure program

+1 On Thu, Jan 30, 2014 at 11:13 AM, Andy Fingerhut wrote: > Thanks to the work and thought of Mark Engelberg, Alex Miller, Rich > Hickey, myself, and likely several others who I should be naming here but > am forgetting, the latest (not yet released) Clojure master version has an > improved has

Re: Request for help optimising a Clojure program

Thanks for posting that here Andy - I've been mostly off the grid this week and haven't had time to do some of this followup. I would also like to say many thanks to Mark and Andy who have spent a lot of time elucidating the original issue and working on how to address it. Alex On Thursday, Ja

Re: Request for help optimising a Clojure program

Thanks to the work and thought of Mark Engelberg, Alex Miller, Rich Hickey, myself, and likely several others who I should be naming here but am forgetting, the latest (not yet released) Clojure master version has an improved hash function that gives a much better variety of hash values, and thus m

Re: Request for help optimising a Clojure program

A few minutes ago I finished copying, pasting, and doing a little reformatting on Mark Engelberg's document on the subject. http://dev.clojure.org/display/design/Better+hashing Andy On Fri, Nov 1, 2013 at 11:28 AM, Alex Miller wrote: > Has anyone created a design page on dev.clojure for t

Re: Request for help optimising a Clojure program

Has anyone created a design page on dev.clojure for this yet? On Thursday, October 31, 2013 9:19:23 AM UTC-5, Andy Fingerhut wrote: > > Just a follow up after a fair amount of thinking and experimentation has > been done on this problem. > > Mark Engelberg has a very nice document describing th

Re: Request for help optimising a Clojure program

awesome news :) Jim On 31/10/13 14:19, Andy Fingerhut wrote: Just a follow up after a fair amount of thinking and experimentation has been done on this problem. Mark Engelberg has a very nice document describing the existing hash functions used by Clojure, examples with why they can cause co

Re: Request for help optimising a Clojure program

Just a follow up after a fair amount of thinking and experimentation has been done on this problem. Mark Engelberg has a very nice document describing the existing hash functions used by Clojure, examples with why they can cause collisions so often, and suggestions for changes to them to have fewe

Re: Request for help optimising a Clojure program

On Fri, Oct 25, 2013 at 9:11 AM, Stuart Halloway wrote: > To save others from having to read this whole thread, is the following > summary correct? > > 1. We believe that the performance issue Paul first encountered is > substantially / entirely caused by hash collisions. > Yes. > > 2. The hash

Re: Request for help optimising a Clojure program

I don't see a general solution for idiomatic Clojure data (so, often not records) other than making the hashes of small integers a spread-out, nonlinear function of them. On Fri, Oct 25, 2013 at 2:11 PM, Mark Engelberg wrote: > On Fri, Oct 25, 2013 at 9:56 AM, David Nolen wrote: > >> What I sugg

Re: Request for help optimising a Clojure program

On Fri, Oct 25, 2013 at 9:56 AM, David Nolen wrote: > What I suggested is far, far more conservative than anything else proposed > on this or on the dev thread. > I understand your point that records are a separate "island" unique to Clojure-land, whereas the other Clojure types need to align wi

Re: Request for help optimising a Clojure program

What I suggested is far, far more conservative than anything else proposed on this or on the dev thread. Changing the hash implementation of sets and vectors etc. is likely to have unintended consequences for performance - http://www.scala-lang.org/old/node/8510.html The original Scala code used

Re: Request for help optimising a Clojure program

Two partial answers in-line below, but as it says there, Mark Engelberg has more experimental data than I do right now on proposed changes. On Fri, Oct 25, 2013 at 9:11 AM, Stuart Halloway wrote: > To save others from having to read this whole thread, is the following > summary correct? > > 1. W

Re: Request for help optimising a Clojure program

On 10/24/13 5:46 AM, Paul Butcher wrote: On 24 Oct 2013, at 11:34, Phillip Lord > wrote: What does Scala do? I mean, given that it doesn't have the same problem, perhaps it has a solution? By default, Scala uses a tree-based set, not a hash-based set. So t

Re: Request for help optimising a Clojure program

To save others from having to read this whole thread, is the following summary correct? 1. We believe that the performance issue Paul first encountered is substantially / entirely caused by hash collisions. 2. The hash collisions could be improved by spreading the hashes of numbers (and not needi

Re: Request for help optimising a Clojure program

As Andy Fingerhut pointed out, since (hash [a b]) is 31*(a + 30) + (b + 31) when a and b are ints, summing the hashes of 2-tuples when the values are small ints, as happens when hashing sets of such 2-tuples, is quite likely to lead to collisions. This particular problem could be avoided by spr

Re: Request for help optimising a Clojure program

OK, it appears defrecord suffers from a problem that used to plague Scala case classes as well - http://issues.scala-lang.org/browse/SI-2537. David On Thu, Oct 24, 2013 at 8:08 AM, Paul Butcher wrote: > On 23 Oct 2013, at 18:37, David Nolen wrote: > > The problem here is that you're not follow

Re: Request for help optimising a Clojure program

On 23 Oct 2013, at 18:37, David Nolen wrote: > The problem here is that you're not following your Scala solution closely > enough. I suspect if you used defrecords to represent the pieces the way that > you used a class in Scala you can avoid the number of collisions for larger > problems. >

Re: Request for help optimising a Clojure program

On 24 Oct 2013, at 11:34, Phillip Lord wrote: > What does Scala do? I mean, given that it doesn't have the same problem, > perhaps it has a solution? By default, Scala uses a tree-based set, not a hash-based set. So the fact that it doesn't run into hashing issues isn't surprising (and is yet a

Re: Request for help optimising a Clojure program

What does Scala do? I mean, given that it doesn't have the same problem, perhaps it has a solution? Andy Fingerhut writes: > If you can think of a different hash function for vectors that doesn't lead > to these types of collisions, I'm all ears. The issue is that the hash > function for sets

Re: Request for help optimising a Clojure program

On 24 Oct 2013, at 01:46, Stuart Halloway wrote: > Is the Scala for lazy or eager? If the latter, you are not comparing apples > to apples (separate from the other differences David already pointed out.) Oh, it's eager. Bear in mind that my purpose wasn't really to directly compare Scala and

Re: Request for help optimising a Clojure program

Ugh, I meant "negligible impact on the running time versus the current hashing strategy" On Wed, Oct 23, 2013 at 11:48 PM, Mark Engelberg wrote: > BTW, in the sample set hashing function I provided, > the `reduce +` should have been `reduce unchecked-add-int` > > I've done some timing tests (on a

Re: Request for help optimising a Clojure program

BTW, in the sample set hashing function I provided, the `reduce +` should have been `reduce unchecked-add-int` I've done some timing tests (on a loop/recur version that leverages primitive math better) and it looks like the strategy I proposed has a negligible impact on the current hashing strateg

Re: Request for help optimising a Clojure program

Agreed, set hashing is definitely a bigger issue. Also agree array indexing is is a pretty common use case, though if people care about performance for manipulating arrays of data with integer indexes then they should probably be looking at core.matrix rather than trying to simulate array progr

Re: Request for help optimising a Clojure program

OK, I get that if lists have to match the Java hash code, then it's a nonstarter to try to improve it. However, Clojure makes a distinction between hasheq and hashCode, one of which is used within Clojure and one of which is used for Java interop, and I don't think they necessarily need to match.

Re: Request for help optimising a Clojure program

On Thursday, 24 October 2013 09:12:21 UTC+8, puzzler wrote: > Even though vectors aren't as prone to collision between similar-looking > vectors, I think you are right that the smallness of the numbers is a > problem: > > Consider the following: > > => (count (set (for [x (range 200) y (range 20

Re: Request for help optimising a Clojure program

Even though vectors aren't as prone to collision between similar-looking vectors, I think you are right that the smallness of the numbers is a problem: Consider the following: => (count (set (for [x (range 200) y (range 200)] (hash [x y] 6369 This means that out of 40,000 common ordered pair

Re: Request for help optimising a Clojure program

Is the Scala for lazy or eager? If the latter, you are not comparing apples to apples (separate from the other differences David already pointed out.) Stu On Wed, Oct 23, 2013 at 8:41 PM, Mark Engelberg wrote: > Perhaps I don't understand your point, but vector hashing is not currently > the s

Re: Request for help optimising a Clojure program

Perhaps I don't understand your point, but vector hashing is not currently the sum of hashes. It's a more complex computation. => (hash [0 2]) 963 => (hash [2 0]) 1023 => (hash [2]) 33 The fact that numbers hash to themselves means that the resulting hashes are not hugely spread apart, but colli

Re: Request for help optimising a Clojure program

There's still a problem with collisions among *vectors* though. I'd say the real underlying problem is that small integers hash to themselves. If you let N be a fairly large number satisfying GCD(N, 2^32 - 1) = 1, then multiplying 32-bit integers by N would send nearby integers to widely separated

Re: Request for help optimising a Clojure program

I'd like to point out that my proposed hash function lends itself nicely to incremental hashing for sets. Furthermore, maps also have very weak hashing, and would benefit from a similar change. Right now: => (hash {1 1}) 0 => (hash {1 1 2 2}) 0 => (hash {1 1 2 2 3 3}) 0 => (hash {1 2 2 3 3 1}) 6

Re: Request for help optimising a Clojure program

OK, here is a more serious proposal, comprised of simple, fast operations: To hash a set, you take each of the items in the set, compute the hash value, xor it with the golden number, and square it. Add these results together. Essentially, it's the sum of the squares of the hashes, the xor is thr

Re: Request for help optimising a Clojure program

On Oct 23, 2013, at 17:03 , Mark Engelberg wrote: > It is true that it must be commutative, but not true that it must be > non-associative. Here is a sample implementation of a hash function for sets > that is commutative and associative but doesn't collide for these sorts of > common rearran

Re: Request for help optimising a Clojure program

It is true that it must be commutative, but not true that it must be non-associative. Here is a sample implementation of a hash function for sets that is commutative and associative but doesn't collide for these sorts of common rearrangements. The idea of this proof of concept is that the hash va

Re: Request for help optimising a Clojure program

On Oct 23, 2013, at 14:34 , Mark Engelberg wrote: > Another example of why this has more to do with the hashing of sets, than > underlying elements: > => (hash #{#{1 2} 3}) > 6 > => (hash #{#{1 3} 2}) > 6 The hash-combining function for sets must be commutative. But in order for the hashes of

Re: Request for help optimising a Clojure program

Another example of why this has more to do with the hashing of sets, than underlying elements: => (hash #{#{1 2} 3}) 6 => (hash #{#{1 3} 2}) 6 -- -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroup

Re: Request for help optimising a Clojure program

I see how changing the hash function for vectors/records/maps would be useful, because if their hash values were more widely distributed, then adding up those hash values would be less likely to yield the same sum. But wouldn't the simplest solution be to change the hashing strategy for sets to be

Re: Request for help optimising a Clojure program

On Oct 23, 2013, at 12:30 , Andy Fingerhut wrote: > If you can think of a different hash function for vectors that doesn't lead > to these types of collisions, I'm all ears. The issue is that the hash > function for sets adds up the hash values of its elements. Those sums of > vector hash va

Re: Request for help optimising a Clojure program

That makes them each different, but if you put them in a set together, like #{[1 2] [2 1]}, the hash of the set is 1-1=0 no matter what order those vectors are put into the set. That is the difficulty. On Wed, Oct 23, 2013 at 10:39 AM, Pablo Nussembaum wrote: > What do you think of adding odd

Re: Request for help optimising a Clojure program

On Wed, Oct 23, 2013 at 10:39 AM, Pablo Nussembaum wrote: > What do you think of adding odd elements and substract even ones? > > [1 2] = 1 - 2 = -1 > [2 1] = 2 - 1 = 1 > Wouldn't multiplying the hash values of the items in a set (rather than adding) result in far fewer accidental collisions fr

Re: Request for help optimising a Clojure program

What do you think of adding odd elements and substract even ones? [1 2] = 1 - 2 = -1 [2 1] = 2 - 1 = 1 On 10/23/2013 02:30 PM, Andy Fingerhut wrote: > If you can think of a different hash function for vectors that doesn't > lead to these types of collisions, I'm all ears. The issue is that > the

Re: Request for help optimising a Clojure program

The problem here is that you're not following your Scala solution closely enough. I suspect if you used defrecords to represent the pieces the way that you used a class in Scala you can avoid the number of collisions for larger problems. Not tested much but I tried something like the following and

Re: Request for help optimising a Clojure program

If you can think of a different hash function for vectors that doesn't lead to these types of collisions, I'm all ears. The issue is that the hash function for sets adds up the hash values of its elements. Those sums of vector hash values are what are colliding, not the individual vector hash val

Re: Request for help optimising a Clojure program

On 23 Oct 2013, at 18:15, Andy Fingerhut wrote: > If we had a 'universal comparator', i.e. a comparison function that provided > a total order on any pair of values that anyone would ever want to put into a > set or use as a map key, then instead of having linked lists for values that > collid

Re: Request for help optimising a Clojure program

Ah, right you are. I missed that. I think the collisions possible with PersistentHashSet and PersistentHashMap were 'well known', at least to a subset of people. What is probably less well known is a nice small program that caused many collisions with today's hash functions, and an explanation o

Re: Request for help optimising a Clojure program

One possibility of a change to PersistentHashSet and PersistentHashMap that would help avoid these cases with pathologically bad performance: If we had a 'universal comparator', i.e. a comparison function that provided a total order on any pair of values that anyone would ever want to put into a s

Re: Request for help optimising a Clojure program

On 23 Oct 2013, at 17:43, Andy Fingerhut wrote: > Paul, your function solve returns a set of solutions, but there is nothing on > the program that seems to rely upon being able to quickly test whether a > particular solution is in such a set. Returning a sequence from solve is > much faster,

Re: Request for help optimising a Clojure program

Paul, your function solve returns a set of solutions, but there is nothing on the program that seems to rely upon being able to quickly test whether a particular solution is in such a set. Returning a sequence from solve is much faster, since it avoids the PersistentHashSet hash collision issue en

Re: Request for help optimising a Clojure program

On 23 Oct 2013, at 17:06, Andy Fingerhut wrote: > I have instrumented a copy of Paul's Clojure program to print the hash code > of all of the solutions in the set returned by solve, and there are *many* > pairs of solutions that have identical hash values Aha! The smoking gun :-) Very many t

Re: Request for help optimising a Clojure program

Mark, I think you have hit the nail on the head. I have instrumented a copy of Paul's Clojure program to print the hash code of all of the solutions in the set returned by solve, and there are *many* pairs of solutions that have identical hash values, and thus collide in a PersistentHashSet. Belo

Re: Request for help optimising a Clojure program

For those of you playing along at home, I also ran Paul's chess program in YourKit with the sampling profiler. Here are all the calls that appear in the "HotSpots" view, along with time spent in those methods. java.io.PushbackInputStream.read() 422977 clojure.lang.PersistentHashMap$HashCollisionN

Re: Request for help optimising a Clojure program

On 23 Oct 2013, at 15:32, David Powell wrote: > When you say it is spending 99% of its time in PersistentHashSet.cons, is > that the time spent in just that method, or the time spent in that method and > the methods that it calls? The latter. > Given that (set ...) is one of the first things

Re: Request for help optimising a Clojure program

When you say it is spending 99% of its time in PersistentHashSet.cons, is that the time spent in just that method, or the time spent in that method and the methods that it calls? Given that (set ...) is one of the first things called by (solve..), and that its contents are produced lazily by a for

Re: Request for help optimising a Clojure program

On 23 Oct 2013, at 14:19, David Nolen wrote: > The Scala code is using immutable sets. Correct - the Scala is immutable throughout. -- paul.butcher->msgCount++ Snetterton, Castle Combe, Cadwell Park... Who says I have a one track mind? http://www.paulbutcher.com/ LinkedIn: http://www.linkedin

Re: Request for help optimising a Clojure program

On 23 Oct 2013, at 14:18, David Nolen wrote: > If set construction was 1000X worse why don't the smaller problem sizes > exhibit exactly the same issue? If the Scala version requires 12G why is the > Clojure version steady at 300M? Both excellent questions. > Aren't Scala for comprehensions o

Re: Request for help optimising a Clojure program

The Scala code is using immutable sets. On Wednesday, October 23, 2013, Timothy Baldridge wrote: > From what I can tell, Clojure uses persistent hash sets inside of set. > This can be fixed by replacing set with (into #{} data). Into uses > transients internally and should be much faster. > > I d

Re: Request for help optimising a Clojure program

If set construction was 1000X worse why don't the smaller problem sizes exhibit exactly the same issue? If the Scala version requires 12G why is the Clojure version steady at 300M? Aren't Scala for comprehensions optimized now into lower level loops? Clojure for comprehensions generate lazy sequen

Re: Request for help optimising a Clojure program

>From what I can tell, Clojure uses persistent hash sets inside of set. This can be fixed by replacing set with (into #{} data). Into uses transients internally and should be much faster. I don't know Scala, but from I can tell, Scala is using mutable collections. I think the combination of these

Re: Request for help optimising a Clojure program

On 23 Oct 2013, at 13:18, Timothy Baldridge wrote: > Great! you have a profiler, use that. Find the hotspots, use YourKit to find > where the .cons is being called from, find things to optimize, and go from > there. This is exactly the same process I would use any optimizations I > attempted.

Re: Request for help optimising a Clojure program

Eh, I said cons, but it's 6:30 in the morning. I meant the for's lazy seq requires at least one allocation per item. Your time spent in PersistentHashSet.cons is probably due to the use of set. Timothy On Wed, Oct 23, 2013 at 6:21 AM, Timothy Baldridge wrote: > This code will have a ton of allo

Re: Request for help optimising a Clojure program

This code will have a ton of allocations: (defn solve [rows cols pieces] (if (empty? pieces) #{#{}} (set (let [candidate (first pieces)] (for [solution (solve rows cols (rest pieces)) x (range 0 cols) y (range 0 rows) :when (allowed

Re: Request for help optimising a Clojure program

Great! you have a profiler, use that. Find the hotspots, use YourKit to find where the .cons is being called from, find things to optimize, and go from there. This is exactly the same process I would use any optimizations I attempted. Timothy On Wed, Oct 23, 2013 at 6:09 AM, Paul Butcher wrote:

Re: Request for help optimising a Clojure program

On 23 Oct 2013, at 12:44, Timothy Baldridge wrote: > That being said, the #1 rule of benchmarking with lein is don't benchmark > with lein. The JVM lein spins up has a different set of goals (namely startup > time). The best way to benchmark is to run the test several thousand times, > from a

Re: Request for help optimising a Clojure program

Lein doesn't use your specified JVM settings, you must override with ^:replace. It's also a good idea to set "-server" as Lein does not default to this. On Wednesday, October 23, 2013, Paul Butcher wrote: > On 23 Oct 2013, at 12:21, David Nolen > > > wrote: > > Those numbers make the larger prob

Re: Request for help optimising a Clojure program

Lein does some odd stuff to the JVM when it runs. Try adding ^:replace to jvm-opts: :jvm-opts ^:replace [] That being said, the #1 rule of benchmarking with lein is don't benchmark with lein. The JVM lein spins up has a different set of goals (namely startup time). The best way to benchmark i

Re: Request for help optimising a Clojure program

On 23 Oct 2013, at 12:21, David Nolen wrote: > Those numbers make the larger problem runtime suspect. How are you running > the Clojure version? With Lein? Yes - lein run. -- paul.butcher->msgCount++ Snetterton, Castle Combe, Cadwell Park... Who says I have a one track mind? http://www.paulb

Re: Request for help optimising a Clojure program

Those numbers make the larger problem runtime suspect. How are you running the Clojure version? With Lein? On Wednesday, October 23, 2013, Paul Butcher wrote: > On 22 Oct 2013, at 20:20, David Nolen > > > wrote: > > On Tue, Oct 22, 2013 at 3:11 PM, Paul Butcher > > > wrote: > >> Yeah - I have

Re: Request for help optimising a Clojure program

On 22 Oct 2013, at 20:20, David Nolen wrote: > On Tue, Oct 22, 2013 at 3:11 PM, Paul Butcher wrote: > Yeah - I have tried giving it more RAM without any effect on the timing > whatsoever. And I couldn't see the point of stopping people with less RAM > than that from being able to run it :-) >

Re: Request for help optimising a Clojure program

On Tue, Oct 22, 2013 at 3:11 PM, Paul Butcher wrote: > Yeah - I have tried giving it more RAM without any effect on the timing > whatsoever. And I couldn't see the point of stopping people with less RAM > than that from being able to run it :-) > But without enough RAM most JVMs will thrash in G

Re: Request for help optimising a Clojure program

On 22 Oct 2013, at 19:55, David Nolen wrote: > I note that the Clojure version isn't being given 12gigs of RAM, is this > something you're giving to the JVM after when you run a AOTed version of the > Clojure code. Yeah - I have tried giving it more RAM without any effect on the timing whatso

Re: Request for help optimising a Clojure program

On 22 Oct 2013, at 18:45, Mark Engelberg wrote: > I looked briefly at the code and can confirm that to my eye, the two > implementations appear to be implementing the same algorithm. Thanks - always good to have a second pair of eyes :-) > My first guess would be that the performance differenc

Re: Request for help optimising a Clojure program

I note that the Clojure version isn't being given 12gigs of RAM, is this something you're giving to the JVM after when you run a AOTed version of the Clojure code. You also haven't said whether the timings for the smaller problems are significantly different between Scala and Clojure. David On

Re: Request for help optimising a Clojure program

I looked briefly at the code and can confirm that to my eye, the two implementations appear to be implementing the same algorithm. My first guess would be that the performance difference comes from Clojure's use of boxed numbers for all the positions. Possibly you could get better performance by

Request for help optimising a Clojure program

I've been playing around with a generalised version of the N-Queens problem that handles other chess pieces. I have a Scala implementation that uses an eager depth-first search. Given enough RAM (around 12G - it's very memory hungry!) it can solve a 6x9 board with 6 pieces in around 2.5 minutes