函数文件夹和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 (of IReduce)。这样就绕过了函数 r/reduce 中的nil的特殊情况。

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

2. Patch 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 stubs。

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、数组和对象类型而使其他随机代码变慢。然而，我不确定我具体应该测试什么。

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

Answer 5

评论由：dnolen 发布

你的时间测试太多了，包括 {{vec}}，{{range}}，lazy sequences。也测试了小 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 发布

这仍然是一种不好的时间安排方式，你在记录范围和序列的代价。使用 {{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 的 bug：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？）

如上所述，alt补丁在精神上与Clojure源代码更为相似。而1号补丁（redux）在精神上与Clojure源代码更为相似。

alt补丁在语义上与原始Clojure源代码略有不同——但尚不清楚哪种行为是“正确”的。

Answer 14

评论由：dnolen 发布

如果基准测试解释了补丁前后性能的改变，那么它们将更有参考价值。

Answer 15

由：jdevuyst发表的评论

{{r/reduce}}之前无法用于nil或JavaScript数组。

我难以推荐一个补丁的一个原因是我不知道您希望针对哪个用例进行优化。