10

Clojureでこのコードを見つけて、最初のn個の素数をふるいにかけました。

(defn sieve [n]
  (let [n (int n)]
    "Returns a list of all primes from 2 to n"
    (let [root (int (Math/round (Math/floor (Math/sqrt n))))]
      (loop [i (int 3)
             a (int-array n)
             result (list 2)]
        (if (>= i n)
          (reverse result)
          (recur (+ i (int 2))
                 (if (< i root)
                   (loop [arr a
                          inc (+ i i)
                          j (* i i)]
                     (if (>= j n)
                       arr
                       (recur (do (aset arr j (int 1)) arr)
                              inc
                              (+ j inc))))
                   a)
                 (if (zero? (aget a i))
                   (conj result i)
                   result)))))))

それから私はSchemeで同等の（私が思う）コードを書きました（私はmit-schemeを使用します）

(define (sieve n)
  (let ((root (round (sqrt n)))
        (a (make-vector n)))
    (define (cross-out t to dt)
      (cond ((> t to) 0)
            (else
             (vector-set! a t #t)
             (cross-out (+ t dt) to dt)
             )))
    (define (iter i result)
      (cond ((>= i n) (reverse result))
            (else
             (if (< i root)
                 (cross-out (* i i) (- n 1) (+ i i)))
             (iter (+ i 2) (if (vector-ref a i)
                               result
                               (cons i result))))))
    (iter 3 (list 2))))

タイミングの結果は次のとおりです。Clojureの場合：

(time (reduce + 0 (sieve 5000000)))
"Elapsed time: 168.01169 msecs"

mit-schemeの場合：

(time (fold + 0 (sieve 5000000)))
"Elapsed time: 3990 msecs"

mit-schemeが20倍以上遅い理由を誰かに教えてもらえますか？

更新：「違いは、解釈/コンパイルモードにありました。mit-schemeコードをコンパイルした後、比較的高速に実行されていました。– abo-abo2012年4月30日15:43」

4

2 に答える 2

15

Java 仮想マシンの最新の化身は、インタープリター言語と比較して非常に優れたパフォーマンスを発揮します。JVM、特に hotspot JIT コンパイラー、高度に調整されたガベージ コレクションなどには、かなりの量のエンジニアリング リソースが投入されています。

あなたが見ている違いは、主にそれによるものだと思います。たとえば、Java プログラムはより高速ですか? Java と Ruby の比較を見ることができます。これは、ベンチマークの 1 つで Java が 220 倍優れていることを示しています。

clojure ベンチマークを実行している JVM オプションについては言及していません。-Xint純粋な解釈モードで実行されるフラグを指定して Java を実行してみて、違いを確認してください。

また、例が小さすぎて JIT コンパイラを実際にウォームアップできない可能性もあります。より大きな例を使用すると、パフォーマンスの差がさらに大きくなる可能性があります。

Hotspot がどれだけ役に立っているかを把握するため。デフォルトのオプション（-server hotspot）と解釈モード（-Xint）でJava 1.6.0_31を使用して、MBP 2011（クアッドコア2.2Ghz）でコードを実行し、大きな違いを確認しました

; with -server hotspot (best of 10 runs)
>(time (reduce + 0 (sieve 5000000)))
"Elapsed time: 282.322 msecs"
838596693108

; in interpreted mode using -Xint cmdline arg
> (time (reduce + 0 (sieve 5000000)))
"Elapsed time: 3268.823 msecs"
838596693108
于 2012-04-30T14:33:18.857 に答える
5

Scheme と Clojure のコードを比較すると、Clojure 側で単純化すべき点がいくつかありました。

  • 可変配列をループで再バインドしないでください。
  • これらの明示的なプリミティブ強制の多くを削除しますが、パフォーマンスは変わりません。Clojure 1.3 の時点で、関数呼び出しのリテラルは、そのような関数シグネチャが利用可能な場合にプリミティブにコンパイルされます。通常、パフォーマンスの違いは非常に小さいため、ループ内で発生する他の操作によってすぐに溺れてしまいます。
  • プリミティブな長い注釈を fn 署名に追加して、n の再バインドを削除します。
  • Math/floor の呼び出しは必要ありません。int 型強制は同じセマンティクスを持ちます。

コード：

(defn sieve [^long n]
 (let [root (int (Math/sqrt n))
       a (int-array n)]
   (loop [i 3, result (list 2)]
     (if (>= i n)
       (reverse result)
       (do
         (when (< i root)
           (loop [inc (+ i i), j (* i i)]
             (when (>= j n) (aset a j 1) (recur inc (+ j inc)))))
         (recur (+ i 2) (if (zero? (aget a i))
                          (conj result i)
                          result)))))))
于 2012-05-02T08:54:30.090 に答える