Clever Geek Handbook

検索エンジン最適化

何とか何とか



メインの仕事から頭が膨らみ始めたら、コンテキストを切り替えて、自分自身のタスクを考え出すのが好きです。これは、あるアルゴリズムの動作の改善、最適化に関連しています。 広告管理システムを10年以上開発してきたので、私の仕事はすべてこの分野にも関連しています。







最近、私の考えは、与えられたパラメーターの広告キャンペーンの検索速度を上げる方法の問題に夢中になりました。 実際、広告キャンペーンは、要求に合ったものを選択するためにチェックする必要がある一連の制限です。 徹底的な検索を高速化しようとして、私は本質に到達しましたが、その成果は傑出したものとは言えませんでした。 同時に、私はいつも正しい道を進んでいない、どこかで何かをひっくり返さなければならないと感じ、スピードが一桁増加するだろうという感覚が常にありました。







昨日、数日前にHighLoad ++のレポートで話したPasha Beyzmanとの会話の後、それは私にわかりました。 ビット操作!!! はい、ビット演算のパワーを理解していますが、正しく準備していませんでした;）テスト結果は私の最も楽観的な期待を超えていました。







アイデア



キャンペーンを選択する際の制限のタイプの1つは、値がセット内にあるかどうかを確認することです。 たとえば、キャンペーンの表示は、国、地域、都市、カテゴリなどによって制限される場合があります。 最初に思い浮かぶのは、キャンペーンレベルのすべての値を持つツリーです。 2番目は値の配列です。セットに値が少ない（約10）場合、直接列挙はツリーを使用するよりも高速になります。 キャンペーンを選択するには、すべてを調べて、それぞれのセット内の特定の値の出現を確認する必要があります。







正しく準備されたビット操作のアルゴリズムは次のとおりです。 制約の特定の値に対して、サイズがキャンペーンの数に等しい大きなビットマスクを構築し、この値をターゲットとするキャンペーンのビットを設定します（または特定のタイプの制限はありません）。 ツリーにビットマスクを配置します。ここで、キーは制約の値です。 たとえば、国の場合、これはツリーになり、キーは国の識別子、値はこの国で表示できるキャンペーンに設定されたビットのマスクです。







このような構造を使用するのは非常に簡単です。 どの国にキャンペーンを選択する必要があるかがわかっているため、識別子によってビットマスクを選択し、他の制限のマスクを使用してAND演算を実行します。 非常に速くて美しい。







テスト



パフォーマンステストなしの場所... 100万のキャンペーンに対して1つの制限の処理をテストしました。 キャンペーンごとに、0から256までの10個の値のセットを使用して制限がランダムに生成されました（コードからメモリ割り当てエラーなどのチェックが削除されました）。 







int nels = 10; int campaigns = 1000000; int *values = (int *) malloc(sizeof(int) * campaigns * nels); srand(13); for (int i = 0; i < campaigns; i++) { for (int j = 0; j < nels; j++) { values[i * nels + j] = rand() % 256; } }


配列内の値を反復処理する



私たちは、すべてのキャンペーンをすべての制限で整理しようとしているだけです。 以降、-O3オプションを使用してコンパイルします。







テスト中です。 







  clock_t cs, ce; int found_campaigns = 0; int reference = 13; cs = clock(); for (int i = 0; i < campaigns; i++) { for (int j = 0; j < nels; j++) { if (values[i * nels + j] == reference) { found_campaigns++; break; } } } ce = clock(); printf("test #1 bruteforce, found: %d, clocks: %ld, sec: %f\n", found_campaigns, (long) (ce - cs), (double) (ce - cs) / CLOCKS_PER_SEC);


結果：クロック：7034、秒：0.007034。







ツリーの値で列挙する



制約値の配列の代わりにツリー（ Judy Arrays ）を使用しようとします。







