streamalism.org

1. Overzicht

In dit artikel zullen we zien hoe soms vals delen multithreading tegen ons kan keren.

Ten eerste gaan we beginnen met een klein beetje over de theorie van caching en ruimtelijke lokaliteit. Dan herschrijven we het LongAdder gelijktijdige hulpprogramma en benchmark het tegen de java.util.concurrent implementatie. In het hele artikel zullen we de benchmarkresultaten op verschillende niveaus gebruiken om het effect van false sharing te onderzoeken.

Het Java-gerelateerde deel van het artikel is sterk afhankelijk van de geheugenlay-out van objecten. Aangezien deze lay-outdetails geen deel uitmaken van de JVM-specificatie en worden overgelaten aan de discretie van de implementator, zullen we ons alleen concentreren op één specifieke JVM-implementatie: de HotSpot JVM. We kunnen de JVM- en HotSpot JVM-termen ook door elkaar gebruiken in het artikel.

2. Cachelijn en coherentie

Processors gebruiken verschillende niveaus van caching - wanneer een processor een waarde uit het hoofdgeheugen leest, kan hij die waarde cachen om de prestaties te verbeteren.

Zoals het blijkt, de meeste moderne processors cachen niet alleen de gevraagde waarde, maar cachen ook nog een paar nabije waarden. Deze optimalisatie is gebaseerd op het idee van ruimtelijke lokaliteit en kan de algehele prestaties van applicaties aanzienlijk verbeteren. Simpel gezegd, processorcaches werken in termen van cacheregels, in plaats van enkele cachebare waarden.

Wanneer meerdere processors op dezelfde of nabijgelegen geheugenlocaties werken, kunnen ze uiteindelijk dezelfde cacheregel delen. In dergelijke situaties is het essentieel om die overlappende caches in verschillende kernen consistent met elkaar te houden. Het handhaven van een dergelijke consistentie wordt cachecoherentie genoemd.

Er zijn nogal wat protocollen om de cachecoherentie tussen CPU-kernen te behouden. In dit artikel gaan we het hebben over het MESI-protocol.

2.1. Het MESI-protocol

In het MESI-protocol, elke cacheregel kan een van deze vier verschillende statussen hebben: gewijzigd, exclusief, gedeeld of ongeldig. Het woord MESI is de afkorting van deze staten.

Laten we een voorbeeld doorlopen om beter te begrijpen hoe dit protocol werkt. Stel dat twee kernen gaan lezen van geheugenlocaties in de buurt:

Kern EEN leest de waarde van een uit het hoofdgeheugen. Zoals hierboven getoond, haalt deze kern nog een paar waarden op uit het geheugen en slaat ze op in een cacheregel. Vervolgens markeert het die cacheregel als exclusief sinds core EEN is de enige kern die op deze cacheregel werkt. Vanaf nu zal deze kern, indien mogelijk, de inefficiënte geheugentoegang vermijden door in plaats daarvan de cache-regel te lezen.

Na een tijdje, core B besluit ook om de waarde van te lezen b uit het hoofdgeheugen:

Sinds een en b zijn zo dicht bij elkaar en bevinden zich in dezelfde cache-regel, beide kernen zullen hun cacheregels taggen als gedeeld.

Laten we nu eens aannemen dat die kern EEN besluit de waarde van te wijzigen een:

De kern EEN slaat deze wijziging alleen op in zijn opslagbuffer en markeert zijn cacheregel als gewijzigd. Het communiceert deze wijziging ook naar de kern B, en deze kern zal op zijn beurt zijn cacheregel markeren als ongeldig.

Zo zorgen verschillende processors ervoor dat hun caches met elkaar in overeenstemming zijn.

3. Onjuist delen

Laten we nu eens kijken wat er gebeurt als core B besluit de waarde van opnieuw te lezen b. Aangezien deze waarde niet recentelijk is gewijzigd, kunnen we een snelle uitlezing van de cacheregel verwachten. De aard van een gedeelde multiprocessorarchitectuur maakt deze verwachting in werkelijkheid echter ongeldig.

Zoals eerder vermeld, werd de hele cacheregel gedeeld tussen de twee kernen. Omdat de cache-regel voor core B is ongeldig nu zou het de waarde moeten lezen b opnieuw uit het hoofdgeheugen:

