streamalism.org

1. Pregled

U ovom ćemo članku vidjeti kako se ponekad lažno dijeljenje može okrenuti prema višestrukim nitima.

Prvo ćemo započeti s malo o teoriji predmemoriranja i prostornom mjestu. Tada ćemo prepisati LongAdder istodobnu korisnost i uporedite je s java.util.concurrent provedba. Kroz članak ćemo upotrijebiti referentne rezultate na različitim razinama kako bismo istražili učinak lažnog dijeljenja.

Dio članka koji se odnosi na Javu uvelike ovisi o rasporedu memorije objekata. Budući da ovi detalji izgleda nisu dio JVM specifikacije i prepušteni su nahođenju implementatora, usredotočit ćemo se samo na jednu specifičnu JVM implementaciju: HotSpot JVM. Također možemo koristiti JVM i HotSpot JVM pojmove naizmjenično u cijelom članku.

2. Cache Line i koherencija

Procesori koriste različite razine predmemoriranja - kada procesor čita vrijednost iz glavne memorije, može predmemorirati tu vrijednost radi poboljšanja performansi.

Kako se ispostavilo, većina modernih procesora ne samo da predmemorira traženu vrijednost već i predmemorira još nekoliko obližnjih vrijednosti. Ova se optimizacija temelji na ideji prostornog lokaliteta i može značajno poboljšati ukupnu izvedbu aplikacija. Jednostavno rečeno, predmemorije procesora rade u smislu linija predmemorije, umjesto pojedinačnih predmemoriranih vrijednosti.

Kada više procesora radi na istom ili obližnjim memorijskim mjestima, na kraju mogu dijeliti istu liniju predmemorije. U takvim je situacijama bitno držati te međusobno preklapajuće predmemorije u različitim jezgrama. Čin održavanja takve dosljednosti naziva se koherencija predmemorije.

Postoji podosta protokola za održavanje koherencije predmemorije između procesorskih jezgri. U ovom ćemo članku govoriti o MESI protokolu.

2.1. Protokol MESI

U MESI protokolu, svaka linija predmemorije može biti u jednom od ova četiri različita stanja: Izmijenjeno, Ekskluzivno, Dijeljeno ili Nevaljano. Riječ MESI akronim je ovih država.

Da bismo bolje razumjeli kako ovaj protokol funkcionira, prođimo kroz primjer. Pretpostavimo da će dvije jezgre čitati s obližnjih memorijskih mjesta:

Jezgra A očitava vrijednost a iz glavne memorije. Kao što je gore prikazano, ova jezgra dohvaća još nekoliko vrijednosti iz memorije i sprema ih u predmemoriju. Zatim označava tu liniju predmemorije kao ekskluzivan budući da jezgra A je jedina jezgra koja radi na ovoj liniji predmemorije. Od sada, kad je to moguće, ova će jezgra izbjegavati neučinkovit pristup memoriji čitanjem iz retka predmemorije.

Nakon nekog vremena, jezgra B također odluči pročitati vrijednost b iz glavne memorije:

Od a i b su tako blizu jedno drugom i borave u istoj liniji predmemorije, obje će jezgre označiti svoje linije predmemorije kao podijeljeni.

Pretpostavimo sada tu srž A odluči promijeniti vrijednost a:

Jezgra A pohranjuje ovu promjenu samo u svoj međuspremnik spremišta i označava liniju predmemorije kao preinačena. Također, ovu promjenu komunicira do srži B, a ova će jezgra svoju liniju predmemorije, pak, označiti kao nevaljano.

Tako se različiti procesori brinu da njihove predmemorije budu međusobno koherentne.

3. Lažno dijeljenje

Sad, da vidimo što će se dogoditi kad jezgra B odluči ponovno pročitati vrijednost b. Kako se ova vrijednost nedavno nije promijenila, mogli bismo očekivati ​​brzo očitavanje iz retka predmemorije. Međutim, priroda zajedničke višeprocesorske arhitekture poništava ovo očekivanje u stvarnosti.

Kao što je ranije spomenuto, cijela linija predmemorije podijeljena je između dvije jezgre. Budući da je linija predmemorije za jezgru B je nevaljano sada bi trebala pročitati vrijednost b iz glavne memorije opet:

