針の目を通して象を縫う方法。 最小限の時間で最大量のデータを処理する

同じJavaまたはC＃の謝罪者から、C / C ++の開発について何を聞くことができますか！ 伝えられるところでは、この言語は時代遅れであり、誰もそれについて書いていない。 ただし、待ち時間なしまたは低待ち時間のサービスを作成する必要がある場合、または大量のデータを処理するためのボトルネックのメモリと実行時間を節約する必要がある場合にのみ、「古風な」C / C ++開発者の助けにすぐに頼ります。 これらの人がメモリを手動で管理する方法を知っていて、1つまたは別の高レベルの操作のスタッフィングをよく知っているからです。 今日、私たちの仕事は、これらの人々に一歩近づくことです。

レーシングカーのボンネットの下

通常、ネットワークアプリケーションのビジネスロジックは、開発言語としてC ++を使用することを好む場所ではありません。 通常、アプリケーションクライアントとデータベースサーバー間のネットワークには、高レベルの言語が選択されます。 しかし、遅かれ早かれ、アプリケーションは、新しいサーバーを購入するよりも最適化する方が安価になるまで成長します。 この場合、C / C ++のビジネスロジックの一部の実装を、C＃、Java、Python、Ruby、またはJavaScriptの確立されたロジックに埋め込むという魅力があります。 ここで、あなたはおそらく楽しい驚きを待っています：C ++では、大量のデータを効率的に処理できる必要があります。 JavaまたはC＃のスキルは、C ++で同じコードについて記述しようとすると、すべての最適化の試みをすぐに無効にします。



事実、newの使用は可能な限り経済的である必要があり、状況にあまり適さないコンテナの不合理な使用は、実際には完全に論理的なコードを完全に不適切にします。 C ++の資格が十分でない従業員によって「最適化」が実行された後、実行時間がほぼ同じままであるか、さらに長くなる可能性があります。 誰かが手をすくめるだろうと彼らは言ったが、ここではすべてがすでに最大限に最適化されている。 誰かが高レベル言語の想像を絶するスピードを同僚に納得させようとします。 私たちの仕事は、会社のお金が無駄にならないようにすることです。 そのため、コードの重要なセクションにC / C ++を埋め込むためのリソースのコストは無駄ではないだけでなく、何度も報われています。 手をすくめて「できなかった」と言うのは専門家ではなく、不可能を求める人です。 結局のところ、それは不可能に思えるだけであり、このレッスンで複雑になるものは何もないでしょう。 必要なのは、C ++でデータを処理するときに役立ついくつかの重要なことを覚えておくことです。

慎重にツールを選択します

スコットマイヤーズの優れた本「The Effective Use of STL」を読むことができなかったなら、私はそれを強くお勧めします。 C ++でどのようなコンテナが必要かを詳細に理解していなければ、STLを使用することは雨の中でアスファルトを修理することに似ています。 基本的なヒントをいくつか紹介しますが、さまざまなコンテナの目的とメソッドのデバイスを完全に理解することが重要です。



最初に覚えておくべきことは、 `std :: vector`は配列ではなくベクトルです。 同じタイプの要素の形でメモリの連続部分を正確にベクトル化する必要がある場合は、このコンテナを使用します。 制御されていないサイズで定期的な追加と削除が必要な場合、 `std :: vector`は有用ではありません。 ビット単位のアクセスと安価なサイズの増加を伴う配列が必要な場合は、 `std :: deque`の方が良く見えます。 確かに、十分な予約メモリがない場合は、新しい連続（！）ブロックが割り当てられ、データは `std :: vector`オブジェクトの古いメモリから新しい要素ごとに転送されます。 最小限の時間で大量のデータを処理することを検討しているため、メモリを既存のオブジェクトに再割り当てすることは、CPU時間を費やしたいものではありません。



