Dubious performance characteristics of hash-maps - Clojure

The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion Dubious performance characteristics of hash-maps
Received-SPF: pass (google.com: domain of richhic...@gmail.com designates 209.85.211.149 as permitted sender) client-ip=209.85.211.149;
MIME-Version: 1.0
Date: Tue, 23 Feb 2010 06:41:28 -0800 (PST)
In-Reply-To: <1266903321-sup-3688@ezyang>
References: <1266903321-sup-3688@ezyang>
User-Agent: G2/1.0
Message-ID: <0ae66976-92a2-4ce1-ab3a-948cf22d4404@t42g2000vbt.googlegroups.com>
Subject: Re: Dubious performance characteristics of hash-maps
From: Rich Hickey <richhic...@gmail.com>
To: Clojure <clojure@googlegroups.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable



On Feb 23, 12:51=A0am, "Edward Z. Yang" <ezy...@MIT.EDU> wrote:
> I'd first like to state that I went into this exercise expecting
> Bagwell's Hash Array Mapped Tries to blow the competition out of the
> water; I'd get a fast functional map and give it to Haskell and people
> would rejoice.
>
> Instead, I found a functional hash-map that was approximately four times
> slower than Haskell's IntMap. =A0I find this puzzling, and would love to
> puzzle it out with you folks.
>
> First, the test case:
>
> =A0 =A0 (ns maptest (:gen-class))
>
> =A0 =A0 (defn mk-random-stream []
> =A0 =A0 =A0 =A0 (let [r (new ec.util.MersenneTwisterFast)]
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(repeatedly (fn [] (. r (nextInt))))))
>
> =A0 =A0 (defn -main [sn]
> =A0 =A0 =A0 (let [n =A0(Integer/parseInt sn)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 rs (take (* 2 n) (mk-random-stream))]
> =A0 =A0 =A0 =A0(time (let [m =A0(apply hash-map (take (* n 2) (interleave=
 rs rs)))]
> =A0 =A0 =A0 =A0 =A0 =A0 (reduce
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (fn [s k] (let [v (get m k)]
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =
=A0 =A0 =A0 =A0 (+ s (if (nil? v) 0 v))))
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 0
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (take n (drop (/ n 2) rs)))))))
>
> We generate an n-sized hash tree, and then do n accesses, half of which
> match and half of which miss. =A0We compute the sum of all the values tha=
t
> catch. =A0We see the following characteristics:
>
> =A0 =A0 =A0 =A0n =A0 Clojure =A0 Haskell (HAMT) =A0 Haskell (IntMap)
> =A0 =A0 =A032K =A0 =A0 .56s =A0 =A0 =A0 =A0 =A0 =A0.30s =A0 =A0 =A0 =A0 =
=A0 .09s
> =A0 =A0 =A064K =A0 =A0 .84s =A0 =A0 =A0 =A0 =A0 =A0.69s =A0 =A0 =A0 =A0 =
=A0 .22s
> =A0 =A0 128K =A0 =A01.65s =A0 =A0 =A0 =A0 =A0 1.50s =A0 =A0 =A0 =A0 =A0 .=
46s
> =A0 =A0 256K =A0 =A02.94s =A0 =A0 =A0 =A0 =A0 3.23s =A0 =A0 =A0 =A0 =A01.=
17s
> =A0 =A0 512K =A0 =A07.32s =A0 =A0 =A0 =A0 =A0 6.96s =A0 =A0 =A0 =A0 =A02.=
70s
>
> I was careful to compile the Clojure code before attempting to run it.
> I also pre-allocate the entire random sequence to prevent it from
> muddying the execution time (although I am using Sean Luke's excellent
> fast Mersenne Twister [1]). =A0The full string I used to invoke the
> program was:
>
> =A0 =A0 /usr/lib/jvm/java-6-sun-1.6.0.16/bin/java -Dfile.encoding=3DUTF-8=
 \
> =A0 =A0 =A0 =A0 -classpath $CLASSES maptest $@
>
> The fact that it's similar in performance to the Haskell
> reimplementation (I'd say that the variance is not particularly
> significant and both are about on par performance wise) seems to
> validate the testing methodology, I hope, though the real proof of the
> pudding would lie in implementing Haskell-style IntMap in Java.
>
> You can see the test code for the Haskell versions here:
>
> =A0 =A0http://github.com/ezyang/hamt
>
> So... what's up with these numbers? =A0Is my methodology wrong? =A0Is the
> garbage collector sucking? =A0Is the algorithm just not as good as it
> makes out to be?
>

