函数文件夹和reducer对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 创建的reducers直接调用 -reduce（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、数组、对象目前）被视为特殊情况，那么{{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、数组和对象类型而减慢其他随机代码，但我不知道我应该测试什么。

（请注意，第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 +)))))


我得到的一些最后结果是

第一个补丁：75680毫秒
第二个补丁：76585毫秒

老实说，尽管第一个补丁大多数时候似乎占上风，但有时第二个补丁更快。

我还试过另一件事，就是在第二个补丁中删除了 {{implements?}}/{{satisfies?}} 检查，并覆盖了类型 {{object}} 的协议方法 coll-fold，而不是像第一个补丁那样（就像第一个补丁）。这种“混合”方法通常（但不总是）导致减速。

我不确定我应该如何进行。也许我应该同时运行这两个补丁几分钟？

Answer 7

评论为：dnolen

这仍然是进行计时的一个糟糕方式，你记录了范围和 seq'ing 的成本。请使用 {{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 msecs
补丁 2: 210756 msecs

对于数组

`
(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 msecs
补丁 2: 119704 msecs

我进行了几次测试，结果相当一致。对于向量，补丁 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}"}-framework}}。

然后我在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数组。

我难以推荐一个补丁的原因之一是我不清楚你想针对哪个用例进行优化。