Some further optimizations for a factor of ~2.3 speed-up over nth5 as copy
& pasted from upthread (6.713742 ms → 2.897630 ms) in
(c/quick-bench (nth-shell 100 (point. 0 0)))
(1) java.util.HashSet has a ctor that takes initial capacity of the set as
an int. Passing in (* 4 (.size s1)) when constructing s0 – (HashSet. (* 4
(.size s1)) – gives me a fair speed-up on its own.
(2) Also, (java.util.HashSet. [p]) is a reflective call – replacing that
with (doto (java.util.HashSet.) (.add p)) seems to result in a tiny, but
measurable speed-up as well (to 5.245931 ms).
(3) Using an iterator results in a good speed-up, particularly in a
size-based loop (counting down from (.size current-set) rather than calling
(.hasNext current-iterator)).
(4) Finally, inlining all the visiting and switching to direct ctor calls
also helped.
Final code:
(deftype point [^long i ^long j]
Object
(equals [this that]
(and (= (.i this) (.i ^point that))
(= (.j this) (.j ^point that))))
(hashCode [this]
(+ (.i this) (* 4000 (.j this)))))
(defn nth-shell [^long n p]
(loop [n n
s1 (doto (HashSet.) (.add p))
s2 (HashSet.)]
(if (zero? n)
s1
(let [s0 (HashSet. (* 4 (.size s1)))
i1 (.iterator s1)]
(dotimes [_ (.size s1)]
(let [^point p (.next i1)
i ^long (.i p)
j ^long (.j p)
p1 (point. (dec i) j)
p2 (point. (inc i) j)
p3 (point. i (dec j))
p4 (point. i (inc j))]
(if-not (or (.contains s1 p1) (.contains s2 p1))
(.add s0 p1))
(if-not (or (.contains s1 p2) (.contains s2 p2))
(.add s0 p2))
(if-not (or (.contains s1 p3) (.contains s2 p3))
(.add s0 p3))
(if-not (or (.contains s1 p4) (.contains s2 p4))
(.add s0 p4))))
(recur (dec n) s0 s1)))))
Also, to check that this still outputs the same neighbours the original
impl (nth*) does:
(defn persistent-shell [shell]
(persistent!
(reduce (fn [out ^point p]
(conj! out [(.-i p) (.-j p)]))
(transient #{})
shell)))
(= (sort (persistent-shell (nth-shell 500 (point. 0 0))))
(sort (nth* 500 [0 0])))
Cheers,
Michał
On 22 November 2016 at 02:03, Didier <[email protected]> wrote:
> I tried it with the safe equals, and it is slightly slower, but still
> faster then all others at 4.5ms. The non safe equals gives me 4s. Though
> this is now within my error margin. If ire-run quick-bench, I sometime get
> a mean equal for each, so I don't think the instance check adds that much
> overhead if any at all.
>
> @miner: Doesn't using the flag (set! *unchecked-math* :warn-on-boxed)
> gives me unchecked math automatically? I was under the impression that +,
> -, /, * etc. would all now perform in an equal way to unchecked-add, etc.
> If not, what is the difference?
>
> @Andy: I tried with the "1.9.0-alpha14" version, and Records were still
> just as slow as with "1.8.0". Maybe I'm using them wrong.
>
> On Tuesday, 15 November 2016 19:39:43 UTC-8, Didier 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/hash
>> set_benchs
>>
>> This is my code for it: https://gist.github.com/didibu
>> s/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/hash
>> set_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.
