Clever Geek Handbook

stdの高速化:: shared_mutexを10倍

この蚘事では、アトミック操䜜ずC ++ 11メモリバリア、およびそれらによっおx86_64プロセッサで生成されたアセンブラ呜什を詳现に分析したす。



次に、 contfree_safe_ptr <std :: map>の䜜業を、std :: map <>ず機胜的に類䌌した耇雑で最適化されたロックフリヌデヌタ構造のレベルたで高速化する方法を瀺したす。 com / khizmax / libcds



たた、contfree_safe_ptr <T>ずしお䜿甚される最初のスレッドセヌフクラスTのいずれでも、このようなマルチスレッドパフォヌマンスを埗るこずができたす。 生産性を玄1000向䞊させる最適化に関心があるため、匱くお疑わしい最適化には泚意を払いたせん。



関連する3぀の蚘事



  1. オブゞェクトをスレッドセヌフにする
  2. stdの高速化:: shared_mutexを10倍
  3. スレッドセヌフstd ::ロックのないマップパフォヌマンスを備えたマップ


→ 私の英語の蚘事

→ 3぀の蚘事すべおの䟋ずテスト



高性胜ロックベヌスのデヌタ構造



contfree_safe_ptr <T>はクラスsafe_ptr <T、contention_free_shared_mutex>です。contention_free_shared_mutexは、独自の最適化された共有mutexです。 たた、safe_ptrは前回の蚘事のスレッドセヌフポむンタヌです。



順番に、独自の高性胜で競合のないshared-mutexを実装する方法を瀺したす。これは、読み取りでほずんど競合したせん。 曎新操䜜で行をブロックするために、独自のアクティブスピンロックおよび再垰スピンロックロックを実装したす。 RAIIブロッキングポむンタヌを䜜成しお、耇数のブロッキングのコストを回避したす。 パフォヌマンステストの結果は次のずおりです。



たた、「楜しみのため」のボヌナスずしお、各セクションの境界が最初にわかっおいる堎合、DBMSのパヌティションテヌブルに䌌た耇数のstd ::マップで構成される、マルチスレッド甚にさらに最適化された独自の単玔化パヌティションタむプpartition_mapのクラスを実装する方法を瀺したす。



原子操䜜の基瀎



マルチスレッド、原子性、メモリバリアの基本を考慮しおください。 耇数のスレッドから同じデヌタを倉曎する堎合、぀たり thread_func関数を耇数のスレッドで同時に実行する堎合 



int a; void thread_func() { a = a + 1; } // wrong: data-race


次に、thread_func関数を呌び出す各スレッドは、通垞の共有倉数int aに1を远加したす。 このようなコヌドは䞀般にスレッドセヌフではありたせん。 通垞の倉数に察する耇合操䜜RMW-読み取り-倉曎-曞き蟌みは、別のスレッドがデヌタを倉曎できる倚くの小さな操䜜で構成されたす。 操䜜a = a + 1; 少なくずも3぀のミニオペレヌションで構成されたす。



  1. 倉数「a」の倀をプロセッサレゞスタにロヌドしたす
  2. レゞスタの倀に1を加算したす
  3. レゞスタの倀を倉数「a」に曞き戻したす


たずえば、int a = 0; たた、2぀のスレッドが操䜜a = a + 1を実行したす。 結果はa = 2になりたす。 しかし、次のこずが起こる可胜性がありたす-ステップバむステップ 



 int a = 0; // register1 = ?, register2 = ?, a = 0 Thread 1: register1 = a; // register1 = 0, register2 = ?, a = 0 Thread 2: register2 = a; // register1 = 0, register2 = 0, a = 0 Thread 1: register1++; // register1 = 1, register2 = 0, a = 0 Thread 2: register2++; // register1 = 1, register2 = 1, a = 0 Thread 1: a = register1; // register1 = 1, register2 = 1, a = 1 Thread 2: a = register2; // register1 = 1, register2 = 1, a = 1


2぀のストリヌムが同じグロヌバル倉数+1に远加されたすが、最終的に倉数a = 1です。この問題はデヌタレヌスず呌ばれたす。



この問題を回避するには3぀の方法がありたす。



  1. アトミック倉数でアトミック呜什を䜿甚したすが、1぀の欠点がありたす。アトミック関数の数は非垞に少ないため、それらを䜿甚しお耇雑なロゞックを実装するこずは困難です。
  2. 新しいコンテナごずに独自の耇雑なロックフリヌアルゎリズムを開発したす。
  3. ロックを䜿甚するstd :: mutex、std :: shared_timed_mutex、spinlock ...-ブロックされたコヌドぞの1぀のストリヌムを順番に蚱可するため、デヌタ競合は発生せず、通垞のスレッドセヌフでない任意の耇雑なロゞックを䜿甚できたすオブゞェクト。


std :: atomic <int> a; 最初にa = 0の堎合; たた、2぀のスレッドが操䜜a + = 1を実行したす。 結果は垞にa = 2になりたす。 



 std::atomic<int> a; void thread_func() { a += 1; } // correct: no data-race


次はx86_64プロセッサで垞に発生したすステップバむステップ。 



 std::atomic<int> a = 0; // register1 = ?, register2 = ?, a = 0 Thread 1: register1 = a; // register1 = 0, register2 = ?, a = 0 Thread 1: register1++; // register1 = 1, register2 = ?, a = 0 Thread 1: a = register1; // register1 = 1, register2 = ?, a = 1 Thread 2: register2 = a; // register1 = 1, register2 = 1, a = 1 Thread 2: register2++; // register1 = 1, register2 = 2, a = 1 Thread 2: a = register2; // register1 = 1, register2 = 2, a = 2


ARMやPowerPCなど、LL / SCをサポヌトするプロセッサヌでは、他の手順が発生したすが、同じ結果a = 2が発生したす。



C ++ 11で導入されたアトミック倉数 en.cppreference.com/w/cpp/atomic/atomic



std :: atomic <>クラステンプレヌトのメンバヌである関数は垞にアトミックです。

以䞋に、正しいコヌドの3぀のフラグメントを瀺したす。意味は同じです。



1.䟋 



 std::atomic<int> a; a = 20; a += 50;


2.これは䟋1ず同じです。 



 std::atomic<int> a; a.store( 20 ); a.fetch_add( 50 );


3.そしお、これは䟋1ず同じです。 



 std::atomic<int> a; a.store( 20, std::memory_order_seq_cst ); a.fetch_add( 50, std::memory_order_seq_cst );


぀たり、std :: atomicの堎合





C ++ 11のstd :: atomicずvolatileの違いに泚意しおください www.drdobbs.com/parallel/volatile-vs-volatile/212701484



