streamalism.org

1. Oversikt

I denne artikkelen får vi se hvordan falsk deling noen ganger kan slå multitrading mot oss.

Først skal vi begynne med litt på teorien om caching og romlig lokalitet. Så skriver vi om LongAdder samtidig verktøy og måle det mot java.util.concurrent gjennomføring. Gjennom artikkelen vil vi bruke referanseresultatene på forskjellige nivåer for å undersøke effekten av falsk deling.

Den Java-relaterte delen av artikkelen avhenger sterkt av minnelayouten til objekter. Siden disse oppsettdetaljene ikke er en del av JVM-spesifikasjonen og overlates til implementeringsmyndighetens skjønn, vil vi bare fokusere på en spesifikk JVM-implementering: HotSpot JVM. Vi kan også bruke vilkårene JVM og HotSpot JVM om hverandre gjennom hele artikkelen.

2. Cache Line og Coherency

Prosessorer bruker forskjellige nivåer av hurtigbufring - når en prosessor leser en verdi fra hovedminnet, kan den cache denne verdien for å forbedre ytelsen.

Som det viser seg, De fleste moderne prosessorer cache ikke bare den valgte verdien, men cache også noen flere verdier i nærheten. Denne optimaliseringen er basert på ideen om romlig lokalitet og kan forbedre den generelle ytelsen til applikasjoner betydelig. Enkelt sagt, prosessorbuffer fungerer i form av hurtigbufferlinjer, i stedet for enkelt cacheable verdier.

Når flere prosessorer opererer på samme eller nærliggende minneplasser, kan det hende at de deler den samme hurtigbufferlinjen. I slike situasjoner er det viktig å holde de overlappende cachene i forskjellige kjerner i samsvar med hverandre. Handlingen med å opprettholde en slik konsistens kalles cache-koherens.

Det er ganske mange protokoller for å opprettholde cache-koherensen mellom CPU-kjerner. I denne artikkelen skal vi snakke om MESI-protokollen.

2.1. MESI-protokollen

I MESI-protokollen, hver cachelinje kan være i en av disse fire forskjellige tilstandene: Modifisert, Eksklusiv, Delt eller Ugyldig. Ordet MESI er forkortelsen til disse tilstandene.

For å bedre forstå hvordan denne protokollen fungerer, la oss gå gjennom et eksempel. Anta at to kjerner skal lese fra nærliggende minneplasser:

Kjerne EN leser verdien av en fra hovedminnet. Som vist ovenfor, henter denne kjernen noen flere verdier fra minnet og lagrer dem i en cache-linje. Deretter markerer den cache-linjen som eksklusiv siden kjernen EN er den eneste kjernen som opererer på denne hurtigbufferlinjen. Fra nå av, når det er mulig, vil denne kjernen unngå ineffektiv minnetilgang ved å lese fra hurtiglinjelinjen i stedet.

Etter en stund, kjernen B bestemmer seg også for å lese verdien av b fra hovedminnet:

Siden en og b er så nær hverandre og ligger i samme cache-linje, begge kjernene vil merke cachelinjene som delt.

La oss anta den kjernen EN bestemmer seg for å endre verdien på en:

Kjernen EN lagrer bare denne endringen i butikkbufferen og markerer hurtigbufferlinjen som endret. Dessuten kommuniserer den denne endringen til kjernen B, og denne kjernen vil i sin tur merke cache-linjen som ugyldig.

Slik sørger forskjellige prosessorer for at cachene deres er sammenhengende med hverandre.

3. Falsk deling

La oss nå se hva som skjer når kjernen B bestemmer seg for å lese verdien på nytt b. Siden denne verdien ikke endret seg nylig, kan vi forvente en rask lesing fra hurtigbufferlinjen. Imidlertid gjør naturen til delt flerprosessorarkitektur ugyldig denne forventningen i virkeligheten.

Som nevnt tidligere ble hele cachelinjen delt mellom de to kjernene. Siden cache-linjen for kjerne B er ugyldig nå skal den lese verdien b fra hovedminnet igjen:

Som vist ovenfor, leser du det samme b verdien fra hovedminnet er ikke den eneste ineffektiviteten her. Denne minnetilgangen vil tvinge kjernen EN å skylle butikkbufferen, som kjernen B trenger å få den siste verdien. Etter å ha spylt og hentet verdiene, vil begge kjernene ende opp med den siste versjonen av hurtigbufferlinjen merket i delt oppgi igjen:

Så dette påfører en cache-miss til en kjerne og en tidlig bufferspyling til en annen, selv om de to kjernene ikke fungerte på samme minneplassering. Dette fenomenet, kjent som falsk deling, kan skade den generelle ytelsen, spesielt når hurtigbufferen er høy. For å være mer spesifikk, når denne hastigheten er høy, vil prosessorer hele tiden nå ut til hovedminnet i stedet for å lese fra cachene sine.

4. Eksempel: Dynamisk striping

For å demonstrere hvordan falsk deling kan påvirke gjennomstrømningen eller ventetiden til applikasjoner, skal vi jukse i denne delen. La oss definere to tomme klasser:

abstrakt klasse Striped64 utvider Antall {} offentlig klasse LongAdder utvider Striped64 implementerer Serializable {}

Selvfølgelig er tomme klasser ikke så nyttige, så la oss kopiere og lime inn litt logikk i dem.

For vår Stripet64 klasse, kan vi kopiere alt fra java.util.concurrent.atomic.Striped64 klasse og lim den inn i klassen vår. Sørg for å kopiere import uttalelser også. Hvis vi bruker Java 8, bør vi også sørge for å erstatte samtaler til sun.misc.Unsafe.getUnsafe () metode til en tilpasset:

privat statisk usikker getUnsafe () {prøv {Field field = Unsafe.class.getDeclaredField ("theUnsafe"); field.setAccessible (true); returner (Usikker) field.get (null); } fange (Unntak e) {kaste nytt RuntimeException (e); }}

Vi kan ikke ringe sun.misc.Unsafe.getUnsafe () fra vår programklasser, så vi må jukse igjen med denne statiske metoden. Fra og med Java 9 implementeres imidlertid den samme logikken ved hjelp av VarHandles, så vi trenger ikke å gjøre noe spesielt der, og bare en enkel kopi-lim vil være tilstrekkelig.

For LongAdder klasse, la oss kopiere alt fra java.util.concurrent.atomic.LongAdder klasse og lim den inn i vår. Igjen, bør vi kopiere import uttalelser også.

La oss nå sammenligne disse to klassene mot hverandre: vår skikk LongAdder og java.util.concurrent.atomic.LongAdder.

4.1. Referanseindeks

For å måle disse klassene mot hverandre, la oss skrive en enkel JMH-referanse:

@State (Scope.Benchmark) offentlig klasse FalseSharing {private java.util.concurrent.atomic.LongAdder innebygd = ny java.util.concurrent.atomic.LongAdder (); privat LongAdder tilpasset = ny LongAdder (); @Benchmark public void builtin () {builtin.increment (); } @Benchmark public void custom () {custom.increment (); }}

Hvis vi kjører denne referanseindeksen med to gafler og 16 tråder i referansemodus for gjennomstrømning (tilsvarende passering “–-bm thrpt -f 2 -t 16 ″ argumenter), vil JMH skrive ut disse statistikkene:

Referansemodus Cnt Score feilenheter FalseSharing.builtin thrpt 40 523964013.730 ± 10617539.010 ops / s FalseSharing.custom thrpt 40 112940117.197 ± 9921707.098 ops / s

Resultatet gir ikke mening i det hele tatt. Den innebygde JDK-implementeringen dverger vår kopimastede løsning med nesten 360% mer gjennomstrømning.

La oss se forskjellen mellom ventetid:

Referansemodus Cnt Score Error Units FalseSharing.builtin avgt 40 28.396 ± 0.357 ns / op FalseSharing.custom avgt 40 51.595 ± 0.663 ns / op