Kao što je prikazano gore, čitanje isto b vrijednost iz glavne memorije ovdje nije jedina neučinkovitost. Ovaj pristup memoriji prisilit će jezgru A da isprazni svoj međuspremnik kao jezgru B treba dobiti najnoviju vrijednost. Nakon ispiranja i dohvaćanja vrijednosti, obje će jezgre završiti s najnovijom verzijom cache line označene u podijeljeni opet navesti:

Dakle, ovo nameće promašaj predmemorije na jednoj jezgri i rano pražnjenje međuspremnika na drugu, iako dvije jezgre nisu radile na istom memorijskom mjestu. Ova pojava, poznata kao lažno dijeljenje, može naštetiti ukupnoj izvedbi, posebno kada je stopa promašaja predmemorije velika. Da budemo precizniji, kada je ova stopa visoka, procesori će neprestano dopirati do glavne memorije umjesto da čitaju iz svoje predmemorije.

4. Primjer: Dynamic Striping

Da bismo pokazali kako lažno dijeljenje može utjecati na protok ili latenciju aplikacija, prevarit ćemo u ovom odjeljku. Definirajmo dvije prazne klase:

apstraktna klasa Striped64 proširuje Broj {} javna klasa LongAdder proširuje Striped64 implementira serializable {}

Naravno, prazne klase nisu toliko korisne, pa kopirajmo i zalijepimo malo logike u njih.

Za naše Prugasta64 klase, možemo kopirati sve iz java.util.concurrent.atomic.Striped64 razred i zalijepite ga u naš razred. Svakako kopirajte uvoz izjave, također. Također, ako koristite Javu 8, trebali bismo zamijeniti svaki poziv na sun.misc.Unsafe.getUnsafe () metoda prema prilagođenoj:

privatni statički Unsafe getUnsafe () {try {Polje polja = Unsafe.class.getDeclaredField ("theUnsafe"); field.setAccessible (true); return (nesigurno) polje.get (null); } catch (Iznimka e) {baciti novi RuntimeException (e); }}

Ne možemo nazvati sun.misc.Unsafe.getUnsafe () iz našeg učitelja učitavanja aplikacija, pa moramo ponovo varati ovom statičnom metodom. Međutim, od Jave 9, ista se logika provodi pomoću VarHandles, pa tamo nećemo trebati raditi ništa posebno, a bio bi dovoljan samo jednostavan copy-paste.

Za LongAdder razreda, kopirajmo sve iz java.util.concurrent.atomic.LongAdder razreda i zalijepite ga u naš. Opet bismo trebali kopirati uvoz izjave, također.

Ajmo sada usporediti ove dvije klase jedna s drugom: naš običaj LongAdder i java.util.concurrent.atomic.LongAdder.

4.1. Mjerilo

Da bismo ove klase uspoređivali jedni s drugima, napišite jednostavno JMH mjerilo:

@State (Scope.Benchmark) javna klasa FalseSharing {private java.util.concurrent.atomic.LongAdder builtin = new java.util.concurrent.atomic.LongAdder (); privatni LongAdder custom = novi LongAdder (); @Benchmark javna praznina builtin () {builtin.increment (); } @Benchmark javna void custom () {custom.increment (); }}

Ako ovu referentnu vrijednost pokrenemo s dvije vilice i 16 niti u načinu mjerenja protoka (ekvivalent prolaza “–-bm thrpt -f 2 -t 16 ″ argumenti), tada će JMH ispisati ove statistike:

Benchmark Mode Cnt Score Greške Jedinice FalseSharing.builtin thrpt 40 523964013.730 ± 10617539.010 ops / s FalseSharing.custom thrpt 40 112940117.197 ± 9921707.098 ops / s

Rezultat uopće nema smisla. Ugrađena implementacija JDK zaklanja naše kopirano rješenje za gotovo 360% veću propusnost.

Pogledajmo razliku između latencija:

Benchmark Mode Cnt Score Greške Jedinice FalseSharing.builtin avgt 40 28.396 ± 0.357 ns / op FalseSharing.custom prosjek 40 51.595 ± 0.663 ns / op

Kao što je gore prikazano, ugrađeno rješenje također ima bolja svojstva kašnjenja.

