clojure - 为什么在此示例中使用 reducer 没有显着加速？

Question

(require '[clojure.core.reducers :as r])

(def data (into [] (take 10000000 (repeatedly #(rand-int 1000)))))

(defn frequencies [coll]
  (reduce (fn [counts x]
    (merge-with + counts {x 1}))
    {} coll))

(defn pfrequencies [coll]
  (r/reduce (fn [counts x]
    (merge-with + counts {x 1}))
    {} coll))


user=> (time (do (frequencies data) nil))
"Elapsed time: 29697.183 msecs"

user=> (time (do (pfrequencies data) nil))
"Elapsed time: 25273.794 msecs"

user=> (time (do (frequencies data) nil))
"Elapsed time: 25384.086 msecs"

user=> (time (do (pfrequencies data) nil))
"Elapsed time: 25778.502 msecs"

谁可以向我展示一个显着加速的示例？

我正在 Mac OSX 10.7.5 上运行，并在 Intel Core i7(2 核， http://ark.intel.com/products/54617 )上运行 Java 1.7。

Answer 1

您将其命名为pfrequencies，它与问题上的parallel-processing 标记一起表明您认为这里有些东西正在使用多个线程。事实并非如此，也不是 reducer 库的“主要”目标。

reducer 为您带来的主要好处是您不需要为惰性序列分配许多中间 cons 单元。在引入归约器之前，频率将分配 10000000 个 cons 单元来创建向量的顺序 View 以供归约器使用。既然 reducer 已经存在，向量就知道如何在不创建此类临时对象的情况下减少自身。但该功能已向后移植到 clojure.core/reduce 中，其行为与 r/reduce 完全相同(忽略一些此处不相关的小功能)。因此，您只是将您的函数与自身的相同克隆进行基准测试。

reducers 库还包含 fold 的概念，它可以并行执行一些工作，然后将中间结果合并在一起。要使用它，您需要提供比 reduce 需要更多的信息:您必须定义如何从无到有开始一个“ block ”；你的函数必须是关联的；并且您必须指定如何组合 block 。 A. Webb's answer演示如何正确使用 fold 在多个线程上完成工作。

但是，您不太可能从折叠中获得任何好处:除了他指出的原因(与 clojure.core/frequencies 相比，您放弃 transient )之外，构建 map 也不是易于并行化。如果频率中的大部分工作是加法(就像(frequencies (repeat 1e6 1))这样的东西)，那么折叠 会有所帮助；但大部分工作是管理 HashMap 中的键，这最终必须是单线程的。你可以并行构建 map ，但随后你必须将它们合并在一起；由于该组合步骤所花费的时间与 block 的大小成正比，而不是恒定的时间，因此无论如何在单独的线程上执行 block 都不会获得什么好处。