使用迭代器加速对多个集合的mapv

Question

当前的mapv对于多个集合的执行如下


(into [] (map f c1 c2 c3))


我建议将其更改为


(let [it1 (clojure.lang.RT/iter c1)
      it2 (clojure.lang.RT/iter c2)]
     (loop [out (transient [])]
       (if (and (.hasNext it1) (.hasNext it2))
        (recur (conj! out (f (.next it1) (.next it2))))
        (persistent! out))))


这将使速度提高5倍。

对于可变参数的情况，我们可以检查colls是否是{{计数的?}}

- 如果是：使用{{多迭代器}}
- 如果不是：像当前实现一样转交给{{map}}

对此有何看法？或者这个更改会不会破坏某些内容？

Answer 1

评论由：alexmiller_作出

迭代器默认情况下应被视为危险和不安全的对象 - 它们是可变的、有状态的、（可能）非线程安全。因此，其使用应谨慎审查，特别是您不希望它们）a）从局部上下文泄露出来（因此它们应该被积极遍历并释放），或b）以触发不纯函数执行的方式使用，以至于它们稍后会重新执行。序列缓存其实现（并且是线程安全的），这使其速度较慢，但在避免此类问题方面更加安全。

在这种情况下，您正在积极地生成一个具体的收集（而不是一个惰性序列），因此第一个问题得到了解决。然而，第二个问题要难理解一些。我认为这可能可以，但需要更多地考虑这一点。

请注意，into使用了transduce，它使用了CollReduce，这将对所有可迭代的colls进行iterReduce，因此您可以简单使用transducer形式


(into [] (map f) c1)


然而，该形式仅接受单个coll。transducer存在多coll支持（请参阅TransformerIterator/createMulti），但在当前api中没有很好地体现。虽然直接利用它比上述建议更好


(defn mapv2 [f & cs]
  （exec (map #(.iterator %) cs)）
        保留 (clojure.lang.TransformerIterator/createMulti (map f) iters)
    循环 [输出 (transient [])
      （当 (.hasNext t)）
        重复 (conj! 输出 (.next t)))
        (persistent! 输出)))))


请注意，这假设了所有的 cs 都是可迭代的，这并不是一个有效的假设。例如：(mapv identity "abc")。因此，仍然需要在回退和性能测试方面做一些工作。

Answer 2

评论人： aralo

Alex: 实际上我确实使用了这个实现，但发现它的速度比手动跟踪迭代器要慢得多。我的猜测是因为 {{xf.applyTo}} 在 {{TransformIterator}} 的 {{step}} 函数中。当我们在 {{createMulti}} 中创建它时，我们已经知道 {{source.size()}}。因此，这个实现可能可以通过直接调用正确的arity变得更智能。
尽管如此，我还没有进行基准测试。所以现在只是一个猜测。

Answer 3

评论人： alexmiller

这似乎是一个合理的猜测，并且可以在 TransformIterator 中进行优化。

Answer 4

评论人： aralo

我实际上考虑了这个问题。我同意这里的正确步骤是充分利用 transducers，并为多个集合提供更好的支持。

因此，我建议改变计划为

1. 使 {{into}} 和 {{transduce}} 与多个集合一起工作
2. 扔掉 {{MultiIterator}}。我们可以通过在 {{TransformIterator}} 中内联完成这些操作来获得更好的性能，这样可以避免 "在 MultiIterator 中构建序列" 和 "在 apply 中展开这个刚创建的序列" 的不必要步骤。

尽管如此，这将使 TransformIterator 变得更加复杂。

之后，我们可以为许多 transducers 提供在多个序列上工作的选项（保留，过滤，map-indexed，取，弃等），并使用 {{into}} 和 {{transduce}} 高效地使用它们。

如果您同意，我可以更改标题以反映新的范围。

Answer 5

评论人： alexmiller

您正在从“现有函数的提升性能”转向进行 API 设计，这涉及到一系列更大的考虑因素。我认为我们不太可能扩展到或 transduce 到多集合领域，而且我认为没有很多 transducer 适合作为原生多集合。因此，我认为您不应该扩大此票据的范围，因为我会取消该票据。

Answer 6

参考： https://clojure.atlassian.net/browse/CLJ-2280（由aralo报告）