streamalism.org

1. Prehľad

V tomto článku uvidíme, ako niekedy môže nesprávne zdieľanie zmeniť multithreading proti nám.

Najprv začneme trochu teóriou ukladania do vyrovnávacej pamäte a priestorovej polohy. Potom prepíšeme LongAdder súbežná užitočnosť a porovnať ju s java.util.concurrent implementácia. V celom článku použijeme testovacie výsledky na rôznych úrovniach na preskúmanie účinku falošného zdieľania.

Časť článku súvisiaca s jazykom Java veľmi závisí od rozloženia pamäte objektov. Pretože tieto podrobnosti rozloženia nie sú súčasťou špecifikácie JVM a sú ponechané na uvážení implementátora, zameriame sa iba na jednu konkrétnu implementáciu JVM: HotSpot JVM. V celom článku tiež môžeme používať pojmy JVM a HotSpot JVM zameniteľné.

2. Cache Line a koherencia

Procesory používajú rôzne úrovne ukladania do pamäte cache - keď procesor načíta hodnotu z hlavnej pamäte, môže túto hodnotu uložiť do vyrovnávacej pamäte, aby zlepšil výkon.

Ukázalo sa, že, väčšina moderných procesorov nielenže ukladá požadovanú hodnotu do medzipamäte, ale ukladá do pamäti aj niekoľko ďalších hodnôt v okolí. Táto optimalizácia je založená na myšlienke priestorovej polohy a môže výrazne zlepšiť celkový výkon aplikácií. Zjednodušene povedané, medzipamäte procesorov fungujú z hľadiska riadkov medzipamäte, namiesto jednotlivých hodnôt uložiteľných do medzipamäte.

Ak viac procesorov pracuje na rovnakom alebo blízkom pamäťovom mieste, môže sa stať, že budú zdieľať rovnaký riadok vyrovnávacej pamäte. V takýchto situáciách je nevyhnutné udržiavať tieto navzájom sa prekrývajúce kešky v rôznych jadrách konzistentné. Akt zachovania takejto konzistencie sa nazýva súdržnosť medzipamäte.

Existuje pomerne veľa protokolov na udržanie súdržnosti medzipamäte medzi jadrami CPU. V tomto článku si povieme niečo o protokole MESI.

2.1. Protokol MESI

V protokole MESI každý riadok vyrovnávacej pamäte môže byť v jednom z týchto štyroch odlišných stavov: upravený, exkluzívny, zdieľaný alebo neplatný. Slovo MESI je skratka týchto štátov.

Aby sme lepšie pochopili, ako tento protokol funguje, poďme si prejsť príkladom. Predpokladajme, že dve jadrá budú čítať z blízkych pamäťových miest:

Jadro A prečíta hodnotu a z hlavnej pamäte. Ako je uvedené vyššie, toto jadro získava z pamäte niekoľko ďalších hodnôt a ukladá ich do riadku medzipamäte. Potom označí tento riadok vyrovnávacej pamäte ako exkluzívny od jadra A je jediné jadro operujúce na tomto linku cache. Pokiaľ to bude možné, odteraz sa toto jadro bude vyhýbať neefektívnemu prístupu do pamäte tým, že bude namiesto toho čítať z riadku vyrovnávacej pamäte.

Po chvíli jadro B sa tiež rozhodne prečítať hodnotu b z hlavnej pamäte:

Odkedy a a b sú tak blízko pri sebe a sú umiestnené v rovnakom riadku vyrovnávacej pamäte, obe jadrá označia svoje riadky vyrovnávacej pamäte ako zdieľané.

Teraz predpokladajme to jadro A sa rozhodne zmeniť hodnotu a:

Jadro A uloží túto zmenu iba do svojej vyrovnávacej pamäte obchodu a označí svoj riadok medzipamäte ako upravené. Taktiež oznamuje túto zmenu jadru B, a toto jadro následne označí svoj riadok pamäte cache ako neplatný.

Takto sa rôzni spracovatelia starajú o to, aby ich pamäte cache boli navzájom prepojené.

3. Falošné zdieľanie

Teraz sa pozrime, čo sa stane, keď bude jadro B sa rozhodne znovu prečítať hodnotu b. Pretože sa táto hodnota v poslednej dobe nezmenila, môžeme očakávať rýchle načítanie z riadku vyrovnávacej pamäte. Avšak povaha zdieľanej viacprocesorovej architektúry toto očakávanie v skutočnosti vyvracia.

