使用迭代器加速多集合的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，这将执行iterReduce在可迭代colls上，所以您可能可以通过简单地使用transducer形式获得相同的效果


(into [] (map f) c1)


除了这个表单只接受一个集合外，还支持transducers的多集合（参见TransformerIterator/createMulti），但在当前的apis中不是很明显。尽管如此，直接利用它似乎比上面的建议要好得多。


(定义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

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

Answer 3

评论者：alexmiller

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

Answer 4

评论者：aralo

我实际上对这个想法有更多的思考。我同意，正确的步骤是充分利用transducers并为多个集合提供更好的支持。

因此，我建议改变游戏计划为

1. 使{{into}}和{{transduce}}与多集合一起工作
2. 弃用{{MultiIterator}}。我们可以通过在{{TransformIterator}}的内联中进行此操作来获得更好的性能，从而避免在{{apply}}中创建“建立一个序列”后跟“展开刚创建的序列”的不必要步骤。

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

之后，我们可以为许多transducer提供在多个序列上操作并有效地与{{into}}和{{transduce}}一起使用的选项（如保留、过滤、索引映射、取、丢弃等）。

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

Answer 5

评论者：alexmiller

您正在从“提升现有函数的性能”转向API设计，这涉及到一系列更广泛的问题考虑。我认为我们不太可能扩展到多集合（multi-coll）领域，我也不认为有很多本就是多集合的转换器。因此，我认为您不应该扩大这个工单的范围，否则我将拒绝它。

Answer 6

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