Da bismo bolje razumjeli što se toliko razlikuje od ovih naizgled identičnih implementacija, pregledajmo neke brojače za praćenje performansi niske razine.

5. Perf Događaji

Za instrumentaciju CPU događaja na niskoj razini, poput ciklusa, ciklusa zaustavljanja, uputa po ciklusu, učitavanja / promašaja predmemorije ili učitavanja / pohrane memorije, možemo programirati posebne hardverske registre na procesorima.

Kako se ispostavilo, alati poput perf ili eBPF već koriste ovaj pristup za izlaganje korisnih mjernih podataka. Od Linuxa 2.6.31, perf je standardni Linux profiler sposoban izložiti korisne brojače za nadzor performansi ili PMC-ove.

Dakle, možemo koristiti perf događaje kako bismo vidjeli što se događa na razini CPU-a prilikom pokretanja svake od ove dvije referentne vrijednosti. Na primjer, ako pokrenemo:

perf stat -d java -jar mjerila.jar -f 2 -t 16 --bm thrpt custom

Perf će natjerati JMH da pokrene referentne vrijednosti prema kopiranom rješenjem i ispiše statistiku:

161657.133662 sat zadataka (msec) # 3.951 CPU su koristili 9321 kontekstne sklopke # 0.058 K / sec 185 cpu-migracija # 0.001 K / sec 20514 greške stranice # 0.127 K / sec 0 ciklusa # 0.000 GHz 219476182640 upute 44787498110 grane # 277.052 M / sec 37831175 promašaji grana # 0,08% svih grana 91534635176 učitavanja L1-dcache # 566.227 M / sek 1036004767 promašaji L1-dcache-load-promašaji # 1,13% svih pogodaka L1-dcache

The L1-dcache-load-misses polje predstavlja broj promašaja predmemorije za predmemoriju podataka L1. Kao što je gore prikazano, ovo je rješenje naišlo na oko milijardu promašaja predmemorije (točnije 1.036.004.767). Ako prikupimo iste statistike za ugrađeni pristup:

161742.243922 sat zadataka (msec) # 3.955 CPU su koristili 9041 kontekstne sklopke # 0.056 K / sec 220 cpu-migracija # 0.001 K / sec 21678 pogreške stranice # 0.134 K / sec 0 ciklusa # 0.000 GHz 692586696913 upute 138097405127 grane # 853.812 M / sec 39010267 promašaji grana # 0,03% svih grana 291832840178 učitavanja L1-dcache # 1804.308 M / sek 120239626 promašaji L1-dcache-load-propuštanja # 0,04% svih pogodaka L1-dcache

Vidjeli bismo da nailazi na puno manje promašaja predmemorije (120.239.626 ~ 120 milijuna) u usporedbi s prilagođenim pristupom. Stoga bi velik broj promašaja predmemorije mogao biti krivac za takvu razliku u performansama.

Zarobimo još dublje u unutarnju reprezentaciju LongAdder pronaći stvarnog krivca.

6. Ponovno posjećeno dinamičko pruganje

The java.util.concurrent.atomic.LongAdder je implementacija atomskog brojača s velikom propusnošću. Umjesto da koristi samo jedan brojač, on koristi niz njih za distribuciju memorijske rasprave između njih. Na taj će način nadmašiti jednostavne atome kao što je AtomicLong u visoko konkurentnim aplikacijama.

The Prugasta64 klasa je odgovorna za ovu raspodjelu prijepora memorije, a ovo je kako toklasa provodi niz brojača:

@ jdk.internal.vm.annotation.Contended static static class Cell {volatile long value; // izostavljeni} prolazne hlapljive stanice [];

Svaki Ćelija obuhvaća pojedinosti za svaki brojač. Ova implementacija omogućuje različitim nitima ažuriranje različitih memorijskih mjesta. Budući da koristimo niz (tj. Pruge) stanja, ta se ideja naziva dinamičko provlačenje. Zanimljivo, Prugasta64 je dobio ime po ovoj ideji i činjenici da radi na 64-bitnim vrstama podataka.

U svakom slučaju, JVM može rasporediti te brojače jedan blizu drugog na hrpu. Odnosno, nekoliko tih brojača bit će u istoj liniji predmemorije. Stoga, ažuriranje jednog brojača može onesposobiti predmemoriju za obližnje brojače.

Ovdje je ključno izuzeće: naivna provedba dinamičkog iscrtavanja patit će od lažnog dijeljenja. Međutim, dodavanjem dovoljno obloga oko svakog brojača, možemo osigurati da svaki od njih boravi na svojoj liniji predmemorije, čime se sprječava lažno dijeljenje:

Kako se ispostavilo, @jdk.internal.vm.annotation.Contended napomena je odgovorna za dodavanje ovog popunjavanja.

Pitanje je samo, zašto ova napomena nije uspjela u kopirano zalijepljenoj implementaciji?

7. Upoznajte @ Sadržaj

Java 8 je predstavila ned.misc.Sadržaj napomena (Java 9 ga je prepakirala pod jdk.internal.vm.notacija paket) kako bi se spriječilo lažno dijeljenje.

U osnovi, kada polje označimo ovom bilješkom, HotSpot JVM će dodati nekoliko dodataka oko označenog polja. Na taj se način može pobrinuti da se polje nalazi na vlastitoj liniji predmemorije. Štoviše, ako ovom bilješkom označimo cijelu klasu, HotSopt JVM će dodati isto udiranje prije svih polja.

The @ Sadržaj napomena je namijenjena internoj upotrebi od strane samog JDK. Prema zadanim postavkama, to ne utječe na raspored memorije ne-internih objekata. To je razlog zašto naš kopirano zalijepljeni zbrojnik ne radi jednako dobro kao ugrađeni.

Da bismo uklonili ovo interno ograničenje, možemo koristiti -XX: -RestrictContended zastava za podešavanje prilikom ponovnog pokretanja referentne vrijednosti:

Benchmark Mode Cnt Score Greške Jedinice FalseSharing.builtin thrpt 40 541148225.959 ± 18336783.899 ops / s FalseSharing.custom thrpt 40 546022431.969 ± 16406252.364 ops / s

Kao što je prikazano gore, sada su referentni rezultati puno bliži, a razlika je vjerojatno samo malo buke.

7.1. Veličina obloga

Prema zadanim postavkama @ Sadržaj napomena dodaje 128 bajtova popunjavanja. To je uglavnom zato što je veličina linije predmemorije u mnogim modernim procesorima oko 64/128 bajtova.

Ta se vrijednost, međutim, može konfigurirati putem -XX: ContendedPaddingWidth zastava za podešavanje. Od ovog pisanja, ova zastava prihvaća samo vrijednosti između 0 i 8192.

7.2. Onemogućavanje @ Sadržaj

Također je moguće onemogućiti @ Sadržaj efekt putem -XX: -EnableContended ugađanje. To se može pokazati korisnim kad je memorija na dobrom mjestu i možemo si priuštiti da izgubimo malo (a ponekad i puno) performansi.

7.3. Koristite slučajeve

Nakon prvog izdanja, @ Sadržaj anotacija korištena je prilično opsežno kako bi se spriječilo lažno dijeljenje u JDK-ovim unutarnjim strukturama podataka. Evo nekoliko zapaženih primjera takvih implementacija:

• The Prugasta64 klasa za primjenu brojača i akumulatora s velikom propusnošću
• The Nit razreda kako bi se olakšala primjena učinkovitih generatora slučajnih brojeva
• The ForkJoinPool red za krađu posla
• The ConcurrentHashMap provedba
• Dvostruka struktura podataka koja se koristi u Izmjenjivač razred

8. Zaključak

U ovom smo članku vidjeli kako ponekad lažno dijeljenje može prouzročiti kontraproduktivne učinke na izvedbu višenitnih aplikacija.

Da bismo stvar učinili konkretnijom, usporedili smo LongAdder implementacija u Javi protiv njezine kopije i koristila je njene rezultate kao polazište za naša ispitivanja izvedbe.

Također, koristili smo i perf alat za prikupljanje neke statistike o mjernim podacima izvedbe pokrenute aplikacije na Linuxu. Da biste vidjeli više primjera perf, toplo se preporučuje čitati blog Branden Greg. Štoviše, eBPF, dostupan od verzije 4.4 Kernel Linuxa, također može biti koristan u mnogim scenarijima praćenja i profiliranja.

Kao i obično, svi su primjeri dostupni na GitHubu.