GCC (または任意のコンパイラ) に実行時サイズ チェックをmemcpy()ループの外側 (そのサイズはコンパイル時定数ではなく、そのループ内で定数) で除外させ、関連するサイズ範囲ごとにループを特殊化させる信頼できる方法はありますか?その中のサイズを繰り返しチェックするのではなく？
これは、大規模なデータ セットの効率的なインメモリ分析用に設計されたオープン ソース ライブラリについて、ここで報告されているパフォーマンスの低下から縮小されたテスト ケースです。(リグレッションは、たまたま私のコミットの 1 つが原因です...)
元のコードは Cython にありますが、次のように純粋な C プロキシに縮小しました。
void take(double * out, double * in,
int stride_out_0, int stride_out_1,
int stride_in_0, int stride_in_1,
int * indexer, int n, int k)
{
int i, idx, j, k_local;
k_local = k; /* prevent aliasing */
for(i = 0; i < n; ++i) {
idx = indexer[i];
for(j = 0; j < k_local; ++j)
out[i * stride_out_0 + j * stride_out_1] =
in[idx * stride_in_0 + j * stride_in_1];
}
}
ストライドは可変です。一般に、配列が連続しているとは限りません (より大きな配列の非連続スライスである可能性があるため)。ただし、c 連続配列の特定のケースでは、上記を次のように最適化しました。
void take(double * out, double * in,
int stride_out_0, int stride_out_1,
int stride_in_0, int stride_in_1,
int * indexer, int n, int k)
{
int i, idx, k_local;
assert(stride_out_0 == k);
assert(stride_out_0 == stride_in_0);
assert(stride_out_1 == 1);
assert(stride_out_1 == stride_in_1);
k_local = k; /* prevent aliasing */
for(i = 0; i < n; ++i) {
idx = indexer[i];
memcpy(&out[i * k_local], &in[idx * k_local],
k_local * sizeof(double));
}
}
(アサートは元のコードには存在しません。代わりに、連続性をチェックし、可能な場合は最適化されたバージョンを呼び出し、そうでない場合は最適化されていないバージョンを呼び出します。)
このバージョンは、ほとんどの場合、非常にうまく最適化されます。これは、通常のユース ケースが小さい場合nと大きい場合であるためkです。ただし、逆のユース ケースも発生し (大小n) k、特定のケース(仮想ワークフローの重要な部分を代表するものとして除外できない) であることが判明し、バージョンは 3.6 倍になります。オリジナルより遅い。これは明らかに、この次のバージョンが元のバージョンと同様に (最適化設定に応じてほぼまたは正確に) 実行されるという事実によって証明されるように、コンパイル時に定数ではないという事実によるものです (または、より良い場合もあります)。の特定の場合:n == 10000k == 4memcpy()kk == 4
if (k_local == 4) {
/* this optimizes */
for(i = 0; i < n; ++i) {
idx = indexer[i];
memcpy(&out[i * k_local], &in[idx * k_local],
k_local * sizeof(double));
}
} else {
for(i = 0; i < n; ++i) {
idx = indexer[i];
memcpy(&out[i * k_local], &in[idx * k_local],
k_local * sizeof(double));
}
}
明らかに、 の特定の値ごとにループをハードコーディングするのは実用的ではないkため、代わりに次のことを試みました (機能する場合は後で一般化できる最初の試みとして)。
if (k_local >= 0 && k_local <= 4) {
/* this does not not optimize */
for(i = 0; i < n; ++i) {
idx = indexer[i];
memcpy(&out[i * k_local], &in[idx * k_local],
k_local * sizeof(double));
}
} else {
for(i = 0; i < n; ++i) {
idx = indexer[i];
memcpy(&out[i * k_local], &in[idx * k_local],
k_local * sizeof(double));
}
}
残念ながら、この最後のバージョンは元のmemcpy()バージョンよりも高速ではありません。これは、GCC の最適化機能に対する私の信頼をやや落胆させるものです。
ここで正しいことを行うのに役立つ追加の「ヒント」をGCCに(何らかの手段で)与える方法はありますか? (さらに良いことに、さまざまなコンパイラで確実に機能する「ヒント」はありますか? このライブラリは、さまざまなターゲット向けにコンパイルされています。)
引用された結果は、「-O2」フラグを使用した 32 ビット Ubuntu 上の GCC 4.6.3 のものですが、GCC 4.7.2 および「-O3」バージョンも同様の (ただし同一ではない) 結果でテストしました。テスト ハーネスをLiveWorkspaceに投稿しましたが、タイミングはコマンドを使用して自分のマシンからのものtime(1)です (LiveWorkspace のタイミングがどれほど信頼できるかはわかりません)。
編集:呼び出しの最小サイズに「マジック ナンバー」を設定することも検討しました。memcpy()テストを繰り返すことでそのような値を見つけることができましたが、異なるコンパイラ/プラットフォームで結果がどの程度一般化できるかはわかりません. ここで使用できる経験則はありますか？
さらなる編集:この場合、k_local変数は実際には役に立たないことに気づきました。エイリアシングが不可能であるためです。これは、可能な場合（kグローバルである場合）に実行したいくつかの実験から削減され、変更したことを忘れていました。その部分は無視してください。
EDIT TAG: Cythonの新しいバージョンでもC++を使用できることに気付いたので、C++から役立つものがある場合に備えてC++としてタグ付けします...
最終編集:(今のところ)特殊なアセンブリにドロップダウンする代わりmemcpy()に、次のことが私のローカルマシンに最適な経験的解決策のようです:
int i, idx, j;
double * subout, * subin;
assert(stride_out_1 == 1);
assert(stride_out_1 == stride_in_1);
if (k < 32 /* i.e. 256 bytes: magic! */) {
for(i = 0; i < n; ++i) {
idx = indexer[i];
subout = &out[i * stride_out_0];
subin = &in[idx * stride_in_0];
for(j = 0; j < k; ++j)
subout[j] = subin[j];
}
} else {
for(i = 0; i < n; ++i) {
idx = indexer[i];
subout = &out[i * stride_out_0];
subin = &in[idx * stride_in_0];
memcpy(subout, subin, k * sizeof(double));
}
}
これは「マジックナンバー」を使用して呼び出すかどうかを決定しますmemcpy()が、連続していることがわかっている小さな配列のケースを最適化します (元の配列ではそのような仮定がないため、ほとんどの場合、元の配列よりも高速です)。