为什么在这个例子中使用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"

谁能告诉我一个显着加速的例子？

我在Intel Core i7上使用Java 1.7在Mac OSX 10.7.5上运行(2核,http://ark.intel.com/products/54617).

Answer 1

你打电话给它pfrequencies,它与parallel-processing问题上的标签一起表明你认为某些东西在这里使用了多个线程.情况并非如此,也不是减速器库的"主要"目标.

减速器给你买的主要是你不需要为懒惰序列分配许多中间缺陷单元.在引入Reducer之前,frequencies将分配10000000个cons单元以创建reduce要使用的向量的顺序视图.现在减速器存在,矢量知道如何在不创建这样的临时对象的情况下减少自己.但是这个功能已被反向移植clojure.core/reduce,其行为完全相同r/reduce(忽略了一些与此无关的小功能).因此,您只需将您的函数与其自身的相同克隆进行基准测试.

reducers库还包括a的概念fold,它可以并行执行某些工作,然后将中间结果合并在一起.要使用它,您需要提供比reduce需要更多的信息:您必须定义如何从零开始"块"; 你的功能必须是联想的; 并且您必须指定如何组合块.答:Webb的答案演示了如何fold正确使用,以便在多个线程上完成工作.

但是,你不可能从折叠中获得任何好处:除了他注意到的原因(你放弃了瞬态,相比之下clojure.core/frequencies),构建地图并不容易并行化.如果大部分工作frequencies都是添加的(就像它的类似(frequencies (repeat 1e6 1))),那么fold会有所帮助; 但大多数工作都是在管理hashmap中的键,最终必须是单线程.您可以并行构建地图,但是您必须将它们合并在一起; 因为该组合步骤需要与块的大小成比例的时间,而不是恒定的时间,所以无论如何通过在单独的线程上执行块来获得很少.

Answer 2

一个fold你的频率函数的版本看起来是这样的

(defn pfrequencies [coll] 
  (r/fold 
    (fn combinef
      ([] {})
      ([x y] (merge-with + x y)))
    (fn reducef
      ([counts x] (merge-with + counts {x 1})))
    coll))

在2个核心上,它可能比clojure.core/frequencies使用瞬变的速度慢得多.至少在4个内核上,它比第一个实现更快(2x),但仍然比clojure.core/frequencies.

你也可以尝试一下

(defn p2frequencies [coll]
  (apply merge-with + (pmap clojure.core/frequencies (partition-all 512 coll))))