データの準備 
 Pvoid_t *sets = (Pvoid_t) malloc(sizeof(Pvoid_t) * campaigns); memset(sets, 0, sizeof(Pvoid_t) * campaigns); for (int i = 0; i < campaigns; i++) { for (int j = 0; j < nels; j++) { PWord_t pw; JLI(pw, sets[i], values[i * nels + j]); } }


テスト中です。 







  found_campaigns = 0; cs = clock(); for (int i = 0; i < campaigns; i++) { PWord_t pw; JLG(pw, sets[i], reference); if (pw) { found_campaigns++; } } ce = clock(); printf("test #2 set, found: %d, clocks: %ld, sec: %f\n", found_campaigns, (long) (ce - cs), (double) (ce - cs) / CLOCKS_PER_SEC);


結果：クロック：7930、秒：0.007930。







10を超える配列値の反復は、ツリーを使用するよりも高速であることが判明しました。 ここで驚くべきことは何もありません。配列を並べ替えると、プロセッサキャッシュが著しく使用されます。 配列とツリーの間の近似的な同等性は、12個の要素にありました。







ビットマスクを使用する



ビットマスクを準備する 
  #define SET_BIT(_n, _i) _n[_i / 64] |= 1ULL << (_i % 64) #define CHECK_BIT(_n, _i) _n[_i / 64] & (1ULL << (_i % 64)) PWord_t pw; Pvoid_t pv = (Pvoid_t) 0; int mask_size = sizeof(uint64_t) * (campaigns / 64 + 1); for (int i = 0; i < campaigns; i++) { for (int j = 0; j < nels; j++) { int id = values[i * nels + j]; JLI(pw, pv, id); if (*pw) { uint64_t *mask = (uint64_t *) *pw; SET_BIT(mask, i); } else { uint64_t *mask = (uint64_t *) malloc(mask_size); memset(mask, 0, mask_size); SET_BIT(mask, i); *pw = (Word_t) mask; } } }


テスト中です。 







  found_campaigns = 0; cs = clock(); JLG(pw, pv, reference); if (pw) { uint64_t *mask = (uint64_t *) *pw; for (int i = 0; i < campaigns; i++) { if (CHECK_BIT(mask, i)) { found_campaigns++; } } } ce = clock(); printf("test #3 bitmaps, found: %d, clocks: %ld, sec: %f\n", found_campaigns, (long) (ce - cs), (double) (ce - cs) / CLOCKS_PER_SEC);


結果：クロック：1393、秒：0.001393。







バスティングよりも5倍高速です。 悪くはないが、より良い。







ビットマスクの使用を高速化する



高速化のために、組み込みのgcc __builtin_ffsll関数を使用します。この関数は、最初のビットセットのインデックスを返します。







テスト中です。 







  found_campaigns = 0; cs = clock(); JLG(pw, pv, reference); if (pw) { uint64_t *mask = (uint64_t *) *pw; for (int i = 0; i < (campaigns / 64 + 1); i++) { uint64_t m = mask[i]; while (m) { int n = __builtin_ffsll(m); m &= ~(1ULL << (n - 1)); found_campaigns++; } } } ce = clock(); printf("test #4 bitmaps 2, found: %d, clocks: %ld, sec: %f\n", found_campaigns, (long) (ce - cs), (double) (ce - cs) / CLOCKS_PER_SEC);


結果：クロック：28、秒：0.000028。







この時点で、私の目は広がりました。 徹底的な検索と比較して250倍の高速化。







プロセッサの動作、SSE、AVX、および同様の命令、キャッシュの配置方法-この知識により、プログラムを大幅に高速化できます。 しかし、美しいアルゴリズムを使用すると、作業を大幅にスピードアップできます。







プログラムのテキストはここにあります： https : //github.com/saterenko/labs/tree/master/bit_limits







PS



初期化で見つかったエラーのPkXwmpgNのおかげで、テストデータの配列全体が埋められたのではなく、その10番目の部分だけが埋められました。 エラーを修正した後、最後のテストの実行時間は1桁増加しました。 徹底的な検索と比較した場合の加速-25回、額の目はもう登ることはありませんが、印象的です;）







More articles:


All Articles