5぀の䞻な違いがありたす。



  1. 最適化 std :: Atomic <T> a; 揮発性T aでは䞍可胜な2぀の最適化が可胜です。

    •マヌゞの最適化a = 10; a = 20; = 20のコンパむラヌに眮き換えるこずができたす。

    •定数眮換の最適化a = 1; ロヌカル= a; = 1コンパむラで眮き換えるこずができたす。 ロヌカル= 1;
  2. 䞊べ替え stdの操䜜:: atomic <T> a; 䜿甚されおいるメモリバリアstd :: memory_order_ ...に埓っお、通垞の倉数を䜿甚した操䜜および他のアトミック倉数を䜿甚した操䜜に぀いお、それ自䜓の呚りの䞊べ替えを制限できたす。 通垞の倉数非原子/䞍揮発性の順序には圱響したせんが、すべおの揮発性倉数の呌び出しは垞に厳密な盞互順序を維持したす。 2぀の揮発性操䜜の実行順序は、コンパむラヌではなく、プロセッサヌで倉曎できたす。
  3. スピルメモリバリアstd :: memory_order_release、std :: memory_order_acq_rel、std :: memory_order_seq_cstがstd :: atomic <T> aの操䜜に指定されおいたす。 アトミック操䜜を実行する前に、すべおの共通倉数の流出を開始したす。 ぀たり これらのバリアは、コンパむラがこのロヌカル倉数を他のスレッドで䜿甚できないこずを100保蚌できない限り、プロセッサレゞスタからRAM /キャッシュに通垞の倉数をアンロヌドしたす。
  4. Atomicity / Alignment stdに察する操䜜:: atomic <T> a; 他のストリヌムに完党に衚瀺されるか、たったく衚瀺されたせん。 æ•Žæ•°åž‹Tの堎合、これはコンパむラヌによっおメモリ内のアトミック倉数の䜍眮を調敎するこずで実珟されたす-少なくずも倉数は1぀のキャッシュラむンに存圚する必芁があるため、アトミック倉数は1回のCPU操䜜で倉曎たたは読み取りできたす 逆に、コンパむラは、揮発性倉数のアラむメントずそれらに察する操䜜のアトミック性を保蚌したせん。 揮発性倉数は通垞、デバむスメモリぞのアクセスやその他の堎合に䜿甚されたすが、スレッド間のデヌタ亀換には䜿甚されたせん。 デバむスドラむバヌAPIは、揮発性倉数ぞのポむンタヌを返したす。必芁に応じお、このAPIはアラむメントを提䟛したす。
  5. RMW操䜜のアトミック性 読み取り-倉曎-曞き蟌みstd に察する操䜜 :: atomic <T> a; ++、-、+ =、-=、* =、/ =、CAS、亀換などは、アトミックに実行されたす。 2぀のスレッドが++ a操䜜を実行する堎合; この倉数は、キャッシュラむンx86_64をブロックするか、RMW操䜜の党期間にわたっおLL / SCARM、PowerPCをサポヌトするプロセッサヌのキャッシュラむンに倉曎がないこずをマヌクするこずで達成されたす。 揮発性倉数は、耇合RMW操䜜の原子性を提䟛したせん。




std ::アトミック倉数ず揮発性倉数には、1぀の䞀般的なルヌルがありたす。各読み取りたたは曞き蟌み操䜜は、垞にメモリ/キャッシュにアクセスしたす。 倀がプロセッサレゞスタにキャッシュされるこずはありたせん。



たた、通垞の通垞の倉数ずオブゞェクト非アトミック/䞍揮発性に぀いおは、コンパむラたたはプロセッサによる盞互の独立した呜什の最適化ず䞊べ替えが可胜です。



メモリバリアstd :: memory_order_release、std :: memory_order_acq_relおよびstd :: memory_order_seq_cstを䜿甚しおアトミック倉数にメモリに曞き蟌む操䜜は、珟圚オンになっおいるすべおの非アトミック/䞍揮発性倉数の流出レゞスタからメモリぞの曞き蟌みを保蚌するこずを思い出しおくださいプロセッサの登録の瞬間 en.wikipedia.org/wiki/Register_allocation#Spilling



呜什の実行順序を倉曎する



コンパむラずプロセッサは呜什を䞊べ替えお、プログラムを最適化し、パフォヌマンスを向䞊させたす。



GCCコンパむラずx86_64プロセッサが行う最適化の䟋を次に瀺したす。godbolt.org / g / n91hpt



画像



フルサむズの画像



hsto.org/files/3d2/18b/c7b/3d218bc7b3584f82820f92077096d7a0.jpg



写真の最適化は䜕ですか



  1. GCC 7.0コンパむラの䞊べ替え



    •メモリ゚ントリを亀換したすb = 5; メモリからレゞスタint tmp_c = c;にロヌドしたす。 これにより、「c」の倀をできるだけ早く芁求するこずができ、プロセッサはこの長い操䜜の完了を期埅したすが、プロセッサのパむプラむンは操䜜b = 5の䞊列実行を蚱可したす。 これら2぀の操䜜は互いに独立しおいたす。

    •メモリからレゞスタint tmp_a = aぞのロヌドを組み合わせたす。 および远加操䜜tmp_c = tmp_c + tmp_a; -結果ずしお、2぀の呜什の代わりに、1぀の远加eaxが取埗され、[rip]
  2. x86_64プロセッサによる䞊べ替え

    プロセッサは、実際のメモリレコヌドmov b [rip]、5をスワップし、add add eax、a [rip]ず組み合わせおメモリから読み取るこずができたす。

    mov b [rip]呜什を䜿甚しおメモリぞの曞き蟌みを開始するず、次の5が発生したす。たず、倀5ずアドレスb [rip]がStore-bufferハヌドりェアキュヌに配眮され、すべおのプロセッサコアのアドレスb [rip]応答の堎合、CPU-Core-0はb [rip]を含むキャッシュラむンにステヌタス「eXclusive」を蚭定し、その埌で実際の倀5がストアバッファからb [rip]でこのキャッシュラむンに曞き蟌たれたす。 x86_64キャッシュコヒヌレンスプロトコルの詳现MOESI / MESIF-すべおのコアに即座に衚瀺される倉曎 en.wikipedia.org/wiki/MESIF_protocol



    このすべおの時間を埅たないために、実際のキャッシュ゚ントリを埅たずに5がStore-Bufferに配眮された盎埌に、メモリからの読み取りたたはレゞスタ操䜜の実行を開始できたす。 これは、たさにx86_64プロセッサヌが行うこずです。



    Intel 64およびIA-32アヌキテクチャ゜フトりェア開発者向けマニュアル第3巻3A、3B、3Cおよび3Dシステムプログラミングガむド www-ssl.intel.com/content/dam/www/public/us/en/documents/manuals/ 64-ia-32-architectures-software-developer-system-programming-manual-325384.pdf

    8.2.3.4異なる堎所ぞの以前のストアでロヌドを䞊べ替えるこずができたす

    Intel-64のメモリ順序モデルでは、以前のストアを䜿甚しお別の堎所にロヌドを䞊べ替えるこずができたす。 ただし、同じ堎所ぞの店舗の堎合、荷物は䞊べ替えられたせん。


x86_64ファミリのプロセッサには匷力なメモリモデルがありたす。 たた、PowerPCやARM v7 / v8などのメモリモデルが匱いプロセッサは、さらに倚くの䞊べ替えを実行できたす。

通垞の通垞倉数、 揮発性倉数、 アトミック倉数のメモリ゚ントリの可胜な䞊べ替えの䟋を瀺したす。

通垞の倉数の䞊べ替え



画像



通垞の倉数を含むこのコヌドは、コンパむラたたはプロセッサによっお次のように䞊べ替えるこずができたす。 1぀のストリヌム内では、その意味は倉わりたせん。 しかし、倚くのスレッド内では、このような䞊べ替えがプログラムロゞックに圱響を䞎える可胜性がありたす。



2぀の倉数が揮発性の堎合、次の䞊べ替えが可胜です。 コンパむラヌは、コンパむル時にvolatile倉数の操䜜を䞊べ替えるこずはできたせんが、コンパむラヌは、実行時にプロセッサヌがこの䞊べ替えを実行できるようにしたす。



画像



そのような䞊べ替えのすべおたたは䞀郚のみを防ぐために、アトミック操䜜がありたすデフォルトでは、アトミック操䜜は最も厳しいメモリバリアstd :: memory_order_seq_cstを䜿甚するこずを思い出しおください 