Som vist ovenfor har den innebygde løsningen også bedre latenstidskarakteristikker.

For å bedre forstå hva som er så forskjellig ved disse tilsynelatende identiske implementeringene, la oss inspisere noen ytelsesovervåkingsteller på lavt nivå.

5. Perf hendelser

For å instrumentere CPU-hendelser på lavt nivå, for eksempel sykluser, stoppsykluser, instruksjoner per syklus, hurtigbufferbelastning / -feil eller minnebelastning / lagring, kan vi programmere spesielle maskinvareregistre på prosessorer.

Som det viser seg, verktøy som perf eller eBPF bruker allerede denne tilnærmingen for å avsløre nyttige beregninger. Per Linux 2.6.31 er perf standard Linux-profilen som kan avsløre nyttige Performance Monitoring Counters eller PMCs.

Så vi kan bruke perf-hendelser for å se hva som skjer på CPU-nivå når vi kjører hver av disse to standardene. For eksempel hvis vi løper:

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

Perf vil få JMH til å kjøre referanseverdiene mot den kopimastede løsningen og skrive ut statistikken:

161657.133662 task-clock (msec) # 3.951 CPUer benyttet 9321 kontekstbrytere # 0,058 K / sek 185 cpu-migrasjoner # 0,001 K / sek 20514 sidefeil # 0,127 K / sek 0 sykluser # 0,000 GHz 219476182640 instruksjoner 44787498110 filialer # 277.052 M / sek 37831175 gren-savner # 0,08% av alle filialer 91534635176 L1-dcache-belastninger # 566,227 M / sek 1036004767 L1-dcache-last-savner # 1,13% av alle L1-dcache-treff

De L1-dcache-last-savner feltet representerer antall hurtigbuffere for L1-databufferen. Som vist ovenfor, har denne løsningen oppstått rundt en milliard hurtigbuffer (1.036.004.767 for å være nøyaktig). Hvis vi samler den samme statistikken for den innebygde tilnærmingen:

161742.243922 task-clock (msec) # 3.955 CPUer benyttet 9041 kontekstbrytere # 0,056 K / sek 220 cpu-migrasjoner # 0,001 K / sek 21678 sidefeil # 0,134 K / sek 0 sykluser # 0,000 GHz 692586696913 instruksjoner 138097405127 filialer # 853.812 M / sek 39010267 gren-savner # 0,03% av alle filialer 291832840178 L1-dcache-belastninger # 1804,308 M / sek 120239626 L1-dcache-last-savner # 0,04% av alle L1-dcache treff

Vi ser at det støter på mye færre hurtigbuffer (1202339626 ~ 120 millioner) sammenlignet med den tilpassede tilnærmingen. Derfor kan det høye antallet hurtigbuffer være skyldige i en slik forskjell i ytelse.

La oss grave enda dypere i den interne representasjonen av LongAdder for å finne den faktiske synderen.

6. Dynamic Striping Revisited

De java.util.concurrent.atomic.LongAdder er en atomimplementering med høy gjennomstrømning. I stedet for bare å bruke en teller, bruker den en rekke av dem for å distribuere hukommelseskonflikten mellom dem. På denne måten vil det overgå de enkle atomene som AtomicLong i svært omstridte applikasjoner.

De Stripet64 klassen er ansvarlig for denne fordelingen av minnekonflikt, og slik er detteklasse implementerer den rekke tellere:

