[ANN] clojure.data.priority-map 0.0.3
https://github.com/clojure/data.priority-map/
A priority map is similar to a sorted map, but sorts the entries by the
values rather than the keys in the map. Think of it as a kind of priority
queue with a full map-like API to query, add, adjust, and remove items and
their priorities.
The new 0.0.3 version addresses a common need where the items map to
complex values which contain the priority, or from which the priority can
be derived.
For example, consider a map:
{:apple {:weight 2, :color :red}, :orange {:weight 2, color :orange},
:banana {:weight 3, color :yellow}}
where you want to sort the map by the fruit's weight.
A common pitfall was to try to solve this with a custom comparator which
compares only on weight. This doesn't work properly because of the
Clojure/Java rule that valid comparators must be total orders. Among
other things, this means the comparator can't have ties between unequal
objects (known as the trichotomy property).
[See https://groups.google.com/forum/#!msg/clojure/VKvH_eg_FtE/Kpy18zGtio4Jfor
one such discussion about this pitfall]
Users were instructed to rework their comparator into a total order, but
for some use cases, this can be a tricky proposition.
To address this need, the new version allows one to specify a keyfn which
extracts or computes the sort keys (i.e., priority) from the map's values.
This is done with one of two new constructors:
priority-map-keyfn (takes a custom keyfn)
priority-map-keyfn-by (takes a custom keyfn and custom comparator)
So for example, the above map could be expressed as:
(priority-map-keyfn :weight
:apple {:weight 2, :color :red}, :orange {:weight 2, color :orange},
:banana {:weight 3, color :yellow})
See the README for further explanation, and let me know if you have any
questions.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
[ANN] Teuta - laughingly simple dependency injection container
Hi all, I'm still fresh to Clojure, so be gentle :) Like so many Java-to-Clojure converts out there, my mind is used to structuring apps using DI containers (a-la Spring), and since I don't see that DI components are going against FP nature of Clojure, so I decided to create my own little DI container. There are some other Clojure libs that tackle this same space, but they are somewhat different than what a typical java developer is used to. Anyway, here is blog post about it: http://pannoniancoder.blogspot.com/2013/10/introducing-teuta-laughingly-simple.html And the project is at: https://github.com/vmarcinko/teuta Any feedback more than welcome. Regards, Vjeran -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: jdbc timestamp automatic timezone
I ended up using a workaround: formatting the timestamps using the timezone offset. However I'm sure there is a better way. Thank you Manuel, I didn't find a better way either. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: JVM assertions in Clojure
Clearly, global overhead of assertions depends on number and type of invariants that you check. My experience was simliar to Paul's. Compililng/disabling the assertions away helps a great deal in many cases. Paul ! I've started using pjstadig.assertions and it works like a charm :) **Thank you very much for sharing!** Best regards, Michał -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Request for help optimising a Clojure program
On 22 Oct 2013, at 20:20, David Nolen dnolen.li...@gmail.com wrote: On Tue, Oct 22, 2013 at 3:11 PM, Paul Butcher p...@paulbutcher.com 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 GC when running that code. Yes, of course. But as I said, I tried giving it more RAM (the same 12G as the Scala solution) and it made no difference whatsoever. In fact, YourKit shows me that, even after running for an hour (i.e. more than 10x longer than the Scala version takes to return the full solution) the Clojure version is still using less than 2G. Whatever is going on, it's not a result of a lack of RAM. Saying both run in less than a second is not particularly informative for the small problems :) Does Scala take 4ms and Clojure takes 400ms on the small problems? That's a big difference. Yes, of course. But my experience with small problems has been that differences between execution time, especially when talking about runtimes as dissimilar as the Clojure and Scala runtimes, are meaningless. Those differences tend to have more to do with startup costs and the vagaries of when hotspot happens to optimise things than anything fundamental. But you asked, so here it is: For Clojure, the 3x3 problem takes 7ms and the 4x4 problem takes 78ms. For Scala, it's 15ms and 252ms respectively. -- paul.butcher-msgCount++ Snetterton, Castle Combe, Cadwell Park... Who says I have a one track mind? http://www.paulbutcher.com/ LinkedIn: http://www.linkedin.com/in/paulbutcher MSN: p...@paulbutcher.com AIM: paulrabutcher Skype: paulrabutcher On 22 Oct 2013, at 20:20, David Nolen dnolen.li...@gmail.com wrote: On Tue, Oct 22, 2013 at 3:11 PM, Paul Butcher p...@paulbutcher.com 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 GC when running that code. Saying both run in less than a second is not particularly informative for the small problems :) Does Scala take 4ms and Clojure takes 400ms on the small problems? That's a big difference. David -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure can't import some Java classes
I've also had a lot of problems with def'ed forms. For example, if I do
this:
(def no-spacing (Spacing/createSpacing 0 0 0 false 0))
Which looks like this:
public static Spacing createSpacing(int minSpaces,
int maxSpaces,
int minLineFeeds,
boolean keepLineBreaks,
int keepBlankLines) {
return myFactory.createSpacing(minSpaces, maxSpaces, minLineFeeds,
keepLineBreaks, keepBlankLines);
}
myFactory is injected at some earlier point:
static void setFactory(SpacingFactory factory) {
myFactory = factory;
}
But during compilation that obviously hasn't happened and I get an NPE
during compilation. It's a little annoying that there really seems to be no
good way to create this value at namespace load time if I'm AOT compiling.
I can obviously defer it using defn with memoize or something, but that
seems clunky for what doesn't seem like that crazy a use case.
On 23 October 2013 15:21, Zach Oakes zsoa...@gmail.com wrote:
Here's the error I get when I import LibGDX's Timer class:
http://pastebin.com/q7wys8yi
On Tuesday, October 22, 2013 9:55:16 PM UTC-4, Alex Miller wrote:
I'd love to see a stack trace when that happens (could even be triggered
by dumping stack in your static initializer if nothing else).
On Saturday, October 12, 2013 3:17:50 AM UTC-5, Wujek Srujek wrote:
So you are saying compilation is trying to instantiate class and run
static initializers? This seems very backward, are you sure?
On Sat, Oct 12, 2013 at 8:30 AM, Zach Oakes zso...@gmail.com wrote:
I should add, I am aware I can bring in a class dynamically with
Class/forName, and that is what I ended up doing for the Timer class.
However, this is not always practical, and sometimes is simply not an
option if aot-compilation is required.
On Saturday, October 12, 2013 2:28:38 AM UTC-4, Zach Oakes wrote:
I recently learned that merely importing a Java class in Clojure
causes static initializers to be run. Sometimes, this causes compilation
errors, because they are written with the assumption that they will only
be
run during runtime.
I ran into this just now while trying to make a simple Clojure game
with LibGDX. After simply importing its Timer class, I began getting
compilation errors. The stack trace shows it is due to a static
initializerhttps://github.com/libgdx/libgdx/blob/511b557c1a2d23bf8110a05b0ef54cc20b7f958d/gdx/src/com/badlogic/gdx/utils/Timer.java#L32attempting
to instantiate the class!
I also ran into this recently while trying to use RoboVM. My question
is, do I have any options? I haven't found many discussions about this
here
or elsewhere. This surprises me, because it seems like something more
people should be running into.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/**group/clojure?hl=enhttp://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google
Groups Clojure group.
To unsubscribe from this group and stop receiving emails from it, send
an email to clojure+u...@googlegroups.com.
For more options, visit
https://groups.google.com/**groups/opt_outhttps://groups.google.com/groups/opt_out
.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an
email to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an email
to
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
dnolen.li...@gmail.comjavascript:_e({}, 'cvml', 'dnolen.li...@gmail.com');
wrote:
On Tue, Oct 22, 2013 at 3:11 PM, Paul Butcher
p...@paulbutcher.comjavascript:_e({}, 'cvml', 'p...@paulbutcher.com');
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 GC when running that code.
Yes, of course. But as I said, I tried giving it more RAM (the same 12G as
the Scala solution) and it made no difference whatsoever. In fact, YourKit
shows me that, even after running for an hour (i.e. more than 10x longer
than the Scala version takes to return the full solution) the Clojure
version is still using less than 2G. Whatever is going on, it's not a
result of a lack of RAM.
Saying both run in less than a second is not particularly informative for
the small problems :) Does Scala take 4ms and Clojure takes 400ms on the
small problems? That's a big difference.
Yes, of course. But my experience with small problems has been that
differences between execution time, especially when talking about runtimes
as dissimilar as the Clojure and Scala runtimes, are meaningless. Those
differences tend to have more to do with startup costs and the vagaries of
when hotspot happens to optimise things than anything fundamental.
But you asked, so here it is:
For Clojure, the 3x3 problem takes 7ms and the 4x4 problem takes 78ms. For
Scala, it's 15ms and 252ms respectively.
--
paul.butcher-msgCount++
Snetterton, Castle Combe, Cadwell Park...
Who says I have a one track mind?
http://www.paulbutcher.com/
LinkedIn: http://www.linkedin.com/in/paulbutcher
MSN: p...@paulbutcher.com javascript:_e({}, 'cvml',
'p...@paulbutcher.com');
AIM: paulrabutcher
Skype: paulrabutcher
On 22 Oct 2013, at 20:20, David Nolen
dnolen.li...@gmail.comjavascript:_e({}, 'cvml', 'dnolen.li...@gmail.com');
wrote:
On Tue, Oct 22, 2013 at 3:11 PM, Paul Butcher
p...@paulbutcher.comjavascript:_e({}, 'cvml', 'p...@paulbutcher.com');
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 GC when running that code.
Saying both run in less than a second is not particularly informative for
the small problems :) Does Scala take 4ms and Clojure takes 400ms on the
small problems? That's a big difference.
David
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to
clojure@googlegroups.comjavascript:_e({}, 'cvml',
'clojure@googlegroups.com');
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com javascript:_e({}, 'cvml',
'clojure+unsubscr...@googlegroups.com');
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an
email to clojure+unsubscr...@googlegroups.com javascript:_e({}, 'cvml',
'clojure+unsubscr...@googlegroups.com');.
For more options, visit https://groups.google.com/groups/opt_out.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to
clojure@googlegroups.comjavascript:_e({}, 'cvml',
'clojure@googlegroups.com');
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com javascript:_e({}, 'cvml',
'clojure%2bunsubscr...@googlegroups.com');
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an
email to clojure+unsubscr...@googlegroups.com javascript:_e({}, 'cvml',
'clojure%2bunsubscr...@googlegroups.com');.
For more options, visit https://groups.google.com/groups/opt_out.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this
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 is to run the test several thousand times, from a jar created with lein uberjar. Timothy On Wed, Oct 23, 2013 at 5:22 AM, Paul Butcher p...@paulbutcher.com wrote: On 23 Oct 2013, at 12:21, David Nolen dnolen.li...@gmail.com 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.paulbutcher.com/ LinkedIn: http://www.linkedin.com/in/paulbutcher MSN: p...@paulbutcher.com AIM: paulrabutcher Skype: paulrabutcher -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- “One of the main causes of the fall of the Roman Empire was that–lacking zero–they had no way to indicate successful termination of their C programs.” (Robert Firth) -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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
dnolen.li...@gmail.comjavascript:_e({}, 'cvml', 'dnolen.li...@gmail.com');
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.paulbutcher.com/
LinkedIn: http://www.linkedin.com/in/paulbutcher
MSN: p...@paulbutcher.com javascript:_e({}, 'cvml',
'p...@paulbutcher.com');
AIM: paulrabutcher
Skype: paulrabutcher
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to
clojure@googlegroups.comjavascript:_e({}, 'cvml',
'clojure@googlegroups.com');
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com javascript:_e({}, 'cvml',
'clojure%2bunsubscr...@googlegroups.com');
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an
email to clojure+unsubscr...@googlegroups.com javascript:_e({}, 'cvml',
'clojure%2bunsubscr...@googlegroups.com');.
For more options, visit https://groups.google.com/groups/opt_out.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
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 p...@paulbutcher.com wrote: On 23 Oct 2013, at 12:44, Timothy Baldridge tbaldri...@gmail.com 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 jar created with lein uberjar. I'm well aware of the issues associated with micro-benchmarking on the JVM. Bear in mind that what I'm doing isn't micro-benchmarking. I have a Scala program that runs in 2.5 minutes, which when re-implemented in Clojure doesn't finish after being run overnight. I.e. the Clojure is (at least) 2 orders of magnitude slower than the Scala. I'd love to be able to run it just once - running it thousands of times with its current performance would require *years*. I've now got it recompiled as an uberjar and I'm running it with 12G RAM (-Xms12G -Xmx12G). So far, it's been running for 12 minutes (i.e. 6x longer than the Scala version takes to complete) and YourKit shows me that it's used less than 300MB RAM (i.e. the vast majority of the 12G is unused). YourKit also shows me that it's still the case that it's spending 99% of its time in PersistentHashSet.cons. I completely understand that playing around with pre-compilation and JVM settings will make a difference to the observed performance. But not two orders of magnitude difference, surely? It strikes me that there's clearly something that I'm missing in the Clojure implementation that's making a dramatic difference to performance. I'd love some help determining what that something is. -- paul.butcher-msgCount++ Snetterton, Castle Combe, Cadwell Park... Who says I have a one track mind? http://www.paulbutcher.com/ LinkedIn: http://www.linkedin.com/in/paulbutcher MSN: p...@paulbutcher.com AIM: paulrabutcher Skype: paulrabutcher -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- “One of the main causes of the fall of the Roman Empire was that–lacking zero–they had no way to indicate successful termination of their C programs.” (Robert Firth) -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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? candidate [x y] solution)]
(conj solution [candidate [x y]]))
Every item in the cons will require an allocation. After that, the
entire thing has to be turned into a set. This entire thing is also
recursive, so that compounds the problem. Perhaps re-write this as a
reducer?
Timothy
On Wed, Oct 23, 2013 at 6:18 AM, Timothy Baldridge tbaldri...@gmail.comwrote:
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 p...@paulbutcher.comwrote:
On 23 Oct 2013, at 12:44, Timothy Baldridge tbaldri...@gmail.com 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 jar created with lein uberjar.
I'm well aware of the issues associated with micro-benchmarking on the
JVM. Bear in mind that what I'm doing isn't micro-benchmarking. I have a
Scala program that runs in 2.5 minutes, which when re-implemented in
Clojure doesn't finish after being run overnight. I.e. the Clojure is (at
least) 2 orders of magnitude slower than the Scala.
I'd love to be able to run it just once - running it thousands of times
with its current performance would require *years*.
I've now got it recompiled as an uberjar and I'm running it with 12G RAM
(-Xms12G -Xmx12G). So far, it's been running for 12 minutes (i.e. 6x longer
than the Scala version takes to complete) and YourKit shows me that it's
used less than 300MB RAM (i.e. the vast majority of the 12G is unused).
YourKit also shows me that it's still the case that it's spending 99% of
its time in PersistentHashSet.cons.
I completely understand that playing around with pre-compilation and JVM
settings will make a difference to the observed performance. But not two
orders of magnitude difference, surely?
It strikes me that there's clearly something that I'm missing in the
Clojure implementation that's making a dramatic difference to performance.
I'd love some help determining what that something is.
--
paul.butcher-msgCount++
Snetterton, Castle Combe, Cadwell Park...
Who says I have a one track mind?
http://www.paulbutcher.com/
LinkedIn: http://www.linkedin.com/in/paulbutcher
MSN: p...@paulbutcher.com
AIM: paulrabutcher
Skype: paulrabutcher
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an
email to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
“One of the main causes of the fall of the Roman Empire was that–lacking
zero–they had no way to indicate successful termination of their C
programs.”
(Robert Firth)
--
“One of the main causes of the fall of the Roman Empire was that–lacking
zero–they had no way to indicate successful termination of their C
programs.”
(Robert Firth)
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
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 tbaldri...@gmail.comwrote:
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? candidate [x y] solution)]
(conj solution [candidate [x y]]))
Every item in the cons will require an allocation. After that, the entire
thing has to be turned into a set. This entire thing is also recursive, so
that compounds the problem. Perhaps re-write this as a reducer?
Timothy
On Wed, Oct 23, 2013 at 6:18 AM, Timothy Baldridge
tbaldri...@gmail.comwrote:
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 p...@paulbutcher.comwrote:
On 23 Oct 2013, at 12:44, Timothy Baldridge tbaldri...@gmail.com
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 jar created with lein uberjar.
I'm well aware of the issues associated with micro-benchmarking on the
JVM. Bear in mind that what I'm doing isn't micro-benchmarking. I have a
Scala program that runs in 2.5 minutes, which when re-implemented in
Clojure doesn't finish after being run overnight. I.e. the Clojure is (at
least) 2 orders of magnitude slower than the Scala.
I'd love to be able to run it just once - running it thousands of times
with its current performance would require *years*.
I've now got it recompiled as an uberjar and I'm running it with 12G RAM
(-Xms12G -Xmx12G). So far, it's been running for 12 minutes (i.e. 6x longer
than the Scala version takes to complete) and YourKit shows me that it's
used less than 300MB RAM (i.e. the vast majority of the 12G is unused).
YourKit also shows me that it's still the case that it's spending 99% of
its time in PersistentHashSet.cons.
I completely understand that playing around with pre-compilation and JVM
settings will make a difference to the observed performance. But not two
orders of magnitude difference, surely?
It strikes me that there's clearly something that I'm missing in the
Clojure implementation that's making a dramatic difference to performance.
I'd love some help determining what that something is.
--
paul.butcher-msgCount++
Snetterton, Castle Combe, Cadwell Park...
Who says I have a one track mind?
http://www.paulbutcher.com/
LinkedIn: http://www.linkedin.com/in/paulbutcher
MSN: p...@paulbutcher.com
AIM: paulrabutcher
Skype: paulrabutcher
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google
Groups Clojure group.
To unsubscribe from this group and stop receiving emails from it, send
an email to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
“One of the main causes of the fall of the Roman Empire was that–lacking
zero–they had no way to indicate successful termination of their C
programs.”
(Robert Firth)
--
“One of the main causes of the fall of the Roman Empire was that–lacking
zero–they had no way to indicate successful termination of their C
programs.”
(Robert Firth)
--
“One of the main causes of the fall of the Roman Empire was that–lacking
zero–they had no way to indicate successful termination of their C
programs.”
(Robert Firth)
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving
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 two things (immutable
collections plus lack of transients) could be causing some performance
impact. I wouldn't expect it to be 1000x but it's a starting place.
Timothy
On Wed, Oct 23, 2013 at 6:36 AM, Paul Butcher p...@paulbutcher.com wrote:
On 23 Oct 2013, at 13:18, Timothy Baldridge tbaldri...@gmail.com 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.
I fear I may have failed to convey the question I'm trying to answer.
I'm sure that I could create a faster solution in Clojure - that's not the
question I'm trying to answer though.
What I'm trying to answer is why the *exact same* algorithm implemented in
Scala is 1000x faster.
As far as I know, the Scala version of the algorithm creates exactly as
many sets and performs exactly as many set operations as the Clojure does.
But the Clojure version is 1000x slower. That strikes me as very strange
and worth getting to the bottom of?
I have, of course, looked at the result of the profiler. And what it seems
to be saying is that set operations in Clojure are ruinously slow. I'm not
sure that I believe that though - I can't think of any reason why Clojure's
sets should be 1000x slower than Scala's? So I'm asking for the help of
this list.
Of course, I can't rule out the possibility that I've failed to convert
the Scala version to Clojure and they're actually implementing very
different algorithms - but I've had several people look at the
implementations and confirm that they appear to be the same. Nevertheless,
if there is a problem there, I'd also be interested to find it as I'm sure
that it will teach me something.
--
paul.butcher-msgCount++
Snetterton, Castle Combe, Cadwell Park...
Who says I have a one track mind?
http://www.paulbutcher.com/
LinkedIn: http://www.linkedin.com/in/paulbutcher
MSN: p...@paulbutcher.com
AIM: paulrabutcher
Skype: paulrabutcher
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an
email to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
“One of the main causes of the fall of the Roman Empire was that–lacking
zero–they had no way to indicate successful termination of their C
programs.”
(Robert Firth)
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: Request for help optimising a Clojure program
On 23 Oct 2013, at 14:18, David Nolen dnolen.li...@gmail.com 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 optimized now into lower level loops? Clojure for comprehensions generate lazy sequences and all the allocation and forcing of thunks that implies. I don't think so - AFAIK Scala's for statement is rewritten into flatMap and map under the hood. Happy to be corrected though. -- paul.butcher-msgCount++ Snetterton, Castle Combe, Cadwell Park... Who says I have a one track mind? http://www.paulbutcher.com/ LinkedIn: http://www.linkedin.com/in/paulbutcher MSN: p...@paulbutcher.com AIM: paulrabutcher Skype: paulrabutcher -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Request for help optimising a Clojure program
On 23 Oct 2013, at 14:19, David Nolen dnolen.li...@gmail.com 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.com/in/paulbutcher MSN: p...@paulbutcher.com AIM: paulrabutcher Skype: paulrabutcher -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure can't import some Java classes
I'm not sure if this is related to the original problem.
How is the setFactory method expected to be invoked, through some sort of
dependency injection framework?
On Wed, Oct 23, 2013 at 7:06 AM, Colin Fleming
colin.mailingl...@gmail.comwrote:
I've also had a lot of problems with def'ed forms. For example, if I do
this:
(def no-spacing (Spacing/createSpacing 0 0 0 false 0))
Which looks like this:
public static Spacing createSpacing(int minSpaces,
int maxSpaces,
int minLineFeeds,
boolean keepLineBreaks,
int keepBlankLines) {
return myFactory.createSpacing(minSpaces, maxSpaces, minLineFeeds,
keepLineBreaks, keepBlankLines);
}
myFactory is injected at some earlier point:
static void setFactory(SpacingFactory factory) {
myFactory = factory;
}
But during compilation that obviously hasn't happened and I get an NPE
during compilation. It's a little annoying that there really seems to be no
good way to create this value at namespace load time if I'm AOT compiling.
I can obviously defer it using defn with memoize or something, but that
seems clunky for what doesn't seem like that crazy a use case.
On 23 October 2013 15:21, Zach Oakes zsoa...@gmail.com wrote:
Here's the error I get when I import LibGDX's Timer class:
http://pastebin.com/q7wys8yi
On Tuesday, October 22, 2013 9:55:16 PM UTC-4, Alex Miller wrote:
I'd love to see a stack trace when that happens (could even be triggered
by dumping stack in your static initializer if nothing else).
On Saturday, October 12, 2013 3:17:50 AM UTC-5, Wujek Srujek wrote:
So you are saying compilation is trying to instantiate class and run
static initializers? This seems very backward, are you sure?
On Sat, Oct 12, 2013 at 8:30 AM, Zach Oakes zso...@gmail.com wrote:
I should add, I am aware I can bring in a class dynamically with
Class/forName, and that is what I ended up doing for the Timer class.
However, this is not always practical, and sometimes is simply not an
option if aot-compilation is required.
On Saturday, October 12, 2013 2:28:38 AM UTC-4, Zach Oakes wrote:
I recently learned that merely importing a Java class in Clojure
causes static initializers to be run. Sometimes, this causes compilation
errors, because they are written with the assumption that they will only
be
run during runtime.
I ran into this just now while trying to make a simple Clojure game
with LibGDX. After simply importing its Timer class, I began getting
compilation errors. The stack trace shows it is due to a static
initializerhttps://github.com/libgdx/libgdx/blob/511b557c1a2d23bf8110a05b0ef54cc20b7f958d/gdx/src/com/badlogic/gdx/utils/Timer.java#L32attempting
to instantiate the class!
I also ran into this recently while trying to use RoboVM. My question
is, do I have any options? I haven't found many discussions about this
here
or elsewhere. This surprises me, because it seems like something more
people should be running into.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient
with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/**group/clojure?hl=enhttp://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google
Groups Clojure group.
To unsubscribe from this group and stop receiving emails from it, send
an email to clojure+u...@googlegroups.com.
For more options, visit
https://groups.google.com/**groups/opt_outhttps://groups.google.com/groups/opt_out
.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an
email to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options,
Re: Clojure can't import some Java classes
So, is this a correct summary of the problem? Importing a class in clojure causes static initializers to run. This differs from Java where static initializers don't run until the first 'initialization' (either the invocation of a constructor, or invocation of a 'main' method) of a class. In some cases, this makes it impossible to create the environment that java classes expect to be present before they are initialized. On Tuesday, October 22, 2013, Zach Oakes wrote: Here's the error I get when I import LibGDX's Timer class: http://pastebin.com/q7wys8yi On Tuesday, October 22, 2013 9:55:16 PM UTC-4, Alex Miller wrote: I'd love to see a stack trace when that happens (could even be triggered by dumping stack in your static initializer if nothing else). On Saturday, October 12, 2013 3:17:50 AM UTC-5, Wujek Srujek wrote: So you are saying compilation is trying to instantiate class and run static initializers? This seems very backward, are you sure? On Sat, Oct 12, 2013 at 8:30 AM, Zach Oakes zso...@gmail.com wrote: I should add, I am aware I can bring in a class dynamically with Class/forName, and that is what I ended up doing for the Timer class. However, this is not always practical, and sometimes is simply not an option if aot-compilation is required. On Saturday, October 12, 2013 2:28:38 AM UTC-4, Zach Oakes wrote: I recently learned that merely importing a Java class in Clojure causes static initializers to be run. Sometimes, this causes compilation errors, because they are written with the assumption that they will only be run during runtime. I ran into this just now while trying to make a simple Clojure game with LibGDX. After simply importing its Timer class, I began getting compilation errors. The stack trace shows it is due to a static initializerhttps://github.com/libgdx/libgdx/blob/511b557c1a2d23bf8110a05b0ef54cc20b7f958d/gdx/src/com/badlogic/gdx/utils/Timer.java#L32attempting to instantiate the class! I also ran into this recently while trying to use RoboVM. My question is, do I have any options? I haven't found many discussions about this here or elsewhere. This surprises me, because it seems like something more people should be running into. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure can't import some Java classes
That's how I read things. Importing a class causes the class to be loaded (via Class.forName()) so that it can be stored in the namespace's mappings. My impression from the commented out older code is that some prior incarnation of the code used class names instead of Class objects in some prior incarnation which would avoid the loading. Seems like importing could potentially defer loading till use (and loading could still be forced via Class.forName() if needed). On Wednesday, October 23, 2013 9:00:28 AM UTC-5, Aaron Cohen wrote: So, is this a correct summary of the problem? Importing a class in clojure causes static initializers to run. This differs from Java where static initializers don't run until the first 'initialization' (either the invocation of a constructor, or invocation of a 'main' method) of a class. In some cases, this makes it impossible to create the environment that java classes expect to be present before they are initialized. On Tuesday, October 22, 2013, Zach Oakes wrote: Here's the error I get when I import LibGDX's Timer class: http://pastebin.com/q7wys8yi On Tuesday, October 22, 2013 9:55:16 PM UTC-4, Alex Miller wrote: I'd love to see a stack trace when that happens (could even be triggered by dumping stack in your static initializer if nothing else). On Saturday, October 12, 2013 3:17:50 AM UTC-5, Wujek Srujek wrote: So you are saying compilation is trying to instantiate class and run static initializers? This seems very backward, are you sure? On Sat, Oct 12, 2013 at 8:30 AM, Zach Oakes zso...@gmail.com wrote: I should add, I am aware I can bring in a class dynamically with Class/forName, and that is what I ended up doing for the Timer class. However, this is not always practical, and sometimes is simply not an option if aot-compilation is required. On Saturday, October 12, 2013 2:28:38 AM UTC-4, Zach Oakes wrote: I recently learned that merely importing a Java class in Clojure causes static initializers to be run. Sometimes, this causes compilation errors, because they are written with the assumption that they will only be run during runtime. I ran into this just now while trying to make a simple Clojure game with LibGDX. After simply importing its Timer class, I began getting compilation errors. The stack trace shows it is due to a static initializerhttps://github.com/libgdx/libgdx/blob/511b557c1a2d23bf8110a05b0ef54cc20b7f958d/gdx/src/com/badlogic/gdx/utils/Timer.java#L32attempting to instantiate the class! I also ran into this recently while trying to use RoboVM. My question is, do I have any options? I haven't found many discussions about this here or elsewhere. This surprises me, because it seems like something more people should be running into. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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 comprehension, if you are looking at the total time spent in PersistentHashSet.assoc, then maybe that will be particularly slow. Not that that solves the problem, but I was wondering if PersistentHashSet.assoc might be a red herring. Also, out of interest, are you using a sampling profiler, or an instrumenting one? Sometimes the built-in hprof profiler is good for this sort of thing: java -Xrunhprof:cpu=times,depth=4 -Xmx2g -jar target\chess-clojure-0.1.0-SNAPSHOT-standalone.jar - you can use either cpu=times for instrumenting, or cpu=samples for sampling. It is nice because the depth parameter lets you find hotspots including a few steps up the stacktrace (4 in this case). And you can use Ctrl-\ / Ctrl-Break / SIG_QUIT to get it to dump the current stats while the program is still running to see if some methods are getting worse over time. On Wed, Oct 23, 2013 at 1:36 PM, Paul Butcher p...@paulbutcher.com wrote: On 23 Oct 2013, at 13:18, Timothy Baldridge tbaldri...@gmail.com 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. I fear I may have failed to convey the question I'm trying to answer. I'm sure that I could create a faster solution in Clojure - that's not the question I'm trying to answer though. What I'm trying to answer is why the *exact same* algorithm implemented in Scala is 1000x faster. As far as I know, the Scala version of the algorithm creates exactly as many sets and performs exactly as many set operations as the Clojure does. But the Clojure version is 1000x slower. That strikes me as very strange and worth getting to the bottom of? I have, of course, looked at the result of the profiler. And what it seems to be saying is that set operations in Clojure are ruinously slow. I'm not sure that I believe that though - I can't think of any reason why Clojure's sets should be 1000x slower than Scala's? So I'm asking for the help of this list. Of course, I can't rule out the possibility that I've failed to convert the Scala version to Clojure and they're actually implementing very different algorithms - but I've had several people look at the implementations and confirm that they appear to be the same. Nevertheless, if there is a problem there, I'd also be interested to find it as I'm sure that it will teach me something. -- paul.butcher-msgCount++ Snetterton, Castle Combe, Cadwell Park... Who says I have a one track mind? http://www.paulbutcher.com/ LinkedIn: http://www.linkedin.com/in/paulbutcher MSN: p...@paulbutcher.com AIM: paulrabutcher Skype: paulrabutcher -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure can't import some Java classes
Agreed - merely importing this class shouldn't be an issue (which is the
issue at hand).
If you need to configure Spacing, you should do that prior to using it in
your def, but that should work fine. If that needs to happen at runtime,
then you shouldn't do this in a def.
On Wednesday, October 23, 2013 9:01:15 AM UTC-5, Aaron Cohen wrote:
I'm not sure if this is related to the original problem.
How is the setFactory method expected to be invoked, through some sort of
dependency injection framework?
On Wed, Oct 23, 2013 at 7:06 AM, Colin Fleming
colin.ma...@gmail.comjavascript:
wrote:
I've also had a lot of problems with def'ed forms. For example, if I do
this:
(def no-spacing (Spacing/createSpacing 0 0 0 false 0))
Which looks like this:
public static Spacing createSpacing(int minSpaces,
int maxSpaces,
int minLineFeeds,
boolean keepLineBreaks,
int keepBlankLines) {
return myFactory.createSpacing(minSpaces, maxSpaces, minLineFeeds,
keepLineBreaks, keepBlankLines);
}
myFactory is injected at some earlier point:
static void setFactory(SpacingFactory factory) {
myFactory = factory;
}
But during compilation that obviously hasn't happened and I get an NPE
during compilation. It's a little annoying that there really seems to be no
good way to create this value at namespace load time if I'm AOT compiling.
I can obviously defer it using defn with memoize or something, but that
seems clunky for what doesn't seem like that crazy a use case.
On 23 October 2013 15:21, Zach Oakes zso...@gmail.com javascript:wrote:
Here's the error I get when I import LibGDX's Timer class:
http://pastebin.com/q7wys8yi
On Tuesday, October 22, 2013 9:55:16 PM UTC-4, Alex Miller wrote:
I'd love to see a stack trace when that happens (could even be
triggered by dumping stack in your static initializer if nothing else).
On Saturday, October 12, 2013 3:17:50 AM UTC-5, Wujek Srujek wrote:
So you are saying compilation is trying to instantiate class and run
static initializers? This seems very backward, are you sure?
On Sat, Oct 12, 2013 at 8:30 AM, Zach Oakes zso...@gmail.com wrote:
I should add, I am aware I can bring in a class dynamically with
Class/forName, and that is what I ended up doing for the Timer class.
However, this is not always practical, and sometimes is simply not an
option if aot-compilation is required.
On Saturday, October 12, 2013 2:28:38 AM UTC-4, Zach Oakes wrote:
I recently learned that merely importing a Java class in Clojure
causes static initializers to be run. Sometimes, this causes
compilation
errors, because they are written with the assumption that they will
only be
run during runtime.
I ran into this just now while trying to make a simple Clojure game
with LibGDX. After simply importing its Timer class, I began getting
compilation errors. The stack trace shows it is due to a static
initializerhttps://github.com/libgdx/libgdx/blob/511b557c1a2d23bf8110a05b0ef54cc20b7f958d/gdx/src/com/badlogic/gdx/utils/Timer.java#L32attempting
to instantiate the class!
I also ran into this recently while trying to use RoboVM. My
question is, do I have any options? I haven't found many discussions
about
this here or elsewhere. This surprises me, because it seems like
something
more people should be running into.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient
with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/**group/clojure?hl=enhttp://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google
Groups Clojure group.
To unsubscribe from this group and stop receiving emails from it,
send an email to clojure+u...@googlegroups.com.
For more options, visit
https://groups.google.com/**groups/opt_outhttps://groups.google.com/groups/opt_out
.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clo...@googlegroups.comjavascript:
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com javascript:
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google
Groups Clojure group.
To unsubscribe from this group and stop receiving emails from it, send
an email to clojure+u...@googlegroups.com
Re: Request for help optimising a Clojure program
On 23 Oct 2013, at 15:32, David Powell djpow...@djpowell.net 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 called by (solve..), and that its contents are produced lazily by a for comprehension, if you are looking at the total time spent in PersistentHashSet.assoc, then maybe that will be particularly slow. Not that that solves the problem, but I was wondering if PersistentHashSet.assoc might be a red herring. Ah - that's entirely plausible. I have basically no experience of profiling Clojure, or understanding the way in which laziness affects doing so (I suspect that it complicates things somewhat?). Also, out of interest, are you using a sampling profiler, or an instrumenting one? Sampling. Sometimes the built-in hprof profiler is good for this sort of thing: java -Xrunhprof:cpu=times,depth=4 -Xmx2g -jar target\chess-clojure-0.1.0-SNAPSHOT-standalone.jar - you can use either cpu=times for instrumenting, or cpu=samples for sampling. It is nice because the depth parameter lets you find hotspots including a few steps up the stacktrace (4 in this case). And you can use Ctrl-\ / Ctrl-Break / SIG_QUIT to get it to dump the current stats while the program is still running to see if some methods are getting worse over time. I've not used hprof before - I'll see if I can divine anything useful from it. Thanks. -- paul.butcher-msgCount++ Snetterton, Castle Combe, Cadwell Park... Who says I have a one track mind? http://www.paulbutcher.com/ LinkedIn: http://www.linkedin.com/in/paulbutcher MSN: p...@paulbutcher.com AIM: paulrabutcher Skype: paulrabutcher -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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$HashCollisionNode.findIndex(Object) 206687 clojure.lang.Util.equiv(Object, Object) 204984 clojure.lang.PersistentHashMap$BitmapIndexedNode.find(int, int, Object, Object) 145968 clojure.lang.PersistentHashMap$NodeSeq.create(Object[]) 81031 clojure.lang.APersistentVector.doEquiv(IPersistentVector, Object) 41656 clojure.lang.Util.dohasheq(IHashEq) 31453 clojure.lang.RT.next(Object) 28671 clojure.lang.PersistentHashMap$NodeSeq.next() 24484 clojure.lang.PersistentVector$1.init(PersistentVector, int, int) 24015 I concur with Paul that it looks like the program is spending nearly all its time mired in hashing. Even the calls on here that aren't obviously related to hashing turn out on further inspection to be related to hashing. For example, doing a backtrace on Util.equiv, one sees that the = operation in the allowed? function is taking negligible time and the equiv method time is almost entirely spent in hash set lookup resolution. Similarly, the RT.next method is negligible time spent stepping through his for sequence, and appears to be almost entirely about stepping through hash collision nodes. My best guess at this point is that there is some sort of bug with the set implementation causing too many items to hash to the same bucket. I have seen this behavior before from time to time when profiling some of my own code (a suspiciously inordinate amount of time spent resolving hash collisions) but have never been able to pin it down with such a pure example. I'll admit that my skills in reading and making sense out of profiler output is pretty weak, but it looks to me that that's what is going on here. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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. Below is an excerpt from that output:
97392280 = (hash #{[:N [2 0]] [:R [4 2]] [:K [0 0]] [:Q [1 3]] [:B [3
0]]})
97392280 = (hash #{[:N [3 0]] [:K [0 0]] [:R [1 2]] [:Q [4 3]] [:B [2
0]]})
97392280 = (hash #{[:N [3 0]] [:K [0 0]] [:R [2 1]] [:Q [1 4]] [:B [4
0]]})
97392280 = (hash #{[:N [4 0]] [:K [0 0]] [:R [3 3]] [:Q [1 2]] [:B [2
0]]})
97392280 = (hash #{[:N [3 0]] [:K [1 0]] [:R [0 2]] [:Q [2 3]] [:B [4
0]]})
97392280 = (hash #{[:N [3 0]] [:K [1 0]] [:R [2 3]] [:Q [0 2]] [:B [4
0]]})
97392280 = (hash #{[:N [4 0]] [:K [1 0]] [:R [0 2]] [:Q [2 3]] [:B [3
0]]})
97392280 = (hash #{[:N [4 0]] [:K [1 0]] [:R [2 3]] [:Q [0 2]] [:B [3
0]]})
97392280 = (hash #{[:K [3 0]] [:N [0 0]] [:Q [4 2]] [:R [2 3]] [:B [1
0]]})
97392280 = (hash #{[:K [3 0]] [:N [0 0]] [:R [4 2]] [:Q [2 3]] [:B [1
0]]})
97392280 = (hash #{[:N [1 0]] [:K [3 0]] [:Q [4 2]] [:R [2 3]] [:B [0
0]]})
97392280 = (hash #{[:N [1 0]] [:K [3 0]] [:R [4 2]] [:Q [2 3]] [:B [0
0]]})
97392280 = (hash #{[:K [4 0]] [:N [0 0]] [:Q [3 2]] [:R [1 3]] [:B [2
0]]})
97392280 = (hash #{[:K [4 0]] [:N [1 0]] [:R [3 2]] [:Q [0 3]] [:B [2
0]]})
97392280 = (hash #{[:K [4 0]] [:N [1 0]] [:R [2 1]] [:Q [3 4]] [:B [0
0]]})
97392280 = (hash #{[:N [2 0]] [:K [4 0]] [:R [0 2]] [:Q [3 3]] [:B [1
0]]})
The hash value of a set is the sum of the hashes of its elements, because
sets are not ordered. The hash of a vector is dependent on the order of
the elements. In fact, for 2-element vectors it is 31*(hash of 1st elem) +
(hash of 2nd elem). The hash value of a small integer is just the integer
value itself.
Thus with many small integers in 2-element vectors like in this problem,
all it takes is having a set of vectors where the first elements sum to the
same value, and the second elements sum to the same value, and the hash of
the whole set of vectors will be equal.
Exactly what would be the best way to improve the hash code for situations
like this, I am not sure yet.
Andy
On Wed, Oct 23, 2013 at 8:46 AM, Mark Engelberg mark.engelb...@gmail.comwrote:
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$HashCollisionNode.findIndex(Object) 206687
clojure.lang.Util.equiv(Object, Object) 204984
clojure.lang.PersistentHashMap$BitmapIndexedNode.find(int, int, Object,
Object) 145968
clojure.lang.PersistentHashMap$NodeSeq.create(Object[]) 81031
clojure.lang.APersistentVector.doEquiv(IPersistentVector, Object) 41656
clojure.lang.Util.dohasheq(IHashEq) 31453
clojure.lang.RT.next(Object) 28671
clojure.lang.PersistentHashMap$NodeSeq.next() 24484
clojure.lang.PersistentVector$1.init(PersistentVector, int, int) 24015
I concur with Paul that it looks like the program is spending nearly all
its time mired in hashing. Even the calls on here that aren't obviously
related to hashing turn out on further inspection to be related to hashing.
For example, doing a backtrace on Util.equiv, one sees that the =
operation in the allowed? function is taking negligible time and the equiv
method time is almost entirely spent in hash set lookup resolution.
Similarly, the RT.next method is negligible time spent stepping through his
for sequence, and appears to be almost entirely about stepping through hash
collision nodes.
My best guess at this point is that there is some sort of bug with the set
implementation causing too many items to hash to the same bucket. I have
seen this behavior before from time to time when profiling some of my own
code (a suspiciously inordinate amount of time spent resolving hash
collisions) but have never been able to pin it down with such a pure
example.
I'll admit that my skills in reading and making sense out of profiler
output is pretty weak, but it looks to me that that's what is going on here.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an
email to clojure+unsubscr...@googlegroups.com.
For more options, visit
Re: Request for help optimising a Clojure program
On 23 Oct 2013, at 17:06, Andy Fingerhut andy.finger...@gmail.com 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 thanks, Andy. -- paul.butcher-msgCount++ Snetterton, Castle Combe, Cadwell Park... Who says I have a one track mind? http://www.paulbutcher.com/ LinkedIn: http://www.linkedin.com/in/paulbutcher MSN: p...@paulbutcher.com AIM: paulrabutcher Skype: paulrabutcher -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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
entirely.
Just replace #{#{}} with [#{}], and remove the call to 'set' in solve.
Andy
On Wed, Oct 23, 2013 at 9:18 AM, Paul Butcher p...@paulbutcher.com wrote:
On 23 Oct 2013, at 17:06, Andy Fingerhut andy.finger...@gmail.com 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 thanks, Andy.
--
paul.butcher-msgCount++
Snetterton, Castle Combe, Cadwell Park...
Who says I have a one track mind?
http://www.paulbutcher.com/
LinkedIn: http://www.linkedin.com/in/paulbutcher
MSN: p...@paulbutcher.com
AIM: paulrabutcher
Skype: paulrabutcher
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an
email to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: Request for help optimising a Clojure program
On 23 Oct 2013, at 17:43, Andy Fingerhut andy.finger...@gmail.com 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, since it avoids the PersistentHashSet hash collision issue
entirely.
Just replace #{#{}} with [#{}], and remove the call to 'set' in solve.
The problem with that, Andy, is that it will result in a lot of duplicates. For
the 4x4 problem, for example, that approach raises the size of the returned
collection from 8 to 384.
My guess is that for the 6x9 problem it will just remove the set handling
problem and replace it with a memory/time issue as the search space grows (and
I only have 16G in my MacBook Pro :-)
I don't need to get this working - I only knocked it together as an interesting
exercise. And if it's helped to track down an issue in the Clojure runtime,
it's already achieved far more than I expected it to :-)
Thanks again,
--
paul.butcher-msgCount++
Snetterton, Castle Combe, Cadwell Park...
Who says I have a one track mind?
http://www.paulbutcher.com/
LinkedIn: http://www.linkedin.com/in/paulbutcher
MSN: p...@paulbutcher.com
AIM: paulrabutcher
Skype: paulrabutcher
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
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 set or use as a map key, then instead of having linked lists for
values that collide, we could have trees like those in the implementations
of sorted-maps and sorted-sets today. Such a comparison function might
look something like 'cc-cmp' a couple of pages down from this link:
https://github.com/jafingerhut/thalia/blob/master/doc/other-topics/comparators.md#comparators-that-work-between-different-types
However, I believe there will always be some types where such a comparator
will fail, and thus not truly be 'universal'. Still, if it hit the sweet
spot of 99.99% of the use cases people cared about, it might be good to
have.
Andy
On Wed, Oct 23, 2013 at 9:06 AM, Andy Fingerhut andy.finger...@gmail.comwrote:
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. Below is an excerpt from that output:
97392280 = (hash #{[:N [2 0]] [:R [4 2]] [:K [0 0]] [:Q [1 3]] [:B [3
0]]})
97392280 = (hash #{[:N [3 0]] [:K [0 0]] [:R [1 2]] [:Q [4 3]] [:B [2
0]]})
97392280 = (hash #{[:N [3 0]] [:K [0 0]] [:R [2 1]] [:Q [1 4]] [:B [4
0]]})
97392280 = (hash #{[:N [4 0]] [:K [0 0]] [:R [3 3]] [:Q [1 2]] [:B [2
0]]})
97392280 = (hash #{[:N [3 0]] [:K [1 0]] [:R [0 2]] [:Q [2 3]] [:B [4
0]]})
97392280 = (hash #{[:N [3 0]] [:K [1 0]] [:R [2 3]] [:Q [0 2]] [:B [4
0]]})
97392280 = (hash #{[:N [4 0]] [:K [1 0]] [:R [0 2]] [:Q [2 3]] [:B [3
0]]})
97392280 = (hash #{[:N [4 0]] [:K [1 0]] [:R [2 3]] [:Q [0 2]] [:B [3
0]]})
97392280 = (hash #{[:K [3 0]] [:N [0 0]] [:Q [4 2]] [:R [2 3]] [:B [1
0]]})
97392280 = (hash #{[:K [3 0]] [:N [0 0]] [:R [4 2]] [:Q [2 3]] [:B [1
0]]})
97392280 = (hash #{[:N [1 0]] [:K [3 0]] [:Q [4 2]] [:R [2 3]] [:B [0
0]]})
97392280 = (hash #{[:N [1 0]] [:K [3 0]] [:R [4 2]] [:Q [2 3]] [:B [0
0]]})
97392280 = (hash #{[:K [4 0]] [:N [0 0]] [:Q [3 2]] [:R [1 3]] [:B [2
0]]})
97392280 = (hash #{[:K [4 0]] [:N [1 0]] [:R [3 2]] [:Q [0 3]] [:B [2
0]]})
97392280 = (hash #{[:K [4 0]] [:N [1 0]] [:R [2 1]] [:Q [3 4]] [:B [0
0]]})
97392280 = (hash #{[:N [2 0]] [:K [4 0]] [:R [0 2]] [:Q [3 3]] [:B [1
0]]})
The hash value of a set is the sum of the hashes of its elements, because
sets are not ordered. The hash of a vector is dependent on the order of
the elements. In fact, for 2-element vectors it is 31*(hash of 1st elem) +
(hash of 2nd elem). The hash value of a small integer is just the integer
value itself.
Thus with many small integers in 2-element vectors like in this problem,
all it takes is having a set of vectors where the first elements sum to the
same value, and the second elements sum to the same value, and the hash of
the whole set of vectors will be equal.
Exactly what would be the best way to improve the hash code for situations
like this, I am not sure yet.
Andy
On Wed, Oct 23, 2013 at 8:46 AM, Mark Engelberg
mark.engelb...@gmail.comwrote:
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$HashCollisionNode.findIndex(Object) 206687
clojure.lang.Util.equiv(Object, Object) 204984
clojure.lang.PersistentHashMap$BitmapIndexedNode.find(int, int, Object,
Object) 145968
clojure.lang.PersistentHashMap$NodeSeq.create(Object[]) 81031
clojure.lang.APersistentVector.doEquiv(IPersistentVector, Object) 41656
clojure.lang.Util.dohasheq(IHashEq) 31453
clojure.lang.RT.next(Object) 28671
clojure.lang.PersistentHashMap$NodeSeq.next() 24484
clojure.lang.PersistentVector$1.init(PersistentVector, int, int) 24015
I concur with Paul that it looks like the program is spending nearly all
its time mired in hashing. Even the calls on here that aren't obviously
related to hashing turn out on further inspection to be related to hashing.
For example, doing a backtrace on Util.equiv, one sees that the =
operation in the allowed? function is taking negligible time and the equiv
method time is almost entirely spent in hash set lookup resolution.
Similarly, the RT.next method is negligible time spent stepping through his
for sequence, and appears to be almost entirely about stepping through hash
collision nodes.
My best guess at this point is that there is some sort of bug with the
set implementation causing too many items
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 of why. Thanks
for that.
Andy
On Wed, Oct 23, 2013 at 10:13 AM, Paul Butcher p...@paulbutcher.com wrote:
On 23 Oct 2013, at 17:43, Andy Fingerhut andy.finger...@gmail.com 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, since it avoids the PersistentHashSet hash collision issue
entirely.
Just replace #{#{}} with [#{}], and remove the call to 'set' in solve.
The problem with that, Andy, is that it will result in a lot of
duplicates. For the 4x4 problem, for example, that approach raises the size
of the returned collection from 8 to 384.
My guess is that for the 6x9 problem it will just remove the set handling
problem and replace it with a memory/time issue as the search space grows
(and I only have 16G in my MacBook Pro :-)
I don't need to get this working - I only knocked it together as an
interesting exercise. And if it's helped to track down an issue in the
Clojure runtime, it's already achieved far more than I expected it to :-)
Thanks again,
--
paul.butcher-msgCount++
Snetterton, Castle Combe, Cadwell Park...
Who says I have a one track mind?
http://www.paulbutcher.com/
LinkedIn: http://www.linkedin.com/in/paulbutcher
MSN: p...@paulbutcher.com
AIM: paulrabutcher
Skype: paulrabutcher
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an
email to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: Request for help optimising a Clojure program
On 23 Oct 2013, at 18:15, Andy Fingerhut andy.finger...@gmail.com 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 collide, we could have trees like those in the implementations of sorted-maps and sorted-sets today. Wouldn't it be better to improve the way that hashes are calculated for vectors? A good hash function should make it unlikely that similar values have the same hash. The current algorithm seems to make that more likely than it should? -- paul.butcher-msgCount++ Snetterton, Castle Combe, Cadwell Park... Who says I have a one track mind? http://www.paulbutcher.com/ LinkedIn: http://www.linkedin.com/in/paulbutcher MSN: p...@paulbutcher.com AIM: paulrabutcher Skype: paulrabutcher -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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 values themselves. Andy On Wed, Oct 23, 2013 at 10:28 AM, Paul Butcher p...@paulbutcher.com wrote: On 23 Oct 2013, at 18:15, Andy Fingerhut andy.finger...@gmail.com 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 collide, we could have trees like those in the implementations of sorted-maps and sorted-sets today. Wouldn't it be better to improve the way that hashes are calculated for vectors? A good hash function should make it unlikely that similar values have the same hash. The current algorithm seems to make that more likely than it should? -- paul.butcher-msgCount++ Snetterton, Castle Combe, Cadwell Park... Who says I have a one track mind? http://www.paulbutcher.com/ LinkedIn: http://www.linkedin.com/in/paulbutcher MSN: p...@paulbutcher.com AIM: paulrabutcher Skype: paulrabutcher -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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 I no longer
see hash collisions dominating in YourKit:
(defrecord Piece [name pos])
(defn piece [name pos]
(Piece. name pos))
(defn takes? [name [dx dy]]
(case name
:K (and (= dx 1) (= dy 1))
:Q (or (zero? dx) (zero? dy) (== dx dy))
:R (or (zero? dx) (zero? dy))
:B (== dx dy)
:N (or (and (== dx 1) (== dy 2)) (and (== dx 2) (== dy 1)
(defn allows? [{name :name [px py] :pos} [x y]]
(let [delta [(Math/abs (int (- px x))) (Math/abs (int (- py y)))]]
(and (not (and (== px x) (== py y))) (not (takes? name delta)
(defn allowed? [{cname :name cpos :pos :as cand} solution]
(every?
(fn [{pos :pos :as piece}]
(and (allows? piece cpos) (allows? cand pos)))
solution))
(defn solve [rows cols pieces]
(if (empty? pieces)
#{#{}}
(set
(let [name (first pieces)]
(for [solution (solve rows cols (rest pieces))
x (range 0 cols)
y (range 0 rows)
:let [cand (piece name [x y])]
:when (allowed? cand solution)]
(conj solution cand))
David
On Wed, Oct 23, 2013 at 1:28 PM, Paul Butcher p...@paulbutcher.com wrote:
On 23 Oct 2013, at 18:15, Andy Fingerhut andy.finger...@gmail.com 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 collide, we could have trees like those in the implementations
of sorted-maps and sorted-sets today.
Wouldn't it be better to improve the way that hashes are calculated for
vectors? A good hash function should make it unlikely that similar values
have the same hash. The current algorithm seems to make that more likely
than it should?
--
paul.butcher-msgCount++
Snetterton, Castle Combe, Cadwell Park...
Who says I have a one track mind?
http://www.paulbutcher.com/
LinkedIn: http://www.linkedin.com/in/paulbutcher
MSN: p...@paulbutcher.com
AIM: paulrabutcher
Skype: paulrabutcher
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an
email to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
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 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 values themselves. Andy On Wed, Oct 23, 2013 at 10:28 AM, Paul Butcher p...@paulbutcher.com mailto:p...@paulbutcher.com wrote: On 23 Oct 2013, at 18:15, Andy Fingerhut andy.finger...@gmail.com mailto:andy.finger...@gmail.com 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 collide, we could have trees like those in the implementations of sorted-maps and sorted-sets today. Wouldn't it be better to improve the way that hashes are calculated for vectors? A good hash function should make it unlikely that similar values have the same hash. The current algorithm seems to make that more likely than it should? -- paul.butcher-msgCount++ Snetterton, Castle Combe, Cadwell Park... Who says I have a one track mind? http://www.paulbutcher.com http://www.paulbutcher.com// LinkedIn: http://www.linkedin.com/in/paulbutcher MSN: p...@paulbutcher.com mailto:p...@paulbutcher.com AIM: paulrabutcher Skype: paulrabutcher -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com mailto:clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com mailto:clojure%2bunsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com mailto:clojure%2bunsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Request for help optimising a Clojure program
On Wed, Oct 23, 2013 at 10:39 AM, Pablo Nussembaum bau...@gmail.com 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 from similar items? -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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 bau...@gmail.com wrote:
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
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 values themselves.
Andy
On Wed, Oct 23, 2013 at 10:28 AM, Paul Butcher p...@paulbutcher.comwrote:
On 23 Oct 2013, at 18:15, Andy Fingerhut andy.finger...@gmail.com
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 collide, we could have trees like those in the implementations
of sorted-maps and sorted-sets today.
Wouldn't it be better to improve the way that hashes are calculated for
vectors? A good hash function should make it unlikely that similar values
have the same hash. The current algorithm seems to make that more likely
than it should?
--
paul.butcher-msgCount++
Snetterton, Castle Combe, Cadwell Park...
Who says I have a one track mind?
http://www.paulbutcher.com/
LinkedIn: http://www.linkedin.com/in/paulbutcher
MSN: p...@paulbutcher.com
AIM: paulrabutcher
Skype: paulrabutcher
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an
email to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an
email to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an
email to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: Request for help optimising a Clojure program
On Oct 23, 2013, at 12:30 , Andy Fingerhut andy.finger...@gmail.com 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 values are what are colliding, not the individual vector hash values themselves. What about the formula used by Boost's hash_combine? http://stackoverflow.com/questions/4948780/magic-number-in-boosthash-combine -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: Request for help optimising a Clojure program
On Oct 23, 2013, at 14:34 , Mark Engelberg mark.engelb...@gmail.com 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 #{#{1 2} 3} and #{#{1 3} 2} to be unequal, it must also be
non-associative. That's possible, but I'm not sure what would be a good
candidate function. Something involving averaging, perhaps?
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure can't import some Java classes
Right, my Spacing problem is not related to the static initializer problem
(which I also suffer from) but it is another example of (what seems to me)
a fairly standard pattern that I can't use in Clojure if I AOT and which
doesn't have an obvious workaround.
On 24 October 2013 03:32, Alex Miller a...@puredanger.com wrote:
Agreed - merely importing this class shouldn't be an issue (which is the
issue at hand).
If you need to configure Spacing, you should do that prior to using it in
your def, but that should work fine. If that needs to happen at runtime,
then you shouldn't do this in a def.
On Wednesday, October 23, 2013 9:01:15 AM UTC-5, Aaron Cohen wrote:
I'm not sure if this is related to the original problem.
How is the setFactory method expected to be invoked, through some sort
of dependency injection framework?
On Wed, Oct 23, 2013 at 7:06 AM, Colin Fleming colin.ma...@gmail.comwrote:
I've also had a lot of problems with def'ed forms. For example, if I
do this:
(def no-spacing (Spacing/createSpacing 0 0 0 false 0))
Which looks like this:
public static Spacing createSpacing(int minSpaces,
**int maxSpaces,
**int minLineFeeds,
**boolean keepLineBreaks,
**int keepBlankLines) {
return myFactory.createSpacing(**minSpaces, maxSpaces,
minLineFeeds, keepLineBreaks, keepBlankLines);
}
myFactory is injected at some earlier point:
static void setFactory(SpacingFactory factory) {
myFactory = factory;
}
But during compilation that obviously hasn't happened and I get an NPE
during compilation. It's a little annoying that there really seems to be no
good way to create this value at namespace load time if I'm AOT compiling.
I can obviously defer it using defn with memoize or something, but that
seems clunky for what doesn't seem like that crazy a use case.
On 23 October 2013 15:21, Zach Oakes zso...@gmail.com wrote:
Here's the error I get when I import LibGDX's Timer class:
http://pastebin.com/q7wys8yi
On Tuesday, October 22, 2013 9:55:16 PM UTC-4, Alex Miller wrote:
I'd love to see a stack trace when that happens (could even be
triggered by dumping stack in your static initializer if nothing else).
On Saturday, October 12, 2013 3:17:50 AM UTC-5, Wujek Srujek wrote:
So you are saying compilation is trying to instantiate class and run
static initializers? This seems very backward, are you sure?
On Sat, Oct 12, 2013 at 8:30 AM, Zach Oakes zso...@gmail.com wrote:
I should add, I am aware I can bring in a class dynamically with
Class/forName, and that is what I ended up doing for the Timer class.
However, this is not always practical, and sometimes is simply not an
option if aot-compilation is required.
On Saturday, October 12, 2013 2:28:38 AM UTC-4, Zach Oakes wrote:
I recently learned that merely importing a Java class in Clojure
causes static initializers to be run. Sometimes, this causes
compilation
errors, because they are written with the assumption that they will
only be
run during runtime.
I ran into this just now while trying to make a simple Clojure game
with LibGDX. After simply importing its Timer class, I began getting
compilation errors. The stack trace shows it is due to a static
initializerhttps://github.com/libgdx/libgdx/blob/511b557c1a2d23bf8110a05b0ef54cc20b7f958d/gdx/src/com/badlogic/gdx/utils/Timer.java#L32attempting
to instantiate the class!
I also ran into this recently while trying to use RoboVM. My
question is, do I have any options? I haven't found many discussions
about
this here or elsewhere. This surprises me, because it seems like
something
more people should be running into.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient
with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/**group**/clojure?hl=enhttp://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google
Groups Clojure group.
To unsubscribe from this group and stop receiving emails from it,
send an email to clojure+u...@googlegroups.com.
For more options, visit
https://groups.google.com/**grou**ps/opt_outhttps://groups.google.com/groups/opt_out
.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with
your first post.
To unsubscribe from this group, send email to
clojure+u...@**googlegroups.com
For more options, visit this group at
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 value of a set is the sum of (expt 3 (abs (hash item))) for each
item in the set.
Implementation:
;; First a wrap-around implementation of expt
(defn- expt [base pow]
(if (zero? pow) 1
(loop [n (int pow), y (int 1), z (int base)]
(let [t (even? n), n (quot n 2)]
(cond
t (recur n y (unchecked-multiply-int z z))
(zero? n) (unchecked-multiply-int z y)
:else (recur n (unchecked-multiply-int z y)
(unchecked-multiply-int z z)))
(declare my-hash)
(defn set-hash [coll]
(reduce + (for [item (seq coll)] (expt 3 (my-hash item)
(defn my-hash [i]
(if (set? i) (set-hash i) (hash i)))
= (my-hash #{#{1 2} 3})
531468
= (my-hash #{#{1 3} 2})
-1010140990
= (my-hash #{#{1 3} #{2 4}})
-2065039966
= (my-hash #{#{1 2} #{3 4}})
-868484254
= (my-hash #{[1 2] [2 1]})
-3497906806
= (my-hash #{[1 1] [2 2]})
-443882362
So this is certainly a solvable problem, the real question is how to go
about designing such a hash function around a smaller number of simple
arithmetic operations. Also, the above implementation is kind of lame
because that expt function treats the hash value of the item as a positive
number, effectively cutting the possible hash values in half. So this
implementation isn't practical, but should serve as an illustration of what
could be done.
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: Request for help optimising a Clojure program
On Oct 23, 2013, at 17:03 , Mark Engelberg mark.engelb...@gmail.com 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 rearrangements. The idea of this proof of concept is that the hash value of a set is the sum of (expt 3 (abs (hash item))) for each item in the set. Associativity is only meaningful for binary operators-- I was assuming a binary hash-combining function that would be applied via reduce or such. The function you've described can't be implemented as a binary operator without changing its behavior, so it can't be described as associative. But you're right that Set's hash function doesn't need to be associative, since it doesn't actually need to be a binary operator. BTW, while looking into this I discovered that Clojure already defines a function clojure.lang.Util/hashCombine that uses Boost's hash-combining algorithm, but it doesn't seem to be used for anything except Symbols at the moment. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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 thrown
in there primarily so common numbers like 0 have a meaningful effect on the
hash (without the xor there's no difference between #{0 1} and #{1}, for
example).
Here's Clojure code:
(declare my-hash)
(defn set-hash [coll]
(reduce + (for [item (seq coll)]
(let [hash-item (.intValue (bit-xor 0x9e3779b9 (my-hash
item)))]
(unchecked-multiply-int hash-item
hash-item)
(defn my-hash [i]
(if (set? i) (set-hash i) (hash i)))
Note that the .intValue call can go away if you convert this to Java and
use int xor rather than Clojure's xor.
This gives really nice spread-out results for similar sets:
= (my-hash #{{1 2} 3})
1067103816
= (my-hash #{{1 3} 2})
3094912306
= (my-hash #{{1 4} {2 3}})
-3227863472
= (my-hash #{{1 3} {2 4}})
2855562010
= (my-hash #{[1 1] [2 2]})
3474272896
= (my-hash #{[1 2] [2 1]})
-1060041718
--
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: Confusing ArityExceptions from macros
Oh, nice! I've been wondering what this error means for at least a month now. Thanks, James On Thursday, October 17, 2013 1:14:21 PM UTC-5, Alex Coventry wrote: If you've ever had a confusing ArityExceptionhttp://clojure-log.n01se.net/date/2013-10-16.html#19:37 while working with macros, the reason may be that clojure.lang.Compiler.macroexpand1 rethrows any ArityExceptionshttps://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Compiler.java#L6475it catches from a call to a macro, in order to reduce the number of arguments reported. This messes up the stack, potentially destroying information about where the ArityException occurred if it did not occur from the call to the macro itself. For instance: user (do (defn inner [] (assoc)) (defmacro f [] (inner)) (f)) ArityException Wrong number of args (-2) passed to: core$assoc clojure.lang.Compiler.macroexpand1 (Compiler.java:6488) user (use 'clojure.repl) (pst) nil ArityException Wrong number of args (-2) passed to: core$assoc clojure.lang.Compiler.macroexpand1 (Compiler.java:6488) clojure.lang.Compiler.macroexpand (Compiler.java:6544) clojure.lang.Compiler.eval (Compiler.java:6618) clojure.lang.Compiler.eval (Compiler.java:6624) clojure.lang.Compiler.eval (Compiler.java:6597) clojure.core/eval (core.clj:2864) clojure.main/repl/read-eval-print--6596/fn--6599 (main.clj:260) clojure.main/repl/read-eval-print--6596 (main.clj:260) clojure.main/repl/fn--6605 (main.clj:278) clojure.main/repl (main.clj:278) clojure.tools.nrepl.middleware.interruptible-eval/evaluate/fn--1251 (interruptible_eval.clj:56) clojure.core/apply (core.clj:617) nil user Note that the call to inner is not in the stack trace, and the number of arguments to it have been reduced by 2, leading to a nonsensical result in this case. The patch at http://dev.clojure.org/jira/browse/CLJ-1279 fixes this bug. Might save you some time, if you're developing macros. Best regards, Alex -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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
= (hash {1 3 2 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@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
Clojure group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
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 collisions don't seem to be as common as with sets and maps. I'm sure it could be improved, but vector/sequence hashing doesn't strike me as a huge issue. On Wed, Oct 23, 2013 at 5:31 PM, Cedric Greevey cgree...@gmail.com wrote: 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 ones, while inducing a permutation on nonzero integers -- the hash space wouldn't be any smaller. That alone won't help much with the vector problem, since 3N + 2N = 5N just as 3 + 2 = 5, though it may help avoid collisions with small integers in small hash maps when the hash is being used modulo a small hash-table length. What might help with vectors, sets, and other small data structures containing integers (but would shrink the hash space by about half) is to additionally square the result (all operations being 2s-complement 32-bit integer operations with wrapping -- Java int arithmetic). Now 1 and 4 won't give the same summed hashes as 3 and 2, and 0 and 5 will be different again. You might also want to add some constant to avoid 0 hashing to 0. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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 mark.engelb...@gmail.comwrote: 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 collisions don't seem to be as common as with sets and maps. I'm sure it could be improved, but vector/sequence hashing doesn't strike me as a huge issue. On Wed, Oct 23, 2013 at 5:31 PM, Cedric Greevey cgree...@gmail.comwrote: 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 ones, while inducing a permutation on nonzero integers -- the hash space wouldn't be any smaller. That alone won't help much with the vector problem, since 3N + 2N = 5N just as 3 + 2 = 5, though it may help avoid collisions with small integers in small hash maps when the hash is being used modulo a small hash-table length. What might help with vectors, sets, and other small data structures containing integers (but would shrink the hash space by about half) is to additionally square the result (all operations being 2s-complement 32-bit integer operations with wrapping -- Java int arithmetic). Now 1 and 4 won't give the same summed hashes as 3 and 2, and 0 and 5 will be different again. You might also want to add some constant to avoid 0 hashing to 0. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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 pairs, there are only 6369 distinct hash values. That's not good. So yes, upon further thought, I think sequence hashing should be improved as well. I want to emphasize that I don't view this as merely a theoretical problem. I have noticed for over a year now, when profiling my Clojure code, that a surprising amount of time was spent on dealing with hash collisions. I chalked it up as the natural behavior of hash tables which will occasionally have collisions, and just learned to live with it, but the more I play around with the existing hash function on data similar to what I use (with small numbers in slightly varying structures), the more I'm convinced that Clojure's weak hashing strategy explains the performance issues I've had. Would love to see the Clojure community tackle this head-on; I think there's a lot of performance to be gained for many real apps by doing this. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Experiences using SQLite with Clojure? Recommendations?
How have your experiences been using SQLite with Clojure? Back when org.xerial/sqlite-jdbc was at v3.7.2, I'd heard some complaints. But I notice that the project appears to be fairly actively maintained (see its [mailing list] and [project page]). The current version is 3.7.15-M1. [mailing list]: https://groups.google.com/forum/?hl=en#!forum/xerial [project page]: https://bitbucket.org/xerial/sqlite-jdbc Any recommendations for or against using SQLite with Clojure? digression navel-gazing-level=8 I wonder if use of SQLite with the JVM platform increases as alternative JVM languages become more popular... /digression Thanks! -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Experiences using SQLite with Clojure? Recommendations?
I'm a proponent of using H2 http://www.h2database.com/html/main.html via clojure.java.jdbc https://github.com/clojure/java.jdbc. H2 is written in Java, so it'll work everywhere your Clojure code does, and it has a lot of stuff not built into SQLite such as encryption. On Wednesday, October 23, 2013 10:14:59 PM UTC-4, John Gabriele wrote: How have your experiences been using SQLite with Clojure? Back when org.xerial/sqlite-jdbc was at v3.7.2, I'd heard some complaints. But I notice that the project appears to be fairly actively maintained (see its [mailing list] and [project page]). The current version is 3.7.15-M1. [mailing list]: https://groups.google.com/forum/?hl=en#!forum/xerial [project page]: https://bitbucket.org/xerial/sqlite-jdbc Any recommendations for or against using SQLite with Clojure? digression navel-gazing-level=8 I wonder if use of SQLite with the JVM platform increases as alternative JVM languages become more popular... /digression Thanks! -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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 200)] (hash [x y] 6369 This means that out of 40,000 common ordered pairs, there are only 6369 distinct hash values. That's not good. So yes, upon further thought, I think sequence hashing should be improved as well. I want to emphasize that I don't view this as merely a theoretical problem. I have noticed for over a year now, when profiling my Clojure code, that a surprising amount of time was spent on dealing with hash collisions. I chalked it up as the natural behavior of hash tables which will occasionally have collisions, and just learned to live with it, but the more I play around with the existing hash function on data similar to what I use (with small numbers in slightly varying structures), the more I'm convinced that Clojure's weak hashing strategy explains the performance issues I've had. Would love to see the Clojure community tackle this head-on; I think there's a lot of performance to be gained for many real apps by doing this. You can't change the hashCode of lists / vectors without breaking the contract for java.util.List (which PersistentList and PersistentVector both implement) - http://docs.oracle.com/javase/7/docs/api/java/util/List.html#hashCode() I don't think breaking this would be a good idea. The java.util.List hashCode isn't actually too bad. It's a decent compromise between an efficient implementation and reasonably effective hashing for most real-world use cases. Sure you can construct artificial examples where you get some collisions, but that's true of any hash code function. But note that the maximum number of collisions is still pretty low: (apply max (vals (frequencies (for [x (range 200) y (range 200)] (hash [x y]) = 7 That's actually the number you really care about, since it is the number of objects in the same hash bucket that drives the pathological O(n^2) behaviours. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
The Problem with Threads
I just read The Problem with Threads and found it very interesting. Although it's a bit dated (2006), it brings some useful and interesting insights to the discussion. The Problem with Threads, Edward A. Lee http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf -r -- http://www.cfcl.com/rdmRich Morin http://www.cfcl.com/rdm/resume r...@cfcl.com http://www.cfcl.com/rdm/weblog +1 650-873-7841 Software system design, development, and documentation -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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. I don't really consider this to be a contrived case. It's pretty typical, in my experience, for Clojure programmers to choose to represent a 2D array as a map from [x y] to values. That's often more practical to intialize and work with than a vectors-in-vector layout. So a map with keys ranging from [0 0] to [199 199] would be what you'd get for a 200x200 array. Having 6-7 objects per bucket isn't the end of the world, but it means that all your lookups are several times slower than they could be. All that said, I think that improving set hashing is a more pressing issue. On Wed, Oct 23, 2013 at 9:05 PM, Mikera mike.r.anderson...@gmail.comwrote: 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 200)] (hash [x y] 6369 This means that out of 40,000 common ordered pairs, there are only 6369 distinct hash values. That's not good. So yes, upon further thought, I think sequence hashing should be improved as well. I want to emphasize that I don't view this as merely a theoretical problem. I have noticed for over a year now, when profiling my Clojure code, that a surprising amount of time was spent on dealing with hash collisions. I chalked it up as the natural behavior of hash tables which will occasionally have collisions, and just learned to live with it, but the more I play around with the existing hash function on data similar to what I use (with small numbers in slightly varying structures), the more I'm convinced that Clojure's weak hashing strategy explains the performance issues I've had. Would love to see the Clojure community tackle this head-on; I think there's a lot of performance to be gained for many real apps by doing this. You can't change the hashCode of lists / vectors without breaking the contract for java.util.List (which PersistentList and PersistentVector both implement) - http://docs.oracle.com/javase/7/docs/api/java/util/List.html#hashCode() I don't think breaking this would be a good idea. The java.util.List hashCode isn't actually too bad. It's a decent compromise between an efficient implementation and reasonably effective hashing for most real-world use cases. Sure you can construct artificial examples where you get some collisions, but that's true of any hash code function. But note that the maximum number of collisions is still pretty low: (apply max (vals (frequencies (for [x (range 200) y (range 200)] (hash [x y]) = 7 That's actually the number you really care about, since it is the number of objects in the same hash bucket that drives the pathological O(n^2) behaviours. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
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 programming with maps and vectors. Right tool for the right job, and all that. On Thursday, 24 October 2013 12:40:13 UTC+8, puzzler wrote: 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. I don't really consider this to be a contrived case. It's pretty typical, in my experience, for Clojure programmers to choose to represent a 2D array as a map from [x y] to values. That's often more practical to intialize and work with than a vectors-in-vector layout. So a map with keys ranging from [0 0] to [199 199] would be what you'd get for a 200x200 array. Having 6-7 objects per bucket isn't the end of the world, but it means that all your lookups are several times slower than they could be. All that said, I think that improving set hashing is a more pressing issue. On Wed, Oct 23, 2013 at 9:05 PM, Mikera mike.r.an...@gmail.comjavascript: wrote: 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 200)] (hash [x y] 6369 This means that out of 40,000 common ordered pairs, there are only 6369 distinct hash values. That's not good. So yes, upon further thought, I think sequence hashing should be improved as well. I want to emphasize that I don't view this as merely a theoretical problem. I have noticed for over a year now, when profiling my Clojure code, that a surprising amount of time was spent on dealing with hash collisions. I chalked it up as the natural behavior of hash tables which will occasionally have collisions, and just learned to live with it, but the more I play around with the existing hash function on data similar to what I use (with small numbers in slightly varying structures), the more I'm convinced that Clojure's weak hashing strategy explains the performance issues I've had. Would love to see the Clojure community tackle this head-on; I think there's a lot of performance to be gained for many real apps by doing this. You can't change the hashCode of lists / vectors without breaking the contract for java.util.List (which PersistentList and PersistentVector both implement) - http://docs.oracle.com/javase/7/docs/api/java/util/List.html#hashCode() I don't think breaking this would be a good idea. The java.util.List hashCode isn't actually too bad. It's a decent compromise between an efficient implementation and reasonably effective hashing for most real-world use cases. Sure you can construct artificial examples where you get some collisions, but that's true of any hash code function. But note that the maximum number of collisions is still pretty low: (apply max (vals (frequencies (for [x (range 200) y (range 200)] (hash [x y]) = 7 That's actually the number you really care about, since it is the number of objects in the same hash bucket that drives the pathological O(n^2) behaviours. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clo...@googlegroups.comjavascript: Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+u...@googlegroups.com javascript: For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com javascript:. For more options, visit https://groups.google.com/groups/opt_out. -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to