2番目の前提条件は、一意のキーと値の比を持つコンテナを慎重に選択することです。 ビッグデータの場合、おそらくすぐに `std :: unordered_map`をビルドし、できるだけ変更しないようにするのが最も簡単です。 実際には、 `std :: unordered_map`のキーを取得することは` std :: map`よりもはるかに効果的です。これも大量のデータに対して、メモリ内に膨大な数のノードを持つ赤黒ツリーを構築および維持する必要はありません。 しかし、キーと値の関係が頻繁に変更される場合（関係が削除され、新しい関係が追加され、これが非常に集中的に行われます）、 `std :: unordered_map`の内部表現を何度も再構築するよりも、` std :: map`のメンテナンスを受け入れるほうが簡単です。 実際、 `std :: unordered_map`内では、実際には、値のチェーンの配列であり、キーと値の関係を頻繁に変更するほど、効果は低くなります。 さらに高速なキー抽出では、ここであなたを救うことはできません：大きなアレイを再構築することは常に高価です。



3番目の重要なポイントはロジックです。 最初に最も効率的なアルゴリズムを記述してから、データが機能するときにデータを保存するのに論理的に適切なものを確認します。 常に唯一の明白な方法でコンテナを選択するようにしてください。 一意の値のセットが必要です-「std :: set」を取得し、めったに変更されない辞書が必要です-気軽に「std :: unordered_map」を使用します。配列が必要で、そのサイズが事前にわかりません-「std :: deque」が必要になる可能性が高いです。配列のサイズが事前にわかっている場合、通常の `std :: vector`も機能します。



4番目はパフォーマンス測定です。 コンテナまたはアルゴリズムの選択に関する決定を、類似のコンテナでランタイムをテストする比較分析で常に確認する必要があります。 したがって、ソートされた「std :: vector」キーと値のペアは、この関係を使用して構築された論理的に適切な「std :: map」よりも処理が効率的であることが判明する場合があります。



プログラムコードのイデオロギービューを作成できますが、信頼すべき唯一の権限はプロファイラーです。プロファイラーは、その構成のさまざまなバージョンのコードのランタイムを測定します。

テキスト費用

テキストを扱う際に最初に学ぶべき最も重要なこと： `std :: string`は、テキストまたはその一部を保存および処理する唯一の方法ではありません。 部分文字列の場合、大きな文字列の各部分の下に数百万の新しいコンテナ `std :: string`を置く必要はありません;各部分文字列の始まりと終わりを示すのに十分です。 各サブストリングに新しい連続メモリブロックを構築し、ソース行に保存されているテキストの一部をコピーするよりも、ソース行で開始/終了イテレーターのペアで構造を開始する方が適切です。



例：nullで終わる文字列へのポインターとして表されるテキスト内のすべての単語を検索します。 簡単にするために、単語をセミコロンで区切ってみましょう。

template <typename word_type> void find_words(char const *text, std::deque<word_type>& result) { char const *start = text; char const *finish = text + std::strlen(text); while (start < finish) { char const* last = std::strchr(start, ';'); if (!last) last = finish; result.push_back(word_type(start, last)); start = last + 1; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

`word_type`として、標準の` std :: string`と、ソース文字列の部分文字列の先頭と末尾へのポインタを格納する独自の型の両方を試します。

 struct one_word { one_word(char const *begin, char const *end) : m_begin(begin), m_end(end) { } char const *m_begin, *m_end; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

単純な比較測定の結果、 `std :: string`コンテナーで絶対に不要な中間行を生成する時間を無駄にしないと、コードの実行が15〜20倍速くなります。 ほとんどの単語が元々「std :: string」で予約されていた16文字のバッファーに収まらない場合、サブストリングを保存するために新しいメモリブロックを動的に割り当てる必要があります。 初期化中のクラス `one_word`は、文字へのポインター型の2つのフィールドのみを埋めます。これは、サブストリングを通過するのに十分です。



Boostライブラリは最適化を特に無視するため、突然「boost :: split」または「boost :: regex」を使用することに決めた場合、あらゆる種類の不要なナンセンスの大規模な暗黙の作成で文字列を解析するときにプロファイラーがパフォーマンスの低下を正確に示すときにこの決定を覚えておいてください。

JSON、XML、すべてすべて

テキストプロトコルを使用するには、できるだけ慎重に対処する必要があります。 前の例が示すように、補助オブジェクトを作成するときのわずかな誤計算は、一見完全に無害なコードのパフォーマンスを損なう可能性があります。



一般的に受け入れられているプロトコルのそれぞれについて、ライブラリが多数あります。 ただし、単純な真実を覚えておく必要があります。



何よりもまず。 どこからでもXML / JSON / YAML構造を読み取る場合、完全なツリーを構築することはほとんどありません。 通常、同じタイプの一連の値を抽出することになります。



第二に、タスクのパフォーマンスが重要である場合、車輪を再発明することを軽daしないでください。あなたのケースは非常に特殊であるため、beatられた道を放棄することが正しい決定になります。



第三：シリアル化するときは、スタック上にバッファを生成して取得してみてください 。 これが不可能な場合は、事前に予約呼び出しを使用して「std :: string」に書き込みます。 最初に `std :: stringstream`を使用してRAM全体を散らし、次にそこから文字列を収集し、さらにすぐに結果に組み込むことができるものを一緒に接着すると、コードが有効になることはありません。



宿題として、 `std :: stringstream`を使用して、それを使用せずに、同じXMLで大きなテキスト構成を生成するパフォーマンスを比較します。 断片化の穴がたくさんあるチーズの形のRAMには速度がありません。

ベースが応答します

データベースを照会するとき、コンパイル段階でどのタイプの値が返されるかはわかりません。 より正確には、クエリ文字列を作成でき、C ++側の単純なSQLのようなORMでラップすることもできますが、主なことは、コンパイル段階では、データベースが応答で何を言っているかほとんどわかりません。



この点で、同じPython、Ruby、およびJavaScriptのような属性をオンザフライで生成する動的に型付けされた言語は、静的型付けを備えたコンパイル言語よりも明確な利点があります。



もちろん、 `IntField`、` FloatField`、およびその他の `* Field`のようなあらゆる種類のタイプを、` BaseField`のような共通の祖先で実行し、リンクおよびポインターのキャストを使用して、コードのすべてのブランチに苦しむことができます。 これにより、一般にデータベースからの単一の応答が断片化され、小さなメモリセルにプッシュされます。



ただし、アカデミーの最初の 3つの レッスンを思い出すと、C ++言語の制限を簡単に回避し、消化可能なAPIを取得できます。 残っているのは、各レコードの各フィールドにメモリを動的に割り当てるコストを最小限にすることです。 これはそれほど難しくありません。



SQLクエリに応答する従来のDBMSは、表形式のデータを提供します。つまり、コンパイル段階ではなく、実行段階ではあるものの、各レコードの形式がわかります。 レコードの構造により、最初に合計ですべてのフィールドのすべてのデータにメモリを割り当てることができます。 将来的には、古き良き「配置新しい」は、準備されたメモリセルによってフィールド値をソートするのに役立ちます。 次のようになります。

1. リクエストのメタデータから、クエリ結果の各フィールドのデータ型を学習します。 データベース側の各タイプには、ビジネスロジック側にも同様のタイプがあります。 スカラーデータは固定サイズのデータ​​であり、それらにメモリを割り当てることはバッファにスペースを残すことを意味し、コンストラクタは必要ありません。 ヒープに追加メモリを割り当てるデータでは、もう少し複雑です。たとえば、「タイプ」テキストの表現を表す「std :: string」です。 しかし、 `std :: string`自体は特定のサイズを持っているため、データベース内のどのタイプのフィールドについても、ビジネスロジック側のタイプとサイズを知っていると言えます。
2. 次に、レコードフィールドのタイプのサイズを単純に合計し、各レコードのデータブロックのサイズを取得します。 クエリ結果全体にメモリを割り当てるために、すべてのフィールドに一度メモリを割り当てることができます。 クエリ結果のメタデータからフィールドを読み込んだ直後に、メモリのヒープに一度だけ登ることがわかりました。 操作の複雑さは、リクエストの結果としてフィールドの数の倍数になります：1000個のフィールドがリクエストされたとしても、1000×*結果としてのレコード数*あいまいなIField *にメモリを割り当てるよりもはるかに簡単です。
3. データ処理の利便性のために、特定のクラスフィールドを作成する必要があります。 これは、C ++ Academyの最初の 2つの講義からの動的に型指定されたデータを含むコンテナーになります。 実際、それぞれに値がありますが、タイプはオプションで保存されます。これは、対応するデータセルのリクエストの結果のタイプ、またはNULLに対応します。
4. データベースに保存されているデータ型の大部分はテキストであるため、ヒープの代わりに直接「フィールド」メモリに格納される「std :: string」ではなく、データベース側で制限されたサイズの小さな行をインライン化することは理にかなっています。 この場合、メモリを割り当てるときに最適な最適化が得られますが、 `char m_text [SIZE]`はそれ自体では何も実行せず、文字列とメモリを操作するpure sの機能は適応しないため、必要なメソッドの実装に苦しむ必要がありますデータベース。
5. 主なことは、レコード内の各タイプのメモリを選択した後、 `new（<where>）Type（<parameters>）`コンストラクトを使用してこれらのフィールドを作成することです。

実装でどのように見えるかを以下に示します。 メインクラスは、データベースで使用する任意の型から動的に型指定されるフィールドコンテナーです。 スカラー型、テキストデータ、およびNULLのみがある場合、次のようになります。

 class field { public: template <typename value_type> field(void* address, value_type const& value); template <typename value_type> field& operator = (value_type const& value); template <typename value_type> value_type get_as() const; bool is_null() const; protected: class data; private: data* m_data; }; class field::data {...}; template <typename value_type> class data_holder : public field::data { public: data_holder(); // NULL data_holder(value_type const& value); <  > private: value_type m_value; }; template <typename value_type> field::field(void* address, value_type const& value) : m_data(new(address) data_holder(value)) { }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

クエリの結果としてフィールドを再配置および削除する操作がまれな場合は、ブロック全体のメモリを大胆にベクトル化します。 結果内のデータを使用してタグゲームを積極的にプレイする場合は、各セルのメモリが個別に割り当てられるメモリデッキの配列を選択します。 この場合、「Academy C ++」の2回目の講義のモデルがより適しています。この場合、オブジェクトの実装用のメモリをクラスデータに格納し、実装内に既にある「新しい配置」を介して初期化します。 std ::同質オブジェクトのdeque`、およびその他-オブジェクト内でのビッグデータの使用を制限します。 レコードメモリ内の行をインライン化することはできなくなりますが、フィールドの存在と順序によって簡単にプレイすることができます。これは、非リレーショナルデータベースや、他のビジネスロジックから取得した結果をさらに処理するプロキシロジックにとって重要です。できる。 次に、フィールドタイプ自体が少し異なります。

 class field { public: //     template <typename value_type> field(value_type const& value); <  > private: data* m_data; uint8_t m_buffer[MAX_FIELD_SIZE]; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、アカデミーコースの冒頭でダイナミックタイピングのメカニズムを説明した徹底性と、2番目のレッスンでクラス内に以前は未知のタイプのデータを配置した場合のメモリの節約について説明しました。



どのパスを選択しても、レコード全体、またはビジネスロジック側のクエリ結果全体、または各レコードのフィールドデッキの柔軟な制御のための単一のメモリブロックは、各フィールドへの大量のメモリ割り当てよりも優れており、ポインタを使用して操作します型の定数キャストが行われるインターフェース上。

静か！ 録音があります！

どちらの場合でも、レコードクラスは次のように機能します。

1. フィールド情報のセットを使用した初期化。
2. メタ情報によるメモリ割り当ては1回のみ発生します。
3. 次に、ループ内のレコードフィールドのリストに、後続の各レコードフィールドの共有メモリに対するオフセットが設定されます。
4. フィールドに関する情報に値がすぐに含まれていた場合は、値とともにフィールドをすぐに目的のアドレスに直接初期化します。

レコードの実装は、レコード全体にモノリシックデータブロックがあるか、動的に型指定されたコンテンツを持つ同じ型の交換可能な要素のセットであるかによって、少し異なります。 単一のメモリブロックの記録実装がどのように見えるかの例を示します。

 class record { public: record(query_result const& result, size_t row); //      field field [const]& operator[](<    int, char const*  std::string const&>) [const]; private: std::vector<uint8_t> m_buffer; std::vector<field> m_fields; }; record::record(query_result const& result, size_t row) { size_t buffer_size = std::accumulate( result.types().begin(), result.types().end(), 0, [](size_t init, field::type type){ return init + type.size(); }); m_buffer.resize(buffer_size); m_fields.reserve(result.types().size()); for(size_t offset=0, index=0; index<result.types().size(); ++index) { m_fields.push_back(field(offset,result[row][index])); offset += result.type_of(index).size(); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最大加速を使用し、クエリ結果全体に対して1つのメモリブロックを使用する場合、書き込みコードはわずかに変更されます。

 class record { public: //      record(void* address, query_result const& result, size_t row); <    > private: std::vector<field> m_fields; <     > };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最も重要な最適化

クエリ結果からビジネスロジック側のプレゼンテーションフィールドにフィールドを展開することはクールですが、非常に頻繁に絶対に不要であることを覚えておくことが重要です。 クライアントデータベースAPIからJSONを直接生成する必要がある場合、それぞれに多数の `field`オブジェクトを持つ` record`オブジェクトの暗闇を作成する必要はありません。 最適化されていても、このアクションは不要です。 スタック上にバッファを作成し、JSON、XML、YAML、またはクライアントが期待する別の形式の形式でクエリ結果を追加して送信します。



しかし、一部のコードが複雑な処理のために内部形式でデータセットを正確に処理することを期待している場合は、疑いなくここで便利なプレゼンテーションを生成する必要があります。 boolのような単純な答えが期待されている場合、つまり、それがhelloベースから来たかどうかを意味する場合、trueに答えるために構造[["hello"]]を生成する必要はまったくありません。



アルゴリズムに追加のステップを追加しないでください-これが最も重要な最適化です。

不滅と永久

学ぶ必要がある主なことは、CのようにC ++がプロセスメモリへの直接アクセスを提供することです。まず、スタック上のメモリが重要であり、次に、事前に割り当てられ、使用のために準備されたバッファ内のメモリです。 Java、C＃、またはPythonは、C / C ++で正しく記述されたプログラムのパフォーマンスに近いものではありません。まさに、メモリを使用した不適切な作業からプログラマを保護するからです。 プロトコルパケット用にスタック上に数キロバイトのメモリを割り当て、ポインタで埋め、ネットワーク上の送信機能としてスタック上のバ​​ッファへのリンクを与えることができます。 このために `std :: vector <uint8_t>`をブロックする必要はありません。純粋で単純なsのスタイルの `uint8_t packet_buffer [MAX_PACKET_SIZE]`で十分です。



C ++言語は、C言語構造の上に便利な高レベル言語構造を構築する機能を提供します。これを使用する必要があります。 パターンは言うまでもなく、コンストラクタとデストラクタを使用せず、例外をスローすることは罪です。 このキッチンを所有している場合、クッキーは良好になりますが、そうでない場合、ごめんなさい：近所（同じJava）に自動電子レンジがあるので、クッキーを焼いてみてください。



C ++言語は、高レベル言語で実装されたアルゴリズムの最適化や、コードからすべてを絞り出すのに最適です。 これを行うために、 `std :: map`を巡回する複雑さを知る必要はまったくありません-時々、単にvectorのvectorの代わりに通常のT **を使用する必要があります。 または、ネットワーク経由で送信するために「std :: string」のサイズを無意味に生成する代わりに、スタック上のすべてを取得して実行します。



主なことは、頭を明るくして、コードの各行で何をするかについて少し考えることです。 何か特別なことが行われていますか？ 結局のところ、私たちがコードの速度を最適化するのは、彫刻家のように余分な部分を切り捨てているからです。 高度な最適化の成功をお祈りします！







Hacker Magazine＃195で最初に発行されました。

投稿者：Vladimir Qualab Kerimov 、リーディングC ++開発者、Parallels



ハッカーを購読する

• サイト資料
• 紙版
• iOS / iPadのハッカー
• Androidのハッカー