Ako už bolo spomenuté skôr, celá linka vyrovnávacej pamäte bola zdieľaná medzi dvoma jadrami. Od čiary cache pre jadro B je neplatný teraz by mala načítať hodnotu b z hlavnej pamäte znova:

Ako je uvedené vyššie, rovnaké čítanie b hodnota z hlavnej pamäte tu nie je jedinou neefektívnosťou. Tento prístup do pamäte vynúti jadro A na vypláchnutie medzipamäte obchodu ako jadra B potrebuje získať najnovšiu hodnotu. Po vyprázdnení a načítaní hodnôt obe jadrá skončia s najnovšou verziou riadku medzipamäte označenou v priečinku zdieľané uveďte znova:

Toto teda ukladá vynechanie medzipamäte jednému jadru a skoré vyprázdnenie vyrovnávacej pamäte ďalšiemu, aj keď tieto dve jadrá nepracovali na rovnakom mieste v pamäti.. Tento jav, známy ako nepravé zdieľanie, môže poškodiť celkový výkon, najmä keď je rýchlosť medzipamäte vysoká. Konkrétnejšie, keď je táto rýchlosť vysoká, procesory budú neustále čítať z hlavnej pamäte namiesto toho, aby čítali zo svojich kešiek.

4. Príklad: Dynamické prúžkovanie

Aby sme demonštrovali, ako môže falošné zdieľanie ovplyvniť priepustnosť alebo latenciu aplikácií, v tejto časti budeme podvádzať. Definujme dve prázdne triedy:

abstraktná trieda Striped64 rozširuje číslo {} verejná trieda LongAdder rozširuje Striped64 implementuje Serializable {}

Prázdne triedy samozrejme nie sú také užitočné, takže do nich skopírujme a vložme trochu logiky.

Pre naše 64 triedy, môžeme všetko skopírovať z java.util.concurrent.atomic.Striped64 triedy a vložte ju do našej triedy. Nezabudnite skopírovať súbor dovoz výroky tiež. Ak používate jazyk Java 8, mali by sme sa ubezpečiť, že ste nahradili akékoľvek volanie na sun.misc.Unsafe.getUnsafe () metóda na vlastnú:

private static Unsafe getUnsafe () {try {Field field = Unsafe.class.getDeclaredField ("theUnsafe"); field.setAccessible (true); návrat (nebezpečné) field.get (null); } catch (Výnimka e) {hodiť novú RuntimeException (e); }}

Nemôžeme volať sun.misc.Unsafe.getUnsafe () z nášho aplikácie classloader, takže musíme znova podvádzať s touto statickou metódou. Od Java 9 je však rovnaká logika implementovaná pomocou VarHandles, takže nebudeme tam musieť robiť nič zvláštne, a stačilo by nám jednoduché kopírovanie a vkladanie.

Pre LongAdder triedy, skopírujme všetko z java.util.concurrent.atomic.LongAdder triedy a prilepte ju do našej. Opäť by sme mali skopírovať dovoz výroky tiež.

Teraz si porovnajme tieto dve triedy navzájom: náš zvyk LongAdder a java.util.concurrent.atomic.LongAdder.

4.1. Referenčná hodnota

Aby sme mohli porovnať tieto triedy navzájom, napíšme jednoduchý test JMH:

@State (Scope.Benchmark) verejná trieda FalseSharing {súkromná java.util.concurrent.atomic.LongAdder builtin = nová java.util.concurrent.atomic.LongAdder (); private LongAdder custom = new LongAdder (); @Benchmark public void builtin () {builtin.increment (); } @Benchmark public void custom () {custom.increment (); }}

Ak spustíme tento test s dvoma vidličkami a 16 vláknami v režime testovania výkonu (ekvivalent odovzdania) “–-bm thrpt -f 2 -t 16 ″ argumenty), potom JMH vytlačí tieto štatistiky:

Benchmark Mode Cnt Score Error Units FalseSharing.builtin thpt 40 523964013.730 ± 10617539.010 ops / s FalseSharing.custom thpt 40 112940117.197 ± 9921707.098 ops / s

Výsledok nemá vôbec zmysel. Integrovaná implementácia JDK zakrýva naše riešenie prelepené kopírovaním o takmer 360% vyššiu priepustnosť.

Pozrime sa na rozdiel medzi latenciami:

Benchmark Mode Cnt Score Error Units FalseSharing.builtin priem. 40 28,396 ± 0,357 ns / op FalseSharing.custom priem. 40 51 595 ± 0,663 ns / op

