函数文件夹和还原器对nil和数组类型出错 + 错别字修复

Question

1. 目前这不起作用

(->> nil

 (r/map identity)
 (r/reduce + 0))
 ; org.mozilla.javascript.JavaScriptException: Error: No protocol method IReduce.-reduce defined for type null

之所以这样，是因为由r/reducer或r/folder创建的还原器直接调用-reduce (of IReduce)。因此它们绕过了函数r/reduce中对nil的特殊情况。

1. 对于类型为数组的集合也存在完全类似的问题。

2. 补丁CLJS-700错误地将coll-fold定义为数组类型cljs.core/IPersistentVector。这应该是cljs.core/PersistentVector。（在ClojureScript中不存在协议IPersistentVector。）

我将很快附上一个补丁，该补丁通过实现nil和数组的IReduce来解决上述所有问题。这个补丁还包括单元测试。

Answer 1

评论由 jdevuyst 提出

一个替代补丁，其中r/reduce和r/fold将数组和nil作为特殊情况处理 -- 与数组和nil实现IReduce和CollFold相反。

r/reducer，r/folder和r/Cat的协议方法的函数现在调用r/reduce和r/fold，而不是直接调用-reduce和coll-fold。

这个补丁还修复了Cat中coll-fold实现的错误，该错误之前使用了(reducef)作为初始值而不是(combinef)。新代码是从Clojure实现复制粘贴的，并使用了fork-join存根。

Answer 2

评论由 dnolen 提出

在第二个补丁中，`{{implements?}}` 可能应该改为 `{{satisfies?}}`。你在补丁之前/之后运行过任何基准测试吗？

Answer 3

_评论由：jdevuyst_ 发布

如果我的理解正确，那么 {{(satisfies? x y)}} 大约等同于 {{(or (implements? x y) (natively-satisfies? x y))}}。

如果原生类型（nil、array、object目前）被视为特殊情况，那么 {{implements?}} 似乎更合适。

{{satisfies?}} 也可以工作，因此我附上了一个新的 'alt' 补丁。

Answer 4

评论由 jdevuyst 提出

第一个补丁实际上在运行以下代码时更快

(time (->> (repeat 1000 (vec (range 1000)))
           vec
           (r/mapcat identity)
           (r/map inc)
           (r/filter even?)
           (r/fold +)))

这需要约700毫秒。使用第一个补丁，它将终止100-300毫秒更快。这是经过重复（但非正式）测试后的结果。

我认为担心的是第一个补丁可能会因为扩展nil、array和object类型而减慢其他随机代码。但我也不太清楚我应该测试什么。

(注意，第2和第3个补丁也包含了{{Cat}}的修复，并包括了更多的单元测试。最好是不要直接应用第一个补丁。)

Answer 5

评论由：dnolen 发布

你的计时太多，包括{{vec}}、{{range}}、懒序列。还要测试小N。看看Mori README上的reducers示例 - https://github.com/swannodette/mori。谢谢。

Answer 6

_评论由：jdevuyst_ 发布

我尝试运行以下代码


(let [coll (vec (repeat 1000 (vec (range 10))))]
  (time (doseq [n (range 1000)]
               (->> coll
                    (r/mapcat identity)
                    (r/map inc)
                    (r/filter even?)
                    (r/fold +)))))


我得到的一些最后结果是

1st patch: 75680 msecs
2nd patch: 76585 msecs

老实说，虽然第一个补丁似乎大部分时候都赢了，但有时第二个补丁更快。

我还尝试了一件事，就是在第二个补丁中移除{{implements?}}/{{satisfies?}}检查，并覆盖类型{{object}}的协议方法coll-fold，而不是像第一个补丁那样（如第一个补丁中所述）。这种"混合"方法通常（但不总是）似乎会导致速度降低。

我不知道我应该怎么进行。或许我应该同时运行这两个补丁几分钟？

Answer 7

评论由：dnolen 发布

这仍然是一种做时间测量的糟糕方法，你记录了范围和seq的成本。使用{{dotimes}}。

Answer 8

评论由 jdevuyst 提出

嗯。我想懒序列确实导致了很多分配。

好吧，我重写了测试并运行了几次。现在我还在向量和数组上进行了测试。

补丁1需要轻微调整。当调用coll-fold时，补丁1只指定了类型{{object}}的回退（即调用r/reduce）。我必须为类型{{array}}添加相同的回退。（这很奇怪！）

所以这里是结果。

对于向量