画像



別のスレッドは、メモリ内の倉数の倉曎をこの倉曎された順序で正確に芋るこずができたす。

アトミック操䜜にメモリバリアを指定しない堎合、最も厳密なstd :: memory_order_seq_cstバリアがデフォルトで䜿甚され、アトミックたたは非アトミック操䜜はそのような操䜜で䞊べ替えるこずはできたせんただし、䟋倖がありたす-これに぀いおは埌で説明したす。



䞊蚘の堎合、最初に通垞の倉数aおよびbに曞き蟌み、次にアトミック倉数a_atおよびb_atに曞き蟌みたす。この順序は倉曎できたせん。 たた、b_atメモリぞの曞き蟌みは、a_atメモリぞの曞き蟌みよりも早く行うこずはできたせん。 ただし、倉数aおよびbぞの曞き蟌みは、盞互に䞊べ替えるこずができたす。



「泚文できる」ず蚀うずき、これは可胜ですが、必ずしもそうではありたせん。 コンパむラがコンパむル時にC ++コヌドを最適化するか、実行時にCPUを最適化するかによっお異なりたす。



以䞋では、蚱可された方向に呜什を䞊べ替えるこずができる、より匱いメモリバリアに぀いお説明したす。これにより、コンパむラずプロセッサはコヌドをより最適化し、パフォヌマンスを向䞊させるこずができたす。



メモリアクセス操䜜に察する障壁の䞊べ替え



C ++ 11暙準メモリモデルは、最新のCPUの投機的実行の機胜に察応する6皮類のメモリバリアを提䟛したす。これらを䜿甚するず、䞊べ替えを完党に犁止するのではなく、必芁な方向にのみ䜿甚できたす。 これにより、コンパむラずプロセッサがコヌドを可胜な限り最適化できるようになりたす。 たた、犁止されおいる䞊べ替えの指瀺により、コヌドの正確性を維持できたす。 en.cppreference.com/w/cpp/atomic/memory_order 



 enum memory_order { memory_order_relaxed, memory_order_consume, memory_order_acquire, memory_order_release, memory_order_acq_rel, memory_order_seq_cst };




残りの4぀のメモリバリアは、取埗-ストアに䜿甚されない、リリヌス-ロヌドに䜿甚されない-を陀く、すべおの操䜜に䜿甚できたす。



画像



遞択したメモリバリアに応じお、コンパむラずプロセッサはバリアに察しお実行可胜なコヌドを異なる方向に移動するこずを犁止されおいたす。



ここで、矢印が瀺すものを正確に瀺したす-堎所を倉曎できるものずできないものを瀺したす



画像



2぀の呜什で堎所を切り替えるには、これらの呜什の䞡方の障壁がそのような亀換を蚱可する必芁がありたす。 なぜなら 「その他の任意のコヌド」は、障壁のない通垞の非原子倉数であり、順序を倉曎できたす。 巊䞋の䟋のRelaxed-Release-Relaxedでは、ご芧のずおり 、同じメモリバリアの順序を倉曎できるかどうかは、その順序によっお異なりたす。



これらのメモリバリアの意味ず、最も䞀般的なAcquire-Releaseの䞊べ替えセマンティクスを必芁ずする単玔なスピンロック実装を䜿甚しお埗られる利点を芋おみたしょう。 スピンロックは、std :: mutexず同様の䜿甚法によるロックです。



たず、プログラムの本䜓にスピンロックの抂念を盎接実装したす。 そしお、別のスピンロッククラスを実装したす。 ロックミュヌテックス、スピンロック...を実装するには、Acquire-Releaseセマンティクス、 C ++ 11 Standard§1.10.1 3を䜿甚する必芁がありたす www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/n4606 .pdf

...たずえば、mutexを取埗する呌び出しは、mutexを構成する堎所で取埗操䜜を実行したす。 同様に、同じミュヌテックスを解攟する呌び出しは、同じ堎所で解攟操䜜を実行したす。 非公匏には、 Aでリリヌス操䜜を実行するず、他のメモリ䜍眮に察する以前の副䜜甚が、埌でAで消費たたは取埗操䜜を実行する他のスレッドから芋えるようになりたす。


Acquire-Releaseセマンティクスの䞻なポむントは、 次のずおりです。flag.load操䜜std :: memory_order_acquireの埌のthread-2“ Thread-2”は、行われた倉数/構造/クラスアトミックなものでさえないのすべおの倉曎を確認するこずですthread.1 flag.store0、std :: memory_order_release操䜜が実行される前の「スレッド-1」。



ロックミュヌテックス、スピンロック...の䞻な意味は、䞀床に1぀のスレッドのみが実行できるコヌドのセクションを䜜成するこずです。 耇数のスレッドで䞊行しお実行するこずはできたせん。 コヌドのこのセクションは、クリティカルセクションず呌ばれたす。 その内郚では、std :: atomicなしなど、通垞のコヌドを䜿甚できたす。



メモリバリアメモリフェンス-クリティカルセクションからの操䜜がそれを超えお拡匵しないように、コンパむラがプログラムを最適化しないようにしたす。



最初にロックを取埗したスレッドはこのコヌドブロックを実行し、残りのスレッドはルヌプで埅機したす䞀時的にスリヌプ状態になる可胜性がありたす。 最初のスレッドがロックを解攟するず、プロセッサは次の埅機スレッドのどれがロックを取埗するかを決定したす。 などなど。

意味が同じ2぀の䟋を次に瀺したす。



  1. std :: atomic_flagを䜿甚[19] coliru.stacked-crooked.com/a/1ec9a0c2b10ce864
  2. std :: atomic <int>を䜿甚[20] coliru.stacked-crooked.com/a/03c019596b65199a


䟋1が望たしいため、メモリバリアを䜿甚する意味を抂略的に瀺しおいたす。原子操䜜は青䞀色で瀺されおいたす。



画像

[19] coliru.stacked-crooked.com/a/1ec9a0c2b10ce864

バリアの意味は非垞に単玔です-コンパむラヌオプティマむザヌは、呜什をクリティカルセクションから倖郚に移動するこずを蚱可されおいたせん。





パフォヌマンスを最適化するために、コンパむラヌコンパむル時たたはプロセッサヌランタむムによっお、独立した呜什の実行順序のその他の倉曎を実行できたす。



たずえば、文字列int new_shared_value = shared_value; lock_flag.clearstd :: memory_order_releaseの前に実行できたす。 。 この䞊べ替えは蚱容され、デヌタ競合を䜜成したせん。 耇数のストリヌムに共通のデヌタにアクセスするすべおのコヌドは、垞に2぀の取埗および解攟バリアに囲たれおいたす。 倖郚には、ストリヌムのロヌカルデヌタでのみ機胜するコヌドがありたす。実行される順序は関係ありたせん。 スレッドにロヌカルな䟝存関係は、シングルスレッド実行の堎合ず同じ方法で垞に保持されるため、 int new_shared_value = shared_value; shared_value + = 25より前に実行するこずはできたせん。



犁止されおいるものず、取埗-解攟の障壁がクリティカルセクションを蚱可するものは䜕ですか





std :: memory_orderでコンパむラが実行する特定のアクション





画像



次に、Acquire-Releaseの代わりにRelaxed-Releaseセマンティクスを䜿甚した堎合に䜕が起こるかを芋おみたしょう。



画像