@ jdk.internal.vm.annotation.Contended statisk sluttklasse Cell {flyktig lang verdi; // utelatt} forbigående flyktige celler [] celler;

Hver Celle innkapsler detaljene for hver teller. Denne implementeringen gjør det mulig for forskjellige tråder å oppdatere forskjellige minneplasseringer. Siden vi bruker en matrise (det vil si striper) av stater, kalles denne ideen dynamisk striping. Interessant, Stripet64 er oppkalt etter denne ideen og det faktum at den fungerer på 64-biters datatyper.

Uansett kan JVM tildele disse tellerne nær hverandre i dyngen. Det vil si at noen få tellere vil være i samme cache-linje. Derfor, oppdatering av en teller kan ugyldiggjøre hurtigbufferen for tellere i nærheten.

Den viktigste takeawayen her er at den naive implementeringen av dynamisk striping vil lide av falsk deling. Derimot, ved å legge til nok polstring rundt hver teller, kan vi sørge for at hver av dem ligger på cachelinjen, og dermed forhindrer falsk deling:

Som det viser seg, @jdk.internal.vm.annotation.Contended kommentar er ansvarlig for å legge til denne polstringen.

Det eneste spørsmålet er, hvorfor fungerte ikke denne kommentaren i implementeringen av kopimastingen?

7. Møt @Contended

Java 8 introduserte sun.misc. fortsatte merknad (Java 9 pakket den om under jdk.internal.vm.annotation pakke) for å forhindre falsk deling.

I utgangspunktet, når vi kommenterer et felt med denne kommentaren, vil HotSpot JVM legge til noen polstringer rundt det kommenterte feltet. På denne måten kan den sørge for at feltet ligger på sin egen cache-linje. Hvis vi dessuten kommenterer en hel klasse med denne kommentaren, vil HotSopt JVM legge til den samme polstringen før alle feltene.

De @Contended merknader er ment å brukes internt av JDK selv. Så som standard påvirker det ikke minnelayouten til ikke-interne objekter. Det er grunnen til at vår kopierte lim ikke fungerer like bra som den innebygde.

For å fjerne denne interne begrensningen, kan vi bruke -XX: -RestrictContended tuning flagg når du kjører referansen:

Referansemodus Cnt Score Error Units FalseSharing.builtin thrpt 40 541148225.959 ± 18336783.899 ops / s FalseSharing.custom thrpt 40 546022431.969 ± 16406252.364 ops / s

Som vist ovenfor, er nå referanseresultatene mye nærmere, og forskjellen er sannsynligvis bare litt støy.

7.1. Polstring Størrelse

Som standard er @Contended kommentar legger til 128 byte polstring. Det er hovedsakelig fordi cache-linjestørrelsen i mange moderne prosessorer er rundt 64/128 byte.

Denne verdien kan imidlertid konfigureres gjennom -XX: ContendedPaddingWidth innstillingsflagg. I skrivende stund godtar dette flagget bare verdier mellom 0 og 8192.

7.2. Deaktivering av @Contended

Det er også mulig å deaktivere @Contended effekt via -XX: -EnableContended innstilling. Dette kan vise seg å være nyttig når minnet er til en premie, og vi har råd til å miste litt (og noen ganger mye) ytelse.

7.3. Bruk tilfeller

Etter den første utgivelsen, @Contended merknader har blitt brukt ganske mye for å forhindre falsk deling i JDKs interne datastrukturer. Her er noen bemerkelsesverdige eksempler på slike implementeringer:

• De Stripet64 klasse for å implementere tellere og akkumulatorer med høy gjennomstrømning
• De Tråd klasse for å lette implementeringen av effektive tilfeldige tallgeneratorer
• De ForkJoinPool jobb-stjele kø
• De ConcurrentHashMap gjennomføring
• Den doble datastrukturen som brukes i Veksler klasse

8. Konklusjon

I denne artikkelen så vi hvordan falsk deling noen ganger kan føre til kontraproduktive effekter på ytelsen til flertrådede applikasjoner.

For å gjøre saken mer konkret, målte vi LongAdder implementering i Java mot kopien og brukte resultatene som utgangspunkt for våre ytelsesundersøkelser.

Vi brukte også perf verktøy for å samle litt statistikk om ytelsesberegningene for et løpende program på Linux. For å se flere eksempler på perf, det anbefales sterkt å lese Branden Gregs blogg. Videre kan eBPF, tilgjengelig fra Linux Kernel versjon 4.4, også være nyttig i mange sporings- og profileringsscenarier.

Som vanlig er alle eksemplene tilgjengelige på GitHub.