streamalism.org

1. Oversigt

I denne artikel vil vi se, hvordan falsk deling undertiden kan vende multithreading mod os.

Først skal vi starte med en smule om teorien om caching og rumlig lokalitet. Så omskriver vi LongAdder samtidig værktøj og benchmark det mod java.util.concurrent implementering. Gennem hele artiklen bruger vi benchmarkresultaterne på forskellige niveauer til at undersøge effekten af ​​falsk deling.

Den Java-relaterede del af artiklen afhænger stærkt af objekternes hukommelseslayout. Da disse layoutoplysninger ikke er en del af JVM-specifikationen og overlades til implementeringsmyndighedens skøn, fokuserer vi kun på en specifik JVM-implementering: HotSpot JVM. Vi kan også bruge JVM og HotSpot JVM-termerne om hverandre i hele artiklen.

2. Cache-linje og sammenhæng

Processorer bruger forskellige niveauer af caching - når en processor læser en værdi fra hovedhukommelsen, kan den cache denne værdi for at forbedre ydeevnen.

Det viser sig, de fleste moderne processorer cache ikke kun den ønskede værdi, men cache også nogle få nærliggende værdier. Denne optimering er baseret på ideen om rumlig lokalitet og kan forbedre applikationernes samlede ydeevne betydeligt. Kort sagt, processorcacher fungerer i form af cache-linjer i stedet for enkelt cache-værdier.

Når flere processorer fungerer på samme eller nærliggende hukommelsesplaceringer, kan de ende med at dele den samme cache-linje. I sådanne situationer er det vigtigt at holde de overlappende cacher i forskellige kerner i overensstemmelse med hinanden. Handlingen med at opretholde en sådan konsistens kaldes cache-kohærens.

Der er en hel del protokoller, der opretholder cache-sammenhængen mellem CPU-kerner. I denne artikel skal vi tale om MESI-protokollen.

2.1. MESI-protokollen

I MESI-protokollen hver cachelinje kan være i en af ​​disse fire forskellige tilstande: Modificeret, Eksklusiv, Delt eller Ugyldig. Ordet MESI er forkortelsen for disse stater.

Lad os gennemgå et eksempel for bedre at forstå, hvordan denne protokol fungerer. Antag, at to kerner læser fra nærliggende hukommelsessteder:

Kerne EN læser værdien af -en fra hovedhukommelsen. Som vist ovenfor henter denne kerne et par flere værdier fra hukommelsen og gemmer dem i en cache-linje. Derefter markerer det cache-linjen som eksklusiv siden kerne EN er den eneste kerne, der fungerer på denne cache-linje. Fra nu af undgår denne kerne, når det er muligt, den ineffektive hukommelsesadgang ved at læse fra cachelinjen i stedet.

Efter et stykke tid, kerne B beslutter også at læse værdien af b fra hovedhukommelsen:

Siden -en og b er så tæt på hinanden og ligger i samme cache-linje, begge kerner vil mærke deres cache-linjer som delt.

Lad os nu antage den kerne EN beslutter at ændre værdien af -en:

Kernen EN gemmer denne ændring kun i sin butiksbuffer og markerer dens cache-linje som ændret. Det kommunikerer også denne ændring til kernen B, og denne kerne markerer igen sin cache-linje som ugyldig.

Sådan sørger forskellige processorer for, at deres cacher er sammenhængende med hinanden.

3. Falsk deling

Lad os nu se, hvad der sker, når kernen B beslutter at genlæse værdien af b. Da denne værdi ikke ændrede sig for nylig, kan vi forvente en hurtig læsning fra cachelinjen. Imidlertid ophæver arten af ​​delt multiprocessorarkitektur denne forventning i virkeligheden.

Som nævnt tidligere blev hele cache-linjen delt mellem de to kerner. Siden cache-linjen for kerne B er ugyldig nu skal det læse værdien b fra hovedhukommelsen igen:

Som vist ovenfor, læser du det samme b værdi fra hovedhukommelsen er ikke den eneste ineffektivitet her. Denne hukommelsesadgang vil tvinge kernen EN at skylle sin butiksbuffer som kernen B skal have den nyeste værdi. Efter skylning og hentning af værdierne ender begge kerner med den nyeste cache-linjeversion, der er mærket i delt tilstand igen:

Så det pålægger en cache-miss til en kerne og en tidlig buffer-skylning til en anden, selvom de to kerner ikke fungerede på samme hukommelsesplacering. Dette fænomen, kendt som falsk deling, kan skade den samlede præstation, især når frekvensen af ​​cachemisset er høj. For at være mere specifik, når denne hastighed er høj, når processorer konstant ud til hovedhukommelsen i stedet for at læse fra deres cacher.

4. Eksempel: Dynamisk stripning

For at demonstrere, hvordan falsk deling kan påvirke applikationernes kapacitet eller latenstid, skal vi snyde i dette afsnit. Lad os definere to tomme klasser:

abstrakt klasse Striped64 udvider Antal {} offentlig klasse LongAdder udvider Striped64 implementerer Serializable {}