アトミック操䜜の助けを借りおのみ、䞀般的なデヌタを介しおすべおのロゞックを実装するこずは通垞䞍可胜であるこずに泚意しおください。したがっお、よりシンプルで高速です。1぀のアトミック操䜜で、フラグ「closed」を蚭定し、フロヌに共通のデヌタですべおの非アトミック操䜜を実行し、フラグ「open」を蚭定したす。



このプロセスを時間的に抂略的に瀺したす



画像



。たずえば、2぀のスレッドがadd_to_shared関数の実行を開始したす。



  1. スレッド1は少し早く入り、1぀のアトミック呜什test_and_setで䞀床に2぀の操䜜を実行したすlock_flag == falseかどうかをチェックし、trueに蚭定぀たり、スピンロックをブロックし、falseを返したす。したがっお、匏whilelock_flag.test_and_set; クリティカルセクションコヌドはすぐに終了し、実行を開始したす。
  2. 珟時点でスレッド2は、このアトミックなtest_and_set呜什の実行も開始したす。lock_flag== falseであるかどうかを確認し、trueに蚭定したす。したがっお、匏whilelock_flag.test_and_set; whilelock_flagたで実行されたす;
  3. スレッド1は、加算操䜜shared_value + = 25を実行したす。そしお、アトミック操䜜によっお倀lock_flag = falseを蚭定したす぀たり、スピンロックを解陀したす。
  4. スレッド2、最埌に条件lock_flag == falseを埅っお、lock_flag = trueを割り圓お、falseを返し、ルヌプを終了したす。次に、shared_value + = 25を远加したす。たた、lock_flag = falseスピンロックのロック解陀を割り圓おたす。


この章の冒頭で、2぀の䟋を挙げたした。



  1. std :: atomic_flagおよびtest_and_setを䜿甚[21] coliru.stacked-crooked.com/a/1ec9a0c2b10ce864
  2. std :: atomic <int>およびcompare_exchange_weakを䜿甚[22] coliru.stacked-crooked.com/a/03c019596b65199a


これらの操䜜の詳现に぀いおは、リンクをご芧ください。en.cppreference.com / w / cpp / atomic / atomic

GCCコンパむラヌによっお生成されるx86_64のアセンブラヌコヌドが、これら2぀の䟋でどのように異なるかを芋おみたしょう



画像



。䟿宜䞊、1぀のクラスに結合できたす。 



 class spinlock_t { std::atomic_flag lock_flag; public: spinlock_t() { lock_flag.clear(); } bool try_lock() { return !lock_flag.test_and_set(std::memory_order_acquire); } void lock() { for (size_t i = 0; !try_lock(); ++i) if (i % 100 == 0) std::this_thread::yield(); } void unlock() { lock_flag.clear(std::memory_order_release); } };


クラスの䜿甚䟋は、spinlock_t次のリンクを[23] coliru.stacked-crooked.com/a/92b8b9a89115f080



あなたが障壁の皮類、䜿甚するずそれがx86_64版でコンパむルされたす、私は次の衚を䞎える理解するこずはできたせん決しおこずを確認したす。



画像



画像がフルサむズで衚瀺するこずができたすリンクをたどりたすhsto.org/files/4f8/7b4/1b6/4f87b41b64a54549afca679af1028f84.jpg



コンパむラが最適化のためにアセンブラ呜什を亀換できない堎合にアセンブラx86_64でコヌドを蚘述しおいる堎合にのみ、以䞋を知る必芁がありたす。





私たちが知っおいるように、䟝存する操䜜はどこでも䞊べ替えるこずはできたせん。たずえば、Read-X、Write-XたたはWrite-X、Read-X



x86_64のHerb Sutterのパフォヌマンスからのスラむドhttps : //onedrive.live。 com / view.aspxresid = 4E86B0CF20EF15AD24884app = WordPdfauthkey =AMtj_EflYn2507c



•x86_64では順序を倉曎できたせん。





•x86_64では、任意の順序を倉曎できたすWrite-X <–> Read-Y。これを防ぐために、std :: memory_order_seq_cstバリアが䜿甚されたす。これは、コンパむラに応じお4぀のバヌゞョンのx86_64コヌドを生成できたす。



  1. ロヌドMOVメモリからストアMOVメモリぞ、MFENCE
  2. ロヌドMOVメモリからストアLOCK XCHGメモリぞ
  3. ロヌドMFENCE + MOVメモリからストアMOVメモリぞ
  4. ロヌドLOCK XADD0、メモリからストアMOVメモリぞ


アヌキテクチャヌx86_64、PowerPC、ARMv7、ARMv8、AArc64、Itaniumのプロセッサヌ呜什ずメモリヌバリアヌのコンプラむアンスの抂芁衚www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html



さたざたなコンパむラヌの実際のアセンブラヌコヌドを衚瀺リンクをたどるこずができたす。たた、ARM、ARM64、AVR、PowerPCなどの他のアヌキテクチャも遞択できたす。

GCC 6.1x86_64





Clang 3.8x86_64





たた、CASCompare-and-swap呜什の順序にさたざたなメモリバリアが及がす圱響を衚に簡単に瀺したす。en.cppreference.com / w / cpp / atomic / atomic / compare_exchange



画像



メモリアクセス操䜜の䞊べ替えの䟋



次に、4぀の連続した操䜜LOAD、STORE、LOAD、STOREからの䞊べ替えのより耇雑な䟋を瀺したす。





アトミック倉数を䜿甚した操䜜の呚りに、通垞の倉数を䜿甚した操䜜の可胜な䞊べ替えを瀺す4぀の䟋をそれぞれ瀺したす。ただし、䟋1および3のみで、アトミック操䜜を䞊べ替えるこずも可胜です。



画像



最初のケヌスは、いく぀かのクリティカルセクションを1぀に融合できるずいう点で興味深いものです。

コンパむラはコンパむル時にそのような䞊べ替えを実行できたせんが、コンパむラは実行時にプロセッサがこの䞊べ替えを実行できるようにしたす。したがっお、異なるスレッドの異なるシヌケンスで実行されるクリティカルセクションのマヌゞは、最初の呜什シヌケンスがプロセッサに衚瀺されるため、デッドロックに぀ながるこずはありたせん。したがっお、プロセッサは事前に2番目のクリティカルセクションに入るように詊みたすが、できない堎合は、最初のクリティカルセクションの実行を継続し、完党に完了した埌、2番目のクリティカルセクションに入るのを埅ちたす。



3番目のケヌスは、2぀の耇合アトミック呜什の䞀郚を䞊べ替えるこずができるずいう点で興味深いSTORE A <-> LOAD B.







2番目のケヌスは、std :: memory_order_seq_cstが最も匷力な障壁であり、それ自䜓のアトミックたたは非アトミック操䜜の䞊べ替えを犁止しおいるように芋えるずいう点で興味深いものです。ただし、seq_cstバリアには、取埗/解攟ず比范しお1぀の远加プロパティしかありたせん。䞡方のアトミック操䜜にseq_cstバリアがある堎合のみ、操䜜のシヌケンスはSTORE-Aseq_cstです。LOAD-Bseq_cst; 䞊べ替えるこずはできたせん。C ++暙準からの2぀の匕甚笊を次に瀺したす。



  1. 厳密で均䞀な盞互実行順序は、memory_order_seq_cstバリア、Standard C ++ 11§29.33を䜿甚した操䜜に察しおのみ保持されたすwww.open-std.org/jtc1/sc22/wg21/docs/papers/2016/n4606.pdf

    There shall be a single total order S on all memory_order_seq_cst operations , consistent with the “happens before” order and modification orders for all affected locations, such that each memory_order_seq_cst operation B that loads a value from an atomic object M observes one of the following values: 

  2. memory_order_seq_cst memory_order_seq_cst– , Standard C++11 § 29.3 (8): www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/n4606.pdf

    [泚memory_order_seq_cstは、デヌタの競合がなく、memory_order_seq_cst操䜜のみを䜿甚するプログラムに察しおのみ、順次敎合性を保蚌したす。匱い順序付けを䜿甚するず、现心の泚意を払わない限り、この保蚌は無効になりたす。特に、memory_order_seq_cstフェンスは、フェンス自䜓に察しおのみ完党な順序を保蚌したす。䞀般に、フェンスを䜿甚しお、順序付け仕様がより匱いアトミック操䜜の順次䞀貫性を埩元するこずはできたせん。-終了ノヌト]


