将 `satisfies?` 的执行速度提升至协议方法调用级别

Question

目前 `satisfies?` 不使用与协议方法相同的实现缓存，使其在实际应用中速度过慢。

使用

(defprotocol p (f [_]))
(deftype x [])
(deftype y [])
(extend-type x p (f [_]))


在补丁之前

(let [s "abc"] (bench (instance? CharSequence s))) ;; 执行时间平均值：1.358360 纳秒
(let [x (x.)] (bench (satisfies? p x))) ;; 执行时间平均值：112.649568 纳秒
(let [y (y.)] (bench (satisfies? p y))) ;; 执行时间平均值：2.605426 微秒


*原因：* `satisfies?` 调用 `find-protocol-impl` 来查看对象是否实现了协议，这需要检查 x 是否是协议接口的实例，或者 x 的类是否是协议的实现之一（或者如果它的继承链会导致这种情况），这个检查相当昂贵且没有缓存。

*提议：* 将协议的方法实现缓存扩展到处理（并缓存）实例检查（包括负结果）。

在补丁之后

(let [x (x.)] (bench (satisfies? p x))) ;; 执行时间平均值：79.321426 纳秒
(let [y (y.)] (bench (satisfies? p y))) ;; 执行时间平均值：77.410858 纳秒


*补丁：* CLJ-1814-v7.patch (依赖于 CLJ-2426)

Answer 1

评论者：michaelblume

这不错。在我们重构它们之前，Honeysql曾经花费 80-90% 的时间在 satisfies? 调用上。

Answer 2

评论者：michaelblume

我明白这确实是一个非常烦人的bug，难以重现。但是，如果我从核心match克隆，将其Clojure依赖指向1.8.0-master-SNAPSHOT，启动REPL，从vim连接到REPL，并重新加载clojure.core.match，我会得到以下结果：

`
|| java.lang.Exception: 命名空间 'clojure.tools.analyzer.jvm.utils' 未找到，编译：(clojure/tools/analyzer/jvm.clj:9:1)
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|5647| clojure.core$throw_if.invokeStatic
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|5733| clojure.core$load_lib.invokeStatic
|| clojure.core$load_lib.doInvoke(core.clj)
|| clojure.lang.RestFn.applyTo(RestFn.java:142)
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|647| clojure.core$apply.invokeStatic
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|5765| clojure.core$load_libs.invokeStatic
|| clojure.core$load_libs.doInvoke(core.clj)
|| clojure.lang.RestFn.applyTo(RestFn.java:137)
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|647| clojure.core$apply.invokeStatic
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|5787| clojure.core$require.invokeStatic
|| clojure.core$require.doInvoke(core.clj)
|| clojure.lang.RestFn.invoke(RestFn.java:703)
zipfile:/Users/michael.blume/.m2/repository/org/clojure/tools.analyzer.jvm/0.6.5/tools.analyzer.jvm-0.6.5.jar::clojure/tools/analyzer/jvm.clj|9| clojure.tools.analyzer.jvm$eval4968$loading5561auto__4969.invoke
zipfile:/Users/michael.blume/.m2/repository/org/clojure/tools.analyzer.jvm/0.6.5/tools.analyzer.jvm-0.6.5.jar::clojure/tools/analyzer/jvm.clj|9| clojure.tools.analyzer.jvm$eval4968.invokeStatic
|| clojure.tools.analyzer.jvm$eval4968.invoke(jvm.clj)
|| clojure.lang.Compiler.eval(Compiler.java:6934)
|| clojure.lang.Compiler.eval(Compiler.java:6923)
|| clojure.lang.Compiler.load(Compiler.java:7381)
|| clojure.lang.RT.loadResourceScript(RT.java:372)
|| clojure.lang.RT.loadResourceScript(RT.java:363)
|| clojure.lang.RT.load(RT.java:453)
|| clojure.lang.RT.load(RT.java:419)
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|5883| clojure.core$load$fnstrong>5669.invoke
zipfile:/Users/michael.blume/.m2/repository(org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|5882| clojure.core$load.invokeStatic
zipfile:/Users/michael.blume/.m2/repository(org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|5683| clojure.core$load_one.invokeStatic
|| clojure.core$load_one.invoke(core.clj)
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|5883| clojure.core$load$fn5669.invoke
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|5882| clojure.core$load.invokeStatic
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|5683| clojure.core$load_one.invokeStatic
|| clojure.core$load_one.invoke(core.clj)
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|5728| clojure.core$load_lib$fn5618.invoke
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|5727| clojure.core$load_lib.invokeStatic
|| clojure.core$load_lib.doInvoke(core.clj)
|| clojure.lang.RestFn.applyTo(RestFn.java:142)
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|647| clojure.core$apply.invokeStatic
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|5765| clojure.core$load_libs.invokeStatic
|| clojure.core$load_libs.doInvoke(core.clj)
|| clojure.lang.RestFn.applyTo(RestFn.java:137)
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|647| clojure.core$apply.invokeStatic
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|5787| clojure.core$require.invokeStatic
|| clojure.core$require.doInvoke(core.clj)
|| clojure.lang.RestFn.invoke(RestFn.java:421)
|| clojure.core.match$eval4949.invokeStatic(form-init2494799382238714928.clj:1)
|| clojure.core.match$eval4949.invoke(form-init2494799382238714928.clj)
|| clojure.lang.Compiler.eval(Compiler.java:6934)
|| clojure.lang.Compiler.eval(Compiler.java:6897)
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|3096| clojure.core$eval.invokeStatic
|| clojure.core$eval.invoke(core.clj)
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/main.clj|240| clojure.main$repl$read_eval_print7404$fn7407.invoke
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/main.clj|240| clojure.main$repl$read_eval_print7404.invoke
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/main.clj|258| clojure.main$repl$fn7413.invoke
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/main.clj|258| clojure.main$repl.invokeStatic
|| clojure.main$repl.doInvoke(main.clj)
|| clojure.lang.RestFn.invoke(RestFn.java:1523)
zipfile:/Users/michael.blume/.m2/repository/org/clojure/tools.nrepl/0.2.10/tools.nrepl-0.2.10.jar::clojure/tools/nrepl/middleware/interruptible_eval.clj|58| clojure.tools.nrepl.middleware.interruptible_eval$evaluate$fn637.invoke
|| clojure.lang.AFn.applyToHelper(AFn.java:152)
|| clojure.lang.AFn.applyTo(AFn.java:144)
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|645| clojure.core$apply.invokeStatic
zipfile:/Users/michael.blume/.m2/repository/org/clojure/clojure/1.8.0-master-SNAPSHOT/clojure-1.8.0-master-SNAPSHOT.jar::clojure/core.clj|1874| clojure.core$with_bindingsSTAR.invokeStatic
|| clojure.core$with_bindingsSTAR.doInvoke(core.clj)
|| clojure.lang.RestFn.invoke(RestFn.java:425)
zipfile:/Users/michael.blume/.m2/repository/org/clojure/tools.nrepl/0.2.10/tools.nrepl-0.2.10.jar::clojure/tools/nrepl/middleware/interruptible_eval.clj|56| clojure.tools.nrepl.middleware.interruptible_eval$evaluate.invokeStatic
|| clojure.tools.nrepl.middleware.interruptible_eval$evaluate.invoke(interruptible_eval.clj)
zipfile:/Users/michael.blume/.m2/repository/org/clojure/tools.nrepl/0.2.10/tools.nrepl-0.2.10.jar::clojure/tools/nrepl/middleware/interruptible_eval.clj|191| clojure.tools.nrepl.middleware.interruptible_eval$interruptible_eval$fn679$fn__682.invoke
zipfile:/Users/michael.blume/.m2/repository/org/clojure/tools.nrepl/0.2.10/tools.nrepl-0.2.10.jar::clojure/tools/nrepl/middleware/interruptible_eval.clj|159| clojure.tools.nrepl.middleware.interruptible_eval$run_next$fn__674.invoke
|| clojure.lang.AFn.run(AFn.java:22)
|| java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
|| java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
|| java.lang.Thread.run(Thread.java:745)

`

