2016-08-21 28 views
2

我嘗試儘可能快地使Clojure中的複數數組相乘。如何在clojure數組處理中擺脫clojure/lang/RT.aset和clojure/lang/RT.intCast?

所選的數據結構是兩個元素:re:im的映射,每個元素都是用於低內存開銷的基本原型double的Java本機陣列。

根據http://clojure.org/reference/java_interop我使用了原型類型數組的精確類型規範。

隨着這些提示aget被轉換成天然陣列dload運算,但有兩個低效率,完全循環的計數器不intlong,所以每次使用呼叫的陣列索引的計數器被轉換的時間來intclojure/lang/RT.intCast。並且aset也不會轉換爲本地操作,但會調用至clojure/lang/RT.aset

另一個低效率是checkcast。它檢查數組實際上是雙精度數組的每一個循環。

結果是此Clojure代碼的運行時間比等效Java代碼(不包括啓動時間)的運行時間多30%。這個函數可以在Clojure中被重寫,這樣它的工作更快嗎?

Clojure代碼,優化的功能是multiply-complex-arrays

(def size 65536) 

(defn get-zero-complex-array 
    [] 
    {:re (double-array size) 
    :im (double-array size)}) 

(defn multiply-complex-arrays 
    [a b] 
    (let [ 
     a-re-array (doubles (get a :re)) 
     a-im-array (doubles (get a :im)) 
     b-re-array (doubles (get b :re)) 
     b-im-array (doubles (get b :im)) 
     res-re-array (double-array size) 
     res-im-array (double-array size) 
     ] 
     (loop [i (int 0) size (int size)] 
      (if (< i size) 
       (let [ 
        a-re (aget a-re-array i) 
        a-im (aget a-im-array i) 
        b-re (aget b-re-array i) 
        b-im (aget b-im-array i) 
        ] 
        (aset res-re-array i (- (* a-re b-re) (* a-im b-im))) 
        (aset res-im-array i (+ (* a-re b-im) (* b-re a-im))) 
        (recur (unchecked-inc i) size)) 
       {:re res-re-array :im res-im-array})))) 

(let [ 
    res (loop [i (int 0) a (get-zero-complex-array)] 
      (if (< i 30000) 
       (recur (inc i) (multiply-complex-arrays a a)) 
       a)) 
    ] 
    (println (aget (get res :re) 0))) 

multiply-complex-arrays主循環生成的Java組件是

91: lload   8 
    93: lload   10 
    95: lcmp 
    96: ifge   216 
    99: aload_2 
100: checkcast  #51     // class "[D" 
103: lload   8 
105: invokestatic #46     // Method clojure/lang/RT.intCast:(J)I 
108: daload 
109: dstore  12 
111: aload_3 
112: checkcast  #51     // class "[D" 
115: lload   8 
117: invokestatic #46     // Method clojure/lang/RT.intCast:(J)I 
120: daload 
121: dstore  14 
123: aload   4 
125: checkcast  #51     // class "[D" 
128: lload   8 
130: invokestatic #46     // Method clojure/lang/RT.intCast:(J)I 
133: daload 
134: dstore  16 
136: aload   5 
138: checkcast  #51     // class "[D" 
141: lload   8 
143: invokestatic #46     // Method clojure/lang/RT.intCast:(J)I 
146: daload 
147: dstore  18 
149: aload   6 
151: checkcast  #51     // class "[D" 
154: lload   8 
156: invokestatic #46     // Method clojure/lang/RT.intCast:(J)I 
159: dload   12 
161: dload   16 
163: dmul 
164: dload   14 
166: dload   18 
168: dmul 
169: dsub 
170: invokestatic #55     // Method clojure/lang/RT.aset:([DID)D 
173: pop2 
174: aload   7 
176: checkcast  #51     // class "[D" 
179: lload   8 
181: invokestatic #46     // Method clojure/lang/RT.intCast:(J)I 
184: dload   12 
186: dload   18 
188: dmul 
189: dload   16 
191: dload   14 
193: dmul 
194: dadd 
195: invokestatic #55     // Method clojure/lang/RT.aset:([DID)D 
198: pop2 
199: lload   8 
201: lconst_1 
202: ladd 
203: lload   10 
205: lstore  10 
207: lstore  8 
209: goto   91 

Java代碼:

class ComplexArray { 

    static final int SIZE = 1 << 16; 

    double re[]; 

    double im[]; 

    ComplexArray(double re[], double im[]) { 
     this.re = re; 
     this.im = im; 
    } 

    static ComplexArray getZero() { 
     return new ComplexArray(new double[SIZE], new double[SIZE]); 
    } 

    ComplexArray multiply(ComplexArray second) { 
     double resultRe[] = new double[SIZE]; 
     double resultIm[] = new double[SIZE]; 
     for (int i = 0; i < SIZE; i++) { 
      double aRe = this.re[i]; 
      double aIm = this.im[i]; 
      double bRe = second.re[i]; 
      double bIm = second.im[i]; 
      resultRe[i] = aRe * bRe - aIm * bIm; 
      resultIm[i] = aRe * bIm + bRe * aIm; 
     } 
     return new ComplexArray(resultRe, resultIm); 
    } 