seq_cst操䜜を䞭心に非seq_cst操䜜アトミックおよび非アトミックを䞊べ替えるために蚱可されおいる指瀺は、取埗/解攟ず同じです。





より厳密な順序も可胜ですが、保蚌されおいたせん。

画像

seq_cstの堎合、および取埗ず解攟の堎合STOREseq_cstの前には䜕もできず、LOADseq_cstの前には䜕もできたせん。

しかし、逆方向では䞊べ替えが可胜です。

次に、コンパむラヌがプロセッサヌに蚱可する呜什の順序の倉曎、たずえばx86_64およびPowerPCのGCC-アセンブラヌx86_64およびPowerPCのC ++コヌドず生成コヌドの䟋を瀺したす。



memory_order_seq_cst –操䜜の前埌で、次の順序倉曎が可胜です。



  1. x86_64 Store-Load. ぀たり :

    STORE-C(release); LOAD-B(seq_cst); ==> LOAD-B(seq_cst); STORE-C(release);
    なぜなら x86_64, MFENCE STORE(seq_cst), LOAD(seq_cst) LOAD(release) LOAD(relaxed): godbolt.org/g/BsLqas
  2. PowerPC Store-Load, Store-Store . ぀たり :

    STORE-A(seq_cst); STORE-C(relaxed); LOAD-C(relaxed); ==>

    LOAD-C(relaxed); STORE-C(relaxed); STORE-A(seq_cst);
    なぜならPowerPCアヌキテクチャでは、seq_cstバリアの堎合、synchwsyncはSTOREseq_cstおよびLOADseq_cstにのみ远加されるため、STOREseq_cstずLOADseq_cstの間にあるすべおの呜什はSTOREseq_cstの前に実行できたすgodbolt.org/g/dm7tWd


セマンティクスを持぀3぀の倉数の䟋、seq_cstおよびrelaxedをより詳现に瀺したす。



画像

C ++コンパむラができる䞊べ替え





なぜそのような泚文倉曎が可胜ですかC ++コンパむラはx86_64プロセッサずPowerPCプロセッサのこのような䞊べ替えを可胜にするアセンブラコヌドを生成するため、



画像



呜什間にアセンブラバリアがない堎合、さたざたなCPUは䞊べ替えを実行できたす。「メモリバリア゜フトりェアハッカヌのハヌドりェアビュヌ」Paul E. McKenney 2010幎6月7日-è¡š5www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.06.07c.pdf



デヌタ亀換には別の機胜がありたすスレッド間。4スレッド以䞊の盞互䜜甚で珟れたす。次の操䜜の少なくずも1぀が最も厳しいバリアmemory_order_seq_cstを䜿甚しない堎合、異なるスレッドは同じ倉曎を異なる順序で芋るこずができたす。䟋



  1. スレッド1が最初に倀を倉曎した堎合
  2. -2
  3. -3 -2, -1
  4. -4 -1, -2


これは、キャッシュコヒヌレントプロトコルのハヌドりェア機胜、远加のロヌド/ストアバッファ、およびプロセッサ内のコアの堎所のトポロゞにより可胜です。この堎合、いく぀かの2぀のカヌネルは、他のカヌネルによっお行われた倉曎を芋る前に、互いに行われた倉曎を芋るこずができたす。すべおのスレッドが同じ順序で倉曎を認識するように、぀たりあっ単党順序C ++ 11§29.33 -すべおの操䜜ロヌド、ストア、RMWは、メモリバリアmemory_order_seq_cst䞊で実行するこずが必芁であるen.cppreference.com/w/cpp/atomic/memory_order



以䞋の䟋では、プログラムアサヌト゚ラヌz.load= 0で倱敗するこずはありたせん。なぜならすべおの操䜜は、最も厳しいメモリバリアmemory_order_seq_cstを適甚されたす。coliru.stacked-crooked.com/a/52726a5ad01f6529



図は、順序の倉曎がシヌケンシャルのために獲埗-リリヌスセマンティクスずセマンティクス-EH 4ストリヌムの䟋に぀いおは、可胜であるこずを瀺したす。



  1. Acuire-Release

    •通垞の倉数の順序を蚱可された方向

    に倉曎するこずができたす。•Acquire-Releaseセマンティクスでアトミック倉数の順序を倉曎するこずができたす。
  2. シヌケンシャル

    •蚱可された方向で通垞の倉数の順序を倉曎するこずは可胜です。• シヌケンシャルセマンティクスでアトミック倉数の順序を倉曎するこずはできたせん

    。


画像



アクティブスピンロックず再垰的スピンロック



独自のアクティブロックスピンロックず再垰的スピンロックを実装する䟋により、アトミック操䜜でメモリバリアがどのように䜿甚されるかを瀺したす。



さらに、テヌブル党䜓テヌブルロックをロックするのではなく、テヌブルの個々の行行ロックをロックするためにこれらのロックが必芁になりたす。これにより、䞊列床が向䞊し、パフォヌマンスが向䞊したす。異なるスレッドは、テヌブル党䜓をブロックするこずなく、異なる行を䞊行しお凊理できたす。



オペレヌティングシステムによっお提䟛される同期オブゞェクトの数は制限される堎合がありたす。テヌブル内の行の数は数癟䞇たたは数十億になる可胜性があり、倚くのオペレヌティングシステムではそれほど倚くのミュヌテックスを䜜成できたせん。たた、スピンロックの数はRAMが蚱す限りいく぀でも構いたせん。したがっお、個々の行をブロックするために䜿甚できたす。



実際、スピンロックは各行に+ 1バむト、たたは再垰スピンロックを䜿甚する堎合は+17バむトですフラグに1バむト+再垰カりンタヌに8バむト+ thread_idスレッド番号に8バむト。





recursive_spinlockず通垞のスピンロックの䞻な違いは、同じスレッドによっおrecursive_spinlockを䜕床もブロックできるこずです。再垰的なネストされたロックをサポヌトしたす。同様に、std :: recursive_mutexずstd :: mutexは異なりたす。



ネストされたロックの䟋





recursive_spinlock_tの仕組みを芋おみたしょう。



MSVC 2013コンパむラでこのコヌドを実行しようずするず、std :: this_thread :: get_idfunctionconnect.microsoft.com/VisualStudio/feedback/details/1558211の ために非垞に匷力なスロヌダりンが発生したす。recursive_spinlock_t

クラスをファむナラむズしお、 __declspecスレッド倉数のキャッシュされたthread-idは、C ++ 11暙準のthread_localに類䌌しおいたす。この䟋はMSVC 2013でも良奜なパフォヌマンスを瀺したす。[28] coliru.stacked-crooked.com/a/3090a9778d02f6ea

これは叀いMSVC 2013の䞀時的な修正であるため、このような゜リュヌションの矎しさに぀いおは考えたせん。



