PS. Results for the original input on my box. Going by the the timings
posted above, yours is rather beefier, so this is probably faster than the
current F# version.
(c/quick-bench (nth-shell 2000 (point. 0 0)))
Evaluation count : 6 in 6 samples of 1 calls.
Execution time mean : 2.956519 sec
Execution time std-deviation : 22.423970 ms
Execution time lower quantile : 2.930938 sec ( 2.5%)
Execution time upper quantile : 2.978283 sec (97.5%)
Overhead used : 21.423788 ns
On 22 November 2016 at 05:21, Michał Marczyk <[email protected]>
wrote:
> 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.
