6

さらに別の合成ベンチマーク:エラトステネスのふるい

C++

#include <vector>
#include <cmath>

void find_primes(int n, std::vector<int>& out)
{
   std::vector<bool> is_prime(n + 1, true);
   int last = sqrt(n);
   for (int i = 2; i <= last; ++i)
   {
      if (is_prime[i])
      {
         for (int j = i * i; j <= n; j += i)
         {
            is_prime[j] = false;
         }
      }
   }

   for (unsigned i = 2; i < is_prime.size(); ++i)
   {
      if (is_prime[i])
      {
         out.push_back(i);
      }
   }
}

OCaml ( Jane Street の CoreおよびResライブラリを使用)

open Core.Std
module Bits = Res.Bits
module Vect = Res.Array

let find_primes n =
  let is_prime = Bits.make (n + 1) true in
  let last = float n |! sqrt |! Float.iround_exn ~dir:`Zero in
  for i = 2 to last do
    if not (Bits.get is_prime i) then () else begin
      let j = ref (i * i) in
      while !j <= n; do
        Bits.set is_prime !j false;
        j := !j + i;
      done;
    end;
  done;
  let ar = Vect.empty () in
  for i = 2 to n do
    if Bits.get is_prime i then Vect.add_one ar i else ()
  done;
  ar

OCaml版(ネイティブ)がC++より13倍くらい遅いのには驚きました。に置き換えましRes.BitsたがCore_extended.Bitarray、〜18倍遅くなりました。なぜそんなに遅いのですか？OCaml はビット操作の高速操作を提供しませんか? ビット配列の代替高速実装はありますか?

明確にするために: 私は C++ の世界から来ており、OCaml をパフォーマンスが重要なコードを書くための可能な代替手段と考えています。実際、私はそのような結果で少し怖いです.

編集：

プロファイリング結果

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 50.81      1.26     1.26                             camlRes__pos_1113
  9.72      1.50     0.24                             camlRes__unsafe_get_1117
  6.68      1.66     0.17                             camlRes__unsafe_set_1122
  6.28      1.82     0.16                             camlNopres_impl__set_1054
  6.07      1.97     0.15                             camlNopres_impl__get_1051
  5.47      2.10     0.14 47786824     0.00     0.00  caml_apply3
  3.64      2.19     0.09 22106943     0.00     0.00  caml_apply2
  2.43      2.25     0.06   817003     0.00     0.00  caml_oldify_one
  2.02      2.30     0.05        1    50.00   265.14  camlPrimes__find_primes_64139
  1.21      2.33     0.03                             camlRes__unsafe_get_1041
...
4

4 に答える 4

4

洗練されたものにジャンプする前に、最初に単純なデータ構造を使用してみましたか?

私のマシンでは、次のコードは C++ バージョンよりも 4 倍遅いだけです (配列をキャッシュとして使用し、リストを結果を蓄積するために最小限の変更を行ったことに注意してください。配列の get/set シンタックス シュガーを使用できます)。

let find_primes n =
  let is_prime = Array.make (n + 1) true in
  let last = int_of_float (sqrt (float n)) in
  for i = 2 to last do
    if not (Array.get is_prime i) then () else begin
      let j = ref (i * i) in
      while !j <= n; do
        Array.set is_prime !j false;
        j := !j + i;
      done;
    end;
  done;
  let ar = ref [] in
  for i = 2 to n do
    if Array.get is_prime i then ar := i :: !ar else ()
  done;
  ar

(4 倍遅い: 10_000_000 の最初の素数を計算するのに 4 秒かかりますが、コードの g++ -O1 または -O2 の場合は 1 秒かかります)

ビットベクトル ソリューションの効率性はおそらく経済的なメモリ レイアウトにあることに気づき、配列の代わりに文字列を使用するようにコードを変更しました。

let find_primes n =
  let is_prime = String.make (n + 1) '0' in
  let last = int_of_float (sqrt (float n)) in
  for i = 2 to last do
    if not (String.get is_prime i = '0') then () else begin
      let j = ref (i * i) in
      while !j <= n; do
        String.set is_prime !j '1';
        j := !j + i;
      done;
    end;
  done;
  let ar = ref [] in
  for i = 2 to n do
    if String.get is_prime i = '0' then ar := i :: !ar else ()
  done;
  ar

これには 2 秒しかかからないため、C++ ソリューションよりも 2 倍遅くなります。

于 2013-02-06T20:23:18.227 に答える
3

このようにマイクロベンチマークを比較することはあまり役に立ちませんが、基本的な結論はおそらく正しいでしょう。これは、OCaml が明らかに不利な状況にあるケースです。C++ は多かれ少なかれ理想的な表現 (機械整数のベクトル) にアクセスできます。OCaml はベクトルを作成できますが、マシンの整数を直接取得することはできません。そのため、OCaml は div と mod を使用する必要があり、C++ では shift と mask を使用できます。

このテストを (別のビット ベクトル ライブラリを使用して) 再現したところ、ビット配列ではない結果の構築に OCaml でかなりの時間が費やされていることがわかりました。そのため、テストはあなたが考えていることを正確に測定していない可能性があります.

アップデート

32 個のブール値を 63 ビットの int にパックする簡単なテストをいくつか試しました。それは物事をより速く進めるように見えますが、ほんの少しです. これは完璧なテストではありませんが、2 の累乗でない効果がマイナーであるというガッシュが正しいことを示唆しています。

于 2013-02-06T18:14:20.027 に答える
3

ジェフリー・スコフィールドが正しいようです。このようなひどいパフォーマンスの低下はdiv、mod操作によるものです。

Bitarray小型モジュールを試作しました

module Bitarray = struct
  type t = { len : int; buf : string }

  let create len x =
    let init = (if x = true then '\255' else '\000') in
    let buf = String.make (len / 8 + 1) init in
    { len = len; buf = buf }

  let get t i =
    let ch = int_of_char (t.buf.[i lsr 3]) in
    let mask = 1 lsl (i land 7) in
    (ch land mask) <> 0

  let set t i b =
    let index = i lsr 3 in
    let ch = int_of_char (t.buf.[index]) in
    let mask = 1 lsl (i land 7) in
    let new_ch = if b then (ch lor mask) else (ch land lnot mask) in
    t.buf.[index] <- char_of_int new_ch
end

文字列をバイト配列として使用します (1 文字あたり 8 ビット)。最初は、ビット抽出にx / 8andを使用しました。x mod 8C++ コードよりも 10 倍遅くなりました。x lsr 3次に、それらをandに置き換えましたx land 7。現在、C++ よりも 4 倍遅いだけです。

于 2013-02-06T23:44:45.020 に答える
1

.cmx ファイルを含む Core を必ずインストールしてください (.cmxa では十分ではありません!)。そうしないと、クロスモジュールのインライン化が機能しません。あなたのプロファイルは、特定の呼び出しがインライン化されていない可能性があることを示唆しています。これは、効率が大幅に低下することを説明しています。

悲しいことに、多くの OCaml プロジェクトで使用されている Oasis パッケージ ツールには現在、.cmx ファイルのインストールを妨げるバグがあります。Core パッケージもこの問題の影響を受けます。おそらく、使用しているパッケージ マネージャー (Opam、Godi) に関係なく発生します。

于 2013-02-12T17:58:05.623 に答える