Selvfølgelig er tomme klasser ikke så nyttige, så lad os kopiere og indsætte nogle logik i dem.

For vores Stribet64 klasse, kan vi kopiere alt fra java.util.concurrent.atomic.Striped64 klasse og indsætte den i vores klasse. Sørg for at kopiere importere udsagn også. Hvis vi bruger Java 8, skal vi også sørge for at erstatte ethvert opkald til sun.misc.Unsafe.getUnsafe () metode til en brugerdefineret:

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

Vi kan ikke ringe til sun.misc.Unsafe.getUnsafe () fra vores applikationsklasselæsser, så vi er nødt til at snyde igen med denne statiske metode. Fra og med Java 9 implementeres den samme logik dog ved hjælp af VarHandles, så vi behøver ikke gøre noget specielt der, og bare en simpel kopipasta er tilstrækkelig.

Til LongAdder klasse, lad os kopiere alt fra java.util.concurrent.atomic.LongAdder klasse og indsætte det i vores. Igen skal vi kopiere importere udsagn også.

Lad os nu sammenligne disse to klasser mod hinanden: vores skik LongAdder og java.util.concurrent.atomic.LongAdder.

4.1. Benchmark

For at sammenligne disse klasser mod hinanden, lad os skrive et simpelt JMH-benchmark:

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

Hvis vi kører dette benchmark med to gafler og 16 tråde i benchmark-tilstand for gennemløb (svarende til forbipasserende) “–-bm trpt -f 2 -t 16 ″ argumenter), så udskriver JMH disse statistikker:

Benchmark Mode Cnt Score Fejlenheder FalseSharing.builtin thrpt 40 523964013.730 ± 10617539.010 ops / s FalseSharing.custom thrpt 40 112940117.197 ± 9921707.098 ops / s

Resultatet giver slet ikke mening. Den indbyggede JDK-implementering dværger vores kopi-indsatte løsning med næsten 360% mere kapacitet.

Lad os se forskellen mellem ventetid:

Benchmark Mode Cnt Score Fejlenheder 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 indbyggede løsning også bedre latenstidskarakteristikker.

For bedre at forstå, hvad der er så forskelligt ved disse tilsyneladende identiske implementeringer, lad os inspicere nogle ydeevneovervågningstællere på lavt niveau.

5. Perf Begivenheder

For at instrumentere CPU-begivenheder på lavt niveau, såsom cyklusser, stall-cyklusser, instruktioner pr. Cyklus, cache-belastninger / -fejl eller hukommelsesbelastninger / -lagre, kan vi programmere specielle hardwareregistre på processorer.

Som det viser sig, værktøjer som perf eller eBPF bruger allerede denne tilgang til at udsætte nyttige metrics. Fra og med Linux 2.6.31 er perf standard Linux-profilen, der er i stand til at udsætte nyttige Performance Monitoring Counters eller PMC'er.

Så vi kan bruge perf-begivenheder til at se, hvad der sker på CPU-niveau, når vi kører hver af disse to benchmarks. For eksempel, hvis vi kører:

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

Perf vil få JMH til at køre benchmarks mod den kopi-indsatte løsning og udskrive statistikken:

161657.133662 task-clock (msec) # 3.951 CPU'er anvendt 9321 kontekst-switches # 0,058 K / sek 185 cpu-migreringer # 0,001 K / sek 20514 sidefejl # 0,127 K / sek 0 cyklusser # 0,000 GHz 219476182640 instruktioner 44787498110 filialer # 277.052 M / sek 37831175 branch-misses # 0,08% af alle filialer 91534635176 L1-dcache-loads # 566.227 M / sec 1036004767 L1-dcache-load-misses # 1,13% af alle L1-dcache-hits

Det L1-dcache-load-savner felt repræsenterer antallet af cache-ulykker for L1-datacachen. Som vist ovenfor har denne løsning stødt på omkring en milliard cache-fejl (1.036.004.767 for at være nøjagtig). Hvis vi samler den samme statistik til den indbyggede tilgang:

161742.243922 task-clock (msec) # 3.955 CPU'er anvendt 9041 kontekst-switches # 0,056 K / sek 220 cpu-migreringer # 0,001 K / sek 21678 sidefejl # 0,134 K / sek 0 cyklusser # 0,000 GHz 692586696913 instruktioner 138097405127 filialer # 853.812 M / sek 39010267 gren-savner # 0,03% af alle grene 291832840178 L1-dcache-belastninger # 1804,308 M / sek 120239626 L1-dcache-load-savner # 0,04% af alle L1-dcache-hits

Vi vil se, at det støder på meget færre cache-savner (120.239.626 ~ 120 millioner) sammenlignet med den brugerdefinerede tilgang. Derfor kan det høje antal cache-savner muligvis være synderen for en sådan forskel i ydeevne.

Lad os grave endnu dybere ned i den interne repræsentation af LongAdder for at finde den faktiske synder.

6. Dynamisk stribe revisited

