この例では、減速機を使用した場合のスピードアップはなぜですか？

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（2コア、http://ark.intel.com/products/54617）でJava 1.7のMac OSX 10.7.5で動作しています。

Answer 1

で

あなたも試してみるかもしれません。それはそうではなく、どちらも減速器ライブラリの「主な」目標ではありません。

レデューサーが購入する主なものは、レイジーシーケンスに多くの中間コンスセルを割り当てる必要がないということです。レデューサーが導入される前に、frequenciesは、reduceが使用するベクターのシーケンシャルビューを作成するためにコンスセル10000000を割り当てます。レデューサーが存在するようになると、ベクターはそのような一時的なオブジェクトを作成せずに自分自身を縮小する方法を知っていますしかし、その機能はclojure.core/reduceにバックポートされています。これはちょうどr/reduceのように動作します（ここでは無関係ないくつかの小さな機能は無視されています）。したがって、あなたは自分自身の同一のクローンに対して機能をベンチマークしているだけです。

還元剤ライブラリには、並行して何らかの作業を行うことができるfoldという概念も含まれています。その後、後で中間結果を結合します。これを使用するには、reduceよりも多くの情報を提供する必要があります。何もないから「チャンク」を開始する方法を定義する必要があります。あなたの機能は結合的でなければなりません。チャンクを結合する方法を指定する必要があります。 A. Webb's answerは、foldを正しく使用して、複数のスレッドで作業を行う方法を示しています。

しかし、フォールディングの利点を得ることはまずありません。その理由に加えて（clojure.core/frequenciesと比較してトランジェントをあきらめます）、マップの構築は簡単には行えません。 frequenciesの作業の大半が（例えば(frequencies (repeat 1e6 1))のようなものになるため）追加された場合、foldが役に立ちます。ほとんどの作業はハッシュマップのキーを管理することになります。ハッシュマップは最終的には最終的にはシングルスレッド化されなければなりません。並列にマップを構築することはできますが、マップをマージする必要があります。その組み合わせのステップは一定の時間ではなく、チャンクのサイズに比例した時間を必要とするため、別のスレッドでチャンクを行うことで少しでも得ることができます。

Answer 2

ご周波数機能のfoldバージョンは2つのコアで

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

ようになり、それは可能性が高いトランジェントを使用していますclojure.core/frequenciesよりもはるかに遅くなります。少なくとも4つのコアでは、最初の実装よりも高速です（2倍）が、さらに遅いのはclojure.core/frequenciesです。あなたは質問にあなたのparallel-processingタグと一緒に、あなたは何かがここに複数のスレッドを使用していることを考える示唆している、それpfrequencies呼ば

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

Answer 3

答えの中には深刻な食べ物がいくつか考えられます。この特定のケースでは、結果ドメインが容易に予測され、インデックスが使用できるベクトルに置かれるため、マップは必要ありません。だから、ナイーブな問題の素朴な実装はのようになります。

ここ

(defn freqs 
    [coll] 
    (reduce (fn [counts x] (assoc counts x (inc (get counts x)))) 
      (vec (int-array 1000 0)) 
      coll)) 

(defn rfreqs 
    [coll] 
    (r/fold 
     (fn combinef 
     ([] (vec (int-array 1000 0))) 
     ([& cols] (apply mapv + cols))) 
     (fn reducef 
     [counts x] (assoc counts x (inc (get counts x)))) 
     coll)) 

combinefはごくわずかであるべき、結果のコレクションの1000の列の上に簡単なマップの追加になります。

これは、通常のバージョンよりも約2〜3倍、特に大きな（10x-100x）データセットで、レデューサーのバージョンを高速化します。 r/foldのパーティションサイズ（オプションの「n」パラメータ）を持ついくつかの厄介な行為は、微調整として行うことができます。データサイズが1E8（最低でも6GBのJVMが必要）で使用するのに最適（* 16 1024）と思われます。

両方のバージョンでトランジェントを使用することもできますが、改善はほとんど見られませんでした。

このバージョンは一般的な使用には適していませんが、ハッシュ管理のオーバーヘッドがなくても速度の向上が見られるかもしれません。