在我的项目中，同样在依赖clojure.core.match后重新加载命名空间时会遇到相同的问题

Answer 3

评论由：bronsa

AOT是否与之有关？

Answer 4

评论者：michaelblume

缩小了一点点，如果你查看tools.analyzer.jvm，打开一个REPL，然后执行(require 'clojure.tools.analyzer.jvm.utils)，我将得到

我看不出AOT在哪里会涉及？

Answer 5

评论由：bronsa

(链接：~michaelblume) 更新的补丁应该可以修复你报告的问题。

Answer 6

评论者：michaelblume

太好了，谢谢 =)

新补丁不再删除未使用的方法实现缓存（MethodImplCache），这是故意的吗？

Answer 7

由：alexmiller发表的评论

如果在描述中有一个变更内容的列表将会很棒。例如：“将MethodImplCache重命名为ImplCache”，这有助于更容易地审查。

Answer 8

评论由：bronsa

附上了一个更新的补丁，该补丁不将MethodImplCache替换为ImplCache，而是简单地重用MethodImplCache，减少此补丁的影响，使其更容易（且更安全）地进行审查。

Answer 9

_由：alexmiller发表的评论_

由于它在新的 {{inst?}} 断言中使用- 请参阅 https://github.com/clojure/clojure/commit/58227c5de080110cb2ce5bc9f987d995a911b13e

Answer 10

_由：alexmiller发表的评论_

我使用v3补丁运行了前后测试。测试前的结果相当接近，但我无法复制测试后的结果。我得到了如下结果，实际上在未找到的情况下更糟：


(let [x (x.)] (bench (satisfies? p x))) ;; 执行时间平均值：76.833504 ns
（let [y (y.)] (bench (satisfies? p y))) ;; 执行时间均值: 20.570007 微秒

Answer 11

评论由：bronsa_ 提出

