Clojure

New collection hash functions are too slow

Details

  • Type: Enhancement Enhancement
  • Status: Closed Closed
  • Priority: Major Major
  • Resolution: Completed
  • Affects Version/s: Release 1.6
  • Fix Version/s: Release 1.6
  • Component/s: None
  • Labels:
  • Patch:
    Code
  • Approval:
    Ok

Description

As reported ( https://groups.google.com/d/msg/clojure-dev/t6LAmVe-RLM/ekLTKxYfU5UJ ) by Mark Engelberg, the new collection hashing functions are slower than invoking the Murmur3 functions directly. See the attached zip for performance tests.

Approach: Made mix-collection-hash, hash-ordered-coll, and hash-unordered-coll use primitive type hints to avoid the bulk of the time.

Patch: clj-1365-v2.patch

Screened by:

Activity

Alex Miller made changes -
Field Original Value New Value
Approval Vetted [ 10003 ]
Fix Version/s Release 1.6 [ 10157 ]
Alex Miller made changes -
Patch Code [ 10001 ]
Description As reported by Mark Engelberg, the new collection hashing functions (in particular mix-collection-hash) is too slow:

{code}
=> (time (dotimes [n 100000000] (mix-collection-hash 1 2)))
"Elapsed time: 957.731399 msecs"
nil
=> (let [x (int 1) y (int 1)] (time (dotimes [n 100000000] (mix-collection-hash x y))))
"Elapsed time: 498.924461 msecs"
nil
=> (let [x (int 1) y (int 1)] (time (dotimes [n 100000000] (clojure.lang.Murmur3/mixCollHash x y))))
"Elapsed time: 47.864854 msecs"
{code}

I observe that the return of mix-collection-hash is not type-hinted and is boxing the return type. There is also the issue of long vs int, but need to fix boxing first.
As reported by Mark Engelberg, the new collection hashing functions (in particular mix-collection-hash) is too slow:

{code}
=> (time (dotimes [n 100000000] (mix-collection-hash 1 2)))
"Elapsed time: 957.731399 msecs"
nil
=> (let [x (int 1) y (int 1)] (time (dotimes [n 100000000] (mix-collection-hash x y))))
"Elapsed time: 498.924461 msecs"
nil
=> (let [x (int 1) y (int 1)] (time (dotimes [n 100000000] (clojure.lang.Murmur3/mixCollHash x y))))
"Elapsed time: 47.864854 msecs"
{code}

*Approach:* Made mix-collection-hash, hash-ordered-coll, and hash-unordered-coll inline calls to Murmur3 for performance. Now seems on par with the direct call as shown above.

*Patch:* clj-1365-v1.patch

*Screened by:*
Attachment clj-1365-v1.patch [ 12833 ]
Labels collections
Stuart Halloway made changes -
Approval Vetted [ 10003 ] Screened [ 10004 ]
Rich Hickey made changes -
Approval Screened [ 10004 ] Incomplete [ 10006 ]
Alex Miller made changes -
Description As reported by Mark Engelberg, the new collection hashing functions (in particular mix-collection-hash) is too slow:

{code}
=> (time (dotimes [n 100000000] (mix-collection-hash 1 2)))
"Elapsed time: 957.731399 msecs"
nil
=> (let [x (int 1) y (int 1)] (time (dotimes [n 100000000] (mix-collection-hash x y))))
"Elapsed time: 498.924461 msecs"
nil
=> (let [x (int 1) y (int 1)] (time (dotimes [n 100000000] (clojure.lang.Murmur3/mixCollHash x y))))
"Elapsed time: 47.864854 msecs"
{code}

*Approach:* Made mix-collection-hash, hash-ordered-coll, and hash-unordered-coll inline calls to Murmur3 for performance. Now seems on par with the direct call as shown above.

*Patch:* clj-1365-v1.patch

*Screened by:*
As reported ( https://groups.google.com/d/msg/clojure-dev/t6LAmVe-RLM/ekLTKxYfU5UJ ) by Mark Engelberg, the new collection hashing functions (in particular mix-collection-hash) are too slow:

{code}
=> (time (dotimes [n 100000000] (mix-collection-hash 1 2)))
"Elapsed time: 957.731399 msecs"
nil
=> (let [x (int 1) y (int 1)] (time (dotimes [n 100000000] (mix-collection-hash x y))))
"Elapsed time: 498.924461 msecs"
nil
=> (let [x (int 1) y (int 1)] (time (dotimes [n 100000000] (clojure.lang.Murmur3/mixCollHash x y))))
"Elapsed time: 47.864854 msecs"
{code}

*Approach:* Made mix-collection-hash, hash-ordered-coll, and hash-unordered-coll inline calls to Murmur3 for performance. Now seems on par with the direct call as shown above.

*Patch:* clj-1365-v1.patch

*Screened by:*
Alex Miller made changes -
Attachment testclj1365.zip [ 12855 ]
Alex Miller made changes -
Approval Incomplete [ 10006 ] Vetted [ 10003 ]
Description As reported ( https://groups.google.com/d/msg/clojure-dev/t6LAmVe-RLM/ekLTKxYfU5UJ ) by Mark Engelberg, the new collection hashing functions (in particular mix-collection-hash) are too slow:

{code}
=> (time (dotimes [n 100000000] (mix-collection-hash 1 2)))
"Elapsed time: 957.731399 msecs"
nil
=> (let [x (int 1) y (int 1)] (time (dotimes [n 100000000] (mix-collection-hash x y))))
"Elapsed time: 498.924461 msecs"
nil
=> (let [x (int 1) y (int 1)] (time (dotimes [n 100000000] (clojure.lang.Murmur3/mixCollHash x y))))
"Elapsed time: 47.864854 msecs"
{code}

*Approach:* Made mix-collection-hash, hash-ordered-coll, and hash-unordered-coll inline calls to Murmur3 for performance. Now seems on par with the direct call as shown above.

*Patch:* clj-1365-v1.patch

*Screened by:*
As reported ( https://groups.google.com/d/msg/clojure-dev/t6LAmVe-RLM/ekLTKxYfU5UJ ) by Mark Engelberg, the new collection hashing functions are slower than invoking the Murmur3 functions directly. See the attached zip for performance tests.

*Approach:* Made mix-collection-hash, hash-ordered-coll, and hash-unordered-coll use primitive type hints to avoid the bulk of the time.

*Patch:* clj-1365-v2.patch

*Screened by:*
Attachment clj-1365-v2.patch [ 12856 ]
Stuart Halloway made changes -
Approval Vetted [ 10003 ] Screened [ 10004 ]
Rich Hickey made changes -
Approval Screened [ 10004 ] Ok [ 10007 ]
Stuart Halloway made changes -
Resolution Completed [ 1 ]
Status Open [ 1 ] Closed [ 6 ]

People

Vote (0)
Watch (1)

Dates

  • Created:
    Updated:
    Resolved: