1

私は、C++コードを文字配列に生成するコンパイラを構築しています。これは、JITコンパイラClangによってLLVM-IRに変換され、さらにJIT変換されて実行可能コードになります(実行されます)。

大量のデータを処理していますが、ある時点で、カスタムデータ型の配列をソートする必要があります。データ型はコンパイラによって動的に構築され、JIT コンパイルごとに異なります。通常、要素はその中のいくつかの数値によって辞書編集的に比較されますが、まれに比較がより複雑になる場合があります (いくつかのポインターと複雑な文字列の比較に従います)。

今私の質問: llvm によってコンパイルされた JIT によって非常に高速で、同時に実行時に非常に高速な効率的なソートアルゴリズムは何ですか? 高速にコンパイルして同時に高速に実行できるアルゴリズムはどこかにありますか?

私の最初のアイデアは、比較関数を JIT して、ポインターとして qsort() に渡すことでした (LLVM で外部のコンパイル済み関数にリンクできます)。ただし、qsort は実行時に驚くほど非効率的です。std::sort を使用する別の方法は、そのテンプレートと stl-blubbla-sugar のために、コンパイル時に驚くほど非効率的です。

次の構造体の実行について、いくつかのパフォーマンス テストを行いました。

struct MyStruct {
int x;
long z;
bool operator<(const struct MyStruct& other) const { return (x < other.x) || (x==other.x&&z<other.z); }
}

1MB データ ランタイム:

  • std::sort: 5 ミリ秒
  • qsort: 14 ミリ秒
  • 自己書き込み: 6 ミリ秒

1GB データ ランタイム:

  • std::sort: 8.9 秒
  • qsort: 24 秒
  • 自筆：10.1秒

残念ながら、現在 JIT コンパイル時間はありませんが、将来投稿する予定です。

現在、自分で書いたソートはqsortやstd::sortよりも優れているようですが、ライブラリの実装を使用したいと考えています。

実行とコンパイルの両方が高速になる既存の並べ替えの実装に関する提案はありますか? または、高速な並べ替えを行いながらコンパイルを高速化する他の可能性はありますか (コンパイル比較関数のみなど)。

ところで、これは私の自作の ( http://alienryderflex.com/quicksort/から盗んだ) ソート ルーチンです (JITing の場合、テンプレート タイプを使用せず、「<=」を含むカスタム タイプに直接置き換えます)。 "):

template< typename Type >
void self_written_sort(Type *arr, int elements) {
    #define  MAX_LEVELS  64
    Type piv;
    int beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R, swap ;
  beg[0]=0; end[0]=elements;
  while (i>=0) {
    L=beg[i]; R=end[i]-1;
    if (L<R) {
      piv=arr[L];
      while (L<R) {
        while (arr[R]>=piv && L<R) R--; if (L<R) arr[L++]=arr[R];
        while (piv<=arr[L] && L<R) L++; if (L<R) arr[R--]=arr[L]; }
      arr[L]=piv; beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L;
      if (end[i]-beg[i]>end[i-1]-beg[i-1]) {
        swap=beg[i]; beg[i]=beg[i-1]; beg[i-1]=swap;
        swap=end[i]; end[i]=end[i-1]; end[i-1]=swap; }}
    else {
      i--;
}}}
4

1 に答える 1

2

最初に関数ポインタを に渡そうとするstd::sortので、次のように使用しますqsort。

  • アルゴリズム自体はプリコンパイルされています
  • 比較関数は JIT され、動的に渡されます

qsortアルゴリズムがメモリを有意義に操作し、比較のみが（実際に）呼び出されるため、それでも優れていると思います。

于 2012-05-14T18:46:19.760 に答える