Re: Help me understand what part of this code is slow, and how to make it faster?

[Alex Miller]

That seems like a decent list. Also sounds like most of the Clojure Alioth 
contributions. :)

-- 
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/d/optout.

Re: Help me understand what part of this code is slow, and how to make it faster?

[Didier]

Here's my findings:

Speed increase from most increase to least:
* Pre-sizing the HashSet - from 4.7ms to 3.7ms
* Inlining - from 4.7ms to 3.9ms
* Using point. constructor instead of ->point - from 2.4ms to 2ms
* Using non relfective HashSet init - from 2.36ms to 2.17ms
* Using iterator instead of doseq - from 2.17ms to 2.07ms

All in all, after this whole experiment, those would be my go to 
recommendations if wanting to optimize something in Clojure:

- If you are creating a lot of temporary structures use deftype for optimum 
performance, avoid records, and go for vectors and maps as a good middle 
ground.
- If you are adding a lot to a data-structure, resort to a mutable version 
for best performance.
- If using a mutable data-structure, try to pre-size them, if you plan on 
them growing a lot.
- If performance is critical, try inlining the functions you call most, 
things called from a loop are great candidates.
- Avoid using ->wtv style constructors, prefer wtv. instead for best 
performance.
- Avoid reflection and checked boxed math, especially if inside a loop.
- Try an iterator as the fastest way to iterate over a structure, though at 
this point, you're probably spending too much time optimizing.

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/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 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/d/optout.

Re: Help me understand what part of this code is slow, and how to make it faster?

[Didier]

@Marczyk, I did try your improvements, and it shaved off 2 seconds, from 4s 
for the nth5 to 2s for your implementation.

I'm curious to try it one change at a time to see if any one of the changes 
was responsible for a bigger part, or if its an its of equal improvements 
that total up to a big speed boost.

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/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 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/d/optout.

Re: Help me understand what part of this code is slow, and how to make it faster?

[Andy Fingerhut]

More likely, records being just as slow with Clojure 1.9.0-alpha14 probably
mean that recalculating of record hashes was not a significant amount of
the time your program was taking.  Thanks for trying it out.

Andy

On Mon, Nov 21, 2016 at 5:03 PM, Didier  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 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/d/optout.
>

-- 
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/d/optout.

Re: Help me understand what part of this code is slow, and how to make it faster?

[Steve Miner]

> On Nov 21, 2016, at 8:03 PM, Didier  wrote:
> 
> @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?

Yes, you’re right about the *unchecked-math* flag.  There shouldn’t be any 
difference.

-- 
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/d/optout.

Re: Help me understand what part of this code is slow, and how to make it faster?

[Michał Marczyk]

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 
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  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: 

Re: Help me understand what part of this code is slow, and how to make it faster?

[Michał Marczyk]

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  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 

Re: Help me understand what part of this code is slow, and how to make it faster?

[Didier]

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/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 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/d/optout.

Re: Help me understand what part of this code is slow, and how to make it faster?

[Steve Miner]