v4 补丁修复了找不到的情况的回归，不确定是怎么回事，对此表示歉意。
以下是现在的计时结果

clojure master

user=> (let [x (x.)] (bench (satisfies? p x)))
评估次数：604961580 次在 60 个样本中平均 10082693 次调用。
             执行时间均值：112.649568 纳秒
    执行时间标准偏差：12.216782 纳秒
   执行时间下四分位数：99.299203 纳秒 ( 2.5%)
   执行时间上四分位数：144.265205 纳秒 (97.5%)
               使用的开销：1.898271 纳秒

在 60 个样本中发现了 3 个异常值（5.0000 %）
    低-严重      2 (3.3333 %)
    低-轻微      1 (1.6667 %)
 异常值方差：73.7545 % 方差因异常值而严重膨胀
nil




user=> (let [y (y.)] (bench (satisfies? p y)))
评估次数：22676100 次在 60 个样本中平均 377935 次调用。
             执行时间均值：2.605426 微秒
    执行时间标准偏差：141.100070 纳秒
   执行时间下四分位数：2.487234 微秒 ( 2.5%)
   执行时间上四分位数：2.873045 微秒 (97.5%)
               使用的开销：1.898271 纳秒

在 60 个样本中发现了 1 个异常值（1.6667 %）
    低-严重      1 (1.6667 %)
 异常值方差：40.1251 % 方差因异常值而适度膨胀
nil



master + v4

user=> (let [x (x.)] (bench (satisfies? p x)))
评估次数：731759100 次在 60 个样本中平均 12195985 次调用。
             执行时间均值：79.321426 纳秒
    执行时间标准偏差：3.959245 纳秒
   执行时间下四分位数：75.365187 纳秒 ( 2.5%)
   执行时间上四分位数：87.986479 纳秒 (97.5%)
                  使用的开销：1.905711 纳秒

在 60 个样本中发现了 1 个异常值（1.6667 %）
    低-严重      1 (1.6667 %)
 异常值方差：35.2614 % 方差因异常值而适度膨胀
nil



user=> (let [y (y.)] (bench (satisfies? p y)))
评估次数：771220140 次在 60 个样本中平均 12853669 次调用。
             执行时间均值：77.410858 纳秒
    执行时间标准偏差：1.407926 纳秒
   执行时间下四分位数：75.852530 纳秒 ( 2.5%)
   执行时间上四分位数：80.759226 纳秒 (97.5%)
                  使用的开销：1.897646 纳秒

在 60 个样本中发现了 4 个异常值（6.6667 %）
    低-严重      3 (5.0000 %)
    低-轻微      1 (1.6667 %)
 异常值方差：7.7866 % 方差因异常值而略膨胀


所以总结一下
master 发现结果 = 112 纳秒
master 无法找到 = 2.6 微秒

master+v4 发现结果 = 79 纳秒
master+v4 无法找到 = 77 纳秒

Answer 12

评论者：michaelblume

对于已经宣布实现特定协议的记录，并且因此实现了相应接口的情况，是否使用对其接口的实例检查作为一个快速路径是有意义的呢？

Answer 13

由：alexmiller发表的评论

Michael - 那个检查已经在里面了

Nicola - 我有一些评论/问题

1. 我不理解NIL东西的用途 - 你能解释一下吗？
2. 在x是接口的实例的情况下，旧代码返回x，而find-protocol-impl*中新的代码返回接口。为什么会有这种变化？
3. 这个：`(alter-var-root (:var protocol) assoc :impl-cache (expand-method-impl-cache cache c impl))` 在我所知的情况下不是线程安全的 - 我认为两个不同线程对于不同impl的同时错过会导致缓存中只包含其中一个。这可能不太可能，可能不是一个大问题，因为缓存将只会在下一个调用中更新（不会给出错误答案），但我想提一下。我觉得没有简单的方法可以避免这一点，除非做出很多改变。

Answer 14

评论由：bronsa

Alex，谢谢你查看这个
1- NIL对象是方法实现缓存中nil的一个占位符，因为find-and-cache-protocol-impl测试nil?以确定是否已经缓存了分派

2- 这种变化纯粹是为了保持一致性，使得find-and-cache-protocol-impl总是返回一个类/接口，而不是类/接口或具体的实例。从行为上讲，它没有改变任何东西，因为find-protocol-impl的两个消费者，即find-protocol-method和，在这种情况下并不关心该值是什么

3- 是的，你是对的，它不是线程安全的，但我认为这是一个合理的权衡，因为它不会引起任何错误行为，最坏的情况是会引起额外的缓存错过。要使其线程安全，将会在每个缓存命中/错失中带来额外的性能损失

Answer 15

评论者：michaelblume

(链接：~bronsa) 我看到这个补丁导致的行为变化

`
(defprotocol BoolProtocol
(proto-fn [this]))

(extend-protocol BoolProtocol
Object
(proto-fn [x] "Object impl")

nil
(proto-fn [x] "Nil impl"))

(proto-fn false)
`

使用Clojure master返回"Object impl"，而使用这个补丁返回"Nil impl"