Clojure

Speed up dissoc on array-maps

Details

  • Type: Enhancement Enhancement
  • Status: Open Open
  • Priority: Major Major
  • Resolution: Unresolved
  • Affects Version/s: Release 1.5
  • Fix Version/s: None
  • Component/s: None
  • Labels:
  • Patch:
    Code
  • Approval:
    Triaged

Description

In latest Clojure master as of Nov 15 2013, the method without() in PersistentArrayMap.java first searches for a matching key using indexOf(key) and saves the result in i.

If a matching key was found, the code then copies the old array to the new smaller one, but unnecessarily repeats the comparison of every key in the map to the key being removed, even though its location is already stored in i.

Activity

Hide
Andy Fingerhut added a comment -

The patch clj-1295-1.diff changes PersistentArrayMap's without() to use System.arraycopy to copy only the necessary parts from the current array to newArray, similar to PersistentHashMap's method removePair().

Benchmark 1 has strings for keys, which are relatively slow to compare to each other.

(def m1 (array-map "abcdef" 1 "abcdeg" 2 "abcdeh" 3 "abcdei" 4))
(time (dotimes [i 100000000] (dissoc m1 "abcdei")))

1.6.0-alpha2 with no changes:
"Elapsed time: 29663.443 msecs"
"Elapsed time: 29490.225 msecs"
"Elapsed time: 29600.138 msecs"
"Elapsed time: 29627.948 msecs"

1.6.0-alpha2 with patch clj-1295-1.diff:
"Elapsed time: 6362.006 msecs"
"Elapsed time: 6121.006 msecs"
"Elapsed time: 6163.377 msecs"
"Elapsed time: 6155.299 msecs"
"Elapsed time: 6395.224 msecs"

Averages about 21% of the run time before the change.

Benchmark 2 has keywords for keys, which are compared via Java ==, so as fast as comparison can get.

(def m2 (array-map :abcdef 1 :abcdeg 2 :abcdeh 3 :abcdei 4))
(time (dotimes [i 100000000] (dissoc m2 :abcdei)))

1.6.0-alpha2 with no changes:
"Elapsed time: 5033.863 msecs"
"Elapsed time: 5028.327 msecs"
"Elapsed time: 5045.019 msecs"
"Elapsed time: 5004.751 msecs"
"Elapsed time: 5039.143 msecs"

1.6.0-alpha2 with patch clj-1295-1.diff:
"Elapsed time: 2874.748 msecs"
"Elapsed time: 2862.878 msecs"
"Elapsed time: 2887.778 msecs"
"Elapsed time: 2874.196 msecs"
"Elapsed time: 2861.807 msecs"

Averages about 57% of the run time before the change.

Show
Andy Fingerhut added a comment - The patch clj-1295-1.diff changes PersistentArrayMap's without() to use System.arraycopy to copy only the necessary parts from the current array to newArray, similar to PersistentHashMap's method removePair(). Benchmark 1 has strings for keys, which are relatively slow to compare to each other. (def m1 (array-map "abcdef" 1 "abcdeg" 2 "abcdeh" 3 "abcdei" 4)) (time (dotimes [i 100000000] (dissoc m1 "abcdei"))) 1.6.0-alpha2 with no changes: "Elapsed time: 29663.443 msecs" "Elapsed time: 29490.225 msecs" "Elapsed time: 29600.138 msecs" "Elapsed time: 29627.948 msecs" 1.6.0-alpha2 with patch clj-1295-1.diff: "Elapsed time: 6362.006 msecs" "Elapsed time: 6121.006 msecs" "Elapsed time: 6163.377 msecs" "Elapsed time: 6155.299 msecs" "Elapsed time: 6395.224 msecs" Averages about 21% of the run time before the change. Benchmark 2 has keywords for keys, which are compared via Java ==, so as fast as comparison can get. (def m2 (array-map :abcdef 1 :abcdeg 2 :abcdeh 3 :abcdei 4)) (time (dotimes [i 100000000] (dissoc m2 :abcdei))) 1.6.0-alpha2 with no changes: "Elapsed time: 5033.863 msecs" "Elapsed time: 5028.327 msecs" "Elapsed time: 5045.019 msecs" "Elapsed time: 5004.751 msecs" "Elapsed time: 5039.143 msecs" 1.6.0-alpha2 with patch clj-1295-1.diff: "Elapsed time: 2874.748 msecs" "Elapsed time: 2862.878 msecs" "Elapsed time: 2887.778 msecs" "Elapsed time: 2874.196 msecs" "Elapsed time: 2861.807 msecs" Averages about 57% of the run time before the change.
Andy Fingerhut made changes -
Field Original Value New Value
Attachment clj-1295-1.diff [ 12465 ]
Andy Fingerhut made changes -
Patch Code [ 10001 ]
Andy Fingerhut made changes -
Description In latest Clojure master as of Nov 15 2013, the method without() in PersistentArrayMap.java first searches for a matching key using indexOf(key) and saves the result in i.

If a matching key was found, the code then copies the old array to the new smaller one, but unnecessarily repeats the comparison of every key in the map to the key being remove, even though its location is already stored in i.
In latest Clojure master as of Nov 15 2013, the method without() in PersistentArrayMap.java first searches for a matching key using indexOf(key) and saves the result in i.

If a matching key was found, the code then copies the old array to the new smaller one, but unnecessarily repeats the comparison of every key in the map to the key being removed, even though its location is already stored in i.
Alex Miller made changes -
Approval Triaged [ 10120 ]
Alex Miller made changes -
Priority Minor [ 4 ] Major [ 3 ]

People

Vote (1)
Watch (1)

Dates

  • Created:
    Updated: