2番目の記事からC ++コードのコンパイルを開始した後、コードがコンパイルされている間は高速に動作するアナログをCで記述できるかどうか疑問に思いました。 時間がありませんでした。コードは5分後にコンパイルされ、Cのアナログはすべて15で書かれました。
だから、問題の声明-いくつかのフィールドの構造があり、各フィールドが指定された範囲内にあるかどうかをチェックするフィルターがあります。 またはチェックしません-各フィールドに対して。 固定フィルターで非常に迅速にこのチェックを行うコードが必要です。 データはランダムであるため、条件付き遷移が少ないほど良くなります-ランダムデータの遷移の予測はまあまあ機能します。
問題は2段階で解決されます。
1.比較演算をより単純なもの、たとえば加算演算やビット演算に置き換えることを学びましょう
2. 1の複数の操作を自由に組み合わせる方法を学びましょう。
だから、最初のポイント。 bの値と[a、c]の範囲があるため、a <= bおよびb <= cを計算する必要があります。 比較なし。 明確にするために、a、b、cを非負とし、7ビットに入れます-つまり 0から127まで。
式（128-a）+ bが8ビットに収まることが保証されていることは簡単にわかります。 さらに、結果の8番目のビットは、a <= bの場合にのみ1です。 たとえば、a = 0の場合、式128 + bの値では、8番目のビットは常に1です。 a = 1の場合、式127 + bの値で、bが0または1の場合、8番目のビットは1です。
bとcを比較した結果はほぼ同じ方法で得られます-式（127-c）+ bは8ビットに配置され、結果の8番目のビットはb <= cの場合にのみ0です。
乾杯！ a <= bをカウントする代わりに、（（128-a）+ b）＆128をカウントします。なぜでしょうか？..
ポイント2。 ビット演算には、誰もが知っている素晴らしい特性があります。単一の命令で、同じ種類のビット演算を一度に多く実行できます。 今年はすでに2013年であるように思われますが、日中はSSEのないプロセッサーを見つけることができないため、64ビットであると想定します-間違いなく可能です。
注意してデータを事前に準備しておけば、算術演算に同様の優れた特性があることを誰もが知っているわけではありません。 たとえば、32ビットの算術演算と、7ビットの符号なし数値の4つのペアがあるとします。 それらがどのように折り畳まれるかを見てください：
1.ゼロに初期化される各数値に高位ビットを追加します。
aaaaaaa-> 0aaaaaaa
2. 8ビットの4つのグループが順番に書き込まれます。
0aaaaaaa0bbbbbbb0ccccccccddddddddd
3.結果の2つの32ビット数を追加します。 32ビットの数値で4つの8ビット加算結果が得られます。
4. 7ビット演算が必要な場合、転送ビットをリセットできます。
目的のタスクで何を行う必要があるかがすぐに明らかになります。
1.データを64ビットのレジスタに格納して、各値に特別な高ビットを設定します。 偶然、記事の例がこのような62ビットのパッキングに割り込んでいたことがあります。1つのシングルビットフィールドの余地がまだあります。
struct T_cash_account_row { unsigned reserved0:1; unsigned code:20; // 0 - 1000000 unsigned carry_code:1; unsigned gender:1; // 0 - 1 unsigned carry_gender:1; unsigned age:7; // 0 - 100 unsigned carry_age:1; unsigned reserved1:1; unsigned amount_of_money:20;// 0 - 1000000 unsigned carry_amount_of_money:1; unsigned height:9; // 0 – 300 unsigned carry_height:1; };
ここでは、特定のコンパイラでビットフィールドを配置する順序に関する知識を使用します。 実際、構造体をunsigned long longに置き換えて、ビット操作で値を設定する必要がありますが、そのためには参照コードを変更する必要があります。 コードは以前よりも少しクロスプラットフォームになり、処理されています。
2.事前に、上記の例の（128-a）や（128-1-c）などの数値から2つの用語を生成します。 128の代わりに、各フィールドの幅をビットで置き換えます。 狂わないように、マクロを使用します。
#define FILL(enum, field, bits) \ if (range_filters->use_filter[enum]) { \ begin_add.field = (1 << bits) - range_filters->begin.field; \ begin_add.carry_##field = range_filters->begin.field == 0; \ end_add.field = (1 << bits) - 1 - range_filters->end.field; \ mask_add.carry_##field = 1; \ }
beginのcarry_fieldの充填に注意します-ビットフィールドは追加せずに算術で動作します。 拡張ビット。したがって、begin = 0の場合、フィールド自体をゼロで埋め、carry_fieldを1で埋める必要があります。 ビットフィールドの代わりに符号なしlong longおよびビット演算を使用する場合は、（1 <<ビット）-beginと書くだけです。
3. 2つの制御用語を使用して、フィールドがスタックされている64ビットの数値を追加します。 転送ビットで必要な情報を取得します
unsigned long long value = *(unsigned long long*)&array_ptr[i]; unsigned long long begin_result = (value + begin_add_i) ^ mask_add_i; unsigned long long end_result = value + end_add_i;
このコードの一部では、厳密なエイリアシングに悪意を持って違反し（そしてそれで地獄に）、キャリービットの1を0に置き換えました。
4.関心のあるすべてのキャリービット（フィルターで考慮する必要のあるキャリービット）が、最初の加算後は1、2番目以降は0であることを確認します。
if (((begin_result | end_result) & mask_add_i) == 0)
1を0に置き換えたため、関心のあるすべてのビットがゼロに等しいことを確認するだけで十分です。
5.パフォーマンスを測定すると、コンパイルに5分かかるC ++コードと比較して、ほぼ2倍の増加が得られます。
Microsoft (R) C/C++ Optimizing Compiler Version 17.00.50727.1 for x64 Generated rows: 100000000 C-search took 0.778000 seconds. C++-optimized search took 0.307000 seconds. C-optimized-search took 0.171000 seconds.
念のため、コード全体 。 / TPスイッチを使用してMSVCでコンパイルし（変更前でも変更後でもC89ではないため）、スイッチなしのgcc（ランダム）でコンパイルします。
もちろん、 そのようなパフォーマンスを測定することはできません 。
もちろん、私は62ビットで幸運でした（元の記事の著者は4000オプションで幸運でした）。
しかし、誰もが自分で結論を出せるようにしてください。
結論として、生産の実際のソリューションはSoAデータスタッキングを使用するようです-構造の配列を使用する代わりに、各フィールドに1つの配列を使用します（ビットマップパッケージなど）。 次に、最初に、線形スキャンによって読み取られたデータの量を節約できます。2番目に、コンパイル時の組み合わせが不要です。3番目に、コードの記述が少なくなります。4番目に、フィールドの数とクエリ構造が動的に変更しやすくなります。 もちろん、実際の本番ソリューションでは、プラットフォーム固有のSIMDを使用します。