`
(let [coll (vec (repeat 100 (vec (range 100))))]
(time (dotimes [n 3000]

      (->> coll
          (r/mapcat identity)
          (r/map inc)
          (r/filter even?)
          (r/fold +)))))

`

补丁1：205872毫秒
补丁2：210756毫秒

对于数组

`
(let [coll (into-array (repeat 100 (into-array (range 100))))]
(time (dotimes [n 3000]

      (->> coll
          (r/mapcat identity)
          (r/map inc)
          (r/filter even?)
          (r/fold +)))))

`

补丁1：123567毫秒
补丁2：119704毫秒

我运行了多次测试，结果相当一致。补丁1对向量更快，而补丁2对数组更快。

这很合理。

在补丁1中，{{reducer}}将直接调用{{-reduce}}。在补丁2中，{{reducer}}首先调用{{r/reduce}}，它根据集合是否为向量调用{{-reduce}}，如果是数组则调用{{array-reduce}}。因此，在向量的情况下，补丁2包含额外的函数调用，但在数组的情况下避免了在原生类型上调用协议方法。

使用宏（或复制粘贴）可以避免额外的函数调用。这样做值得尝试吗，或者说保持代码清洁更重要？

--

我刚刚意识到补丁2在语义上与Clojure略有不同，尽管这可能是一个Clojure的错误：https://groups.google.com/forum/#!searchin/clojure-dev/kv-reduce/clojure-dev/bEqECvbExGo/iW4B2vEUh8sJ。我建议使用宏（或复制粘贴）以避免补丁2中的额外函数调用，这也可能修复这种差异。

Answer 9

评论由：dnolen 发布

你是如何进行基准测试的？使用V8？JavaScriptCore？SpiderMonkey？在浏览器中？使用优化设置等。

Answer 10

评论由 jdevuyst 提出

我使用了 repljs（Rhino？）。我将在明天在一个更现实的环境中再次测试。

Answer 11

评论由：dnolen 发布

是的，用 Rhino 做基准测试并不具有信息性。

Answer 12

评论由 jdevuyst 提出

我用 {{cljs}} 编译了相同的代码（n=3000）。使用了 {{"{:optimizations :advanced}"}}。

然后我在 Firefox、Chrome 和 Safari 的最新稳定版本中进行测试。我关闭了所有浏览器。对于每个浏览器，我采取了以下步骤

• 打开浏览器
• 打开开发者控制台
• 运行补丁 1 的基准测试
• 运行补丁 2 的基准测试
• 运行补丁 1 的基准测试并记录结果
• 运行补丁 2 的基准测试并记录结果
• 关闭浏览器

Firefox
- 补丁 1。向量：26057 毫秒
- 补丁 1。数组：25026 毫秒
- 补丁 2。向量：26258 毫秒
- 补丁 2。数组：36653 毫秒
- 总结：补丁 1 对于向量和数组更快

Chrome
- 补丁 1。向量：7804 毫秒
- 补丁 1。数组：7092 毫秒
- 补丁 2。向量：7754 毫秒
- 补丁 2。数组：6768 毫秒
- 总结：补丁 2 对于向量和数组更快

Safari
- 补丁 1。向量：167230 毫秒
- 补丁 1。数组：108780 毫秒
- 补丁 2。向量：173940 毫秒
- 补丁 2。数组：110012 毫秒
- 总结：补丁 1 对于向量和数组更快

我对这个结果感到不确定。

Answer 13

评论由 jdevuyst 提出

我附上了第一个补丁的新版本。

这个补丁修复了 {{r/Cat}} 的问题。（这个问题也在第二和第三个补丁中得到了解决。包含单元测试。）

这个补丁还修复了数组对于 {{r/fold}} 的问题。

总结来说，需要在以下补丁之间做出选择。

• CLJS-736-patch-1-redux.patch
• CLJS-736-alt.patch（使用 implements？）/ CLJS-alt-satisfies.patch（使用 satisfies？）

实现细节是 patch-1-redux 在精神上与 Clojure 源代码更相似。alt 补丁在精神上与 ClojureScript 源代码更相似。

如上所述，alt 补丁在语义上与原始 Clojure 源代码略有不同——但不确定哪种行为是“正确”的。

Answer 14

评论由：dnolen 发布

如果基准测试能够解释在修补程序前后性能的变化，它们将更有信息量。

Answer 15

评论由 jdevuyst 提出

{{r/reduce}}之前对nil或JavaScript数组不起作用。

我难以推荐一个补丁的原因之一是，我不知道你希望优化哪个用例。