前の記事で、検索を1.3倍高速化することができました： GitHub.com
言語構成を簡単に説明することはしませんが、実際のタスクの段階の1つを解決するときのC ++の利点を示します。
私たちはまだMSVC11（MSVS2012）とGCC 4.7.2でクロスプラットフォームを記述し、それらでCを使用し、部分的に実装された標準C ++ 11です。
わかりやすくするために、インデックス検索なしで記述していますが、このソリューションは後でインデックス検索で使用されます。
1. C ++のハードコアソリューション
これは、Cで本当にハードコアなソリューションのように見えたはずです。これは、C開発者にとって残念なことに、3840の関数を作成し、どこでも間違いを犯さないためです。 C開発者はそれらを記述しますが、私たちはそれらを非常に敬意を持って扱い、C ++コンパイラがこれらの3840関数をどのように記述できるかを示します。 彼はそれを迅速に行いませんが、C開発者が書くよりも桁違いに速く正確に行います。
非常に簡単です。DBMSの理論では、述語の
selectivity
（
selectivity
）-条件（述語）の1つに応じた適切なテーブル行の割合などがあります。 条件の選択性が低いほど、それを比較する必要が早くなり、ラインが適合しないことがすぐにわかります。 つまり 以下の条件下で比較を取り除きます。
実際のDBMSでは、このために、オプティマイザーは統計を収集し、データ配布スケジュールに応じて選択度を計算するために必要な式を選択します。 今日は、フィールドの列挙を使用した離散数学と組み合わせ論で十分であると思うので、簡単にするために、データの一様分布の計算からカーディナリティーの選択性を検討します。 （列のカーディナリティーは、列内の固有値の割合です。）
選択性（行数）は次と等しくなります：
selectivity = c_array_size * (1 + field.end – field.begin) / cardinality;
配列のサイズと均等に分散されたデータのカーディナリティは、コンパイルの段階でわかっています。 また、実行時に各フィールドの検索条件の境界を取得し、選択性を計算します。
次に、選択度が小さい順にフィールドを選択します。 また、選択したフィールド番号の順序に応じて、最適な関数の数値インデックスを作成し、それを呼び出して検索します。
検索条件のバリアントごとに最適化された関数、または多態性クラスは、2つのネストされたテンプレートの巻き戻しで生成します。
- 検索条件の存在に関するすべてのオプションを列挙する（ 以前のC ++ソリューションと同様 ）
- 検索語の順序に関するすべてのオプションを列挙する
合計で、
(2^5)*5! = 32*120 = 3840
配列が作成され、読み込まれ
(2^5)*5! = 32*120 = 3840
(2^5)*5! = 32*120 = 3840
オブジェクトで、実装は異なりますが、共通の基本抽象祖先があります。
1つのフィールドの範囲チェックは常に一緒に行われます。 コンパイル時間を遅らせないために、1つのフィールドの最小値と最大値の検証を個別に交換したり、交換したりしません。
次に、コードがどのように見えるかを見てみましょう。
2.依存関係を減らす
まず、ソリューションを実装するには、テンプレートcompile-time-gettersを介して文字列のフィールドへのアクセスを実装する必要があります。 また、依存関係を軽減する素晴らしいボーナスも追加されます。コード内のフィールドのタイプと数の変更は、
T_cash_account_row.
行の構造のみに影響し
T_cash_account_row.
検索クラスのインターフェースは変更されず、テンプレート検索クラスをインスタンス化することにより、任意のテーブルでの検索の実装が実行されます。
これは、フィールドを持つ行構造のコードのようになります。
/* Row */ struct T_cash_account_row { // Fields: enum T_field_enum { amount_of_money_e, gender_e, age_e, code_e, height_e, /*<<<<<- add fields here (with index) */ last_e /*<<<<<- add included fields here (without index) */ }; static_assert(last_e > 0, "Number of indexed fields in enum of T_cash_account_row must be greater than 0!"); unsigned code:20; // 0 - 1000000 unsigned gender:1; // 0 - 1 unsigned age:7; // 0 - 100 unsigned amount_of_money:20; // 0 - 1000000 unsigned height:9; // 0 – 300 // Get field value template<int field_enum> inline typename std::enable_if<field_enum == code_e, decltype(code)>::type get_field_value() const { return code; } template<int field_enum> inline typename std::enable_if<field_enum == gender_e, decltype(gender)>::type get_field_value() const { return gender; } template<int field_enum> inline typename std::enable_if<field_enum == age_e, decltype(age)>::type get_field_value() const { return age; } template<int field_enum> inline typename std::enable_if<field_enum == amount_of_money_e, decltype(amount_of_money)>::type get_field_value() const { return amount_of_money; } template<int field_enum> inline typename std::enable_if<field_enum == height_e, decltype(height)>::type get_field_value() const { return height; } template<int field_enum> inline typename std::enable_if<field_enum == last_e, bool>::type get_field_value() const { return true; } static_assert(5 == last_e, "Add/delete new field-case and correct this assert!"); }; /* ----------------------------------------------------------------------- */
enum T_field_enum
、デフォルトでは常に0から始まる昇順の値を持ちます（ C ++ 03 7.2列挙型宣言 ）。
#include <type_traits>
ライブラリの
std::enable_if<>
を使用すると、特定のテンプレートパラメータ値に対してのみ関数/クラスのインスタンスを受け取ることができます。 そうでない場合、インスタンス化中に置換エラーが発生し、 SFINAE（substitution-failure-is-not-an-error）の原則に従って、置換エラーが発生すると、コンパイルエラーは発生せず、関数インスタンスは単に作成されません。 標準の詳細（ C ++ 03 14.8.2テンプレート引数の推論 ）。
これは、たとえば次のように、getterテンプレートパラメータを介してさまざまなタイプの必要なフィールドにアクセスするために必要です。
auto code = row->get_field_value<T_cash_account_row::code_e>();
この場合、5つのフィールドはすべて同じタイプであり、
std::enable_if<>
なしでも実行できますが、先に考えます。 私の例では、5つのフィールドのいずれかのタイプを変更でき、ゲッターはコンパイルして正常に動作します。 テンプレート関数の特殊化によってそれらを作成した場合、異なるタイプにアクセスするとエラーが発生するとします。たとえば、このようなコードはコンパイルされません。
/* Row */ struct T_cash_account_row { // Fields: enum T_field_enum { amount_of_money_e, gender_e, age_e, code_e, height_e, /*<<<<<- add fields here (with index) */ last_e /*<<<<<- add included fields here (without index) */ }; static_assert(last_e > 0, "Number of indexed fields in enum of T_user_row must be greater than 0!"); unsigned code:20; // 0 - 1000000 unsigned gender:1; // 0 - 1 unsigned age:7; // 0 - 100 unsigned amount_of_money:20; // 0 - 1000000 int height; // 0 – 300 // Get field value template<int field_enum> inline unsigned get_field_value(); template<int field_enum> inline int get_field_value(); static_assert(5 == last_e, "Add/delete new field-case and correct this assert!"); }; template<> inline unsigned T_cash_account_row::get_field_value<T_cash_account_row::code_e>() { return code; } template<> inline unsigned T_cash_account_row::get_field_value<T_cash_account_row::gender_e>() { return gender; } template<> inline unsigned T_cash_account_row::get_field_value<T_cash_account_row::age_e>() { return age; } template<> inline unsigned T_cash_account_row::get_field_value<T_cash_account_row::amount_of_money_e>() { return amount_of_money; } template<> inline int T_cash_account_row::get_field_value<T_cash_account_row::height_e>() { return height; } template<> inline unsigned T_cash_account_row::get_field_value<T_cash_account_row::last_e>() { return 1; } /* ----------------------------------------------------------------------- */ int main() { T_cash_account_row *row = new T_cash_account_row; auto code = row->get_field_value<T_cash_account_row::code_e>(); return 0; }
コンパイラは、
get_field_value<>()
関数のあいまいな呼び出しに関するエラーを自然にスローします。 Ideone.com
このバージョンは問題なくコンパイルされます： ideone.com
ゲッターで正しくなりました。今度は、前の記事のプロモーションに似たテンプレートの展開を使用しますが、コンストラクターではなくファンクターに使用します（ファンクターは、演算子呼び出し
operator()(…)
オーバーロードされたクラス
operator()(…)
）：
// The templated functor of unrolling of the input templated functor (reusable) template<unsigned unroll_count, template<unsigned> class T> struct T_unroll_functor { T_unroll_functor<unroll_count-1, T> next_unroll; T<unroll_count-1> functor; template<typename T1, typename T2> inline bool operator()(T1 const& val1, T2 const& val2) { return next_unroll(val1, val2) && functor(val1, val2); } }; // End of unroll template<template<unsigned> class T> struct T_unroll_functor<0, T> { template<typename T1, typename T2> inline bool operator()(T1 const&, T2 const&) { return true; } }; // -------------------------------------------------------------------------
このプロモーションでは、
last_e
列挙の値とテンプレートゲッターを介したフィールドへのアクセスに基づいて、各フィールドの比較を拡張します。
そして、次のようにファンクター
struct T_test_pred
をデプロイします。
// The filters for each search variant (range_filters) template<typename T_row, unsigned index_pred> struct T_custom_filter : T_filter<T_row> { // Test predicates functor for unrolling template<unsigned field_num> struct T_test_pred { bool inline operator()(T_row *const __restrict row, T_range_filters *const __restrict range_filters) const { typedef typename T_row::T_field_enum T_field_enum; // Without fields where use_filter==0 return ( T_filter<T_row>::template T_get_use_filter<index_pred, field_num>::value || (row->template get_field_value<static_cast<T_field_enum>(field_num)>() >= range_filters->begin.template get_field_value<static_cast<T_field_enum>(field_num)>()&& row->template get_field_value<static_cast<T_field_enum>(field_num)>() <= range_filters->end.template get_field_value<static_cast<T_field_enum>(field_num)>()) ); } }; // ----------------------------------------------------------------------- // search virtual size_t search(T_row *const __restrict array_ptr, const size_t c_array_size, T_row *const __restrict result_ptr, T_range_filters *const __restrict range_filters) final { size_t result_size = 0; size_t i; // loop index T_unroll_functor<T_row::last_e, T_test_pred> test_predicate; 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; } }; // -------------------------------------------------------------------------
また、クラス
T_filter<>, T_custom_filter<> T_optimized_search<>
では、テーブル行タイプが渡されるテンプレートパラメーター
T_row
れ
T_row
ことに
T_row
T_cash_account_row
。この場合は
T_cash_account_row
です。
これで、テーブルフィールドの数、名前、およびタイプのすべての変更が
T_cash_account_row
内に排他的に集中し、検索コード全体がテンプレートクラスから自動的に生成されます。目的の行のタイプでテンプレートをインスタンス化するだけです。
T_optimized_search<T_cash_account_row> optimized_search; // C++ optimized search
結果の作業コードへのリンクは次のとおりです。GitHub.com
この例は、コードの重要な領域でチームリーダーおよびパフォーマンスアーキテクトがモジュールの外部インターフェイスだけでなく、これらのインターフェイスを介して送信されるオブジェクトのタイプにも注意を払う必要がある理由を明確に示しています。 私たちの場合、これらは
T_cash_account_row T_range_filters
です。
T_cash_account_row
テンプレートゲッターを介してパラメーターを渡す機能を設定した
T_cash_account_row
、テンプレートのプロモーションを通じてモジュールの開発者によるより柔軟な実装、およびTDDテストによる開発手法を使用する場合のテストのより柔軟な実装を事前に決定します。
コンパイラーMSVC11（MSVS2012）およびCPU Core i5 K750の1つのコアでは、結果は次のようになります。
生成された行：10,000,000
C ++-検索中...
C ++-最適化された検索には0.056000秒かかりました。
見つかった行：38
C検索...
C-searchには0.074000秒かかりました。
Cより高速なC ++：1.321429回
見つかった行：38
ご覧のとおり、C ++コードはCコードの1.3倍高速であり、結果の
test_predicate
関数の
test_predicate
コードは以前のC ++バージョンtest_pradicate_enum_cpp.asmと同じです。
「TortoiseDiffからの不快な画像」
しかし、今ではすべての変更を1か所に集中しているため、この検索モジュールの使用が非常に容易になります。
さらに、別のより生産的な最適化のためにコードを準備しました。
3. 3.5〜5.3倍の加速
コンパイル時の計算や、たとえばテンプレートでの素数の検索が考慮されている C ++に関する記事が頻繁にあります。 記事は興味深いものですが、著者自身が気づいているように、「まったく役に立たないことをする方法を教えます」。
コンパイル時の計算とテンプレートを使用した最適化から顕著な検索高速化を実現する方法を説明します。
3.1単純なテンプレート計算
必要なもののうち最も単純なものから始めましょう。コンパイル時の階乗計算を実装します：
template <unsigned N> struct factorial : std::integral_constant<unsigned, N * factorial<N-1>::value> {}; template <> struct factorial<0> : std::integral_constant<unsigned, 1> {};
要素数が
(2^5)*5! = 3840
静的配列
std::array<>
を作成するには、階乗計算が必要
(2^5)*5! = 3840
(2^5)*5! = 3840
。
離散数学と組み合わせ論から、一意の要素の異なる順列の数は、それらの数の階乗に等しいことが知られています。 また、要素の存在に関するオプションの数は、要素の数の程度で2です。 （もちろん、欠落している要素がどのように再配置されるかは絶対に重要ではありません。余分なオプションがないとコンパイルが速くなる可能性がありますが、この記事はできる限り簡素化するよう努めています。）
次に、構造内でどのような最適化が行われるかを見てみましょう
インスタンス化時に
struct T_custom_filter
します。
まず、
index_order
パラメーターも受け入れるようになりました。 次に、検索のねじれのないファンクターが変更されました。
// The filters for each search variant (range_filters) template<typename T_row, unsigned index_pred, unsigned index_order = 0> struct T_custom_filter : T_filter<T_row> { // Test predicates functor for unrolling template<unsigned field_num> struct T_test_pred { bool inline operator()(T_row *const __restrict row, T_range_filters *const __restrict range_filters) const { typedef typename T_row::T_field_enum T_field_enum; // Without fields where use_filter==0 enum { ordered_field_number = T_filter<T_row>::template T_number_field<index_order, field_num>::value }; return ( T_filter<T_row>::template T_get_use_filter<index_pred, ordered_field_number>::value || (row->template get_field_value<static_cast<T_field_enum>(ordered_field_number)>() >= range_filters->begin.template get_field_value<static_cast<T_field_enum>(ordered_field_number)>() && row->template get_field_value<static_cast<T_field_enum>(ordered_field_number)>() <= range_filters->end.template get_field_value<static_cast<T_field_enum>(ordered_field_number)>()) ); } }; // ----------------------------------------------------------------------- // search virtual size_t search(T_row *const __restrict array_ptr, const size_t c_array_size, T_row *const __restrict result_ptr, T_range_filters *const __restrict range_filters) final; }; // -------------------------------------------------------------------------
前と同様に、
T_get_use_filter
テンプレートは、指定されたindex_predインデックスの
number_filter
フィールドでフィルターを使用する（または使用しない）ためのフラグを返します。
// whether to use the filter for a given predicate? (strictly at compile time) template <unsigned index_pred, unsigned number_filter> struct T_get_use_filter : std::integral_constant<bool, !(index_pred & 1<<number_filter)> {};
T_number_field<>
テンプレートから、
index_order
フィールドと
field_num
のフィールド番号を比較するためのインデックスに基づいて、ゲッター
get_field_value<static_cast<T_field_enum>(ordered_field_number)>()
から値を取得するためにフィールド番号
ordered_field_number
を取得します。
3.2より複雑なテンプレート計算
今より難しい。 テンプレートクラス
T_number_field<>
フィールド順序の計算を実装します。 フィールド順序インデックス
index_order
は次のように生成されます-たとえば、5つのフィールドのインデックスは次の式を使用してコンパイルされます。
index_order = field0 + 5*field1 + 5*4*field2 + 5*4*3*field3 + 5*4*3*2*field4;
field1
フィールド番号（5つのうち使用可能）。比較するときに最初に来る。 field2-0から3（残りの4つのうち）のフィールド番号、比較時に2番目に来る; ...; field5は、最後に来る0から0（残りの1番目から）までのフィールドの番号です。 常に0であるため、省略できます。
index_order = field0 + 5*field1 + 5*4*field2 + 5*4*3*field3;
または、同じです：
index_order = field0 + 5*(field1 + 4*(field2 + 3*(field3)));
誰かがindex_orderの値を計算システムの可変基数を持つ数値として表現する方が簡単かもしれません
field0
は基数5の最初の数字（5値0〜4を取ることができます）、
field1
は基数4の2桁目です（4値0を取ることができます） -3）など。 したがって、（5！）の組み合わせでは、任意のフィールド順列をエンコードできます。 理解を深めるために、確率論の基礎または離散数学からの検索に慣れることをお勧めします。
視覚的には、これは次のように表すことができます。カッコ（）は利用可能な最低優先度値（最高優先度）を示し、正方形[]-利用可能からの番号、およびカーリー{}-フィールドの実数。 たとえば、最初は次の優先順位を持つ5つのフィールドがあります：5、3、1、2、4
フィールド番号：0 1 2 3 4
比較優先度：5 3（1）2 4-[2]-現在のフィールド番号（field0）{2}
比較優先度：5 3（2）4-[2]-現在のフィールド番号（field1）{3}
比較優先度：5（3）4-[1]-現在のフィールド番号（field2）{1}
比較優先度：5（4）-[1]-現在のフィールド番号（field3）{4}
比較優先度：（5）-[0]-現在のフィールド番号（field4）{0}
index_order = field0 + 5*(field1 + 4*(field2 + 3*(field3)));
インデックス値を取得します：
index_order = 2 + 5*(2 + 4*(1 + 3*(1))) = 92;
後で、ランタイム関数
T_optimized_search::get_index_order().
これがどのように実装されるかを示します
T_optimized_search::get_index_order().
現在、昇格の結果、このインデックスはコンパイル段階で認識され、逆の問題は、コンパイル時に各フィールドのシリアル番号を取得する方法です。
最初に、角括弧[]で数値を取得する方法を学びます。 特定の場合、「現在のフィールド番号」は、
index_order = 2 + 5*(2 + 4*(1 + 3*(1))) = 92
した
index_order = 2 + 5*(2 + 4*(1 + 3*(1))) = 92
について
index_order = 2 + 5*(2 + 4*(1 + 3*(1))) = 92
ように見つかります。
field0 = index_order％5 = 92％5 = 2; field1 =（index_order / 5）％4 =（92/5）％4 = 2; field2 =（index_order /（5 * 4））％3 =（92/5 * 4）％3 = 1; field3 =（index_order /（5 * 4 * 3））％2 =（92/5 * 4 * 3）％2 = 1; field4 = 0;
コンパイル時に、次のテンプレートクラスがこれを行います。
// Get the sequence number the remaining field for the number_filter, after removal of all previous template <unsigned index_order, unsigned number_filter, unsigned index = T_row::last_e> struct T_number_remaining_field : std::integral_constant<unsigned, T_number_remaining_field<index_order / index, number_filter - 1, index - 1>::value> {}; // End of unroll template <unsigned index_order, unsigned index> struct T_number_remaining_field<index_order, 0, index> : std::integral_constant<unsigned, index_order % index> {}; // -------------------------------------------------------------------------
そして、number_filterに等しい「現在のフィールド番号」の値を取得し、この方法でテンプレートをインスタンス化します
T_number_remaining_field<index_order, number_filter>::value
。
混乱する瞬間があります：誰かが（
number_filter=0
）でそれを考えるかもしれません。
T_number_remaining_field<index_order, 0>::value
2つのパラメーターを持つ
T_number_remaining_field<index_order, 0>::value
部分的な特殊化がすぐに呼び出されます。
template <unsigned index_order, unsigned index> struct T_number_remaining_field<index_order, 0, index>
index_order
置き換えられ、0は
index
置き換えられ
index
。 しかし、これはそうではありません！
標準（ C ++ 03 14.8.2テンプレート引数の推論 ）によれば、最初に、デフォルト値は
index = T_row::last_e
あり、実際、インスタンス化は
T_number_remaining_field<index_order, 0, T_row::last_e>::value
。 そして、専門へのアピールがあります。
template <unsigned index_order, unsigned index> struct T_number_remaining_field<index_order, 0, index>
また、5つのフィールドの現在のゼロフィールド番号（
T_row::last_e=5
）の場合、必要に応じて
index_order % 5
を取得し
index_order % 5
。
角括弧内の「現在のフィールド番号」を見つける方法を実装しました。 次に、中括弧{}で囲まれたフィールドの実際のフィールド番号の受信を実装する必要があります。
視覚的な表現からわかるように、角括弧[]内の「現在のフィールド番号」は、中括弧{}内の実際のフィールド番号と必ずしも一致しません。 番号の付いたカードのデッキが下から上へ昇順で並んでいると想像すると、最初はそれらの番号はデッキ内の順序と一致します。 しかし、真ん中からカードを取り出すと、それらの上にあるカードは、毎回デッキのユニット番号を実際の番号に比べて減らします。
私たちの場合、これにより、実数と優先順位の値がより低い実数{}および優先順位値（）（以前に削除されたより高い優先順位）を持つすべてのフィールドが、「現在のフィールド値」[]もっと。 このようなオフセットは、次のテンプレートクラスによって計算されます。
// Get 1 or 0 offset if current_field (for number_filter) affect to number_field template <unsigned index_order, unsigned number_filter, unsigned number_field> struct T_offset { enum { current_field = T_number_remaining_field<index_order, number_filter>::value, value = (current_field <= number_field)?1:0 }; }; // Get offset of number_field (enum in row-type) for number_filter template <unsigned index_order, unsigned number_filter, unsigned number_field> struct T_offset_number_field { enum { offset = T_offset<index_order, number_filter-1, number_field>::value, value = T_offset_number_field<index_order, number_filter-1, number_field + offset>::value + offset }; }; // End of unroll template <unsigned index_order, unsigned number_field> struct T_offset_number_field<index_order, 0, number_field> : std::integral_constant<unsigned, 0> {};
最後に、次のテンプレートクラスで実際のフィールド番号を取得します。
// (Main) Get number of field (enum in row-type) for number_filter template <unsigned index_order, unsigned number_filter> struct T_number_field { enum { remaining_field = T_number_remaining_field<index_order, number_filter>::value, value = remaining_field + T_offset_number_field<index_order, number_filter, remaining_field>::value }; }; // -------------------------------------------------------------------------
できた
3.3ネストされたテンプレートのプロモーション
ここで、検索フィールドの存在とその順序でフィルターテンプレート
T_custom_filter<>
をインスタンス化する必要があります。 これを行うには、ネストされたテンプレートプロモーションを使用します。
template<typename T_row> class T_optimized_search { // unroll tamplates template<unsigned index_pred> struct T_unroll_find { template<unsigned index_order> struct T_unroll_order { template<typename T> T_unroll_order(T &filters) { filters[index_pred + index_order*(1<<T_row::last_e)].reset( new T_custom_filter<T_row, index_pred, index_order>() ); } }; T_unroll_constructor<factorial<T_row::last_e>::value, T_unroll_order> fill_ordered_filter; template<typename T> T_unroll_find(T &filters) : fill_ordered_filter(filters) {} }; // ------------------------------------------------------------------------- std::array<std::unique_ptr<T_filter<T_row>>, (1<<T_row::last_e)*factorial<T_row::last_e>::value> filters; T_unroll_constructor< 1<<T_row::last_e, T_unroll_find> fill_filter; public: T_optimized_search() : fill_filter(filters) {} // C++ optimized search inline size_t search(T_row *const __restrict array_ptr, const size_t c_array_size, T_row *const __restrict result_ptr, T_range_filters *const __restrict range_filters) { auto const& filter = filters[T_filter<T_row>::get_index_pred(range_filters) + T_filter<T_row>::get_index_order(range_filters)*(1<<T_row::last_e)]; return filter->search(array_ptr, c_array_size, result_ptr, range_filters); } }; // -------------------------------------------------------------------------
ここでは、フィールド比較の存在のコンパイル時プロモーション
struct T_unroll_find<>
を使用し、その内部でフィールド比較の順序のプロモーションを使用しました
struct T_unroll_order<>
。
また、検索関数では
get_index_pred()
、フィールドを比較する必要性に応じてインデックスを取得するランタイム関数
get_index_order()
と、フィールドを比較するために必要な順序に応じてインデックスを取得するランタイム関数を使用します。
最初の機能は同じままです。
// Get index of T_test_pred version for current search range static inline const unsigned get_index_pred(T_range_filters *const __restrict range_filters) { unsigned result = 0; for(size_t i = 0; i < T_row::last_e; ++i) result |= range_filters->use_filter[i]?(1<<i):0; return result; } // -------------------------------------------------------------------------
そして2番目が追加されました
get_index_order()
。まず、
struct T_cash_account_row
関数が文字列の構造に現れていることを明確にします
get_bitf_size()
-カーディナリティを取得するために（この形式で、スイッチ/ケースを介さずに、constexpr、つまりコンパイル時として機能できますが、MSVC11はまだサポートしていません）：
/* Row */ struct T_cash_account_row { ... // Get cardinality template<int field_enum> // constexpr // not supported in the MSVS2012(MVCC11) static inline const unsigned int get_bitf_size() { return (field_enum == gender_e)? 1: (field_enum == age_e)? 100: (field_enum == height_e)? 300: (field_enum == code_e)? 1000000: (field_enum == amount_of_money_e)?1000000: 0; static_assert(5 == last_e, "Add/delete new field-case and correct this assert!"); } };
もう一度、選択性の式（行数）を思い出します：
selectivity = c_array_size * (1 + field.end – field.begin) / cardinality;
そして、フィールドの比較の順序に応じて、コンストラクターのテンプレートプロモーションを使用して各条件/フィールドの選択性を計算するインデックス自体を取得する機能：
// The unrolling filling of selectivity in a compile-time template<unsigned field_num> struct T_selectivity_fill { T_selectivity_fill(std::map<unsigned, unsigned> *const __restrict ordered_filters, T_range_filters *const __restrict range_filters) { // selectivity for each field-filter const unsigned selectivity = range_filters->use_filter[field_num]? ((1 + range_filters->end.template get_field_value<field_num>() - range_filters->begin.template get_field_value<field_num>() )*c_array_size / T_row::template get_bitf_size<field_num>()) // cardinality :c_array_size; ordered_filters->insert(std::make_pair(field_num, selectivity)); } }; // Get index of T_test_pred version for current search range static inline const unsigned get_index_order( T_range_filters *const __restrict range_filters) { unsigned result = 0; std::map<unsigned, unsigned> ordered_filters; T_unroll_constructor<T_row::last_e, T_selectivity_fill> selectivity_fill(&ordered_filters, range_filters); unsigned multiplexor = 1; for(size_t i = 0; i < T_row::last_e; ++i) { unsigned cur_index = 0, min_index = 0; unsigned field_num = ordered_filters.cbegin()->first; unsigned min = c_array_size; for(auto const& it : ordered_filters) { if (it.second < min) min = it.second, field_num = it.first, min_index = cur_index; ++cur_index; } ordered_filters.erase(field_num); result += min_index*multiplexor; multiplexor *= (T_row::last_e - i); } return result; } // -------------------------------------------------------------------------
ここで、キー入力には
std::map<>
フィールド番号が入力され、値には想定される選択性が入力されます。次に、サイクルで最小の選択性を見つけ、対応するフィールド番号をキーから取得し、そこからレコードを削除し、
std::map<>
このフィールド番号を使用してインデックスをコンパイルします。したがって、各フィールドのループで。関数によって返されたこのインデックスが
get_index_order
数学的に取得される方法についてはすでに説明しました。
index_order = field1 + 5*(field2 + 4*(field3 + 3*(field4)));
したがって、検索テンプレートを
3840
一度巻き戻し、これらのオブジェクトで静的配列に入力し、これらの検索条件に最適化された検索関数で必要なオブジェクトのランタイムインデックスを取得することができました。
結果のアセンブラー関数コード
test_predicate
C ++の以前のバージョンと比較して変更されました-2つの比較が場所を変更し、それらの最初のものが最後になりました：github.com asm。
「TortoiseDiffからの写真」
4.テスト結果
C ++でのこのソリューションの完全に機能するバージョンは次のとおり です。GitHub.com
–O3 –march = nativeスイッチ、CPU Core i5 K750、およびexeファイルサイズ1.3MBのGCC4.7.2では、結果は次のようになります。
生成された行：10000000
C ++-検索...
C ++-最適化された検索には0.017000秒かかりました。
見つかった行：38
C-Searching ...
C-searchには0.090000秒かかりました。
Cより高速なC ++：5.294118回
見つかった行：38
また、キー/ O2 / Ob2 / Oi、CPU Core i5 K750、exeファイルサイズ1.42MBのMSVC11（MSVS2012）では、結果は次のようになります。
生成された行：10000000
C ++-検索中...
C ++-最適化された検索には0.021000秒かかりました。
見つかった行：38
C-Searching ...
C-searchは0.074000秒かかりました。
Cより高速なC ++：3.523809回
見つかった行：38
ご覧のとおり、ランタイムはCの74ミリ秒からC ++の21ミリ秒に低下しました。速度は3.5倍に増加しました。素晴らしい。そして、ご覧のとおり、GCCはさらに顕著な速度の違い、5.3倍を示しています。そして、これはSIMD命令やキャッシュプリフェッチとは異なり、絶対にクロスハードウェアソリューションです。プログラム実行用に最適化された1つのパスを作成するPGOとは異なり、入力データのすべての場合に最適化された3840個のパスを作成しました。
このソリューションは複雑に思えるかもしれませんが、C ++を本当に理解することの意味が明確になりました。 C ++がよくわからない場合は、Cで書くという選択肢が1つしかありません。
これは、関数ポインターの配列によってCで解決できるという疑念を払拭するために、例を挙げます。なぜなら , C , , .
C: GitHub.com
C- diff : GitHub.com
GCC4.7.2 –O3 –march=native, CPU Core i5 K750 :
Generated rows: 10000000
C-optimized-Searching…
C-optimized-search took 0.049000 seconds.
Found rows: 38
C-Searching…
C-search took 0.086000 seconds.
The C++ faster than C: 1.755102 times
Found rows: 38
また、キー/ O2 / Ob2 / Oi、CPU Core i5 K750を使用したMSVC11では、結果は次のようになります。
生成された行：10000000
C-optimized-Searching ...
C-optimized-searchは0.045000秒かかりました。
見つかった行：38
C-Searching ...
C-searchは0.074000秒かかりました。
Cよりも高速なC ++：1.644444回
見つかった行：38
Cでの最適化の結果を見ると、C ++での最適化よりも2〜3倍遅れています。
CのGCCの加速はC ++の5.3倍に対して1.8倍であり、CのMSVCの加速はC ++の3.5倍に対して1.6倍です。さらに、Cの最適化は、C ++コンパイラーによって簡単にコンパイルできますが、変更は1つもありませんが、その逆はできません。
5.結論
C ++テンプレートを使用して、コンパイル時に計算とクロスハードウェア最適化を実装し、実際のタスクで3.5〜5.3倍の加速を実現する方法を示しました。
C ++には適用できなかったCのような最適化はありません。ほぼ完全な後方互換性があります。しかし、C-C ++の唯一の代替-そのような最適化のためのテンプレート-は、数十、数百、数千の関数を書くことです-コピーアンドペーストは本当にそうです。
この最適化はJavaおよびC＃には適用できないことを思い出させてください。ジェネリックでは、パラメーターで値を使用することはできませんが、タイプのみが可能です。 JavaとC＃には他にも利点があります-それらは開発されたライブラリであり、愚かなエラーに対する保護です。
次の記事では、このタスクに最適なインデックス検索オプション、インデックスハッシュ結合とビットマップANDマルチインデックス接続がここで適切ではない理由、およびインデックス構成テーブルとインデックスオンリースキャンデータアクセス戦略を使用する必要がある理由について説明します。バイナリ検索の短所と、なぜ私たちの場合、順序付きハッシュインデックスが適しているのかを説明します。 Core i5 K750の1つのコアで毎秒0.15〜360万リクエストの速度を実現し、競合アクセスが弱く変更が少ないマルチスレッドバージョンでこれがどのように実装されるかを示します。 GPUでのこの検索を高速化し、レコードグループごとに1つのメモリバリアを備えた分散スレッド状態である将来のマルチスレッドパターンの理由を示します。次に、負荷の高いWebプロジェクトの検索問題に近づき、FastCGIとboost :: asioを使用して実装を比較します。しかし、一度にすべてではありません。