Zoals hierboven getoond, hetzelfde lezen b waarde uit het hoofdgeheugen is hier niet de enige inefficiëntie. Deze geheugentoegang zal de kern forceren EEN om zijn opslagbuffer door te spoelen, als de kern B moet de laatste waarde krijgen. Na het doorspoelen en ophalen van de waarden, krijgen beide cores de laatste versie van de cacheregel getagd in het gedeeld verklaar opnieuw:

Dit legt dus een cache-misser op aan één kern en een vroege buffer doorspoelen naar een andere, ook al werkten de twee kernen niet op dezelfde geheugenlocatie. Dit fenomeen, dat bekend staat als false sharing, kan de algehele prestaties nadelig beïnvloeden, vooral wanneer de snelheid van de cache-missers hoog is. Om specifieker te zijn, wanneer deze snelheid hoog is, zullen processors constant contact opnemen met het hoofdgeheugen in plaats van uit hun caches te lezen.

4. Voorbeeld: dynamische strepen

Om aan te tonen hoe vals delen de doorvoer of latentie van applicaties kan beïnvloeden, gaan we in deze sectie vals spelen. Laten we twee lege klassen definiëren:

abstracte klasse Striped64 breidt uit Nummer {} openbare klasse LongAdder breidt uit Striped64 implementeert Serializable {}

Natuurlijk zijn lege klassen niet zo handig, dus laten we er wat logica in kopiëren en plakken.

Voor onze Gestreept64 klasse, kunnen we alles kopiëren van de java.util.concurrent.atomic.Striped64 class en plak het in onze class. Zorg ervoor dat u het importeren verklaringen. Als u Java 8 gebruikt, moeten we ervoor zorgen dat elke aanroep naar sun.misc.Unsafe.getUnsafe () methode naar een aangepaste methode:

private static Unsafe getUnsafe () {probeer {Field field = Unsafe.class.getDeclaredField ("theUnsafe"); field.setAccessible (true); return (onveilig) field.get (null); } catch (uitzondering e) {throw nieuwe RuntimeException (e); }}

We kunnen de sun.misc.Unsafe.getUnsafe () van onze applicatie classloader, dus we moeten opnieuw vals spelen met deze statische methode. Vanaf Java 9 wordt echter dezelfde logica geïmplementeerd met VarHandles, dus we hoeven daar niets speciaals te doen, en een simpele copy-paste zou voldoende zijn.

Voor de LongAdder klasse, laten we alles kopiëren van de java.util.concurrent.atomic.LongAdder class en plak deze in de onze. Nogmaals, we moeten het importeren verklaringen.

Laten we nu deze twee klassen met elkaar vergelijken: onze gewoonte LongAdder en java.util.concurrent.atomic.LongAdder.

4.1. Benchmark

Laten we een eenvoudige JMH-benchmark schrijven om deze klassen met elkaar te vergelijken:

@State (Scope.Benchmark) openbare klasse FalseSharing {privé java.util.concurrent.atomic.LongAdder ingebouwd = nieuwe java.util.concurrent.atomic.LongAdder (); private LongAdder custom = nieuwe LongAdder (); @Benchmark public void builtin () {builtin.increment (); } @Benchmark public void custom () {custom.increment (); }}

Als we deze benchmark uitvoeren met twee vorken en 16 threads in de doorvoer-benchmarkmodus (het equivalent van passeren “–-bm thrpt -f 2 -t 16 ″ argumenten), dan zal JMH deze statistieken afdrukken:

Benchmarkmodus Cnt Score Fouteenheden FalseSharing.builtin thrpt 40 523964013.730 ± 10617539.010 ops / s FalseSharing.custom thrpt 40 112940117.197 ± 9921707.098 bewerkingen / s

Het resultaat klopt helemaal niet. De ingebouwde JDK-implementatie verkleint onze copy-paste-oplossing met bijna 360% meer doorvoer.

Laten we eens kijken naar het verschil tussen latenties:

Benchmarkmodus Cnt Score Fouteenheden FalseSharing.builtin avgt 40 28.396 ± 0.357 ns / op FalseSharing.custom avgt 40 51.595 ± 0.663 ns / op

Zoals hierboven getoond, heeft de ingebouwde oplossing ook betere latentiekenmerken.