Ako je uvedené vyššie, vstavané riešenie má tiež lepšie charakteristiky latencie.

Aby sme lepšie pochopili, čo je na týchto zdanlivo identických implementáciách také odlišné, poďme sa pozrieť na niektoré počítadlá monitorovania výkonu na nízkej úrovni.

5. Perf udalosti

Na vybavenie nízkoúrovňových udalostí CPU, ako sú cykly, zastavovacie cykly, pokyny na cyklus, načítanie / vynechanie pamäte cache alebo načítanie / uloženie pamäte, môžeme na procesoroch naprogramovať špeciálne hardvérové ​​registre.

Ako sa ukazuje, nástroje ako výkon alebo eBPF tento prístup už používajú na zverejnenie užitočných metrík. Od Linuxu 2.6.31 je perf štandardný linuxový profiler schopný odhaliť užitočné čítače sledovania výkonu alebo PMC.

Takže môžeme pomocou udalostí perf vidieť, čo sa deje na úrovni CPU pri spustení každej z týchto dvoch referenčných hodnôt. Napríklad, ak spustíme:

perf stat -d java -jar benchmarky.jar -f 2 -t 16 --bm thpt zvyk

Perf prinúti JMH spustiť benchmarky proti riešeniam vloženým pri kopírovaní a vytlačí štatistiky:

161657.133662 task-clock (msec) # 3,951 CPU used utilized 9321 context-switch # 0,058 K / sec 185 cpu-migrations # 0,001 K / sec 20514 page-faults # 0,127 K / s 0 cyklov # 0,000 GHz 219476182640 pokyny 44787498110 pobočiek # 277,052 M / s 37831175 min. odbočka # 0,08% všetkých pobočiek 91534635176 L1-dcache -load # 566,227 M / s 1036004767 L1-dcache-load-min. # 1,13% všetkých zásahov L1-dcache

The L1-dcache-load-misses pole predstavuje počet vynechaní medzipamäte pre dátovú medzipamäť L1. Ako je uvedené vyššie, toto riešenie narazilo na približne jednu miliardu chýb cache (presnejšie 1 036 004 767). Ak zhromaždíme rovnaké štatistiky pre vstavaný prístup:

161742,243922 task-clock (msec) # 3,955 CPU utilized 9041 context-switch # 0,056 K / sec 220 cpu-migrations # 0,001 K / sec 21678 page-faults # 0,134 K / s 0 cyklov # 0,000 GHz 692586696913 pokyny 138097405127 pobočky # 853,812 M / s 39010267 premeškané odbočky # 0,03% všetkých pobočiek 291832840178 L1-dcache-zaťaženia # 1804,308 M / s 120239626 L1-dcache-load-premeškané # 0,04% všetkých zásahov L1-dcache

Videli by sme, že v porovnaní s vlastným prístupom naráža na oveľa menej chýb cache (120 239 626 ~ 120 miliónov). Preto môže byť vysokým počtom chýb v medzipamäti vinník takého rozdielu vo výkone.

Poďme sa ešte hlbšie zaoberať vnútornou reprezentáciou LongAdder nájsť skutočného vinníka.

6. Dynamické prúžkovanie prehodnotené

The java.util.concurrent.atomic.LongAdder je implementácia atómového počítadla s vysokou priepustnosťou. Namiesto toho, aby ste použili iba jeden pult, je to ich pole na distribúciu sporu o pamäť medzi nimi. Týmto spôsobom prekoná jednoduché atomy ako napr AtomicLong vo veľmi sporných aplikáciách.

The 64 trieda je zodpovedná za toto rozdelenie tvrdenia o pamäti a taktotrieda implementuje toto pole počítadiel:

