heaps in clojure vs SML

[Maris]

I implemented leftist heap (from Purely Functional Data Structures book)  in clojure. 

https://gist.github.com/maruks/135fef92455578b61de2

It takes 32 seconds to insert 100000 elements in heap:

(time  (peek   (reduce conj (empty-heap)  (range 10000000 20000000 100)   )))

"Elapsed time: 32649.71438 msecs"

10000000

Why is it so much slower than SML NJ?  Something wrong with my code?

Here is SML version:

https://gist.github.com/maruks/c863eac9cf057a071307

And function that inserts 100000 elements in 54 milliseconds !

fun test(n:int) : int  =

    let

val r = List.tabulate(n, fn x => 10000000 + 100 * x)

val h = foldl ( fn (e, h) => IntHeap.insert(e , h) )  IntHeap.empty  r 

    in

IntHeap.findMin(h)

    end

[Nicola Mometto]

If you set! *warn-on-reflection* to true, you'd see a lot of reflection
warnings from your code.

Type-hinting the code like this: http://sprunge.us/ATiV makes your
example execute in 120ms on my machine.

Maris writes:

> I implemented leftist heap (from Purely Functional Data Structures book)
> in clojure.
>
> https://gist.github.com/maruks/135fef92455578b61de2
>
> It takes 32 seconds to insert 100000 elements in heap:
>
> (time (peek (reduce conj (empty-heap) (range 10000000 20000000 100)
> )))
> "Elapsed time: 32649.71438 msecs"
> 10000000
>
> Why is it so much slower than SML NJ? Something wrong with my code?
>
>
> Here is SML version:
> https://gist.github.com/maruks/c863eac9cf057a071307
>

> And function that inserts 100000 elements in *54* milliseconds !

>
> fun test(n:int) : int =
> let
> val r = List.tabulate(n, fn x => 10000000 + 100 * x)
> val h = foldl ( fn (e, h) => IntHeap.insert(e , h) ) IntHeap.empty r
> in
> IntHeap.findMin(h)
> end

--

[Maris]

yes,  it helped     :-)

type hints make non-trivial difference   

thank you

[Mars0i]

You also might want to use Criterium rather than time for accurate benchmarking.

[Ashton Kemerling]

Also remember to give the JVM some warm up time, as the JVM depends heavily on JIT style optimizations, and measuring performance without it might not represent real world behavior,

--

Ashton

[Maris Orbidans]

I published my heap implementation on github:  

https://github.com/maruks/clj-data

It has reasonable performance.   I used it for   https://www.hackerrank.com/challenges/messy-medians

[org.clojars.maruks/maruks.data "0.0.1"]

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@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+u...@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 a topic in the Google Groups "Clojure" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/clojure/GBoLa_WBRfA/unsubscribe.
To unsubscribe from this group and all its topics, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Mars0i]

Criterium automates the JVM warmup process.