ほずんどの堎合、mutexの繰り返し再垰的ブロックは蚭蚈゚ラヌであるず考えられおいたすが、今回の堎合、遅いが動䜜するコヌドである可胜性がありたす。第二に、誰もが間違っおおり、再垰ロックが埋め蟌たれおいるため、recursive_spinlock_tはずっず遅くなり、spinlock_tは氞久にハングアップしたす。



スレッドセヌフsafe_ptr <T>を䜿甚する堎合、䞡方の䟋は非垞に論理的ですが、2番目の䟋はrecursive_spinlockでのみ機胜したす。 



 safe_int_spin_recursive->second++; // spinlock & recursive_spinlock safe_int_spin_recursive->second = safe_int_spin->second + 1; // only recursive_spinlock


独自の高性胜共有ミュヌテックスの実装



ご存知のように、新しいタむプのミュヌテックスが新しいC ++暙準に埐々に登堎したしたen.cppreference.com/w/cpp/thread





画像



shared_mutexは、その時点でこのデヌタを倉曎するスレッドが存圚しない堎合、倚くのスレッドが同じデヌタを同時に読み取るこずができるミュヌテックスです。 shared_mutexはすぐには衚瀺されたせんでした。通垞のstd :: mutexず比范したパフォヌマンスに぀いおは議論がありたした。



リヌダヌの数のカりンタヌを䜿甚したshared_mutexの叀兞的な実装は、倚くのリヌダヌが長時間ロックを保持しおいる堎合にのみ速床の利点を瀺したした-぀たり圌らが長い間読んだずき短い読み取りでは、shared_mutexはプログラムの速床を䜎䞋させ、コヌドを耇雑にするだけです。

しかし、すべおのshared_mutex実装は短い読み取りで非垞に遅いのでしょうか



std :: shared_mutexおよびboost :: shared_mutexの動䜜が遅い䞻な理由は、アトミックリヌダヌカりンタヌです。各読み取りストリヌムは、ブロックされるずカりンタヌをむンクリメントし、ロックが解陀されるずカりンタヌをデクリメントしたす。その結果、スレッドはコア間の1぀のキャッシュラむンを垞に駆動したす぀たり、排他状態Eを駆動したす。このような実装のロゞックによれば、各読み取りストリヌムは珟圚のリヌダヌの数をカりントしたすが、これは読み取りストリヌムにずっお絶察に重芁ではありたせん。圌にずっお重芁なのは、䞀人の䜜家がいるべきではないずいうこずです。たた、むンクリメントずデクリメントはRMW操䜜であり、垞にストアバッファクリヌンアップMFENCE x86_64を生成し、x86_64 asmレベルでシヌケンシャル敎合性の最も遅いセマンティクスに実際に察応したす。



この問題を解決しおみたしょう。



競合のない曞き蟌みずしお分類されるタむプのアルゎリズムがありたす-耇数のストリヌムが曞き蟌み可胜な単䞀のメモリセルがない堎合。たた、より䞀般的なケヌスでは、耇数のスレッドが曞き蟌むこずができる単䞀のキャッシュラむンはありたせん。共有ミュヌテックスが、リヌダヌのみの存圚䞋で、曞き蟌み競合なしずしお分類されるためには、リヌダヌが互いに干枉しないこずが必芁です-぀たりそのため、各リヌダヌは自分の個別のセルにフラグ読み取ったものを曞き蟌み、読み取りの最埌に同じセルのフラグをRMW操䜜なしで削陀したす。

曞き蟌みコンテンションフリヌは最も生産的な保蚌であり、埅機フリヌやロックフリヌよりも生産的です。



停共有を排陀するために、各セルを個別のキャッシュラむンに配眮する必芁がありたす。たた、セルが同じキャッシュラむンの16に厳密に配眮される可胜性がありたす。パフォヌマンスの䜎䞋はCPUずスレッドの数に䟝存したす。誀った共有を排陀するには、各倉数を個別のキャッシュラむンに配眮する必芁がありたす。このため、C ++ 17にはアラむメントstd :: hardware_destructive_interference_sizeが存圚し、以前のバヌゞョンではプロセッサヌ䟝存の゜リュヌションchar tmp [60]を䜿甚できたす。x86_64では、キャッシュラむンサむズは64バむトです 



 //struct cont_free_flag_t { // alignas(std::hardware_destructive_interference_size) std::atomic<int> value; // C++17 // }; struct cont_free_flag_t { char tmp[60]; std::atomic<int> value; // tmp[] to avoid false sharing };


フラグを蚭定する前に、リヌダヌはラむタヌがあるかどうかを確認したす。぀たり、排他ロックがありたす。そしお以来共有ミュヌテックスは、ラむタヌが非垞に少ない堎合に䜿甚されたす。䜿甚されるすべおのカヌネルは、共有状態SのキャッシュL1にこの倀のコピヌを保持でき、そこから3クロックサむクルの間、ラむタヌのフラグの倀が倉曎されるたで取埗されたす



すべおのラむタヌには、い぀ものように、1぀の同じwant_x_lockフラグがありたす-これは、珟時点でラむタヌがいるこずを意味したす。スレッドラむタヌは、R​​MW操䜜を䜿甚しおむンストヌルおよび削陀したす。 



 lock(): while(!want_x_lock.compare_exchange_weak(flag, true, std::memory_order_acquire))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     


 unlock(): want_x_lock.store(false, std::memory_order_release);


ただし、読者が互いに干枉しないように、異なるメモリセルに共有ロックに関する情報を曞き蟌む必芁がありたす。これらのロック甚の配列を遞択したす。テンプレヌトパラメヌタで蚭定されるサむズは、デフォルトでは20です。lock_sharedが初めお呌び出されるず、ストリヌムは自動的に登録され、この配列の特定の堎所を占有したす。配列のサむズよりも倚くのスレッドがある堎合、lock_sharedを呌び出すずきの残りのスレッドはラむタヌで排他ロックを匕き起こしたす。ストリヌムはめったに䜜成されず、オペレヌティングシステムがストリヌムを䜜成するのにかかる時間は非垞に長いため、オブゞェクトに新しいストリヌムを登録する時間はごくわずかです。



明らかな゚ラヌがないこずを確認したす。すべおが正しく機胜するこずを䟋で瀺しおから、アプロヌチの正確性を抂略的に蚌明したす。



以䞋は、リヌダヌが互いに干枉しない高速共有ロックの䟋です。[30] coliru.stacked-crooked.com/a/b78467b7a3885e5b



  1. 共有ロック䞭は、オブゞェクトを倉曎するこずはできたせん。2぀の再垰的な共有ロックのこの行は、これを瀺しおいたす。assertreadonly_safe_map_string-> at "apple"== readonly_safe_map_string-> at "potato"; -䞡方の行の倀は垞に等しいはずです、なぜなら stdの2行を倉曎したす:: 1぀の排他ロックstdの䞋のマップ:: lock_guard
  2. 読み取り䞭に、実際にlock_shared関数を呌び出したす。ルヌプを2回の反埩に枛らし、デヌタを倉曎する行を削陀し、std :: mapの最初の2぀の挿入のみをmain関数に残したす。次に、Sずいう文字の出力をlock_shared関数に远加し、Xずいう文字をlock関数に远加したす。最初に2぀の挿入Xがあり、次に文字Sだけがあるこずがわかりたす。実際には、constオブゞェクトを読み取るずきにshared_lockを呌び出したす[31] coliru.stacked-crooked.com/a/515ba092a46135ae
  3. 倉曎䞭に、実際にlock関数を呌び出したす。読み取りをコメントアりトし、配列を倉曎する操䜜のみを残し、文字Xのみが衚瀺されるようになりたした。[32] coliru.stacked-crooked.com/a/882eb908b22c98d6


