Below is the fastest version I tested, using ideas from the various responses
in this thread. It runs in ~4s on my machine, compared with ~27s for the
original version.
The biggest win by far was from James Reeves' suggestion of switching to Java's
mutable HashSet. I'm not sure why; I'd thought that using transients and
transducers with Clojure's native sets would provide comparable performance,
but this was not true in my testing.
I also couldn't figure out how to avoid the reflection warning when invoking
HashSet's constructor that takes a generic Collection, which is why that ugly
doto is there in nth-neighbors. How would I avoid that?
(ns hash-set-bench
(import
[java.util HashSet]
[java.awt Point]))
(set! *warn-on-reflection* true)
(set! *unchecked-math* :warn-on-boxed)
(defn neighbors [^Point p]
(let [x (.-x p), y (.-y p)]
[(Point. x (inc y))
(Point. x (dec y))
(Point. (inc x) y)
(Point. (dec x) y)]))
(defn nth-neighbors [^long n ^Point p]
(loop [n n, s1 (doto (HashSet.) (.add p)), s2 (HashSet.)]
(if (zero? n) s1
(let [s0 (HashSet.)]
(doseq [_ s1, p (neighbors _)]
(when-not (or (.contains s1 p) (.contains s2 p))
(.add s0 p)))
(recur (dec n) s0 s1)))))
> On Nov 15, 2016, at 19:39, Didier <[email protected]> wrote:
>
> Hey all,
>
> I came upon a benchmark of F#, Rust and OCaml, where F# performs much faster
> then the other two. I decided for fun to try and port it to Clojure to see
> how Clojure does. Benchmark link: https://github.com/c-cube/hashset_benchs
>
> This is my code for it:
> https://gist.github.com/didibus/1fd4c00b69d927745fbce3dcd7ca461a
>
> (ns hash-set-bench
> "A Benchmark I modified to Clojure from:
> https://github.com/c-cube/hashset_benchs";)
>
> (defn iterNeighbors [f [i j]]
> (f [(dec i) j])
> (f [(inc i) j])
> (f [i (dec j)])
> (f [i (inc j)]))
>
> (defn nth* [n p]
> (loop [n n s1 #{p} s2 #{}]
> (if (= n 0)
> s1
> (let [s0 (atom #{})]
> (letfn [(add [p]
> (when (not (or (contains? s1 p) (contains? s2 p)))
> (reset! s0 (conj @s0 p))))]
> (doseq [p s1] (iterNeighbors add p))
> (recur (dec n) @s0 s1))))))
>
> #_(printf "result is %d" (count (time (nth* 2000 [0 0]))))
>
> And here's the F# code:
> https://github.com/c-cube/hashset_benchs/blob/master/neighbors2.fsx
>
> Currently, this takes about 30s in Clojure, while it only takes around 3s for
> OCaml, Rust and F#.
>
> From what I see, the differences between my code and theirs are:
> • Lack of a Point struct, I'm just using a vector.
> • They use a mutable set, I don't.
> • They overrode Hashing for their point struct, as well as equality. I
> rely on Clojure's default hashing, and vector equality.
> I'm not sure if any of these things should really impact performance that
> much though. And what I could do in Clojure if I wanted to improve it.
>
>
>
> Any Help?
>
>
>
> Thanks.
>
>
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to [email protected]
> Note that posts from new members are moderated - please be patient with your
> first post.
> To unsubscribe from this group, send email to
> [email protected]
> 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 [email protected].
> For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
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 [email protected].
For more options, visit https://groups.google.com/d/optout.
