尽可能使用transients与select-keys

Question

问题：当前select-keys使用conj来添加条目。如果映射可编辑，则可以使用conj!来代替提高select-keys的性能。

此外，keyseq作为seq进行遍历，但可以改用reduce进行遍历，这可能会更快。

方法1：使用transient映射和conj!，保持loop/recur
方法2：重新实现select-keys，改用reduce代替loop/recur
方法3：结合方法一和方法二

|选定的键大小 | loop/recur | transient | reduce | transient + reduce |
| :-- | :-- | :-- | :-- | :-- | :-- |
|1 | 243 ns | 256 ns | 161 ns | 188 ns |
|7 | 1.1 ms | - | 885 ns | 454 ns |

从这些数字中，选择了方法3。

注意：为了以reduce的形式实现select-keys，需要将select-keys移动到reduce定义之后。这强制了(declare select-keys)，因为它是用在reduce定义之前。

补丁：(链接：https://dev.clojure.org/jira/secure/attachment/17392/0001-CLJ-1789-Use-transients-and-reduce-with-select-keys.patch 文件名：0001-CLJ-1789-Use-transients-and-reduce-with-select-keys.patch)

Answer 1

评论者：slipset

标准的Clojure select-keys

 (bench (clojure.core/select-keys {:a "b" :c "d"} [:a]))
评估计数：246382440，在60个样本的4106374次调用中。
             平均执行时间：243.245536 ns
    执行时间标准差：2.714803 ns
   执行时间下四分位数：238.473675 ns ( 2.5%)
   执行时间上四分位数：248.544255 ns (97.5%)
                   使用的开销：1.845047 ns


使用transients

(bench (select-keys {:a "b" :c "d"} [:a]))
评估计数：232727220，在60个样本的3878787次调用中。
             平均执行时间：256.937568 ns
    执行时间标准差：10.025123 ns
   执行时间下四分位数：249.951872 ns（2.5%）
   执行时间上四分位数：276.251590 ns（97.5%）
                   使用的开销：1.845047 ns

在60个样本中发现了5个异常值（8.3333%）
   低严重     3（5.0000%）
   低轻微     2（3.3333%）
 异常值的方差：25.4503% 异常值略微增加了方差


减少执行时间后

(bench (select-keys {:a "b" :c "d"} [:a]))
评估次数：364807860次，在60个样本中的6080131次调用。
             执行时间平均值：161.582833 ns
    执行时间标准差：2.212659 ns
   执行时间下四分位数：158.027524 ns（2.5%）
   执行时间上四分位数：167.673682 ns（97.5%）
                   使用的开销：1.845047 ns

在60个样本中发现了3个异常值（5.0000%）
   低严重     3（5.0000%）
 方差因异常值增加：1.6389% 异常值略微增加了方差

减少 + 临时

(bench (select-keys {:a "b" :c "d"} [:a]))
评估次数：318075720次，在60个样本中的5301262次调用。
             执行时间平均值：188.656164 ns
    执行时间标准差：3.024952 ns
   执行时间下四分位数：183.867285 ns（2.5%）
   执行时间上四分位数：195.466784 ns（97.5%）
                   使用的开销：1.845047 ns

在60个样本中发现了4个异常值（6.6667%）
    低严重     4（6.6667%）
 方差因异常值增加：1.6389% 异常值略微增加了方差


在大图/选择上

(bench (clojure.core/select-keys {:a "b" :c "d" :b "b" :d "d" :e "e" :f "f" :g "g"} [:a :c :b :d :e :f :g]))
评估次数：56147160次，在60个样本中的935786次调用。
             执行时间平均值：1.104653 µs
    执行时间标准差：36.366516 ns
   执行时间下四分位数：1.048257 µs（2.5%）
   执行时间上四分位数：1.142031 µs（97.5%）
                   使用的开销：1.845047 ns

在60个样本中发现了5个异常值（8.3333%）
    低严重     4（6.6667%）
    低轻微     1（1.6667%）
 方差因异常值增加：19.0389% 异常值略微增加了方差

reduce

(bench (select-keys {:a "b" :c "d" :b "b" :d "d" :e "e" :f "f" :g "g"} [:a :c :b :d :e :f :g]))
评估次数：67723500次，在60个样本中的1128725次调用。
             执行时间平均值：885.840664 ns
    执行时间标准差：11.503115 ns
   执行时间下四分位数：864.403495 ns（2.5%）
   执行时间上四分位数：905.721942 ns（97.5%）
                   使用的开销：1.845047 ns

临时 + reduce

(bench (select-keys {:a "b" :c "d" :b "b" :d "d" :e "e" :f "f" :g "g"} [:a :c :b :d :e :f :g]))
评估次数：134119380次，在60个样本中的2235323次调用。
             执行时间平均值：454.587795 ns
    执行时间标准差：15.681611 ns
   执行时间下四分位数：439.822498 ns（2.5%）
   执行时间上四分位数：485.797378 ns（97.5%）
                   使用的开销：1.845047 ns

在60个样本中发现了3个异常值（5.0000%）
   低严重     3（5.0000%）
 方差因异常值增加：20.6393% 异常值略微增加了方差


附加补丁同时使用临时和reduce

Answer 2

评论者：alexmiller

在我看来，提出的方案是好的。描述需要更好地反映所考虑和选择的内容。

Answer 3

参考： https://clojure.atlassian.net/browse/CLJ-1789 （由 alexmiller 报告）