10

私はまだOCamlの学習の初期段階にあり、OCamlのジェネリックコードから最大のパフォーマンスを引き出すための最良の方法が何であるかを知りたいと思っています。

小さな実験として、2つのポリモーフィック関数を作成しました。1つはC ++で、もう1つは特定の配列で最大の要素を見つけるOCamlで作成しました。

私が観察したことは、C ++ではこの種の抽象化に対してペナルティを支払わないのに対し、OCamlでのペナルティはパフォーマンスの大幅な低下です。余談ですが、私がすぐに作成したC ++ソリューションは、OCamlソリューションよりも一般的ですが、それは主に言語の経験がないことによるものです。

私の質問は次のとおりです：私が今観察した巨大なパフォーマンスペナルティを支払うことなく、OCamlでポリモーフィック関数を記述して使用する方法は？

この特定の問題について私が観察したもう1つのことは、OCamlの機能ソリューションは命令型ソリューションよりも遅いのに対し、C ++の「機能的」ソリューションは、アナログの命令型アプローチと比較してペナルティを受けなかったことです。

C ++コードはg++ -std="c++0x" -O3 -o max_cpp max.cpp、gcc-4.6.3を使用してコンパイルされ、OCamlコードはocamlopt -o max_ml max.mlocamloptバージョン3.12.1を使用してコンパイルされました。生成された実行可能ファイルは両方とも32ビットで、Ubuntux6411.04で実行されました。

両方のプログラムのコードを提出します。

C ++コード（もちろん、完全に安全というわけではありません;））

#include <iostream>
#include <vector>
#include <numeric>
template <typename T> T max (T a, T b) {
     return (a>b)? a : b;
}

template <typename I> typename I::value_type find_max (I begin, I end) {
    auto max = *begin;
    for (begin++;begin!=end;begin++)
            if (*begin > max) max = *begin;
    return max;
}

template <typename I> typename I::value_type find_max1(I begin, I end) {
    return std::accumulate(begin, end, *begin, max< typename I::value_type> );
}

int main(int argc, char ** argv) {
    const size_t nElem = atoi(argv[1]);
    const size_t nIter = atoi(argv[2]);
    std::vector<int> intA(nElem);
    std::vector<double> dubA(nElem);
    for (int i=0;i<nIter;i++) {
            auto res1 = find_max(intA.begin(), intA.end());
            auto res2 = find_max(dubA.begin(), dubA.end());
            std::cout << "Max int: " << res1 << " " << "Max dub: " << res2 << std::endl;
    }
}

OCamlコード

let max a b = if a > b then a else b

(* functional version *)
let find_max vector =
    Array.fold_right max vector vector.(0)

(* imperative version *)
let find_max1 vector =
    let length = Array.length vector in
    let max = ref (vector.(0)) in
    for i=1 to length-1 do
            if vector.(i) > !max then max := vector.(i)
    done; max

let nElems = int_of_string Sys.argv.(1)

let nIter  = int_of_string Sys.argv.(2)

let _ = let intA = Array.make nElems 0 in
    let dubA = Array.make nElems 0.0 in
    for i=1 to nIter do
            let res1 = find_max intA in
            let res2 = find_max dubA in
            print_int !res1;
            print_newline ();
            print_float !res2;
    done

ただし、関数を「オーバーロード」してintとfloatを区別すると、プログラムのパフォーマンスはC ++コードのパフォーマンスを50％も上回ります。なんでだろうか。

let find_max_int (vector : int array) =
    let length = Array.length vector in
    let max = ref (vector.(0)) in
    for i=1 to length-1 do
            if vector.(i) > !max then max := vector.(i)
    done; max

let find_max_float (vector : float array) =
    let length = Array.length vector in
    let max = ref (vector.(0)) in
    for i=1 to length-1 do
            if vector.(i) > !max then max := vector.(i)
    done; max

タイミングは、次のようにかなり大雑把に実行されました time ./max_cpp 1000000 100。 time ./max_ml 1000000 100

4

2 に答える 2

8

OCamlでは、比較演算子(<)は型のジェネリック関数です'a -> 'a -> bool（同様に等式など）。これは、任意のタイプのデータ構造に対してアドホック比較を効果的に実行するランタイムシステムの特別なプリミティブによって実装されることを意味します。タイプチェッカーは、整数の単相比較を最適化し、多形の場合に実行時に型チェックを実行する代わりに、特殊な比較操作にフロートすることができます。この操作のみをテストした場合、効率の10倍の違いは驚くべきことではありません。

最大限の柔軟性を得るには、の比較操作を抽象化する必要があることに注意してくださいfind_max。ただし、これにより単形化の最適化が妨げられるため、インラインバージョンの方がパフォーマンスが向上します。

あなたのアプローチ（マイクロベンチマークを実行し、実際のプログラムのパフォーマンスについて興味深いことを学ぶことを望んでいる）には欠陥があると思います。あなたはOCamlのパフォーマンス動作の非常に特殊なケースに遭遇し、そこからポリモーフィック関数のパフォーマンスが「貧弱」であると誤って結論付けました。これは明らかに時期尚早の最適化からの悪い結論です。実行する予定の計算の実際の代表的な例を記述してから、この実際のコードのパフォーマンスについて推論します。この種のマイクロベンチマークからはほとんど真実を学ぶことができず、多くの無関係な詳細を学ぶことができます。

（ただし、C ++コードの特殊化アプローチでは、OCamlコンパイル手法よりも一般的に効率的なコードを生成できます。これは、すべてのタイプに対して関数の1つのバージョンのみをコンパイルしますが、対応するデータ表現を妥協する必要があります。OCamlではオーバーヘッドが発生する可能性があります。ポリモーフィズムに関連します。ただし、これはかなり特定の場合にのみ観察可能であり、コードの小さな重要なセクションで特定のインラインパスを作成できることがよくあります。見返りとして得られるのは、はるかに高速なコンパイル（重複なし）と実際に読み取り可能なエラーです。メッセージ-概念がC++に統合されている場合のように。）

編集：私は実際、比較を抽象化すると型指向の最適化が妨げられると言ったのは間違っていました。次のコードは、手動でインライン化されたバージョンほど高速ではありませんが、多態的な比較を使用したバージョンよりも著しく高速です。

let find_max1 comp vector =
    let length = Array.length vector in
    let max = ref (vector.(0)) in
    for i=1 to length-1 do
      if comp !max vector.(i) then max := vector.(i)
    done;
    !max

let find_max_int (vector : int array) = find_max1 (fun x y -> x < y) vector
let find_max_float (vector : float array) = find_max1 (fun x y -> x < y) vector
于 2012-12-19T17:42:02.313 に答える
2

実際、コンパイル時の特殊な関数と実行時のディスパッチを比較しています。ocaml側のより適切なコードは、ファンクターを使用することです。これにより、理論的には間接呼び出しの数をゼロに減らすことができますが、それでも最適化が不十分になると思います。もう1つの問題は、データ表現が均一であり、どのような場合でもユーザータイプに特化/インライン化されていないことです。

于 2012-12-20T09:36:05.677 に答える