    public static void main(String args[]) { 
     ComplexArray a = getZero(); 
     for (int i = 0; i < 30000; i++) { 
      a = a.multiply(a); 
     } 
     System.out.println(a.re[0]); 
    } 
} 

大會Java代碼相同的循環的:

13: iload   4 
    15: ldc   #5     // int 65536 
    17: if_icmpge  92 
    20: aload_0 
    21: getfield  #2     // Field re:[D 
    24: iload   4 
    26: daload 
    27: dstore  5 
    29: aload_0 
    30: getfield  #3     // Field im:[D 
    33: iload   4 
    35: daload 
    36: dstore  7 
    38: aload_1 
    39: getfield  #2     // Field re:[D 
    42: iload   4 
    44: daload 
    45: dstore  9 
    47: aload_1 
    48: getfield  #3     // Field im:[D 
    51: iload   4 
    53: daload 
    54: dstore  11 
    56: aload_2 
    57: iload   4 
    59: dload   5 
    61: dload   9 
    63: dmul 
    64: dload   7 
    66: dload   11 
    68: dmul 
    69: dsub 
    70: dastore 
    71: aload_3 
    72: iload   4 
    74: dload   5 
    76: dload   11 
    78: dmul 
    79: dload   9 
    81: dload   7 
    83: dmul 
    84: dadd 
    85: dastore 
    86: iinc   4, 1 
    89: goto   13 
+0

爲什麼不使用Clojure的Java實現? – OlegTheCat

+0

@OlegTheCat這是可能的,我只是徘徊,如果有一種意識形式的方式來編寫Clojure編譯器創建最佳代碼的Clojure代碼。 –

+0

@OlegTheCat有趣的引用是來自http://clojure.org/reference/java_interop的「結果代碼與速度完全相同」。我知道如果這個例子是規則(並且Clojure中的數組處理可以是有效的)或者是一個異常。 –

回答

1

你最近怎麼樣標記此代碼?我建議使用類似標準的東西,或者在比較時間之前至少執行很多處決。當JIT足夠暖和時,應該通過JIT對事件進行優化。我也推薦使用最新的JVM,-server和-XX:+ AggressiveOpts。

通常我覺得最好不要試圖強制Clojure在循環中使用整數 - 而是將長整數作爲循環計數器使用,使用(set! *unchecked-math* true),並讓Clojure在編入索引時向下舍入整數。雖然這看起來像是額外的工作,但我對現代硬件/ JVM/JIT的印象是差別遠遠小於預期(因爲無論如何你都主要使用64位整數)。此外,它看起來像是作爲循環變量攜帶大小,但它永遠不會改變 - 也許你這樣做是爲了避免與我的類型不匹配,但我只是讓大小(作爲一個長)在循環之前,並做很長的增量和而不是比較。

有時你可以通過在循環之前讓事情減少檢查。雖然很容易看到代碼並說出它們何時不需要,但編譯器並沒有對此進行任何分析,而是將其留給JIT來優化事物(它通常非常擅長,實際上你的代碼的99%很重要)。

(set! *unchecked-math* :warn-on-boxed) 

(def ^long ^:const size 65536) 

(defn get-zero-complex-array [] 
    {:re (double-array size) 
    :im (double-array size)}) 

(defn multiply-complex-arrays [a b] 
    (let [a-re-array (doubles (get a :re)) 
     a-im-array (doubles (get a :im)) 
     b-re-array (doubles (get b :re)) 
     b-im-array (doubles (get b :im)) 
     res-re-array (double-array size) 
     res-im-array (double-array size) 
     s (long size)] 
    (loop [i 0] 
     (if (< i s) 
     (let [a-re (aget a-re-array i) 
       a-im (aget a-im-array i) 
       b-re (aget b-re-array i) 
       b-im (aget b-im-array i)] 
      (aset res-re-array i (- (* a-re b-re) (* a-im b-im))) 
      (aset res-im-array i (+ (* a-re b-im) (* b-re a-im))) 
      (recur (inc i))) 
     {:re res-re-array :im res-im-array})))) 

(defn compute [] 
    (let [res (loop [i 0 a (get-zero-complex-array)] 
       (if (< i 30000) 
       (recur (inc i) (multiply-complex-arrays a a)) 
       a))] 
    (aget (get res :re) 0))) 
+0

在使用'* unchecked-math *'後,時間從1.34 java變爲1.22 java,在將size移出循環後再次出現let(2行比在你的建議中要高一些)到1.17 java和'^ long ^:const'和''''''long'類型的類型轉到1.15 java。亞歷克斯,謝謝你的寶貴意見。 –

+0

我使用Windows下'time'程序的輸出來測量牆壁時間。我跑5次並獲得中位數。爲了獲得多倍的Java時間,我減去了執行30000個循環的時間,並花時間在Java和Clojure中執行1循環,然後將Clojure差異除以Java差異。 –

+0

該問題與競爭性編程有關,因此代碼沒有時間運行超過10秒,所以在幾分鐘的熱身之後我不測量它。 –