Om beter te begrijpen wat er zo anders is aan deze schijnbaar identieke implementaties, laten we enkele low-level prestatiebewakingstellers bekijken.

5. Prestaties

Voor het instrumenteren van CPU-gebeurtenissen op laag niveau, zoals cycli, blokkeercycli, instructies per cyclus, laden / missen van cache of laden / opslaan van geheugen, kunnen we speciale hardwareregisters op de processors programmeren.

Het blijkt dat tools zoals perf of eBPF gebruiken deze benadering al om bruikbare statistieken bloot te leggen. Vanaf Linux 2.6.31 is perf de standaard Linux-profiler die bruikbare Performance Monitoring Counters of PMC's kan blootleggen.

We kunnen dus perf-gebeurtenissen gebruiken om te zien wat er op CPU-niveau gebeurt bij het uitvoeren van elk van deze twee benchmarks. Als we bijvoorbeeld uitvoeren:

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

Perf zorgt ervoor dat JMH de benchmarks uitvoert tegen de gekopieerde oplossing en de statistieken afdrukt:

161657.133662 taakklok (msec) # 3.951 Gebruikte CPU's 9321 context-switches # 0.058 K / sec 185 cpu-migraties # 0.001 K / sec 20514 paginafouten # 0.127 K / sec 0 cycli # 0.000 GHz 219476182640 instructies 44787498110 branches # 277.052 M / sec 37831175 branch-misses # 0,08% van alle branches 91534635176 L1-dcache-load # 566,227 M / sec 1036004767 L1-dcache-load-misses # 1,13% van alle L1-dcache-hits

De L1-dcache-load-misses veld vertegenwoordigt het aantal cache-missers voor de L1-gegevenscache. Zoals hierboven getoond, is deze oplossing ongeveer een miljard cache-missers tegengekomen (1,036,004,767 om precies te zijn). Als we dezelfde statistieken verzamelen voor de ingebouwde benadering:

161742.243922 taakklok (msec) # 3.955 Gebruikte CPU's 9041 context-switches # 0.056 K / sec 220 cpu-migraties # 0.001 K / sec 21678 paginafouten # 0.134 K / sec 0 cycli # 0.000 GHz 692586696913 instructies 138097405127 branches # 853.812 M / sec 39010267 branch-missers # 0,03% van alle branches 291832840178 L1-dcache-load # 1804.308 M / sec 120239626 L1-dcache-load-misses # 0.04% van alle L1-dcache-hits

We zouden zien dat het veel minder cache-missers tegenkomt (120.239.626 ~ 120 miljoen) in vergelijking met de aangepaste benadering. Daarom kan het hoge aantal cache-missers de boosdoener zijn voor een dergelijk prestatieverschil.

Laten we nog dieper ingaan op de interne weergave van LongAdder om de feitelijke boosdoener te vinden.

6. Dynamische striping opnieuw bezocht

De java.util.concurrent.atomic.LongAdder is een atoomtellerimplementatie met een hoge doorvoer. In plaats van slechts één teller te gebruiken, gebruikt het een reeks ervan om de geheugenconflicten tussen hen te verdelen. Op deze manier presteert het beter dan de eenvoudige atomica zoals AtomicLong in zeer betwiste toepassingen.

De Gestreept64 class is verantwoordelijk voor deze verdeling van geheugenconflicten, en dit is hoe ditclass implementeert die reeks tellers:

@ jdk.internal.vm.annotation.Contended statische laatste klasse Cel {vluchtige lange waarde; // weggelaten} tijdelijke vluchtige cel [] cellen;

Elk Cel bevat de details voor elke teller. Deze implementatie maakt het voor verschillende threads mogelijk om verschillende geheugenlocaties bij te werken. Omdat we een array (dat wil zeggen strepen) van staten gebruiken, wordt dit idee dynamische striping genoemd. Interessant is dat Gestreept64 is vernoemd naar dit idee en het feit dat het werkt op 64-bits gegevenstypen.

Hoe dan ook, de JVM mag die tellers bij elkaar in de hoop toewijzen. Dat wil zeggen, een paar van die tellers zullen in dezelfde cacheregel staan. Daarom het bijwerken van één teller kan de cache voor tellers in de buurt ongeldig maken.

De belangrijkste afweging hier is dat de naïeve implementatie van dynamische striping zal lijden onder false sharing. Echter, door voldoende opvulling rond elke teller toe te voegen, kunnen we ervoor zorgen dat ze allemaal op de cacheregel staan, waardoor het vals delen wordt voorkomen:

Het blijkt dat de @jdk.internal.vm.annotation.Contended annotatie is verantwoordelijk voor het toevoegen van deze opvulling.

De enige vraag is: waarom werkte deze annotatie niet in de geplakte implementatie?

7. Ontmoet @Contended

Java 8 introduceerde het zon.misc. beweerd annotatie (Java 9 heeft het opnieuw verpakt onder de jdk.internal.vm.annotation pakket) om vals delen te voorkomen.

Kortom, wanneer we een veld annoteren met deze annotatie, zal de HotSpot JVM wat opvullingen toevoegen rond het geannoteerde veld. Op deze manier kan het ervoor zorgen dat het veld op zijn eigen cacheregel staat. Bovendien, als we een hele klasse annoteren met deze annotatie, zal de HotSopt JVM dezelfde opvulling voor alle velden toevoegen.

De @Contended annotatie is bedoeld om intern door de JDK zelf te worden gebruikt. Het heeft dus standaard geen invloed op de geheugenlay-out van niet-interne objecten. Dat is de reden waarom onze gekopieerde adder niet zo goed presteert als de ingebouwde.

Om deze interne beperking te verwijderen, kunnen we de -XX: -RestrictContended afstemmingsvlag bij het opnieuw uitvoeren van de benchmark:

Benchmarkmodus Cnt Score Fouteenheden FalseSharing.builtin thrpt 40 541148225.959 ± 18336783.899 bewerkingen / s FalseSharing.custom thrpt 40 546022431.969 ± 16406252.364 bewerkingen / s

Zoals hierboven getoond, zijn de benchmarkresultaten nu veel dichterbij, en het verschil is waarschijnlijk slechts een beetje ruis.

7.1. Opvulmaat

Standaard is het @Contended annotatie voegt 128 bytes aan opvulling toe. Dat komt vooral omdat de grootte van de cacheregel in veel moderne processors ongeveer 64/128 bytes is.

Deze waarde is echter configureerbaar via de -XX: ContendedPaddingWidth tuning vlag. Op het moment van schrijven accepteert deze vlag alleen waarden tussen 0 en 8192.

7.2. Het uitschakelen van het @Contended

Het is ook mogelijk om het @Contended effect via de -XX: -EnableContended afstemmen. Dit kan handig blijken te zijn als het geheugen schaars is en we het ons kunnen veroorloven om een ​​beetje (en soms veel) aan prestatie te verliezen.

7.3. Gebruik cases

Na de eerste release, het @Contended annotatie is vrij uitgebreid gebruikt om vals delen in de interne datastructuren van JDK te voorkomen. Hier zijn een paar opmerkelijke voorbeelden van dergelijke implementaties:

• De Gestreept64 klasse om tellers en accumulatoren met hoge doorvoer te implementeren
• De Draad klasse om de implementatie van efficiënte generatoren van willekeurige getallen te vergemakkelijken
• De ForkJoinPool wachtrij voor het stelen van werk
• De ConcurrentHashMap implementatie
• De dubbele gegevensstructuur die wordt gebruikt in het Uitwisselaar klasse

8. Conclusie

In dit artikel hebben we gezien hoe vals delen soms een averechts effect kan hebben op de prestaties van multithreaded applicaties.

Om de zaken concreter te maken, hebben we de LongAdder implementatie in Java tegen zijn kopie en gebruikte de resultaten ervan als uitgangspunt voor ons prestatieonderzoek.

We gebruikten ook de perf tool om enkele statistieken te verzamelen over de prestatiestatistieken van een actieve applicatie op Linux. Om meer voorbeelden te zien van perf, het wordt ten zeerste aanbevolen om de blog van Branden Greg te lezen. Bovendien kan eBPF, beschikbaar vanaf Linux Kernel versie 4.4, ook nuttig zijn in veel scenario's voor tracering en profilering.

Zoals gewoonlijk zijn alle voorbeelden beschikbaar op GitHub.