問題の声明
私が実装したアルゴリズムの1つには、メモリを操作するときに興味深い機能がありました。
- 膨大な数の同じ種類の小さなオブジェクトが数千から数億個も目立つ可能性があります。
- オブジェクトはPODタイプでした。
ポッドC ++のPlain Old Data Structureは、メンバーとしてPODSのみを含み、ユーザー定義のデストラクタ、ユーザー定義のコピー割り当て演算子、およびメンバーへのポインタ型の非静的メンバーを持たない集合クラスです。 - 必要なオブジェクトの数は事前にはわかりませんでしたが、100、またはおそらく1億が必要になることがありました。
- オブジェクトは一度に1つずつ削除されることはなく、ある時点で一度に不要になります。
- アルゴリズムは十分に並列化されているため、プロセッサコアの数に応じて、複数のスレッドが同時にオブジェクトの割り当てに関与します。
このような状況で標準の新しい-deleteを使用すると、オブジェクトの削除に非常に大きな時間の損失が生じます。 デバッガーなしで削除が少なくとも数秒行われた場合、デバッガーが存在すると、メモリーの割り当て解除は約100（！）回遅くなり、プロジェクトのデバッグはまったく不可能になります。 さらに、割り当てられたオブジェクトの数が多いため、メモリアロケータの内部データのメモリオーバーランが非常に顕著になりました。
1つのタイプの膨大な数のオブジェクトを割り当て、それらのバッチを削除する問題を解決するために、ロックのないコンテナMassAllocatorが作成されました。 コードはVisual Studio 2012によってコンパイルされます。完全なプロジェクトコードはgithubで入手できます。
追加機能
私の場合、オブジェクトは相互に参照することができ、メモリを節約するために、小さなハックが発明されました。 オブジェクトの数は40億未満であることが保証されているため、4バイトを節約する64ビットポインターの代わりに32ビットインデックスが使用されました。 そのため、メモリ消費を約12％削減できました。
標準ライブラリアルゴリズム（std :: sortなど）を適用するために、イテレータをリポジトリに簡単に作成できることは素晴らしいボーナスであることがわかりました。
実装
アイデアは、ブロック内の要素を順番に選択することです。 標準のmallocは、要素の配列として論理的に表されるメモリブロックを割り当てます。 ユーザーが要素を選択する要求ごとに、配列の次の要素へのポインターが返され、選択された要素のカウンターが増分されます。 配列からすべての要素が選択されると、次のメモリブロックが要求されます。 メモリは非常に迅速に解放され、割り当てられたブロックはすべて、要素のデストラクタを呼び出すことなく解放されます。
すべてのブロックのサイズは同じであるため、パススルー番号を使用して要素にアクセスするのは非常に簡単です。
template <typename T> typename MassAllocator<T>::reference MassAllocator<T>::operator[](size_type index) { size_t indexOfBlock = index / elementsInBlockCount_; size_t indexInBlock = index % elementsInBlockCount_; return blocks_[indexOfBlock][indexInBlock]; }
新しいアイテムをハイライトします
そのため、すべての要素は連続してブロックに配置されます。 新しい要素の分布は非常に単純に見えます。選択した要素のカウンターを増やし、要素が分布している現在のブロックの場所が終わっていないことを確認し、必要に応じて新しいブロックを選択する必要があります。 もちろん、異なるスレッドからインクリメントされるカウンターは、アトミック変数std :: atomicを介して実装する必要があり、アルゴリズム自体はロックフリーでなければなりません！
アトミックカウンターはインデックスを順番に発行し、ブロック内に空きがある限りはすべて問題ありません。 しかし、ブロックは終了し、新しいブロックを選択する必要があります。 ブロックは1つのスレッドによって割り当てられ、残りはこの時間だけ一時停止し、ブロックの割り当て後に作業を再開する必要があります。 1つのアトミックカウンターを使用して、1つの仮定でこのロジックを実装できました。残りのスレッドがアイドル待機サイクルで32ビットカウンターをオーバーフローできないように、メモリブロックの割り当て時間が十分に短い必要があります。 アクセス同期のために、64ビットのアトミック変数が使用されました。これは論理的に2つの部分に分割されています。下位32ビットはブロック内の要素のカウンターで、上位32ビットは割り当てられたメモリブロックのカウンターです。 カウンターは次のように宣言されます。
std::atomic<uint64_t> curAtomicIndex_
各メモリブロックには、同じ数の要素、たとえば100000が割り当てられます。カウンターをインクリメントした後、ブロック内の要素カウンターについて3つの異なる状況が発生する可能性があります。
- 1〜99999の数字が受信されました。この状況は、ブロックに十分なスペースがあることを意味し、受信した数字で要素を予約しました。
- ブロックサイズ-100000と一致するインデックスが取得されました。これは、スレッドが「ラッキー」であり、ブロックが終了したことを意味します。 この場合、新しいメモリブロックを割り当て、そこからゼロ要素を取得し、最高のブロックカウンタをインクリメントし、最低のカウンタを最初の空き要素-1に設定し、新しい値をアトミック変数に書き込む必要があります。
- ブロックサイズより大きい数値のインデックスが受信されました。 これは、現在、スレッドの1つがメモリを割り当てていることを意味し、最下位のカウンターを1に設定するまで待機することを強制されます。この場合、急いではいけません。
std::this_thread::yield();
最初は、2つの32ビットカウンターで実装しようとしましたが、この場合は競合効果があります。 たとえば、ブロック内のインデックスに対して最初の要求が作成され、次にブロック番号が作成されます。
// ! uint32_t itemIndex = atomicIndex++; uint32_t blockIndx = atomicBlock.load();
スレッドがitemIndex要素の有効なインデックスを受信した場合がありますが、blockIndxブロックインデックスが受信されるまで、スレッドスケジューラーはスリープ状態にし、スリープ中に別のスレッドによって新しいブロックが割り当てられました。 したがって、エレメントインデックスとブロックインデックスの両方は、クリティカルセクションまたは1つのアトミック変数のいずれかでアトミックに取得する必要があります。
要素を選択するためのコードには、選択した要素へのポインタと同時にこの要素のインデックスを返すことができるという特性があり、64ビット整数の上部と下部への呼び出しは、ビット演算ではなく、ユニオンを介して編成されます。
template <typename T> typename MassAllocator<T>::pointer MassAllocator<T>::createElement(size_type *returningIndex) { // union 32 64 union { uint64_t index; struct HiLoParts { uint32_t itemIndex; uint32_t blockIndx; } parts; }; // index = curAtomicIndex_++; // , if(parts.itemIndex < elementsInBlockCount_) { if (returningIndex != nullptr) *returningIndex = parts.blockIndx * elementsInBlockCount_ + parts.itemIndex; return &(blocks_[parts.blockIndx][parts.itemIndex]); } if (parts.itemIndex == elementsInBlockCount_) { // auto bufferSize = elementsInBlockCount_ * sizeof(T); T* buffer = (T*)malloc(bufferSize); memset(buffer, 0, bufferSize); blocks_.push_back(buffer); // parts.blockIndx = (unsigned int)(blocks_.size() - 1); parts.itemIndex = 0; if (returningIndex != nullptr) *returningIndex = parts.blockIndx * elementsInBlockCount_ + parts.itemIndex; // setIndex(parts.blockIndx, 1); return &(blocks_[parts.blockIndx][parts.itemIndex]); } //, while(true) { // index = curAtomicIndex_++; if (parts.itemIndex == 0xffffffff) // , throw std::string("Atomic index overflow"); if (parts.itemIndex >= elementsInBlockCount_) { // , std::this_thread::yield(); continue; } // , if (returningIndex != nullptr) *returningIndex = parts.blockIndx * elementsInBlockCount_ + parts.itemIndex; return &(blocks_[parts.blockIndx][parts.itemIndex]); } }
性能
x64プラットフォームでは、MassAllocatorを使用した8スレッドでの8000万個の要素の割り当ては、i5 2500Kで約2000ミリ秒で実行され、70ミリ秒でリリースされます。 newを使用した分離は約1350ミリ秒で発生しますが、削除による削除は17400ミリ秒で実行されます。 デバッガーでは、プロジェクトがリリース構成でビルドされたとしても、テストが完了するのを一度も待つことができませんでした。
x86プラットフォームでのテストでは、new-deleteのオーバーヘッドが大きく、8,000万のオブジェクトに十分なアドレス空間がないため、割り当てられたオブジェクトの数を半分にする必要がありました。 4,000万のオブジェクトが2400ミリ秒でMassAllocatorによって割り当てられ、35ミリ秒で解放されます。一方、newは750ミリ秒で作業を行い、6430ミリ秒で削除されます。
予想通り、プロファイリングはボトルネックを示します-特にx86では、アトミックカウンターが増加します。 このフラグメントを高速化することに関して、まだ根本的なアイデアはありません。
おわりに
ロックフリーアルゴリズムは私にとって新しい分野です。そのため、アルゴリズムの正確性に関する考慮事項やコードの高速化に関する提案に耳を傾けます。
Update1
プロファイリングで示されているように、ほとんどの時間は64ビットカウンターcurAtomicIndex_のアトミックインクリメントに費やされています。 x64では、これは単一の
lock xadd QWORD PTR
コマンド
lock xadd QWORD PTR
に変換され、x86モードでは詩全体に変換されます
$again$158: ; 2424 : again: ; 2425 : mov ecx, edx; mov ecx, edx ; 2426 : mov ebx, eax; mov ebx, eax ; 2427 : add ebx, dword ptr _Value; add ebx, DWORD PTR $T7[ebp] ; 2428 : adc ecx, dword ptr _Value[4]; adc ecx, DWORD PTR $T7[ebp+4] ; 2429 : lock cmpxchg8b [esi]; lock cmpxchg8b QWORD PTR [esi] ; 2430 : jnz again; jne SHORT $again$158
したがって、64ビットモードでの要素の選択ははるかに高速です。
メモリの解放は、x64とx86の両方で高速です。
代替案は、
boost::object_pool
を使用することです。これはイデオロギー的に適していますが、マルチスレッドではなく、複数のスレッドで動作できます。
new-deleteを置き換えるには、
boost::fast_pool_allocator
試してください
boost::fast_pool_allocator
-deleteよりも高速で、32ビットモードでは、より高速な割り当てにより、MassAllocの分類（割り当て+リリース）全体で同等になります。
メモリ効率の面では、すべての選択肢はMassAllocに劣るため、32ビットモードではnew-deleteもboostもありません:: fast_pool_allocatorには8,000万のオブジェクトを収容するのに十分なアドレス空間がありますが、MassAllocatorは1570 MBしか消費しません。