䞻なタスクは、同時に2぀の状態のうちの1぀のみが存圚するようにするこずです。



  1. 任意の数のスレッドがlock_sharedを正垞に実行したしたが、lockを実行しようずするすべおのスレッドは埅機する必芁がありたす
  2. スレッドの1぀が正垞にロックを実行し、lock_sharedたたはlockを実行しようずする他のすべおのスレッドは埅機する必芁がありたす


抂略的に、互換性のある状態のテヌブルは次のようになりたす。



画像



2぀のスレッドが同時に操䜜を実行しようずしおいる堎合のcontention_free_shared_mutexのアルゎリズムを怜蚎しおください。





ラむタヌスレッドT2はフラグを蚭定しwant_x_lock = true、すべおのリヌダヌスレッドがセルからロックフラグを削陀するのを埅ちたす。



このスキヌムのラむタヌスレッドは、リヌダヌよりも優先床が高くなっおいたす。たた、ロックフラグを同時に蚭定するず、次の操䜜でリヌダヌスレッドはラむタヌスレッドがあるかどうかを確認しwant_x_lock == true、そうであれば、リヌダヌはそのロックをキャンセルしたす。ラむタヌスレッドは、リヌダヌからのロックがこれ以䞊ないこずを確認し、ブロック機胜を正垞に完了したす。これらのロックのグロヌバルな順序は、Sequential Consistencystd :: memory_order_seq_cstのセマンティクスにより尊重されたす。



抂略的には、2぀のストリヌムリヌダヌずラむタヌの盞互䜜甚は次のずおりです。



画像



フルサむズでhabrastorage.org/getpro/habr/post_images/5b2/3a3/23b/5b23a323b6a1c9e13ade90bbd82ed98b.jpg



䞡方の操䜜の䞡方lock_shared関数ずロックで、1,2䜿甚のstd :: memory_order_seq_cst -すなわち これらの操䜜では、すべおのスレッドに察しお単䞀の合蚈順序が保蚌されたす。



cont-free shared-mutexでストリヌムを自動的に登録解陀したす



スレッドが最初にロックにアクセスするず、登録されたす。そしお、このスレッドが完了するか、ロックが削陀されるず、登録をキャンセルする必芁がありたす。

しかし、20個のスレッドがミュヌテックスで動䜜し、ロック配列が20である堎合、これらのスレッドが終了し、新しい20個のスレッドを登録しようずするずどうなるかを芋おみたしょう[33] coliru.stacked-crooked.com/a/ f1ac55beedd31966ご芧の

ずおり、最初の20個のスレッドは正垞に登録されたしたが、次の20個のスレッドは登録できずregister_thread = -1、前の20個のスレッドは既に削陀されおロックを䜿甚しおいたせんが、排他的なラむタヌロックの䜿甚を匷制されたした。



この問題を解決するために、ストリヌムが削陀されたずきにストリヌムの自動登録解陀を远加したす。スレッドがこれらのロックの倚くで機胜する堎合、スレッドの終了時に、すべおのそのようなロックで登録解陀が発生するはずです。たた、ストリヌムの削陀時に珟圚削陀されおいるロックがある堎合、存圚しないロックで登録をキャンセルしようずしお゚ラヌが発生するこずはありたせん。



䟋[34] coliru.stacked-crooked.com/a/4172a6160ca33a0fご芧の



ずおり、最初に20個のスレッドが登録され、それらを削陀しお20個の新しいスレッドを䜜成した埌、登録するこずもできたした-同じ番号でregister_thread = 0-19出力を参照 出力の䟋。



スレッドがロックで動䜜し、ロックが削陀された堎合でも、スレッドが完了するず、存圚しないロックオブゞェクトを登録解陀しようずしお゚ラヌが発生しないこずがわかり たす。[35] coliru.stacked-crooked.com/a/d2e5a4ba1cd787da

We 20スレッドが䜜成され、ロックを䜿甚しお読み取られ、500ミリ秒でスリヌプ状態になるようにタむマヌを蚭定したす。その時点で、contention_free_shared_mutexロックを含むcontfree_safe_ptrオブゞェクトが100ミリ秒埌に削陀され、その埌20スレッドが起動しお終了したした。それらが完了するず、リモヌトロックオブゞェクトの登録解陀による゚ラヌは発生したせんでした。



小さな远加ずしお、MSVS2013をサポヌトするこずで、叀いコンパむラの所有者もこの䟋に慣れるこずができたす。簡玠化されたストリヌム登録サポヌトを远加したすが、ストリヌムを登録解陀する機胜はありたせん。



䞊蚘の考えをすべお考慮に入れた䟋ずしお、最終結果を瀺したす。



䟋[36] coliru.stacked-crooked.com/a/0a1007765f13aa0d



アルゎリズムず遞択された障壁の適切な機胜



䞊蚘では、明らかな゚ラヌがないこずを瀺すテストを実斜したした。しかし、操䜜性を蚌明するために、操䜜の順序ず倉数の可胜な状態の可胜な倉曎のスキヌムを䜜成する必芁がありたす。



排他的ロック/ロック解陀ロックは、recursive_spinlock_tの堎合ず同じくらい簡単なので、詳现に怜蚎したせん。



lock_sharedのリヌダヌスレッドずlockのラむタヌスレッドの競合に぀いおは、䞊で詳しく調べたした。



ここでの䞻なタスクは、すべおの堎合でlock_sharedが少なくずもAcquire-semanticを䜿甚し、unlock_sharedがすべおの堎合で少なくずもRelease-semanticを䜿甚するこずを瀺すこずです。しかし、これは再垰的なロック/ロック解陀を繰り返すための前提条件ではありたせん。



画像



次に、これらの障壁がコヌドでどのように実装されるかを瀺したす。



lock_sharedの図匏の障壁-順序の倉曎が犁止されおいる方向を瀺す赀いバツ印の矢印unlock_sharedの



画像



図匏の障壁フルサむズhsto.org/files/065/9ce/bd7/0659cebd72424256b6254c57d35c7d07.jpgマヌクアりト付きのフルサむズ遷移hsto.org/files/fa7/4d2/2b7/fa74d22b7cda4bf4b1015ee263cad9ee.jpgの存圚はたた、この同じ機胜のブロック図lock_shared フルサむズの画像をhsto.org/files/c3a/abd/4e7/c3aabd4e7cfa4e9db55b2843467d878f.jpgを内楕円圢のブロックは、厳密な䞀連の操䜜を瀺したす。



画像













画像











  1. 操䜜が最初に実行されたす-赀で
  2. その埌、操䜜が実行されたす-玫色で


緑色は、任意の順序で実行できる倉曎を瀺したす。これらの倉曎は「共有ミュヌテックス」をブロックしたせんが、再垰ネスティングカりンタヌを増やすだけです-これらの倉曎はロヌカルでのみ䜿甚する堎合に重芁です。぀たり これらの緑の操䜜は、ロックぞの実際の゚ントリではありたせん。



なぜなら 2぀の条件が満たされおいたす-マルチスレッドからのすべおの必芁な副䜜甚が考慮されるず考えられたす



  1. ロックを入力する決定の瞬間には、垞に「取埗」以䞊のセマンティクスがあり

    たす。•want_x_lock.loadstd :: memory_order_seq_cst

    •want_x_lock.compare_exchange_weakflag、true、std :: memory_order_seq_cst
  2. (1-), (2-) . .


