Improve perf of select-keys by using keyword-identical?

Question

{{select-keys}} uses {{not=}} to compare keywords. Instead, using {{keyword-identical?}} results in decent speedups (an average of 1.34 across benchmarks and engines). Note that using {{identical?}} and {{lookup-sentinel}} doesn't appear to improve perf.

Speedup Summary:


            V8: 1.15, 1.08, 1.08
  SpiderMonkey: 1.71, 1.48, 1.67
JavaScriptCore: 1.33, 1.35, 1.25
       Nashorn: 1.16, 1.04, 0.97
    ChakraCore: 1.59, 1.66, 1.72



Before:

Benchmarking with V8
;;; select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs, 179 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs, 121 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs, 183 msecs

Benchmarking with SpiderMonkey
;;; select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs, 251 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs, 201 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs, 290 msecs

Benchmarking with JavaScriptCore
;;; select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs, 112 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs, 73 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs, 119 msecs

Benchmarking with Nashorn
;;; select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs, 1277 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs, 524 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs, 635 msecs

Benchmarking with ChakraCore
;;; select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs, 463 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs, 268 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs, 414 msecs


After


Benchmarking with V8
;;; select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs, 155 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs, 112 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs, 169 msecs

Benchmarking with SpiderMonkey
;;; select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs, 146 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs, 135 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs, 173 msecs

Benchmarking with JavaScriptCore
;;; select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs, 84 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs, 54 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs, 95 msecs

Benchmarking with Nashorn
;;; select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs, 1099 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs, 502 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs, 648 msecs

Benchmarking with ChakraCore
;;; select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs, 292 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs, 151 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs, 240 msecs

Answer 1

Comment made by: slipset

Just want to bring your attention to CLJ-1789, where reimplementing select-keys in terms of reduce gave a significant speedup.
Added a patch to show that way.

Answer 2

Comment made by: mfikes

Here are the perf numbers for Erik's patch:

`

        V8: 0.81, 1.14, 1.30

SpiderMonkey: 1.49, 1.31, 1.58
JavaScriptCore: 1.02, 0.99, 0.96

   Nashorn: 1.13, 1.17, 1.21
ChakraCore: 1.27, 1.35, 1.28

`

After:

`
Benchmarking with V8
;;; select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs, 220 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs, 106 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs, 141 msecs

Benchmarking with SpiderMonkey
;;; select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs, 169 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs, 153 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs, 183 msecs

Benchmarking with JavaScriptCore
;;; select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs, 110 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs, 74 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs, 124 msecs

Benchmarking with Nashorn
;;; select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs, 1128 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs, 447 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs, 524 msecs

Benchmarking with ChakraCore
;;; select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs, 366 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs, 199 msecs
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs, 323 msecs
`

Answer 3

Comment made by: slipset

Uploaded a patch without transients as well.

Answer 4

Comment made by: mfikes

Since the CLJ-1789 patch works better with larger maps, here is an additional perf test covering that case using the data from that ticket, testing both the original patch I had attached and Erik's subsequent patch. You can see the CLJ-1789 approach pays off for ClojureScript as well.

Erik, I see you attached a 3rd patch. I'd recommend adding perf numbers with each such patch, so the effect of the patch under advanced optimizations can be more readily assessed.

`
Engine keyword-identical? CLJ-1789

        V8:               1.13      1.29

SpiderMonkey: 1.89 2.39
JavaScriptCore: 1.02 0.96

   Nashorn:               1.12      1.42
ChakraCore:               1.68      1.82

`

Before:

`
Benchmarking with V8
;;; select-keys
[m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs, 373 msecs

Benchmarking with SpiderMonkey
;;; select-keys
[m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs, 668 msecs

Benchmarking with JavaScriptCore
;;; select-keys
[m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs, 200 msecs

Benchmarking with Nashorn
;;; select-keys
[m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs, 2236 msecs

Benchmarking with ChakraCore
;;; select-keys
[m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs, 1074 msecs
`

After (keyword-identical?)

`
Benchmarking with V8
;;; select-keys
[m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs, 330 msecs

Benchmarking with SpiderMonkey
;;; select-keys
[m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs, 353 msecs

Benchmarking with JavaScriptCore
;;; select-keys
[m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs, 197 msecs

Benchmarking with Nashorn
;;; select-keys
[m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs, 1991 msecs

Benchmarking with ChakraCore
;;; select-keys
[m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs, 640 msecs
`

After (CLJ-1789)

`
Benchmarking with V8
;;; select-keys
[m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs, 290 msecs

Benchmarking with SpiderMonkey
;;; select-keys
[m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs, 279 msecs

Benchmarking with JavaScriptCore
;;; select-keys
[m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs, 209 msecs

Benchmarking with Nashorn
;;; select-keys
[m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs, 1578 msecs

Benchmarking with ChakraCore
;;; select-keys
[m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs, 591 msecs
`

Answer 5

Comment made by: slipset

Both patches should have benchmarks now

Answer 6

Comment made by: slipset

oh, and as a comment to the comment about larger maps, I believe the performance transient bit is dependent on the size of the selected keys,
eg the more selected keys found in the map, the more we gain from conj!

Answer 7

Comment made by: mfikes

Running these 4 benchmarks

[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 runs [m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 runs [m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 runs [m {:a "b", :c "d", :b "b", :d "d", :e "e", :f "f", :g "g"}], (select-keys m [:a :c :b :d :e :f :g]), 200000 runs

against all 5 engines with the 3 attached patches yields the following speedups on my machine:

`
CLJS-2383.patch:

        V8: 1.11, 1.10, 1.64, 1.18  Avg: 1.26

SpiderMonkey: 2.36, 1.46, 1.79, 2.02 Avg: 1.91
JavaScriptCore: 1.28, 1.34, 1.23, 1.49 Avg: 1.34

   Nashorn: 1.19, 1.17, 1.06, 1.29  Avg: 1.18
ChakraCore: 1.61, 1.78, 1.75, 2.11  Avg: 1.81
                            Overall avg: 1.50
     Avg excluding Nashorn & ChakraCore: 1.50

0001-CLJS-2383-Speed-up-select-keys.patch:

        V8: 0.70, 0.95, 1.05, 1.23  Avg: 0.98

SpiderMonkey: 1.20, 1.09, 1.05, 2.03 Avg: 1.34
JavaScriptCore: 0.78, 0.84, 0.83, 1.02 Avg: 0.87

   Nashorn: 1.18, 1.08, 1.02, 1.48  Avg: 1.19
ChakraCore: 1.00, 1.12, 1.19, 1.75  Avg: 1.27
                            Overall avg: 1.13
     Avg excluding Nashorn & ChakraCore: 1.06	

0002-CLJS-2383-Speed-up-select-keys-no-transient.patch:

        V8: 1.28, 1.45, 1.37, 1.33  Avg: 1.36

SpiderMonkey: 1.54, 1.44, 1.70, 2.17 Avg: 1.71
JavaScriptCore: 1.01, 0.99, 1.03, 1.13 Avg: 1.04

   Nashorn: 1.39, 1.21, 1.14, 1.26  Avg: 1.25
ChakraCore: 1.20, 1.23, 1.19, 1.39  Avg: 1.25
                            Overall avg: 1.32
     Avg excluding Nashorn & ChakraCore: 1.37	

`

Answer 8

Comment made by: mfikes

Summary: If applied, CLJS-2383.patch would be the one to apply as it provides the greatest speedup of all the patches.

Answer 9

Reference: https://clojure.atlassian.net/browse/CLJS-2383 (reported by mfikes)