使用迭代器加速多个集合中 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 是否 {{counted?}}

- 如果是：使用 {{MultiIterator}}
- 如果不是：像当前实现一样转发到 {{map}}

对此有什么想法吗？或者这会破坏某些内容？

Answer 1

_评论者：alexmiller_

迭代器默认应该是危险且不安全的 - 它们是可变的、有状态的、（可能）非线程安全对象。因此，其使用应小心审查，尤其是你不希望它们：a) 从局部化上下文中泄漏出去（因此应该积极遍历并释放）或 b) 被用于触发执行不纯净函数的方式，从而使得它们会在以后重新执行。序列缓存它们的实际实现（且是线程安全的），这使得它们速度较慢，但避免这种问题的安全性更高。

在这种情况下，你正在积极生成一个具体的集合（而不是懒序列），因此解决了第一个问题。然而，第二个问题则更难以推理。我认为可能没问题，但还需要更多思考。

请注意，into 使用 transduce，它使用 CollReduce，这将执行 Iterable colls 的 iterReduce，所以你可能可以使用 transducer 表达式来达到相同的效果


(into [] (map f) c1)


除了这个表单只包含一个coll之外，transformers也支持多个colls的支持（见TransformerIterator/createMulti），但在当前的api中表现不佳。不过，直接利用它可能比上面的建议好得多。


(defn mapv2 [f & cs]
  (let [iters (map #(.iterator %) cs)
        t (clojure.lang.TransformerIterator/createMulti (map f) iters)]
    (loop [out (transient [])]
      (if (.hasNext t)
        (recur (conj! out (.next t)))
        (persistent! out)))))


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

Answer 2

评论者：aralo

Alex：我实际上使用了这个非常具体的实现，但发现它比手动跟踪迭代器要慢得多。我的猜测是因为在TransformIterator的step函数中有一个{{xf.applyTo}}。在{{createMulti}}中创建它时，我们已经知道{{source.size()}}。因此，这个实现可能可以通过直接调用正确的arity来变得更聪明。
虽然，我没有对任何东西进行基准测试。所以现在只是猜测。

Answer 3

评论者：alexmiller

这看起来是合理的猜测，可以在TransformIterator中优化。

Answer 4

评论者：aralo

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

所以我会建议改变计划来

1. 让{{into}}和{{transduce}}支持多个集合
2. 扔掉{{MultiIterator}}。我们可以通过在{{TransformIterator}}内部内联来完成这项任务，这样可以避免在apply时“在MultiIterator中建立序列”和“展开刚刚创建的序列”这两个不必要的步骤。

不过，这会使TransformIterator变得很复杂。

然后，我们可以选择让许多transducers能够跨越多个序列（保持、过滤、map-indexed、取、丢弃等）并有效地使用它们与{{into}}和{{transduce}}。

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

Answer 5

评论者：alexmiller

您正在从“增强现有功能的功能性”转向进行 API 设计，这涉及许多更重要的考虑因素。我认为我们不太可能扩展到或转换到多集合领域，并且我认为没有多少转换器可以作为原生多集合有意义。因此，我认为您不应该扩大这个工单的范围，否则我将拒绝它。

Answer 6

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