Here are the major points:
The algorithm requires that for about 400,000 points there will be
~8,000,000 iterations. This is a very tight loop. You cannot create anything
in this loop, not even a regular Object, much less a temporary Clojure
vector for doing vector math.
The Java version avoids this problem entirely. It just operates on two
primitive double arrays, one for x values, and one for y values (The Clojure
version could probably in fact be made a bit faster by just supplying two
such primitive global arrays, but I'm tired/bored of optimizing this
further- this would eliminate the overhead of the javax.vecmath.Vector2d
calls).
Having tried to do vector math with Clojure persistent vectors before,
I've realized it's just not designed for that kind of thing (yet).
So I used javax.vecmath.Vector2d since it's readily available and seems to
have relatively good performance. One problem I ran into was that
javax.vecmath.Vector2d methods tend to mutate the original. This creates
problems for the algorithm. This was a issue- how to do vector math without
mutating instances in the original primitive array?
So I worked up this hack:
(def #^Vector2d mutable-point (point 0 0))
(defmacro sub [v1 v2]
`(do
(.set mutable-point (.x ~v1) (.y ~v1))
(let [#^Vector2d mutable-point# mutable-point
#^Vector2d v# ~v2]
(.sub mutable-point# ~v2)
mutable-point#)))
This avoids
mutating the original array, it also avoids any overhead from creating
a javax.vecmath.Vector2d object in the inner loop.
Finally quadrant-one-pseudo-angle and
pseudo-angle were converted into macros. These functions essentially
got called for each iteration. By inlining them via macros, it
eliminates the overhead of 2 function calls per iteration.
That's about it.
While I recommend optimizing a slow Clojure prorgram at least once to get an
idea of how optimization can be done, writing this
kind of code in Clojure seems to me to be generally counter
productive. Java is painful for writing
general program logic, but for low-level code - it's pretty good for that
and easy to write.
David
On Sun, Aug 16, 2009 at 4:53 PM, Daniel Werner <
daniel.d.wer...@googlemail.com> wrote:
>
> David,
>
> could you please post a version of your solution[1] annotated with
> some comments on where you used which kind of optimization, and why?
> Your code looks very clean to me, and with some additional
> explanations I think this could become a good example on how to
> optimize computation-heavy Clojure code.
>
> [1] github.com/swannodette/convex-hull/tree/master
>
> Thanks!
>
> Daniel
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