@ jdk.internal.vm.annotation.Contended static final class Cell {volatile long value; // vynechané} prechodné prchavé bunky [] bunky;

Každý Bunka zapuzdruje podrobnosti každého počítadla. Táto implementácia umožňuje rôznym vláknam aktualizovať rôzne umiestnenia pamäte. Pretože používame pole (tj. Pruhy) stavov, táto myšlienka sa nazýva dynamické pruhovanie. Je zaujímavé, že 64 je pomenovaný po tejto myšlienke a skutočnosti, že pracuje na 64-bitových dátových typoch.

V každom prípade môže JVM v halde prideliť tieto počítadlá blízko seba. To znamená, že niekoľko týchto počítadiel bude v rovnakom riadku vyrovnávacej pamäte. Preto aktualizácia jedného počítadla môže spôsobiť neplatnosť vyrovnávacej pamäte pre počítadlá v okolí.

Kľúčovým príkladom je, že naivná implementácia dynamického pruhovania bude trpieť nesprávnym zdieľaním. Avšak pridaním dostatočného množstva polstrovania okolo každého pultu môžeme zaistiť, aby sa každý z nich nachádzal na svojom riadku vyrovnávacej pamäte, čím zabránime falošnému zdieľaniu:

Ako sa ukazuje, @jdk.internal.vm.anotácia. Contended za pridanie tejto výplne je zodpovedná anotácia.

Jedinou otázkou je, prečo táto anotácia nefungovala pri implementácii kopírovanej prilepením?

7. Zoznámte sa @ Contended

Java 8 predstavila slnko.misc.obsah anotácia (Java 9 ju prebalila pod jdk.internal.vm.anotácia balíček), aby sa zabránilo falošnému zdieľaniu.

V zásade, keď anotujeme pole s touto anotáciou, HotSpot JVM pridá okolo polia s anotáciami nejaké výplne. Týmto spôsobom môže zaistiť, aby sa pole nachádzalo na vlastnom riadku vyrovnávacej pamäte. Ak navyše touto anotáciou anotujeme celú triedu, program HotSopt JVM pridá pred všetky polia rovnaké polstrovanie.

The @ Contended anotácia je určená na interné použitie samotným JDK. Takže predvolene to nemá vplyv na rozloženie pamäte neinterných objektov. To je dôvod, prečo naša sčítačka vložená sčítačka nefunguje tak dobre ako vstavaná.

Na odstránenie tohto interného obmedzenia môžeme použiť znak -XX: -RestrictContended ladiaca vlajka pri opätovnom spustení referenčnej hodnoty:

Benchmark Mode Cnt Score Error Units FalseSharing.builtin thpt 40 541148225.959 ± 18336783.899 ops / s FalseSharing.custom thpt 40 546022431.969 ± 16406252.364 ops / s

Ako je uvedené vyššie, referenčné výsledky sú teraz oveľa bližšie a rozdiel je pravdepodobne len v podobe šumu.

7.1. Veľkosť vypchávky

V predvolenom nastavení je @ Contended anotácia pridá 128 bajtov výplne. Je to hlavne preto, že veľkosť riadkovej pamäte cache je v mnohých moderných procesoroch okolo 64/128 bajtov.

Táto hodnota je však konfigurovateľná pomocou -XX: ContendedPaddingWidth ladiaca vlajka. Od tohto písania tento príznak akceptuje iba hodnoty medzi 0 a 8192.

7.2. Zakazuje sa @ Contended

Je tiež možné deaktivovať @ Contended účinok prostredníctvom -XX: -EnableContended ladenie. To sa môže ukázať ako užitočné, keď je pamäť na špičkovej úrovni a my si môžeme dovoliť stratiť trochu (a niekedy aj veľa) výkonu.

7.3. Prípady použitia

Po prvom vydaní @ Contended anotácia sa používala pomerne často, aby sa zabránilo falošnému zdieľaniu v interných údajových štruktúrach JDK. Tu je niekoľko pozoruhodných príkladov takýchto implementácií:

• The 64 triedy na implementáciu počítadiel a akumulátorov s vysokou priepustnosťou
• The Závit triedy na uľahčenie implementácie efektívnych generátorov náhodných čísel
• The ForkJoinPool rad na krádež práce
• The ConcurrentHashMap implementácia
• Duálna dátová štruktúra použitá v Výmenník trieda

8. Záver

V tomto článku sme videli, ako niekedy môže nepravdivé zdieľanie spôsobiť kontraproduktívne účinky na výkon viacvláknových aplikácií.

Aby sme veci konkretizovali, vykonali sme test LongAdder implementáciu v Jave proti svojej kópii a použili jej výsledky ako východiskový bod pre naše vyšetrovanie výkonu.

Tiež sme použili výkon nástroj na zhromažďovanie štatistík o metrikách výkonu spustenej aplikácie v systéme Linux. Ak chcete vidieť viac príkladov perf, dôrazne sa odporúča prečítať si blog Brandena Grega. Okrem toho môže byť eBPF dostupný od verzie Linux Kernel verzie 4.4 tiež užitočný v mnohých scenároch sledovania a profilovania.

Ako obvykle sú všetky príklady dostupné na GitHub.