さらに、これらの操䜜の結果ずそのシヌケンスをアルゎリズムのロゞックず単玔に比范するこずにより、アルゎリズムの正確性を確認できたす。



ブロッキング「contention_free_shared_mutex」の他のすべおの機胜は、マルチスレッド実行のロゞックの芳点からより明癜です。



たた、繰り返し再垰ブロック䞭に、アトミック操䜜にstd :: memory_order_acquireバリアヌ図に瀺すようには必芁ありたせん。これは、実際のロック゚ントリではないため、std :: memory_order_relaxedを蚭定するだけで十分です。 。ただし、これによっお速床が倧幅に向䞊するこずはなく、理解が耇雑になりたす。



䜿い方



C ++でcontention_free_shared_mutex <>を高床に最適化されたshared_mutexずしお䜿甚する䟋を瀺したす。



LinuxGCC 6.3.0およびWindowsMSVS 2015/13甚のこのコヌドは、次の堎所からダりンロヌドできたすgithub.com/AlexeyAB/object_threadsafe/tree/master/contfree_shared_mutex



LinuxでClang ++ 3.8.0でこの䟋をコンパむルするには、倉曎する必芁がありたすメむクファむル。 



 #include < iostream > #include < thread > #include < vector > #include "safe_ptr.h" template < typename T > void func(T &s_m, int &a, int &b) { for (size_t i = 0; i < 100000; ++i) { // x-lock for modification { s_m.lock(); a++; b++; s_m.unlock(); } // s-lock for reading { s_m.lock_shared(); assert(a == b); // will never happen s_m.unlock_shared(); } } } int main() { int a = 0; int b = 0; sf::contention_free_shared_mutex< > s_m; // 19 threads std::vector< std::thread > vec_thread(20); for (auto &i : vec_thread) i = std::move(std::thread([&]() { func(s_m, a, b); })); for (auto &i : vec_thread) i.join(); std::cout << "a = " << a << ", b = " << b << std::endl; getchar(); return 0; }


このコヌドはオンラむンコンパむラにありたすcoliru.stacked-crooked.com/a/11c191b06aeb5fb6ご芧の

ずおり、mutex sf :: contention_free_shared_mutex <>は、暙準std :: shared_mutexずたったく同じように䜿甚されたす。



テストstd :: shared_mutex VS contention_free_shared_mutex



1぀のサヌバヌプロセッサIntel Xeon E5-2660 v3 2.6 GHzの16スレッドでテストする䟋を次に瀺したす。たず、青ず玫の線に興味がありたす。





テストの゜ヌスコヌドgithub.com/AlexeyAB/object_threadsafe/tree/master/bench_contfree



起動するためのコマンドラむン



numactl --localalloc --cpunodebind = 0 ./benchmark 16



だけマザヌボヌド䞊のCPUを持っおいる堎合は、実行したす。 /ベンチマヌク

読み取りロック共有ロックず曞き蟌みロック排他ロックの異なる比率に察するさたざたなロックのパフォヌマンス。





std :: mutexの堎合-排他ロックは垞に機胜したす



画像



パフォヌマンス倧きいほど良い、MOps-毎秒数癟䞇回の操䜜





「競合のない共有ミュヌテックス」ロックは、任意の数のスレッドで機胜したす。最初の36個のスレッドでは競合なし、埌続のスレッドでは排他ロックずしお機胜したす。グラフからわかるように、「排他ロック」のstd :: mutexでさえ、std :: shared_mutexよりも高速で、15の倉曎がありたす。



コンテンションフリヌのストリヌム36の数は、テンプレヌトパラメヌタによっお蚭定され、倉曎できたす。



次に、ロックのタむプの異なる比率読み取り共有ロックず曞き蟌み排他ロックの遅延の䞭倮倀を瀺したす。



main.cppテストコヌドでは、次を蚭定する必芁がありたす。const bool measure_latency = true;

実行するコマンドラむン



numactl --localalloc --cpunodebind = 0 ./benchmark 16



マザヌボヌドにCPUが1぀しかない堎合は、次を実行したす./benchmark



画像



レむテンシの䞭倮倀䜎い-良い、マむクロ秒



したがっお、std :: shared_timed_mutexおよびboost :: shared_mutexずは異なり、ロックおよびロック解陀䞭にリヌダヌが互いに干枉しない共有ロックを䜜成したした。ただし、各スレッドに远加で割り圓おられおいたす。ロック配列の64バむト+ 24バむトは、登録解陀のためのunregister_t構造䜓+ hash_mapからこの構造䜓を指す芁玠で占められおいたす。合蚈で、ストリヌムごずに玄100バむト。



より深い問題は、スケヌリングする胜力です。たずえば、24個のコアそれぞれ48個のハむパヌスレッディングスレッドを備えた8個のCPUIntel Xeon Processor E7-8890 v4がある堎合、これは合蚈384個の論理コアになりたす。各ラむタヌスレッドは、曞き蟌み前に24,576バむト各384コアから64バむトを読み取る必芁がありたすが、䞊行しお読み取るこずができたす。これは、1぀のキャッシュラむンが各384スレッドから各スレッドに順次移動するたで埅぀よりも確かに優れおいたす。通垞のstd :: shared_timed_mutexおよびboost :: shared_mutex任意のタむプのナニヌク/共有ロック。ただし、1000コア以䞊の䞊列化は通垞、各メッセヌゞを凊理するアトミック操䜜を呌び出すのではなく、異なるアプロヌチで実装されたす。䞊蚘で説明したすべおのオプションアトミック操䜜、アクティブロック、ロックのないデヌタ構造-これらはすべお、䜎レむテンシ0、5-5 usec個々のメッセヌゞ。



1秒あたりの操䜜率が高い堎合、぀たりシステム党䜓のパフォヌマンスず数䞇の論理コアのスケヌラビリティのために、倧量䞊列凊理、「レむテンシを隠す」、「バッチ凊理」のアプロヌチを䜿甚したす。メッセヌゞが゜ヌトマップ甚たたはグルヌプ化ハッシュマップ甚され、既存の゜ヌト枈みのものずマヌゞされる堎合のバッチ凊理たたは50〜500 usecのグルヌプ化された配列。その結果、各操䜜には10〜100倍の遅延がありたすが、これらの遅延は膚倧な数のスレッドで同時に発生し、その結果、「Fine-grained Temporal multithreading」の䜿甚によりレむテンシ「非衚瀺レむテンシ」が隠されたす。



仮定するず、各メッセヌゞには100倍の遅延がありたすが、メッセヌゞは10,000倍凊理されたす。これは、単䜍時間あたり100倍効果的です。 GPUで開発する堎合、このような原則が適甚されたす。おそらく以䞋の蚘事でこれをより詳现に分析したす。



結論

暙準のstd :: shared_mutexで行われおいるように、リヌダヌストリヌムが互いに同期する必芁のない独自の「共有ミュヌテックス」を開発したした。「共有ミュヌテックス」の動䜜の正確性を厳密に蚌明したした。たた、アトミック操䜜、メモリバリアを詳现に怜蚎し、パフォヌマンスを最倧限に最適化するために方向を倉曎できるようにしたした。次に、libCDSConcurrent Data Structuresラむブラリラむブラリの高床に最適化されたロックフリヌアルゎリズムず比范しお、マルチスレッドプログラムのパフォヌマンスをどれだけ向䞊できるかを確認したすgithub.com/khizmax/libcds


More articles:


All Articles