Det java.util.concurrent.atomic.LongAdder er en atomimplementering med høj kapacitet. I stedet for bare at bruge en tæller bruger den en række af dem til at distribuere hukommelseskonflikten mellem dem. På denne måde vil det overgå de enkle atomer som f.eks AtomicLong i stærkt anfægtede applikationer.

Det Stribet64 klasse er ansvarlig for denne fordeling af hukommelseskonflikt, og sådan er detklasse implementerer denne række tællere:

@ jdk.internal.vm.annotation.Contended static final class Cell {flygtig lang værdi; // udeladt} forbigående flygtige celler [] celler;

Hver Celle indkapsler detaljerne for hver tæller. Denne implementering gør det muligt for forskellige tråde at opdatere forskellige hukommelsesplaceringer. Da vi bruger en matrix (dvs. striber) af tilstande, kaldes denne idé dynamisk stribe. Interessant nok Stribet64 er opkaldt efter denne idé og det faktum, at den fungerer på 64-bit datatyper.

Under alle omstændigheder kan JVM allokere disse tællere nær hinanden i bunken. Det vil sige, et par disse tællere vil være i samme cache-linje. Derfor, opdatering af en tæller kan ugyldiggøre cachen for tællere i nærheden.

Den vigtigste afhentning her er, den naive implementering af dynamisk striping vil lide under falsk deling. Imidlertid, ved at tilføje tilstrækkelig polstring omkring hver tæller, kan vi sikre os, at hver af dem ligger på sin cache-linje, hvilket forhindrer falsk deling:

Som det viser sig, er @jdk.internal.vm.annotation.Contended annotation er ansvarlig for at tilføje denne polstring.

Det eneste spørgsmål er, hvorfor fungerede denne kommentar ikke i den kopimastede implementering?

7. Mød @ Contended

Java 8 introducerede sun.misc. fortsat kommentar (Java 9 ompakket det under jdk.internal.vm.annotation pakke) for at forhindre falsk deling.

Dybest set, når vi kommenterer et felt med denne kommentar, tilføjer HotSpot JVM nogle polstringer omkring det kommenterede felt. På denne måde kan det sikre, at feltet ligger på sin egen cache-linje. Desuden, hvis vi kommenterer en hel klasse med denne kommentar, tilføjer HotSopt JVM den samme polstring før alle felterne.

Det @ Contended kommentar er beregnet til at blive brugt internt af JDK selv. Så som standard påvirker det ikke hukommelseslayoutet for ikke-interne objekter. Det er grunden til, at vores kopi-indsatte adder ikke fungerer så godt som den indbyggede.

For at fjerne denne interne begrænsning kan vi bruge -XX: -RestrikContended tuning flag, når du kører benchmark:

Benchmark Mode Cnt Score Fejlenheder FalseSharing.builtin thrpt 40 541148225.959 ± 18336783.899 ops / s FalseSharing.custom thrpt 40 546022431.969 ± 16406252.364 ops / s

Som vist ovenfor er benchmarkresultaterne nu meget tættere, og forskellen er sandsynligvis bare lidt støj.

7.1. Polstring størrelse

Som standard er @ Contended annotation tilføjer 128 byte polstring. Det skyldes primært cache-linjestørrelsen i mange moderne processorer er omkring 64/128 bytes.

Denne værdi kan imidlertid konfigureres gennem -XX: ContendedPaddingWidth tuning flag. I skrivende stund accepterer dette flag kun værdier mellem 0 og 8192.

7.2. Deaktivering af @ Contended

Det er også muligt at deaktivere @ Contended effekt via -XX: -EnableContended indstilling. Dette kan vise sig at være nyttigt, når hukommelsen har en præmie, og vi har råd til at miste en smule (og nogle gange meget) ydeevne.

7.3. Brug sager

Efter sin første frigivelse, @ Contended annotering er blevet brugt ret udstrakt for at forhindre falsk deling i JDKs interne datastrukturer. Her er et par bemærkelsesværdige eksempler på sådanne implementeringer:

• Det Stribet64 klasse til implementering af tællere og akkumulatorer med høj kapacitet
• Det Tråd klasse for at lette implementeringen af ​​effektive tilfældige talgeneratorer
• Det ForkJoinPool kø for at stjæle arbejde
• Det ConcurrentHashMap implementering
• Den dobbelte datastruktur, der anvendes i Veksler klasse

8. Konklusion

I denne artikel så vi, hvordan falsk deling undertiden kan medføre kontraproduktive effekter på ydeevnen for multitrådede applikationer.

For at gøre sagen mere konkret benchmarkede vi LongAdder implementering i Java mod dets kopi og brugte resultaterne som udgangspunkt for vores præstationsundersøgelser.

Vi brugte også perf værktøj til at indsamle nogle statistikker om præstationsmålingerne for en kørende applikation på Linux. For at se flere eksempler på perf, det anbefales stærkt at læse Branden Gregs blog. Desuden kan eBPF, der er tilgængelig fra Linux Kernel version 4.4, også være nyttigt i mange sporings- og profileringsscenarier.

Som sædvanligt er alle eksemplerne tilgængelige på GitHub.