繰り返す

llvm-DenseMapのデータ構造とメモリ割り当て戦略



Data Structure Memory Allocation Strategy Llvm Densemap



データ構造サブパート

DenseMapこれはllvmで使用される非常に広範なデータ構造であり、その実装はQuadratic probing（二次探索）ハッシュテーブルに基づいており、キーと値のペア自体はstd::pair。DenseMapコンストラクターと代入演算子の定義は次のとおりです。DenseMap 4つのデータメンバーがありますBuckets、NumEntries、NumTombstones、NumBuckets、それぞれハッシュバケット（連続メモリの一部）の最初のアドレス、保存されたデータの数を示すために使用されますTombstone数（二次探索メソッドでデータを削除するときに削除済みフラグを設定する必要があります）、数バケットの。

template KeyT, typename ValueT, typename KeyInfoT = DenseMapInfo<KeyT>, typename BucketT = detail::DenseMapPair<KeyT, ValueT>> class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>, KeyT, ValueT, KeyInfoT, BucketT> { // Lift some types from the dependent base class into this class for // simplicity of referring to them. using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT> BucketT *Buckets unsigned NumEntries unsigned NumTombstones unsigned NumBuckets public: /// Create a DenseMap with an optional p InitialReserve that guarantee that /// this number of elements can be inserted in the map without grow() explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve) } DenseMap(const DenseMap &other) : BaseT() { init(0) copyFrom(other) } DenseMap(DenseMap &&other) : BaseT() { init(0) swap(other) } ~DenseMap() { this->destroyAll() operator delete(Buckets) } void swap() { this->incrementEpoch() RHS.incrementEpoch() std::swap(Buckets, RHS.Buckets) std::swap(NumEntries, RHS.NumEntries) std::swap(NumTombstones, RHS.NumTombstones) std::swap(NumBuckets, RHS.NumBuckets) } DenseMap& operator=(const DenseMap& other) { if (&other != this) copyFrom(other) return *this } DenseMap& operator=(DenseMap &&other) { this->destroyAll() operator delete(Buckets) init(0) swap(other) return *this } }

DenseMap継承元DenseMapBase、DenseMapBase 2012年 チャンドラー・カルース 追加、達成するためにSmallDenseMap、will DenseMapハッシュロジックは抽象化されますDenseMapBaseメモリ管理のロジックは残りますがDenseMap with SmallDenseMap達成します。

DenseMapを基本クラスに因数分解します。 ハッシュテーブルロジックと、割り当ておよび成長戦略を提供する派生クラスを実装します。

これは、実際にはDenseMapとまったく同じように動作し、同じセマンティクスを持つすべての同じタイプとインターフェイスポイントをサポートするSmallDenseMapを構築するための最初の（そして最大の）ステップです。 - コミットメッセージ

メモリ管理

DenseMapメモリ管理。主にoperator newメモリの割り当てoperator deleteメモリを解放します。

初期化

DenseMap関連するメソッドはinit()、getMinBucketToReserveForEntries() with allocateBuckets()、次のとおりです。

class DenseMapBase { /// Returns the number of buckets to allocate to ensure that the DenseMap can /// accommodate p NumEntries without need to grow(). unsigned getMinBucketToReserveForEntries(unsigned NumEntries) { // Ensure that 'NumEntries * 4 if (NumEntries == 0) return 0 // +1 is required because of the strict equality. // For example if NumEntries is 48, we need to return 401. return NextPowerOf2(NumBuckets * 4 / 3 + 1) } } template class DenseMap : public DenseMapBase { explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve) } void init(unsigned InitNumEntries) { auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries) if (allocateBuckets(InitBuckets)) { this->BaseT::initEmpty() } else { NumEntries = 0 NumTombstones = 0 } } bool allocateBuckets(unsigned Num) { NumBuckets = Num if (NumBuckets == 0) { Buckets = nullptr return false } Buckets = static_cast(operator new(sizeof(BucketT) * NumBuckets)) return true } }

DenseMap初期化は次の3つのステップに分かれています。

  • 要素の初期数については、初期最小バケット数を計算します
  • バケット数については、メモリを割り当てます
  • 初期化

バケットの最小数を計算する方法は、getMinBucketToReserveForEntries()であるため、DenseMapバレルの数には2つの基準があります。

  1. バケットの数は2の累乗でなければなりません
  2. DenseMap of load factor > 3/4またはNumber of empty buckets <1/8の場合、バケットの数を増やす必要があります

これらの2つの基準を満たすために、getMinBucketToReserveForEntries()まず最初にNumber of elements * 4/3次に大なり記号を計算しますNumber of elements * 4/3 2の最小の累乗、2の累乗を計算する方法はNextPowerOf2()、実装は次のとおりです。

inline uint64_t NextPowerOf2(uint64_t A) = (A >> 2) A

バケットにメモリを割り当てる方法はallocateBuckets()です。メソッドは、operator new()データを格納するためのヒープメモリを割り当てることです。最後は情報の初期化です。空のバケットを初期化する方法はinitEmpty()です。方法は次のとおりです。

void initEmpty() { setNumEntries(0) setNumTombstones(0) assert((getNumBuckets() & (getNumBuckets() - 1) == 0) && ' # initial buckets must be a power of two!') const KeyT EmptyKey = getEmptyKey() for (BucketT *B = getBuckets(), *E = getBucketsEnd() B != E ++B) ::new (&new->getFirst()) KeyT(EmptyKey) }

上記の2つのポイントがあります。1つはバケットの数が2の累乗ではないことを確認することであり、もう1つはプリセットempty key数です。 on empty key計算、後で紹介しますDenseMapInfo後で紹介します。

増加する

DenseMap初期化フェーズでは、バケットの初期数の計算、バケットの割り当て、およびempty key初期化。バケットの数が十分でない場合、標準はload factor > 3/4またはNumber of empty buckets <1/8であり、データを格納するために新しいバケットを割り当てる必要があることを示します。 for DenseMapバケット数を増やす方法はgrow()です。この方法は、次のように定義されています。

void grow(unsigned AtLeast) { unsigned OldNumBuckets = NumBuckets BucketT *OldBuckets = Buckets allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast - 1)))) if (!OldBuckets) { this->BaseT::initEmpty() return } this->moveFromOldBuckets(OldBuckets, OldBuckets + OldNumBuckets) // Free the old table. operator delete(OldBuckets) }

成長プロセスとstd::vector非常によく似ており、新しいバケットの数の計算とメモリの割り当て、データのコピー、古いバケットの解放に分けられます。バケット数の計算にもNextPowerOf2()メソッドを使用します。

注：元のgrow（）で計算されたバケットの数は次のとおりです。 単に2を掛ける 、これと今std::vectorアプローチは非常に似ています。を参照してください。 DenseMap.h 。実際DenseMap最初の実現はstd::vector達成されました。

掃除

クリーンアップ操作はshrink_and_clear()によって行われます。このメソッドは主に、コンテナclear()メソッドと同様に、メモリの一部を再割り当てし、初期化してから元のメモリを解放することによって実現されます。

void shrink_and_clear() { unsigned OldNumEntries = NumEntries this->destroyAll() // Reduce the number of buckets. unsigned NewNumBuckets = 0 if (OldNumEntries) NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1)) if (NewNumBuckets == NumBuckets) { this->BaseT::initEmpty() return } operator delete(Buckets) init(NewNumBuckets) }

空のキーとトゥームストーンキーとハッシュ値の計算

空のキー、トゥームストーンキー、およびハッシュ値の計算DenseMapInfoテンプレートクラスに実装されているllvmは、一般的なタイプのDenseMapInfoポインタタイプ、整数タイプなどの空の特殊バージョンを提供します。キーは基本的に、タイプが表すことができる最大値です。たとえば、for short用語では、空のキーは0x7FFF、トゥームストーンキーは空のキー-1です。

詳細に紹介する必要があるのは、ハッシュ値の計算です。DenseMapハッシュ値の計算は乗算であり、各ハッシュシードは37であるため、問題はなぜ37がハッシュシードとして選択されるのかということです。

なぜ37

on DenseMapInfo途中のハッシュ値の計算には2つの問題があります。まず、最初の質問は、なぜ素数がハッシュ関数のハッシュシードとして一般的に使用されるのかということです。 2番目の質問は、llvmが他の素数の代わりに37を選択した理由です。

最初の質問では、素数はハッシュの衝突を効果的に回避できますが、これまでのところ、私を満足させる説明は見つかりませんでした。 2番目の質問については、llvm-devに関連する質問があります [llvm-dev]整数のデフォルトのハッシュ関数（DenseMapInfo.h） 、しかし、この質問に対する完全な答えはありませんが、テストプロセスでは比較的良好なパフォーマンスがあり、31を使用しても同様の結果が得られると推定されます。

しかし、「mallocによって返されるポインターは16バイト整列されているため、k >> 4がここにあると思います」という文があります。私はこれまでこの問題に注意を払ったことがなく、まだ深く考えていません。 stackoverflowに関連する質問があります mallocとnewはint​​に揃えられたアドレスを返しますか？ カスタムメモリ割り当て機能が特定のタイプの割り当て専用である場合、この要件は必要ありません。

検索して挿入

DenseMapオープンアドレス法の実装に基づいて、調査では2次プロービングを採用しています。最初のプロービング位置によってシーケンス全体が決まり、各キーワードには対応する一意の固定プロービングシーケンスがあります。

検索

DenseMap関数で検索find()達成DenseMap二次探索方法を使用するため、検索プロセスは標準の二次探索方法です。find()最終呼び出しLookupBucketFor() To見つけてください。LookupBucketFor()プロセスは次のとおりです。

  1. プローブ数を設定ProbeAmt Is 1、キー値KEYが計算され、バケットのIDがキー値によって取得されます
  2. 場合Buckets[ID]キー値がKEYの場合、値を見つけて現在の位置を記録し、trueを返します。それ以外の場合は3にジャンプします。
  3. ケースBuckets[ID]キー値EmptyKeyの場合、値が見つかりません。現在の位置を記録して、戻ります。それ以外の場合は、3に進みます。
  4. バケットBuckets[ID] for TombstoneKeyの場合、スルーID = ID + ProbeAmt++。 2にジャンプして、実行を続行します。

バケットIDの計算方法はKey value & (number of buckets-1)で、これは剰余演算に相当します。 2番目の探索の鍵はID = ID + ProbeAmt++、場合ProbeAmt自己インクリメント操作がない場合、それは線形探索であり、自己インクリメント操作の存在は二次探索です。実際、この2次的な調査は、次の図に示すように、「アルゴリズムの概要-第3版」の11-3の演習です。 2番目の探索の微分公式はIDn = IDn-1 + iとして近似できます。これは二次方程式であり、対応するm with n Valueであることがわかります。

画像

/// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in /// FoundBucket. If the bucket contains the key and a value, this returns /// true, otherwise it returns a bucket with an empty market or tombstone and /// returns false. template<typename LookupKetT> bool LookupBucketFor(const LookupKey &Val, const BucketT *&FoundBucket) const { const BucketT *BucketsPtr = getBuckets() const unsigned NumBuckets = getNumBuckets() if (NumBuckets == 0) { FoundBucket = nullptr return false } /// FoundTombstone - Keep track of whether we find a tombstone while probing. const BucketT *FoundTombstone = nullptr const KeyT EmptyKey = getEmpty() const KeyT TombstoneKey = getTombstoneKey() assert(!KeyInfoT::isEqual(Val, EmptyKey) && !KeyInfoT::isEqual(Val, TombstoneKey) && 'Empty/Tombstone value shouldn't be inserted into map!') unsigned BucketNo = getHashValue(Val) & (NumBuckets - 1) unsigned ProbeAmt = 1 while(true) { const BucketT *ThisBucket = BucketsPtr + BucketNo // Found Val's buckets? If so, return it. if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) { FoundBucket = ThisBucket return true } // If we found an empty bucket, the key doesn't exist in the set. // Insert it and return the default value. if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) { // If we've already seen a tombstone while probing, fill it in instead // of the empty bucket we eventually probed to. FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket return false } // If this a tombstone, remember it. If Val ends up not in the map, we // prefer to return it than something that would require more probing. if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) && !FoundTombstone) FoundTombstone = ThisBucket // Remember the first tombstone found. // Otherwise, it's a hash collision or a tombstone, continue quadratic // probing. BucketNo += ProbeAmt++ BucketNo &= (NumBuckets - 1) } } iterator find(const_arg_type_t Val) { BucketT *TheBucket if (LookupBucketFor(Val, TheBucket)) return makeIterator(TheBucket, getBucketsEnd(), *this, true) return end() }

上記のコードについてLLVM_LIKELY後で紹介します。

インサート

DenseMap最終的には呼び出しますLookupBucketFor()挿入位置を見つけるためですが、挿入できる場合はバケットの数が不足しているため、メモリを再割り当てするために新しいバケットを拡張する必要があります。挿入エントリはinsert()、特定の挿入プロセス中try_emplace()完了、はいin-placeタイプ挿入中のコードは次のとおりです（コードが少し多すぎます）。try_emplace() C ++ 17をシミュレートstd::map::try_emplace、参照 [DenseMap] C ++ 17スタイルのtry_emplaceメソッドを追加します。 。

[DenseMap] C ++ 17スタイルのtry_emplaceメソッドを追加します。
これにより、LLVMで何度も発生する「マップにない場合は構築する」問題を解決するためのエレガントなパターンが提供されます。 try_emplaceがない場合は、番兵値（nullptr）に依存するか、2つのルックアップを実行する必要があります。

注：大胆な文章、理解していませんか？

DenseMap::try_emplace左辺値と右辺値の2つのバージョンが提供されていますが、ロジックは同じです。最初に使用してくださいKey問い合わせmap同じキー値がすでに存在するかどうか、存在する場合は、戻り、呼び出します存在しない場合InsertIntoBucket()、この関数は実際の挿入操作を実行し、必要に応じてメモリを再割り当てします。

// -------------------------lvalue version-------------------- --- // Inserts key, value pair into the map if the key isn't already in the map. // If the key is already in the map, it returns false and doesn't update the // value. std::pair bool> insert(const std::pair &KV) { return try_emplace(KV.first, KV.second) } // Inserts key, value pair into the map if the key isn't already in the map. // The value is constructed in-place if the key is not in the map, otherwise // it is not moved. template <typename ... Ts> std::pair bool> try_emplace(const KeyT &Key, Ts &&... Args) { BucketT *TheBucket if (LookupBucketFor(Key, TheBucket)) return std::make_pair( makeIterator(TheBucket, getBucketsEnd(), *this, true), false) // Already in map. // Otherwise, insert the new element. TheBucket = InsertIntoBucket(TheBucket, Key, std::forward(Args)...) return std::make_pair(makeIterator(TheBucket, getBucketsEnd(), *this, true), true) } // -------------------------lvalue version-------------------- --- // -------------------------Rvalue version-------------------- --- // Inserts key, value pair into the map if the key isn't already in the map. // If the key is already in the map, it returns false and doesn't update the // value. std::pair bool> insert(std::pair &&KV) { return try_emplace(std::move(KV.first), std::move(KV.second)) } // Inserts key, value pair into the map if the key isn't already in the map. // The value is constructed in-place if the key is not in the map, otherwise // it is not moved. template <typename ... Ts> std::pair bool> try_emplace(const KeyT &Key, Ts &&... Args) { BucketT *TheBucket if (LookupBucketFor(Key, TheBucket)) return std::make_pair( makeIterator(TheBucket, getBucketsEnd(), *this, true), false) // Already in map. // Otherwise, insert the new element. TheBucket = InsertIntoBucket(TheBucket, std::move(Key), std::forward(Args)...) return std::make_pair(makeIterator(TheBucket, getBucketsEnd(), *this, true), true) } // -------------------------Rvalue version-------------------- ---

InsertIntoBucket()の定義は次のとおりです。関数は、次の2つのステップに分かれています。

  • transfer InsertIntoBucketImpl()、負荷率に応じてバケット数を増やす必要があるかどうかを判断し、挿入位置に戻します。
  • 挿入位置に応じて、placement new指定したメモリ位置にオブジェクトを作成します。
template <typename KayArg, typename... ValueArgs> BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key, ValueArgs &&... Values) { TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket) TheBucket->getFirst() = std::forward(Key) ::new (&TheBucket->getSecond()) ValueT(std::forward(Values)...) return TheBucket } template<typename LookupKeyT> BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup, Bucket *TheBucket) { incrementEpoch() // If the load of the hash table is more than 3/4, or if fewer than 1/8 of // the buckets are empty(meaning that many are filled with tombstones), // grow the table. // // The later case is tricky. For example, if we had one empty bucket with // tons of tombstones, failing lookups (e.g. for insertion) would have to // probe almost the entire table until it found the empty bucket. If the // table completely filled with tombstones, no lookup would ever succeed, // causing infinite loops in lookup. unsigned NewNumEntries = getNumEntries() + 1 unsigned NumBuckets = getNumBuckets() if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) { this->grow(NumBuckets * 2) LookupBucketFor(Lookup, TheBucket) NumBuckets = getNumBuckets() } else if (LLVM_UNLIKELY(NumBuckets - (NewNumEntries + getNumTombstones()) <= NumBuckets / 8)) { this->grow(NumBuckets) LookupBucketFor(LookUp, TheBucket) } assert(TheBucket) // Only update the state after we've grown our bucket space appropriately // so that when growing buckets we have self-consistent entry count. incrementNumEntries() // If we are writing over a tombstone, remember this. const KeyT EmptyKey = getEmptyKey() if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey)) decrementNumTombstones() return TheBucket }

まず、見てみましょうInsertIntoBucketImpl()実現InsertIntoBucketImpl()ロジックは次のとおりです。

  1. 最初の判断NumEntries / NumBuckets >= 3 /4 If true、これは、バケットの数を増やし、呼び出しgrow()バケットの数を増やし、挿入位置を再計算して、3に進む必要があることを意味します。 _ + _ |次に、2にジャンプします。
  2. 場合false for NumEntries / NumBuckets <3 / 4、but true、Then EmptyEntries / NumBuckets <= 1 / 8墓石が多すぎます 場合DenseMapすべてがトゥームストーンの場合、無限ループが発生する可能性があります。現時点では、バケットの数は増えませんが、再ハッシュされます 。次に、挿入位置を再計算して3にジャンプします。
  3. 増加DenseMap、挿入位置がNumEntriesの場合、それに応じて減少Tombstone数量

注：ステップ2での再ハッシュについては、を参照してください。 再ハッシュしますが、墓石でいっぱいになっても成長しません。 データ構造が最初に実装されたとき、それは非常に鈍いことがわかります。

挿入位置が計算されたら、最後に挿入位置に従って進みますTombstone挿入は新しい位置で行われます。

削除

削除者in-place実現は非常に一般的ですDenseMap::erase()検索プロセスでの探索に影響を与えないように、関数の位置を設定しますopen addressing識別、この関数の定義は次のとおりです。

tombstone

bool erase(const KeyT &Val) { BucketT *TheBucket if (!LookupBucketFor(Val, TheBucket)) return false // not in map. TheBucket->getSecond().~ValueT() TheBucket->getFirst() = getTombstoneKey() decrementNumEntries() incrementNumTombstones() return true } bool erase(const KeyT &Val) { BucketT *TheBucket = &*I TheBucket->getSecond().~ValueT() TheBucket->getFirst() = getTombstoneKey() decrementNumEntries() incrementTombstones() }パーツが紹介されました、借ります LLVMデータ構造の概要 内容DenseMap大まかに次の部分に分けることができます。

  • DenseMapは、二次的にプローブされたHashMapです。
  • すべてを単一のメモリ割り当てに保持します
  • 挿入後にイテレータが無効になる可能性がある
  • std :: mapインターフェースに非常によく一致します
  • キーとしてすべてのポインタと整数型をサポートします
  • 追加のキータイプは、カスタムDenseMapInfoクラスで指定できます。
    struct KeyInfo {
    静的インラインTgetEmptyKey（）{…}
    静的インラインTgetTombstoneKey（）{…}
    static unsigned getHashValue（const T＆Val）{…}
    static bool is Equal（const T＆LHS、const T＆RHS）{…}
    }
    DenseMap M

C ++サブパート

std :: forward

`std :: forward`は、完全な転送を実現するために使用されます。関連するコンテンツについては、[範囲ベースのforループの同等の形式] [13]を参照してください。

いわゆる完全転送とは、関数テンプレートで、テンプレートのパラメータータイプに従って、パラメーターが関数テンプレート内の別の関数に完全に渡されることを意味します。
。。。。
実際、C ++ 11は、「参照の折りたたみ」と呼ばれる新しい言語ルールを導入し、それを新しいテンプレート推定ルールと組み合わせることで、完全な転送を完了します。

*注： `universe reference`の導出規則は、` auto && `がテンプレートRules * code> code>の` T && `の導出と同等であることに注意してください。

：：新着

クラスタイプに演算子newが定義されている場合でも、次の例の形式を使用してグローバル演算子を使用できます。

T * TObject = :: new TObject

スコープ解決演算子（：:）は、グローバルな新しい演算子の使用を強制します。

NextPowerOf2

`llvm :: NextPowerof2（uint64_t A）`は、 `A`よりも大きい最小の2 ^ Nを計算するために使用され、関数は次のように定義されます。この実現は、単純なシフトおよび加算操作によって関数を実現します。これは非常に美しいです。 DenseMap

ConstantLog2

`llvm :: ConstantLog2`は、テンプレートメタプログラミングによって実現される` 2 ^ N`のNの値を計算するための単純なテンプレート関数です。テンプレートメタプログラミングがわかりません。これは、実装権を記録するためのエントリポイントです。 /// Returns the next power of two (in 64-bits) that is strictly greater than A. /// Returns zero on overflow. inline uint64_t NextPowerOf2(uint64_t A) = (A >> 2) A

std :: integer_constant

タグディスパッチ

*注： `std :: integral_constant`と` tagdispatching`はテンプレートメタプログラミングと密接に関連しています。私はこれを理解していないので、他人を誤解させることを恐れています。子供たち、とりあえず脇に置いておきます*

alignof

`std :: alignof`は、型に必要な配置の長さを取得するためにc ++ 11によって導入された演算子です。

alignof演算子（c ++ 11以降）
タイプの配置要件を照会します。

注意すべきもう一つのことは
  • 最も弱いアライメント（最小のアライメント要件）は、 char 、 符号付き文字 、および unsigned char 、これは 1 。
  • あらゆるタイプの最大の基本的な配置は、 std :: max_align_it

さらに使用します アラインアス namespace detail { /// A tiny meta function to compute the log2 of a compile constant. template struct ConstantLog2 : std::integral_constant2>::value + 1> {} template struct ConstantLog2<1> : std::integral_constant0> {} } more std::max_align_itメモリアライメント要件よりも良くなるため。

std :: try_emplace

stricter(larger) C ++ 17で新しく追加されたインターフェイスです、はいstd::try_emplace拡張バージョンです。std::emplace主に不要な一時オブジェクトの作成を直接減らすために、C ++ 11によって追加されました。 std::emplace構築。in place主にC ++ 11によって追加された次の2つの機能を介して。を参照してください。 C ++での完全な転送とユニバーサル参照 。

  • 可変個引数テンプレート
  • 完璧な転送

To std::emplace例として、libc ++での定義は次のとおりであり、さまざまなマクロ定義が削除されています。次のコードは2つの部分に分けることができます。

  1. 到達したかどうかを判断しますstd::vector::emplace容量に到達した場合は3に進み、到達しなかった場合は2に進みます
  2. 指定された位置にオブジェクトを作成します（基本的に、新しい位置と見なすことができます）
  3. メモリを再割り当てし、指定された場所にオブジェクトを構築します
std::vector

最初に使用する理由を紹介します#if __cplusplus >= 201103L template<typename _Tp, typename _Alloc> template<typename... _Args> #if __cplusplus > 201402L typename vector::reference #else void #endif vector:: emplace_back(_Args&&... __args) { if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) { _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, std::forward(__args)...) ++this->_M_impl._M_finish } else _M_realloc_insert(end(), std::forward(__args)...) #if __cplusplus > 201402L return back() #endif } #endif一時オブジェクトの作成を回避するために、最初にオブジェクトをパラメーターとして渡すプロセスをスキップする必要があります。このプロセスを回避するには、オブジェクトの作成を遅らせる必要があります。唯一の方法はto variadic templatesで、指定したメモリに直接作成します。

タイプTのオブジェクトではなく、引数をTのコンストラクターに渡します。 このようにして、オブジェクトの構築が遅れます。新しいオブジェクトに必要なメモリに対応するようにベクトルが拡張され、コンストラクタが呼び出されて、ベクトル内のオブジェクトが初期化されます。 可変個引数テンプレートはコピーとは何の関係もありません。コンストラクターに可変数の引数を転送することのみを許可します。 - ベクトルのemplace_back

次に、使用する理由を紹介しますThe parameters required by the constructor are passed in、前述のように、コンストラクターのパラメーターは直接渡されるため、パラメーターを渡すと不要なコピーが生成されます。したがって、perfect forwarding use emplace()、So右辺値参照または右辺値参照、および左辺値参照または左辺値参照に到達するように。左辺値参照の場合、1つのコピー構成が削減され、右辺値参照の場合、1つの移動構成が削減されます。完璧な転送に関する関連コンテンツを見る C ++での完全な転送とユニバーサル参照 。

コンストラクター自体への引数は、右辺値参照として渡され、std :: moveを使用してコンストラクターに転送されるため、コピーされません。基本的に、移動セマンティクスはオブジェクトの深いコピーを回避します。

これで、perfect forwarding不要な一時オブジェクトの作成を減らし、プログラム実行時のオーバーヘッドを減らすことができます。たとえば、次の図に示すように、std::emplaceを使用すると、指定されたメモリ位置に直接配置されます（つまり、std::vector::emplace_back()）in-placeの形式でオブジェクトを構築するには実装はemplace_back()の関連実装を参照できます。
emplace_back

for libc++たとえば、パラメーターリストを使用してコンストラクターのパラメーターを渡すことを選択してから、for emplace区別する方法std::map::emplace値の合計keyに注意してください。何？ 、方法はParameters of the constructorを使用することです。

あるのでstd::forward_as_tupleそれからstd::emplace存在の目的は何ですか？std::try_emplace主に使用されますstd::try_emplace挿入、応答はmap問題を説明するために、同じキー値がmap実現の概略図にすでに存在します。 on std::map標準では、std::map中間libc++の実現は指定されていません。もちろん、これは大多数ですstd::map達成方法です。
std :: map :: emplace
上に示したように、std::map最初にノードを構築し、次にキー値がすでに存在するかどうかを確認し、存在しない場合は挿入します。std::map::emplaceこのアプローチは本当にばかげています！std::emplace対応libc++コア機能は次のとおりです。最初にノードを作成し、次にクエリを実行し、最後にクエリの結果に基づいて挿入するかどうかを決定することがはっきりとわかります。 is std::map::emplace値is std::mapオブジェクトが作成されるときのフォームの存在も、次のように作成されることに注意する必要がありますstd::pair。

std::pair

template <class _Tp, class _Compare, class _Allocator> template <class... _Args> pair<typename __tree::iterator, bool> __tree::__emplace_unique_impl(_Args&&... __args) { __node_holder __h = __construct_node(_VSTD::forward(__args)...) __parent_pointer __parent __node_base_pointer& __child = __find_equal(__parent, __h->__value_) __node_pointer __r = static_cast(__child) bool __inserted = false if (__child == nullptr) { __insert_node_at(__parent, __child, static_cast(__h.get())) __r = __h.release() __inserted = true } return pair bool>(iterator(__r), __inserted) } in libc++のコア機能を以下に示します。以下のコードから、最初にクエリ操作が実行され、次にクエリの結果に応じて、オブジェクトを作成して挿入するかどうかが決定されることがわかります。 この関数のパラメーターはの形式であり、上記std::map::try_emplaceパラメーターはキーとArgsを鉄片として扱うためのものであることに注意してください。もちろん、これが|であるかどうかはわかりません。 _ + _ |最初にクエリを作成してから挿入できないのはなぜですか？

__emplace_unique_impl()

オン std::map::emplace と template <class _Key, class _Args> pair<typename __tree::iterator, bool> __tree::__emplace_unique_key_args(_Key const& __k, _Args& __args) #endif { __parent_pointer __parent __node_base_pointer& __child = __find_equal(__parent, __k) __node_pointer __r = static_cast(__child) bool __inserted = false if (__child == nullptr) { #ifndef _LIBCPP_CXX03_LANG __node_holder __h = __construct_node(_VSTD::forward(__args)...) #else __node_holder __h = __construct_node(__args) #endif __insert_node_at(__parent, __child, static_cast(__h.get())) __r = __h.release() __inserted = true } return pair bool>(iterator(__r), __inserted) } 動作の違いは、C ++標準で詳しく説明されています。

std :: map :: emplace
コンテナ内にキーを持つ要素がすでに存在する場合でも、要素が構築される可能性があります。その場合、新しく構築された要素はすぐに破棄されます。
std :: map :: try_emplace
kに相当するキーがすでにコンテナに存在する場合、何もしません。

より直感的な表現については、を参照してください。 C ++ 1zでtry_emplace（）の代わりにstd :: map :: emplace（）を使用する理由はありますか？ 、

  • 挿入が行われない場合、try_emplace（）は右辺値引数から移動しません。これは、値がstd :: unique_ptrなどの移動専用タイプのマップを操作する場合に役立ちます。
  • try_emplace（）は、mapd_typeのキーと引数を別々に処理します。これにより、value_type（std :: pair）で表される一般的なミューテーターよりも直感的になります。

この時点で、すでにわかっていますstd::map::emplaceはいstd::map::try_emplaceデータを挿入するときに、キー値がすでに存在する状況に対して特別な最適化が行われ、不要なコンストラクター呼び出しのステップが節約されます。他の違いは、この違いから拡張されます。もちろん、これは最も明白な違いにすぎません。この部分は簡単な紹介ですtry_emplace with emplace、私はC ++の専門家ではなく、一時的に先に進むことができません。

その他のサブパーツ

__builtin_expect

std::emplace命令は、CPU命令のプリフェッチの成功率を向上させるのと同様に、分岐予測に関する関連情報を提供するために使用されますか？
-std::try_emplace命令は分岐予測情報を提供します。戻り値は__builtin_expectの値です。

LLVM_UNLIKELY

__builtin_expect(long exp, long, c)完了exp実現は次のとおりです。

LLVM_UNLIKELY

さらに__builtin_expect llvmデータ構造について2つの話があります。つまり、「CppCon 2014：Chandler Carruth」アルゴリズムの効率、データ構造のパフォーマンス」と「CppCon 2016：Chandler Carruth」高性能コード201：ハイブリッドデータ構造''

- - ファローアップ - - -
llvmのデータ構造とメモリ割り当て戦略-StringMap＆DenseSet＆SparseSet
llvmのデータ構造とメモリ割り当て戦略-FoldingNodeSet＆SmallVector＆StringRef＆ArrayRef
llvm-clang静的アナライザーのメモリー割り当て戦略におけるデータ構造とメモリー割り当て戦略
llvmのデータ構造とメモリ割り当て戦略-BumpAllocator