> On Nov 21, 2016, at 3:05 PM, Didier  wrote:
> 
> I experimented with this a lot, and took everyone's advice, and this is the 
> fastest I got, even faster then Michael Gardner's answer.
> 
> (deftype point5 [^long i ^long j]
>   Object
>   (equals [this that] (and (= (.i this) (.i ^point5 that))
>(= (.j this) (.j ^point5 that
>   (hashCode [this] (+ (.i this) (* 4000 (.j this)


Java equals and hashCode are notoriously tricky to get right.  Equals should 
handle any kind of “that” so you typically need to test instance? (basically, 
instanceOf in Java).  Here are a couple of reference links:

http://stackoverflow.com/questions/27581/what-issues-should-be-considered-when-overriding-equals-and-hashcode-in-java

http://www.angelikalanger.com/Articles/JavaSolutions/SecretsOfEquals/Equals.html

In this case, I suggest you try something like this:

(equals [this that] (or (identical? this that)
(and (instance? point5 that)
 (= (.i this) (.i ^point5 that))
 (= (.j this) (.j ^point5 that)

It might be a little slower but it should be safer.

If you’re out for speed, you could also try unchecked-add, unchecked-multiply, 
unchecked-inc, and unchecked-dec where it's safe to ignore the chance of 
overflows.  I mention these only because you’re trying to compete on 
benchmarks.  Most of the time, you shouldn’t use them.





-- 
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/d/optout.

Re: Help me understand what part of this code is slow, and how to make it faster?

[Andy Fingerhut]

Not sure which version of Clojure you are using, but in all versions up to
the latest 'official' release, Clojure 1.8.0, records have their hash value
calculated every time they are needed, with no caching of the calculated
value.  The hash value is needed every time an operation is done in a
Clojure set, and probably a java HashSet, too.

The latest alpha release, Clojure 1.9.0-alpha14, contains a performance
improvement where records cache their hash value after it is first
calculated.  http://dev.clojure.org/jira/browse/CLJ-1224

I don't know if that change would make your version of the code using
records and Java HashSet's competitive with your fastest code or not, but
you may wish to try it.

Andy

On Mon, Nov 21, 2016 at 12:05 PM, Didier  wrote:

> I experimented with this a lot, and took everyone's advice, and this is
> the fastest I got, even faster then Michael Gardner's answer.
>
> (deftype point5 [^long i ^long j]
>   Object
>   (equals [this that] (and (= (.i this) (.i ^point5 that))
>(= (.j this) (.j ^point5 that
>   (hashCode [this] (+ (.i this) (* 4000 (.j this)
>
> (defn iter-neighbors5 [f ^point5 p]
>   (let [i ^long (.i p)
> j ^long (.j p)]
> (f (->point5 (dec i) j))
> (f (->point5 (inc i) j))
> (f (->point5 i (dec j)))
> (f (->point5 i (inc j)
>
> (defn nth5 [n p]
>   (loop [n ^long n
>  s1 (HashSet. [p])
>  s2 (HashSet.)]
> (if (zero? n)
>   s1
>   (let [s0 (HashSet.)]
> (letfn [(add [p]
>  (when (not (or (.contains s1 p) (.contains s2 p)))
>(.add s0 p)))]
>(doseq [p s1] (iter-neighbors5 add p))
>(recur (dec n) s0 s1))
>
> This is basically the closest I can get to the F#, Rust and OCaml
> solution. I create a minimal class where I overload equals and hashCode
> using the same logic the F# solution uses. It gives me equal performance to
> F# on my machine: 3s.
>
> Here's the run down from slowest to fastest with a size of 100 using
> criterium. All of them I did my best to avoid reflection and boxed numeric
> and had enabled uncheck math. Granted I did not find that boxing and
> unchecked math really provided a drastic improvement in my case.:
>
>1. Using a record to hold the point with a java HashSet - 826ms
>2. Using a struct to hold the point with a java HashSet - 246ms
>3. Using a volatile with a Clojure HashSet and vectors for point - 50ms
>4. Using an atom with a Clojure HashSet and vectors for point - 51ms
>5. Using java.awt Point with a java HashSet and add as a closure - 41ms
>6. Using vectors with a java HashSet, but with add done inside doseq,
>without a closure - 11ms
>7. Using vectors with a java HashSet and add as a closure - 9ms
>8. Using java.awt Point with a java HashSet, but with add done inside
>doseq, without a closure (Michael Gardner's solution) - 7.5ms
>9. Using deftype with overloaded equals and hashCode as points with a
>java HashSet, but with add done inside doseq, without a closure - 6ms
>10. Using deftype with overloaded equals and hashCode as points with a
>java HashSet and add as a closure - 4ms
>
> This is what I gathered from my experiments:
>
>- Using java's mutable HashSet instead of Clojure's persistent hashset
>gave a significant speed improvement. From 30s to 5s. This was the most
>significant speed boost.
>- Records are really slow, probably because of the time to instantiate
>them. So slow, that even though it was using a mutable HashSet, it was
>still slower then Clojure sets with vectors.
>- Similarly, structs are also pretty slow, which I'd guess is also
>because of instantiating them. Though they were faster then Records.
>- Volatile did not noticeably improve performance compared to Atom,
>but I learned about them today, did not know Clojure had that.
>- Unsafe Math and type hinting numeric to get rid of boxing did not
>noticeably improve performance, but I learned about it today too. Speaking
>of which, is ^long faster then ^int?
>- Vectors were as fast as java.awt.Point. Though for some reason,
>putting the java.awt.Point inside a closure slowed the whole thing down
>quite a bit. Where as without it, using a closure actually performed
>faster. Maybe I did something wrong here, since I find that a little
>surprising and confusing.
>- Defining my own type optimized for my specific use-case was the
>fastest. deftypes are lightweight, and instantiate quickly, and with the
>custom equals and hashCode tailored to the problem, they performed best,
>matching F# and beating out OCaml and Rust.
>
>
> 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 

Re: Help me understand what part of this code is slow, and how to make it faster?

[Didier]

I experimented with this a lot, and took everyone's advice, and this is the 
fastest I got, even faster then Michael Gardner's answer.

(deftype point5 [^long i ^long j]
  Object
  (equals [this that] (and (= (.i this) (.i ^point5 that))
   (= (.j this) (.j ^point5 that
  (hashCode [this] (+ (.i this) (* 4000 (.j this)

(defn iter-neighbors5 [f ^point5 p]
  (let [i ^long (.i p)
j ^long (.j p)]
(f (->point5 (dec i) j))
(f (->point5 (inc i) j))
(f (->point5 i (dec j)))
(f (->point5 i (inc j)

(defn nth5 [n p]
  (loop [n ^long n
 s1 (HashSet. [p])
 s2 (HashSet.)]
(if (zero? n)
  s1
  (let [s0 (HashSet.)]
(letfn [(add [p]
 (when (not (or (.contains s1 p) (.contains s2 p)))
   (.add s0 p)))]
   (doseq [p s1] (iter-neighbors5 add p))
   (recur (dec n) s0 s1))

This is basically the closest I can get to the F#, Rust and OCaml solution. 
I create a minimal class where I overload equals and hashCode using the 
same logic the F# solution uses. It gives me equal performance to F# on my 
machine: 3s.

Here's the run down from slowest to fastest with a size of 100 using 
criterium. All of them I did my best to avoid reflection and boxed numeric 
and had enabled uncheck math. Granted I did not find that boxing and 
unchecked math really provided a drastic improvement in my case.:

   1. Using a record to hold the point with a java HashSet - 826ms
   2. Using a struct to hold the point with a java HashSet - 246ms
   3. Using a volatile with a Clojure HashSet and vectors for point - 50ms
   4. Using an atom with a Clojure HashSet and vectors for point - 51ms
   5. Using java.awt Point with a java HashSet and add as a closure - 41ms
   6. Using vectors with a java HashSet, but with add done inside doseq, 
   without a closure - 11ms
   7. Using vectors with a java HashSet and add as a closure - 9ms
   8. Using java.awt Point with a java HashSet, but with add done inside 
   doseq, without a closure (Michael Gardner's solution) - 7.5ms
   9. Using deftype with overloaded equals and hashCode as points with a 
   java HashSet, but with add done inside doseq, without a closure - 6ms
   10. Using deftype with overloaded equals and hashCode as points with a 
   java HashSet and add as a closure - 4ms
   
This is what I gathered from my experiments:

   - Using java's mutable HashSet instead of Clojure's persistent hashset 
   gave a significant speed improvement. From 30s to 5s. This was the most 
   significant speed boost.
   - Records are really slow, probably because of the time to instantiate 
   them. So slow, that even though it was using a mutable HashSet, it was 
   still slower then Clojure sets with vectors.
   - Similarly, structs are also pretty slow, which I'd guess is also 
   because of instantiating them. Though they were faster then Records.
   - Volatile did not noticeably improve performance compared to Atom, but 
   I learned about them today, did not know Clojure had that.
   - Unsafe Math and type hinting numeric to get rid of boxing did not 
   noticeably improve performance, but I learned about it today too. Speaking 
   of which, is ^long faster then ^int?
   - Vectors were as fast as java.awt.Point. Though for some reason, 
   putting the java.awt.Point inside a closure slowed the whole thing down 
   quite a bit. Where as without it, using a closure actually performed 
   faster. Maybe I did something wrong here, since I find that a little 
   surprising and confusing.
   - Defining my own type optimized for my specific use-case was the 
   fastest. deftypes are lightweight, and instantiate quickly, and with the 
   custom equals and hashCode tailored to the problem, they performed best, 
   matching F# and beating out OCaml and Rust.
   

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/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: 
> 

Re: Help me understand what part of this code is slow, and how to make it faster?

[Michael Gardner]

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  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 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/d/optout.

-- 
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/d/optout.

Re: Help me understand what part of this code is slow, and how to make it faster?

[Alex Miller]

In general, any benchmark code using math should be aware of boxing (old 
post here: http://insideclojure.org/2014/12/15/warn-on-boxed/).

I would recommend doing the work to leverage primitive longs and unchecked 
math. Generally this makes numeric code like this about 2 orders of 
magnitude faster.

Removing the stateful atom and converting to a purely functional form would 
probably be a win too, but it's hard to say.

Make sure to run it multiple times before looking at timings so that the 
JVM compiles and optimizes the code.


On Tuesday, November 15, 2016 at 9:39:43 PM UTC-6, 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/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 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/d/optout.

Re: Help me understand what part of this code is slow, and how to make it faster?

[Alex Miller]

On Wednesday, November 16, 2016 at 8:10:27 AM UTC-6, Jason Felice wrote:
>
> I'll bet the atom accesses dominate the computation.  They are a part of 
> Clojures software transactional memory (STM) and have a cost.
>

Atoms don't use the STM and if used in a single-threaded context like this, 
they will be uncontended, so the fastest case. That said, if you want 
something stateful, a volatile is faster in a single-threaded context.

-- 
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/d/optout.

Re: Help me understand what part of this code is slow, and how to make it faster?

[Jason Felice]

I'll bet the atom accesses dominate the computation.  They are a part of
Clojures software transactional memory (STM) and have a cost.

Something like this (untested) should be faster:

(->> (iterate  neighbors #{p}) (drop 1999) first)

neighbors could be:

(into #{} (for [[id jd] [[-1 0] [+1 0] [0 +1] [0 -1]]
[(+ i id) (+ j jd)]))

This creates some negligible lazy lists.

If you want to test actual time for hash inserts, though, you'll probably
need to use transients or some such, and the code would become less
idiomatic.


On Tue, Nov 15, 2016 at 10:39 PM, 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/
> 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 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/d/optout.
>

-- 
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/d/optout.

Re: Help me understand what part of this code is slow, and how to make it faster?

[James Reeves]

On 16 November 2016 at 03:39, Didier  wrote:
>
> 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.
>
It's the mutability of the set that's causing the greatest performance
impact. You can't substitute in an immutable data structure into an
algorithm that makes heavy use of a mutable structure, and expect it to
have the same performance.

Something like this is more faithful to the original F# benchmark you
posted:

(defn nth* [n p]
  (loop [n n, s1 (java.util.HashSet. [p]), s2 (java.util.HashSet.)]
(if (= n 0)
  s1
  (let [s0 (java.util.HashSet.)]
(letfn [(add [p]
  (when-not (or (.contains s1 p) (.contains s2 p))
(.add s0 p)))]
  (doseq [p s1] (iter-neighbors add p))
  (recur (dec n) s0 s1))

- James



>
> 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 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/d/optout.
>

-- 
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/d/optout.

Help me understand what part of this code is slow, and how to make it faster?

[Didier]

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 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/d/optout.