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

Ascending order - Click to sort in descending order
Hide
Permalink
Alex Miller added a comment -

Added to 1.6 release.

Show
Alex Miller added a comment - Added to 1.6 release.
Hide
Permalink
Alex Miller added a comment -

Made hash functions inline for performance.

Show
Alex Miller added a comment - Made hash functions inline for performance.
Hide
Permalink
Rich Hickey added a comment -

Reported where?

This looks like bad benchmarking.

(dotimes [_ 10] (let [x 1 y 1] (time (dotimes [n 1000000000] (clojure.lang.Murmur3/mixCollHash x y)))))

and

(dotimes [_ 10] (let [x 1 y 1] (time (dotimes [n 1000000000] #_(clojure.lang.Murmur3/mixCollHash x y)))))

take the same time on my machine.

I'd need to see tests where the return was definitely used, it seems this is just more easily ignored by hotspot when not used.

We probably only need to hint count and the return for decent results.

Show
Rich Hickey added a comment - Reported where? This looks like bad benchmarking. (dotimes [_ 10] (let [x 1 y 1] (time (dotimes [n 1000000000] (clojure.lang.Murmur3/mixCollHash x y))))) and (dotimes [_ 10] (let [x 1 y 1] (time (dotimes [n 1000000000] #_(clojure.lang.Murmur3/mixCollHash x y))))) take the same time on my machine. I'd need to see tests where the return was definitely used, it seems this is just more easily ignored by hotspot when not used. We probably only need to hint count and the return for decent results.
Hide
Permalink
Alex Miller added a comment -

It was reported by Mark Engelberg in his Instaparse rework - he observed these calls taking noticeably longer and overall times 10-20% down. I will ask him to chime in here.

Show
Alex Miller added a comment - It was reported by Mark Engelberg in his Instaparse rework - he observed these calls taking noticeably longer and overall times 10-20% down. I will ask him to chime in here.
Hide
Permalink
Rich Hickey added a comment -

Could someone please test hinting hint count and the return? I'd hate for the answer to anyone's perf issues be inlining.

Show
Rich Hickey added a comment - Could someone please test hinting hint count and the return? I'd hate for the answer to anyone's perf issues be inlining.
Hide
Permalink
Alex Miller added a comment -

I will provide some more data for consideration of the options.

Show
Alex Miller added a comment - I will provide some more data for consideration of the options.
Hide
Permalink
Alex Miller added a comment -

Test project for different variants

Show
Alex Miller added a comment - Test project for different variants
Hide
Permalink
Alex Miller added a comment -

Attached a test project with different variants for testing and better benchmarking. To run: 

unzip testclj1365.zip
cd clj1365
lein uberjar
java -server -cp target/clj1365-0.1.0-SNAPSHOT-standalone.jar clj1365.core

Results:

mix-collection-hash original
"Elapsed time: 57.777 msecs"
"Elapsed time: 18.034 msecs"
"Elapsed time: 20.591 msecs"
"Elapsed time: 25.179 msecs"
"Elapsed time: 21.781 msecs"
mix-collection-hash hints
"Elapsed time: 14.983 msecs"
"Elapsed time: 8.871 msecs"
"Elapsed time: 8.793 msecs"
"Elapsed time: 8.92 msecs"
"Elapsed time: 8.873 msecs"
mix-collection-hash inline
"Elapsed time: 10.04 msecs"
"Elapsed time: 7.117 msecs"
"Elapsed time: 7.306 msecs"
"Elapsed time: 7.324 msecs"
"Elapsed time: 7.175 msecs"
Murmur3/mixCollHash
"Elapsed time: 9.522 msecs"
"Elapsed time: 7.288 msecs"
"Elapsed time: 7.397 msecs"
"Elapsed time: 7.364 msecs"
"Elapsed time: 7.345 msecs"

From these results, I infer that the unhinted version is slower (21 ms) than a static call (7 ms). Inlining gives you same perf as static. Hinting inputs and return gives almost the same perf (9 ms).

Show
Alex Miller added a comment - Attached a test project with different variants for testing and better benchmarking. To run: 
unzip testclj1365.zip
cd clj1365
lein uberjar
java -server -cp target/clj1365-0.1.0-SNAPSHOT-standalone.jar clj1365.core
Results: 
mix-collection-hash original
"Elapsed time: 57.777 msecs"
"Elapsed time: 18.034 msecs"
"Elapsed time: 20.591 msecs"
"Elapsed time: 25.179 msecs"
"Elapsed time: 21.781 msecs"
mix-collection-hash hints
"Elapsed time: 14.983 msecs"
"Elapsed time: 8.871 msecs"
"Elapsed time: 8.793 msecs"
"Elapsed time: 8.92 msecs"
"Elapsed time: 8.873 msecs"
mix-collection-hash inline
"Elapsed time: 10.04 msecs"
"Elapsed time: 7.117 msecs"
"Elapsed time: 7.306 msecs"
"Elapsed time: 7.324 msecs"
"Elapsed time: 7.175 msecs"
Murmur3/mixCollHash
"Elapsed time: 9.522 msecs"
"Elapsed time: 7.288 msecs"
"Elapsed time: 7.397 msecs"
"Elapsed time: 7.364 msecs"
"Elapsed time: 7.345 msecs"
From these results, I infer that the unhinted version is slower (21 ms) than a static call (7 ms). Inlining gives you same perf as static. Hinting inputs and return gives almost the same perf (9 ms).

People

Vote (0)
Watch (1)

Dates

  • Created:
    Updated:
    Resolved:
Atlassian JIRA (v4.4#649-r158309) | Report a problem
Powered by a free Atlassian JIRA open source license for Clojure. Try JIRA - bug tracking software for your team.