尽可能使用transients与select-keys

Question

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

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

方法1：使用transient map和conj!，保持loop/recur
方法2：重新实现select-keys以代替loop/recur使用reduce
方法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。

注意：为了将select-keys用reduce实现，需要将其移动到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 纳秒
    执行时间标准差：10.025123 纳秒
   执行时间下四分位数：249.951872 纳秒 ( 2.5%)
   执行时间上四分位数：276.251590 纳秒 (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 纳秒
    执行时间标准差：2.212659 纳秒
   执行时间下四分位数：158.027524 纳秒 ( 2.5%)
   执行时间上四分位数：167.673682 纳秒 (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 纳秒
    执行时间标准差：3.024952 纳秒
   执行时间下四分位数：183.867285 纳秒 ( 2.5%)
   执行时间上四分位数：195.466784 纳秒 (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 微秒
    执行时间标准差：36.366516 纳秒
   执行时间下四分位数：1.048257 微秒 ( 2.5%)
   执行时间上四分位数：1.142031 微秒 (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 纳秒
    执行时间标准差：11.503115 纳秒
   执行时间下四分位数：864.403495 纳秒 ( 2.5%)
   执行时间上四分位数：905.721942 纳秒 (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 纳秒
    执行时间标准差：15.681611 纳秒
   执行时间下四分位数：439.822498 纳秒 ( 2.5%)
   执行时间上四分位数：485.797378 纳秒 (97.5%)
                   使用的开销：1.845047 ns

在60个样本中发现了3个异常值（占5.0000%）
   低-严重     3 (5.0000%)
 异常值方差：20.6393% 异常值导致方差中等程度膨胀


所附补丁同时使用 Both transients 和 reduce

Answer 2

评论由：alexmiller发表

我认为所提方案很好。描述需要更好地反映所考虑和选择的内容。

Answer 3

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