通过使用keyword-identical?改进select-keys的性能

Question

{{select-keys}}使用{{not=}}来比较关键字。相反，使用{{keyword-identical?}}可以获得不错的速度提升（基准测试和引擎的平均值为1.34）。请注意，使用{{identical?}}和{{lookup-sentinel}}似乎不会提高性能。

速度提升摘要


            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



之前

使用V8进行基准测试
;; test select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000次运行，179毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000次运行，121毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000次运行，183毫秒

使用SpiderMonkey进行基准测试
;; test select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000次运行，251毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000次运行，201毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000次运行，290毫秒

使用JavaScriptCore进行基准测试
;; test select-keys
[m {\:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000次运行，112毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000次运行，73毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000次运行，119毫秒

使用Nashorn进行基准测试
;; test select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000次运行，1277毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000次运行，524毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000次运行，635毫秒

使用ChakraCore进行基准测试
;; test select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000次运行，463毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000次运行，268毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000次运行，414毫秒


之后


使用V8进行基准测试
;; test select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000次运行，155毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000次运行，112毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000次运行，169毫秒

使用SpiderMonkey进行基准测试
;; test select-keys
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000次运行，146毫秒
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000次运行，135毫秒
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000次运行，173毫秒

使用JavaScriptCore进行基准测试
;; test select-keys
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000次运行，84毫秒
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000次运行，54毫秒
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000次运行，95毫秒

使用Nashorn进行基准测试
;; test select-keys
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000次运行，1099毫秒
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000次运行，502毫秒
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000次运行，648毫秒

使用ChakraCore进行基准测试
;; test select-keys
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000次运行，292毫秒
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000次运行，151毫秒
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000次运行，240毫秒

Answer 1

评论由：slipset发表

只想提醒您注意CLJ-1789，其中用reduce重新实现select-keys获得了显著的速度提升。
添加了一个补丁以展示这种方法。

Answer 2

评论由：mfikes发表

以下是Erik补丁的性能数据

`

        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

`

之后

`
使用V8进行基准测试
;; test select-keys
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000次运行，220毫秒
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000次运行，106毫秒
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000次运行，141毫秒

使用SpiderMonkey进行基准测试
;; test select-keys
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000次运行，169毫秒
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000次运行，153毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000次运行，183毫秒

使用JavaScriptCore进行基准测试
;; test select-keys
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000次运行，110毫秒
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000次运行，74毫秒
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000次运行，124毫秒

使用Nashorn进行基准测试
;; test select-keys
[[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000次运行，1128毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 次运行, 447 毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 次运行, 524 毫秒

使用ChakraCore进行基准测试
;; test select-keys
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 次运行, 366 毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 次运行, 199 毫秒
[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 次运行, 323 毫秒
`

Answer 3

评论由：slipset发表

还上传了一个不带瞬态的补丁。

Answer 4

评论由：mfikes发表

由于 CLJ-1789 补丁对较大的映射效果更好，这里有一个额外的性能测试，该测试覆盖了该案例，使用了该票据的数据，测试了我在帖子中附加的原始补丁和 Erik 的后续补丁。您可以看到 CLJ-1789 方法对 ClojureScript 也是有益的。

Erik，我看到您附加了一个第三个补丁。我建议在每次这样的补丁中添加性能数字，以便可以更轻松地评估补丁在高级优化下的效果。

`
引擎关键字-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

`

之前

`
使用V8进行基准测试
;; test 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 次运行, 373 毫秒

使用SpiderMonkey进行基准测试
;; test 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 次运行, 668 毫秒

使用JavaScriptCore进行基准测试
;; test 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 次运行, 200 毫秒

使用Nashorn进行基准测试
;; test 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 次运行, 2236 毫秒

使用ChakraCore进行基准测试
;; test 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 次运行, 1074 毫秒
`

关键字-identical? 之后

`
使用V8进行基准测试
;; test 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 次运行, 330 毫秒

使用SpiderMonkey进行基准测试
;; test 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 次运行, 353 毫秒

使用JavaScriptCore进行基准测试
;; test 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 次运行, 197 毫秒

使用Nashorn进行基准测试
;; test 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 次运行, 1991 毫秒

使用ChakraCore进行基准测试
;; test 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 次运行, 640 毫秒
`

CLJ-1789 之后

`
使用V8进行基准测试
;; test 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 次运行, 290 毫秒

使用SpiderMonkey进行基准测试
;; test 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 次运行, 279 毫秒

使用JavaScriptCore进行基准测试
;; test 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 次运行, 209 毫秒

使用Nashorn进行基准测试
;; test 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 次运行, 1578 毫秒

使用ChakraCore进行基准测试
;; test 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 次运行，591 毫秒
`

Answer 5

评论由：slipset发表

这两个补丁现在都有了基准测试

Answer 6

评论由：slipset发表

顺便说一下，对于关于较大映射的评论，我认为性能 transient 位依赖于所选键的大小，
例如，在映射中找到的所选键越多，我们从 conj! 获得的增益就越大

Answer 7

评论由：mfikes发表

运行这 4 个基准测试

[m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c]), 200000 次运行 [m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :x]), 200000 次运行 [m {:a 1, :b 2, :c 3, :d 4}], (select-keys m [:a :b :c :x :y :z]), 200000 次运行 [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 次运行

在所有 5 个引擎上使用 3 个附加补丁得出如下速度提升，在我的机器上

`
CLJS-2383.patch

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

SpiderMonkey: 2.36, 1.46, 1.79, 2.02 平均：1.91
JavaScriptCore: 1.28, 1.34, 1.23, 1.49 平均：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 平均：1.34
JavaScriptCore: 0.78, 0.84, 0.83, 1.02 平均：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 平均：1.71
JavaScriptCore: 1.01, 0.99, 1.03, 1.13 平均：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

评论由：mfikes发表

总结：如果应用，CLJS-2383.patch 应是首选，因为它提供了所有补丁中最大的速度提升。

Answer 9

参考：[https://clojure.atlassian.net/browse/CLJS-2383](https://clojure.atlassian.net/browse/CLJS-2383)（由 mfikes 报告）