Yes, the methodology is wrong, at least on the Clojure/JVM side.
First, benchmarking anything without -server is a waste of time.
Second, the JVM does dynamic profile-driven compilation - performance
on single cold runs is not indicative of optimal performance. Third,
putting the random stream gen call in the let doesn't preallocate the
sequence, nor move its execution there (and thus out of the timing),
as Clojure's repeatedly/take etc are lazy. Fourth, it's possible to
structure the code more like your Haskell IntMap code [1] (i.e. no
interleave). Fifth, AOT compilation makes no difference in performance
- Clojure code is always compiled.

Try this:

;run with java -server -Xmx1024m

(defn mk-random-stream []
  (let [r (new ec.util.MersenneTwisterFast)]
    (repeatedly (fn [] (. r (nextInt))))))

(defn main [i]
  (let [vals (vec (take (* i 2) (mk-random-stream)))]
    (dotimes [_ 10]
      (time
       (let [m (apply hash-map (take i vals))]
         (reduce (fn [s k] (+ s (m k 0)))
           0
           (take i (drop (/ i 2) vals))))))))

(doseq [n (range 15 20)]
  (let [i (int (Math/pow 2 n))]
    (println " I =3D " i)
    (main i)))

I =3D  32768
"Elapsed time: 199.499 msecs"
"Elapsed time: 43.018 msecs"
"Elapsed time: 24.715 msecs"
"Elapsed time: 24.081 msecs"
"Elapsed time: 39.707 msecs"
"Elapsed time: 23.909 msecs"
"Elapsed time: 25.918 msecs"
"Elapsed time: 27.328 msecs"
"Elapsed time: 23.797 msecs"
"Elapsed time: 23.874 msecs"
 I =3D  65536
"Elapsed time: 66.411 msecs"
"Elapsed time: 298.676 msecs"
"Elapsed time: 58.821 msecs"
"Elapsed time: 66.621 msecs"
"Elapsed time: 60.428 msecs"
"Elapsed time: 56.664 msecs"
"Elapsed time: 67.778 msecs"
"Elapsed time: 56.833 msecs"
"Elapsed time: 58.613 msecs"
"Elapsed time: 60.37 msecs"
 I =3D  131072
"Elapsed time: 118.257 msecs"
"Elapsed time: 173.605 msecs"
"Elapsed time: 121.663 msecs"
"Elapsed time: 166.162 msecs"
"Elapsed time: 118.889 msecs"
"Elapsed time: 158.164 msecs"
"Elapsed time: 120.545 msecs"
"Elapsed time: 157.452 msecs"
"Elapsed time: 120.446 msecs"
"Elapsed time: 154.614 msecs"
 I =3D  262144
"Elapsed time: 390.623 msecs"
"Elapsed time: 247.928 msecs"
"Elapsed time: 336.522 msecs"
"Elapsed time: 361.865 msecs"
"Elapsed time: 250.092 msecs"
"Elapsed time: 324.004 msecs"
"Elapsed time: 619.761 msecs"
"Elapsed time: 250.708 msecs"
"Elapsed time: 253.414 msecs"
"Elapsed time: 247.428 msecs"
 I =3D  524288
"Elapsed time: 752.528 msecs"
"Elapsed time: 1254.839 msecs"
"Elapsed time: 1126.026 msecs"
"Elapsed time: 589.351 msecs"
"Elapsed time: 532.753 msecs"
"Elapsed time: 532.615 msecs"
"Elapsed time: 554.859 msecs"
"Elapsed time: 529.93 msecs"
"Elapsed time: 525.966 msecs"
"Elapsed time: 551.065 msecs"

Note as HotSpot kicks in to optimize the code.

Note also the near-linearity of the times with increase in N,
indicating the promised near-constant-time performance (unlike the
IntMap times).

Regards,

Rich

[1] http://github.com/ezyang/hamt/blob/master/IntMapTest.hs
Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
Account Options
