データ検索のタスクは、多くの場合、Webサービス、データベース管理システム（DBMS）、ジオサーチ、および分析にあります。
まず、説明を簡単にするために、値の範囲が5つのフィールドを含む10,000,000個の要素（構造）の配列をフルパスで検索する問題を引き起こします：amount_of_money（0-1000000）、gender（0-1）、age（0-100）、code （0-1000000）、高さ（0-300）。 次の記事では、ソリューションにインデックス検索を追加します。
MSVC11（MSVS2012）およびGCC 4.7.2でクロスプラットフォームを作成し、それらで部分的に実装されたC ++ 11標準を使用します。
1. Cのソリューション
Cでのこの問題の最も簡単な解決策は、8バイトを占めるビットフィールドの構造を作成することです（一般的に、
#pragma pack(push,1)
ディレクティブがない場合、フィールドは基本タイプのサイズの境界を超えることはできません。この場合、符号なし-32ビットです）。
/* Fields */ enum T_field_enum { amount_of_money_e, gender_e, age_e, code_e, height_e, last_e }; struct T_cash_account_row { // 1 – double word (32 bits) unsigned code:20; // 0 - 1000000 unsigned gender:1; // 0 - 1 unsigned age:7; // 0 - 100 // 2 – double word (32 bits) unsigned amount_of_money:20; // 0 - 1000000 unsigned height:9; // 0 – 300 };
これらの要素の10,000,000個にメモリを割り当てます。
const size_t c_array_size = 10000000; struct T_cash_account_row *const array_ptr = ( struct T_cash_account_row *)calloc(c_array_size, sizeof(struct T_cash_account_row)); if (array_ptr == NULL) { printf ("calloc error\n"); exit(1); }
サイクルで、条件で指定された範囲内のランダムな値を入力します。
/* Generate random data for the one row */ static inline struct T_cash_account_row generate_row() { struct T_cash_account_row cash_account_row; cash_account_row.age = rand() % 100; cash_account_row.amount_of_money = (rand() % 1000)*(rand() % 1000); cash_account_row.code = (rand() % 1000)*(rand() % 1000); cash_account_row.gender = rand() % 2; cash_account_row.height = rand() % 300; return cash_account_row; } /* ----------------------------------------------------------------------- */ /* in int main() { … } */ /* Fill table random data */ for(i = 0; i < c_array_size; ++i) array_ptr[i] = generate_row();
検索フィルターフィルター構造を作成します。ここで、
last_e
は文字列内のフィールド数を含む列挙です（C ++ 03 7.2列挙宣言） 。
/* Filters */ struct T_range_filters { struct T_cash_account_row begin, end; /* bytes array or bitset from https://gist.github.com/jmbr/667605 */ unsigned char use_filter[last_e]; }; /* ----------------------------------------------------------------------- */
ここで、
use_filter[]
、特定のフィールド条件でフィルタリングするかどうかを示すために使用されます。
そして、ループ内の配列のすべての要素を通過する特定のフィールドをチェックして検索します。
/* Compare row with filters */ static inline unsigned char test_predicate(struct T_cash_account_row const*const row, struct T_range_filters const*const range_filters) { return (!range_filters->use_filter[amount_of_money_e] || (row->amount_of_money >= range_filters->begin.amount_of_money && row->amount_of_money <= range_filters->end.amount_of_money)) && (!range_filters->use_filter[gender_e] || (row->gender >= range_filters->begin.gender && row->gender <= range_filters->end.gender)) && (!range_filters->use_filter[age_e] || (row->age >= range_filters->begin.age && row->age <= range_filters->end.age)) && (!range_filters->use_filter[code_e] || (row->code >= range_filters->begin.code && row->code <= range_filters->end.code)) && (!range_filters->use_filter[height_e] || (row->height >= range_filters->begin.height && row->height <= range_filters->end.height)); } /* ----------------------------------------------------------------------- */ /* search */ static inline size_t search(struct T_cash_account_row const*const array_ptr, const size_t c_array_size, struct T_cash_account_row *const result_ptr, struct T_range_filters const*const range_filters) { size_t result_size = 0; size_t i; /* loop index */ for(i = 0; i < c_array_size; ++i) { if(test_predicate(array_ptr + i, range_filters)) result_ptr[result_size] = array_ptr[i], ++result_size; } return result_size; }
GitHub.comの作業コード全体へのリンク
ここでは、インデックスなしでフルパスを使用して高速化と最適化を行うことができます。
- ループを展開して、ループ条件との比較回数を減らし、1回の反復で複数のフィルタリングtest_predicateを実行しますか？ -これは、test_predicate組み込み関数の行を5〜15回比較し、RAMにアクセスする場合と比較すると小さすぎます。
- prefetching-cacheを実行しますか？ -CとC ++の両方で可能ですが、タスクのフレームワークでは、ほとんど何もしません。 複数の検索はできる限りLLC（L3）にキャッシュされ、80 MBのアレイ全体はとにかく使用できなくなります。
- SSEのベクトル比較コマンドを使用します：CMPSS、COMISS、UCOMISS ？ -CとC ++の両方で可能です。 ただし、この最適化は、ARMやPower [PC]などのx86 / x64以外のプロセッサでは移植できません。
- CおよびC ++でコンパイラとPGO最適化キーを使用できます。 PGOはいずれにせよ、妥協です。 最適化されたコードは、プログラム実行の1つの方法で作成され、他の方法を損なう、つまり ある程度の入力があると、より速くなり、少し遅くなります。 可能な実行パスごとに最適化されたコードを作成する方法を示しますが、プログラムの最も重要な部分でのみ速度を上げます。
Cでのこの低レベル（非アーキテクチャ）最適化は終了し、これらの最適化のいずれもC ++に適用できます。
2. CおよびC ++での別の最適化の様子
- まず、上記のCのソリューションは、変更なしでC ++コンパイラで簡単にコンパイルできます。 ほとんどの場合、下位互換性が発生します。
C： ideone.comでオンラインコンパイラが作成されます。
オンラインC ++ 11コンパイラーの結果： ideone.com
ランダムシードカウントをコメントアウトしました/* srand (time(NULL)); */
- 第二に、特にcなC開発者は、別の最適化を提供できます-検索条件の数の各バリアントに対してtest_predicate /検索関数の2 ^ 5 = 32バリアントを作成し、配列へのポインタを保存し、条件に応じて実行時に必要なバリアントを選択します検索。 これにより、比較の回数が大幅に削減されます。
検索条件が、年齢とコードの5つの2つのフィールドに到達したとします。 次に、
search_12()
関数を呼び出します。
/* Compare row with filters */ static inline unsigned char test_predicate_12(struct T_cash_account_row const*const __restrict row, struct T_range_filters const*const __restrict range_filters) { return (row->age >= range_filters->begin.age && row->age <= range_filters->end.age) && (row->code >= range_filters->begin.code && row->code <= range_filters->end.code); } /* ----------------------------------------------------------------------- */ /* search */ static inline size_t search_12(struct T_cash_account_row const*const __restrict array_ptr, const size_t c_array_size, struct T_cash_account_row *const __restrict result_ptr, struct T_range_filters const*const __restrict range_filters) { size_t result_size = 0; size_t i; /* loop index */ for(i = 0; i < c_array_size; ++i) { if(test_predicate_12(array_ptr + i, range_filters)) result_ptr[result_size] = array_ptr[i], ++result_size; } return result_size; }
ただし、この関数の条件の数は、最初の15個から4個に減少しました。 実際には、C比較のソリューションバージョンでは、15フィールドのうち9フィールドのみが実行されました。2つのフィールドの検索
test_predicate
に対して、これは
test_predicate
関数の逆アセンブラで
test_predicate
ます： github.com 。 これは、各比較
use_filter[] == false
後に、次のフィールドの比較への条件付き遷移
use_filter[] == false
あったために発生しました。 つまり これらの4つの比較に加えて、
use_filter[]
を
use_filter[]
比較は5回だけでした。
ここで説明する解決策は、たとえば、5の2つのフィールドで検索する場合、1.3倍の加速を与えます。 悪くはありませんが、小さな問題があります-C開発者はこれらの32個の関数を手動で作成する必要があります。すべてのオプションを試して間違いを犯す必要はありません。 10個のフィールドを持つテーブルに対して同様のソリューションが必要な場合、1024個の関数を作成する必要があります。 一般的に、コードを完成させるときはおとぎ話にすぎません！
さらに、文字列
char[]
strcmp()
介し
char[]
比較
char[]
など、重要な比較を行うタイプフィールドを追加するときに混乱が生じます。 C ++では、オーバーロードされた比較演算子を使用してカスタムタイプを作成することでこれを解決します。 （C ++の基本型の演算子はオーバーロードできません-演算子パラメーターの1つはユーザークラスでなければなりません。）
また、C ++で必要な数の最適化された関数を自動的に作成するタスクは、テンプレートを展開することで簡単に解決できます。
これはCとランタイムで完全に解決でき、コンパイル時に最適化された32〜1024個の関数をブロックする必要がないように思えるかもしれません。 条件5の数に等しい数の関数へのポインターの配列を作成し、各検索でこの検索クエリに使用される条件を持つ関数のみで各配列を埋めましょう。 最後に、1（true）を返す関数へのポインターを追加します。 そして、これらの各関数は、それ自体と同じ型の関数の配列へのポインターと、呼び出される次の関数のインデックスを受け取ります。 残念ですが、この場合、関数は埋め込まれず（インライン）、関数呼び出しは条件分岐との比較よりも速くありません。
Cのこのランタイムソリューションの作業バージョンは次のとおりです。GitHub.com
MSVCでわかるように、速度は74ミリ秒から84ミリ秒に低下しました。 また、GCCではさらに最大117ミリ秒です。 Cでは、このような最適化は不可能ですが、多数の関数を作成することによる最適化のみが可能です。
3. C ++でのソリューション
テンプレートのプロモーションは、あるテンプレートのインスタンス（インスタンス化）を別のテンプレートで作成し、テンプレートパラメーターの値を作成者の値よりも1つ小さくすることによって実行されます。 また、パラメーター値が0のテンプレートの場合、何もしない空の特殊化を作成します。 その結果、パラメーターNを使用してテンプレートのプロモーションをインスタンス化すると、N-ツイストされていないテンプレートのインスタンスが取得されます。各インスタンスでは、コンストラクターまたは次のテンプレートインスタンスを呼び出す
inline
ステートメントが呼び出されます。 このプロモーションでは、テンプレート関数とテンプレートクラスの両方が参加できます。
テンプレート自体のロジックからプロモーションを取得するには、テンプレートプロモーションクラスを作成します。 1つのパラメーターを使用すると、ツイストを解除する必要がある数が使用され、2番目のパラメーターを使用すると、ツイストを解除する必要があるテンプレートが使用されます。
// The templated constructor of unrolling of the class (no return, mandatory call to the constructor, called once) template<unsigned unroll_count, template<unsigned> class T> struct T_unroll_constructor { T_unroll_constructor<unroll_count-1, T> next_unroll; T<unroll_count-1> functor; template<typename T1> inline T_unroll_constructor(T1 & val1) : next_unroll(val1), functor(val1) {} }; // End of unroll template<template<unsigned> class T> struct T_unroll_constructor<0, T> { template<typename T1> inline T_unroll_constructor(T1 &) {} }; // -------------------------------------------------------------------------
次に、基本抽象検索クラスを作成します。 テンプレートの子クラスを継承します。このクラスは、テンプレートパラメータで32ビットの
unsigned int
値を受け取ります。各ビットは、対応するフィルタを使用するかどうかを意味します。
// Abstract base class of filters for each search variant (range_filters) struct T_filter { // search virtual size_t search(T_cash_account_row const*const __restrict array_ptr, const size_t c_array_size, T_cash_account_row *const __restrict result_ptr, T_range_filters const*const __restrict range_filters) = 0; }; // ------------------------------------------------------------------------- // The filters for each search variant (range_filters) template<unsigned index_pred> struct T_custom_filter : T_filter { inline unsigned char test_predicate(T_cash_account_row const*const __restrict row, T_range_filters const*const __restrict range_filters) { return (!(index_pred & 1<<amount_of_money_e) || (row->amount_of_money >= range_filters->begin.amount_of_money && row->amount_of_money <= range_filters->end.amount_of_money)) && (!(index_pred & 1<<gender_e) || (row->gender >= range_filters->begin.gender && row->gender <= range_filters->end.gender)) && (!(index_pred & 1<<age_e) || (row->age >= range_filters->begin.age && row->age <= range_filters->end.age)) && (!(index_pred & 1<<code_e) || (row->code >= range_filters->begin.code && row->code <= range_filters->end.code)) && (!(index_pred & 1<<height_e) || (row->height >= range_filters->begin.height && row->height <= range_filters->end.height)); } // ------------------------------------------------------------------------- // search virtual size_t search(T_cash_account_row const*const __restrict array_ptr, const size_t c_array_size, T_cash_account_row *const __restrict result_ptr, T_range_filters const*const __restrict range_filters) final { size_t result_size = 0; size_t i; // loop index for(i = 0; i < c_array_size; ++i) { if(test_predicate(array_ptr + i, range_filters)) result_ptr[result_size] = array_ptr[i], ++result_size; } return result_size; } }; // -------------------------------------------------------------------------
なぜなら テンプレートパラメータ
index_pred
と列挙型
amount_of_money_e, gender_e …
コンパイル段階で既知であり、コンパイラは常にtrueのようにいくつかの条件を
amount_of_money_e, gender_e …
ます。 実際、コンパイラーによるプログラムの最適化を支援しています。 これはこれで最も重要な決定です！
次に、このテンプレートの子クラス
template<unsigned index_pred> struct T_custom_filter
32クラスに
template<unsigned index_pred> struct T_custom_filter
されるかを示します。 それぞれのオブジェクトを32個作成し、それらのベース型のポインターを静的配列
std::array<>
保存しましょう。 実行時には、検索条件に応じて、目的のオブジェクトを多態的に参照します。
class T_optimized_search { // unroll tamplates template<unsigned index_pred> struct T_unroll_find { template<typename T> T_unroll_find(T &filters) { filters[index_pred].reset( new T_custom_filter<index_pred>() ); } }; // ------------------------------------------------------------------------- // Get index of T_test_pred version for current search range inline unsigned get_index_pred(T_range_filters const*const __restrict range_filters) { unsigned result = 0; for(size_t i = 0; i < last_e; ++i) result |= range_filters->use_filter[i]?(1<<i):0; return result; } std::array<std::unique_ptr<T_filter>, 1<<last_e> filters; T_unroll_constructor< 1<<last_e, T_unroll_find> fill_filter; public: T_optimized_search() : fill_filter(filters) {} // C++ optimized search inline size_t search(T_cash_account_row const*const __restrict array_ptr, const size_t c_array_size, T_cash_account_row *const __restrict result_ptr, T_range_filters const*const __restrict range_filters) { auto const& filter = filters[get_index_pred(range_filters)]; return filter->search(array_ptr, c_array_size, result_ptr, range_filters); } }; // -------------------------------------------------------------------------
ここで、
unsigned get_index_pred((T_range_filters const*const __restrict range_filters)
は、指定された
range_filters
検索条件データに必要な検索オブジェクトのインデックス番号を返します。
Cのソリューションと同じ方法で使用されます。
T_optimized_search optimized_search; // C++ optimized search result_size = optimized_search.search(array_ptr, c_array_size, result_ptr, &range_filters);
これは、Cの2つの
test_predicate
関数の逆
test_predicate
コードと、MSVC11（MSVS 2012）でコンパイルされたC ++で最適化された逆アセンブラコードの比較です
test_predicate
表示すると違いがはっきりと見えます： GitHub.comの diffリンク
15個の比較のうち、9個が検索条件の下で実行され、cmpアセンブラコマンドの4個の比較のみが残っていることがわかります。
「TortoiseDiffからの不満の写真と私のコメント」
実際、テンプレートの助けを借りて、各フィルターを使用するためのテストの外側にループから出ました。 ループ内では、コンパイル時に既知の
use_filter[]
フィルターを使用する値を取得しました。これにより、コンパイラーは最適化中にそれらを除外できます。 つまり この最適化は、サイクルから外部への計算またはチェックの削除の同様のすべてのケースに適用できます。
C ++の例では、*const
定数ポインタを使用して関数にパラメータを渡すCスタイルの方法を使用したため、CとC ++の差分では、議論中の最適化のみに影響する変更が表示されます。 ただし、C ++スタイルのインターフェイスを使用すると、関数は＆リンクを介してパラメーターを取得できるため、*の後にconst
を忘れる可能性がなくなり、これはやや短くなります。 ただし、 Google C ++スタイルガイドでは、不変のパラメーターをconst&
constantリンクで渡し、mutableを定数ポインター*const
渡すことを推奨しています。 コードがこのスタイルで記述されている場合、別の関数に渡される変数の変更（または変更ではない）を完全に制御できます。 値渡しする場合
void func(int const& a, int *b) {} // function of other developer in Google C++ Style int* a = new int(1); int b = 2; func(*a, b);
コンパイラーは、関数がパラメーターを変更したいというエラーをスローします。 これは、TDDテストを介して開発する場合、外部テスト呼び出しがインターフェイス形式を厳密に設定する場合に特に重要です。この場合、外部テストでのそのような呼び出しは、b-変更できないことを関数開発者に伝えます。
そして、ポインターを渡す（またはアドレスを取得する）場合：
void func(int const& a, int *b) {} // function of other developer in Google C++ Style int* a = new int(1); int b = 2; func(*a, &b);
エラーなしでコンパイルします。 また、関数呼び出しからでも、関数によって変数b
が変化せず、変数b
が変化することは明らかです。 また、TDDの場合、開発者はb
をポインタで取得する必要があるため、変更する必要があるという事実について話します。 そしてa
彼は定数の参照または値によって受け入れなければならず、その外部の値を変更することはできません。
しかし、リンクがないCでは、このアプローチは不可能です。 関数が常にポインターによってのみ受け入れる場合、呼び出し側では、それらが変更できないことを保証することは不可能であり、ユーザー型変数の値の受け渡しには大きなオーバーヘッドが発生する可能性があります。
4.結論
C ++でのこのソリューションの完全に機能するバージョンを次に示します。GitHub.com
GCC4.7.2で–O3 –march = native、CPUCore i5 K750キー、およびexeファイルサイズが74Kの場合、結果は次のようになります。
生成された行：10,000,000
C ++-検索中...
C ++-最適化された検索には0.061000秒かかりました。
見つかった行：38
C検索...
C-searchには0.089000秒かかりました。
Cより高速なC ++：1.459016回
見つかった行：38
キー/ O2 / Ob2 / Oi、CPU Core i5 K750、および138Kのexeファイルのサイズを持つMSVC11（MSVS2012）では、結果は次のようになります。
生成された行：10,000,000
C ++-検索中...
C ++-最適化された検索には0.056000秒かかりました。
見つかった行：38
C検索...
C-searchには0.074000秒かかりました。
Cより高速なC ++：1.321429回
見つかった行：38
ご覧のとおり、実行時間は74ミリ秒から56ミリ秒に短縮されました。 速度が1.3倍になりました。 原則として、悪くはありません。
たった1.3倍？ また、フルパス検索の3.5〜5.3倍の高速化についてはどうでしょうか。
結論-コンパイル時にコンパイラーが知っているほど、プログラムを最適化できるようになります。 そして、これにおいて、テンプレートは彼を他の何にも比して助けます。
ところで、この最適化はJavaおよびC＃には適用されません。 ジェネリックでは、型ではなく値を持つパラメーターを使用することはできません。
次の記事では、 3.5〜5.3の高速化を実現し、インデックスを使用しないハードコアソリューションです。 ただし、このソリューションはインデックス検索でさらに使用されます。