Boekrecensie: Is Parallel Programming Hard, And, If So, What Can You Do About It?

Ik heb een groot deel van dit leerboek gelezen en ben verzadigd. Ik zal het waarschijnlijk in de nabije toekomst niet verder lezen, dus ik wilde deze recensie schrijven terwijl alles nog vers in mijn geheugen zit.

Context en omstandigheden

In dit gedeelte beschrijf ik de mindset, de levensfase en de fysieke omgeving waarin ik me bevond toen ik aan dit leerboek begon. Dit is vergelijkbaar met de tedieuze persoonlijke inleidingen op receptwebsites; sla dit over als dat je niet interesseert.

Mijn professionele leven draaide het afgelopen decennium om TLA⁺ en gedistribueerde systemen, en ik begon te denken dat het tijd was voor verandering. Het was een overgangsperiode die emotioneel turbulent was. In 2022 had ik geprobeerd (en gefaald) om over te stappen naar Lean, in de hoop een ongelooflijk niche en niet-bestaande baan te vinden als degene die de resultaten van quantum-informatieverwerking voor onderzoekers formaliseert. Ik brandde daarop uit, wat, gezien de recente vorderingen in geautomatiseerde stellingbewijsvoering, wellicht mijn tijdelijk profetische zenuwstelsel was dat me behoedde voor een fout.

Dit was de geschiedenis en context waarin ik in 2026 de Software Should Work-conferentie bijwoonde in Columbia, Missouri. De conferentie had veel goede presentaties, maar ik genoot vooral van die over Fil-C door Filip Pizlo. Ik heb ook uitgebreid met Fil gesproken over interpreters en vervolgens over concurrency.

Ik hield mezelf voor dat ik behoorlijk deskundig was op het gebied van concurrency dankzij TLA⁺ en gedistribueerde systemen, maar toen Fil me vertelde over de moeilijkheid van het schrijven van een concurrent lock-free garbage collector, realiseerde ik me dat ik eigenlijk heel weinig wist over concurrency (het gevoel hebben dat je weinig weet, is het kenmerk van een goede conferentie).

Fil noemde ook dat TLA⁺ mogelijk niet nuttig (of in ieder geval niet ergonomisch) is voor het redeneren over gebeurtenissen die letterlijk gelijktijdig plaatsvinden (een reële mogelijkheid bij een multicore CPU!) en benadrukte het belang van het analyseren van concurrente algoritmen op lineariseerbaarheid, een concept dat ik in de context van gedistribueerde systemen min of meer begreep.

Dit alles leek zeer aantrekkelijk, dus zocht ik naar een leerboek over concurrency dat meer gericht was op lock-free aspecten in plaats van mutex-gebaseerde patronen of message-passing. Is Parallel Programming Hard, And, If So, What Can You Do About It? leek aan deze eisen te voldoen, aangezien het zich richt op algemene concurrent programming en CPU-cache-effecten, in plaats van specifiek op het schrijven van lock-free datastructuren. Het boek had bovendien een aantal redelijk interessante discussiedraden op Hacker News (uit 2023, 2021, 2020, 2015, 2014, 2011). Ik geloof niet in tijd verspillen aan 'analysis paralysis' bij het zoeken naar het exacte "juiste" leerboek (wat eigenlijk gewoon een slimme manier van uitstellen is), dus dit leek me goed genoeg.

De fysieke setting waarin ik dit boek las, was een vakantie van anderhalve week bij mijn familie in een rustig, bosrijk deel van Canada. 2026 bleek overigens een bijzonder verschrikkelijk muggenseizoen te zijn. Daarom bracht ik veel tijd door op een koel, met gaas afgesloten terras, waakzaam in de gaten gehouden door honderden bewakers die ervoor zorgden dat ik mijn post niet verliet. Satellieten en zendmasten hebben de afleidende internetverbinding irritant goed gemaakt, zelfs in de meer afgelegen delen van het land, maar verder was dit een optimale locatie om een leerboek te lezen.

Het formaat van het leerboek

Enkele korte opmerkingen over de feitelijke structuur van het leerboek; het is beschikbaar in maar liefst drie verschillende PDF-formaten:

• Een dual-column formaat, zoals een wetenschappelijk artikel.
• Een single-column formaat met grote marges.
• Een single-column formaat zonder marges.

Die laatste is perfect voor het lezen op mijn Pine64 PineNote. Het leerboek bevat een enorm aantal interne links. Sommige van deze links worden gebruikt in korte kennis-check-vragen, waarbij het klikken op de link je naar het antwoord brengt. Andere links worden gebruikt telkens wanneer een figuur of sectie wordt genoemd, of voor overvloedige voetnoten en citaties.

Helaas zijn deze laatste zeer irritant en zouden ze waarschijnlijk met ten minste 80% verminderd moeten worden. Als je e-reader geen fysieke bladerknoppen heeft, bestaat je leeservaring eruit dat je constant per ongeluk op een van deze links klikt terwijl je de pagina wilde omslaan, waardoor je naar onbekende plekken wordt gestuurd. E-books zijn al desoriënterend genoeg om in te navigeren zonder dit, en het maakte het vrijwel onmogelijk om snel heen en weer te bladeren tussen twee secties met herhaalde tikken.

In gevallen waarin ik wél op een link wilde klikken, stonden er soms twee links direct naast elkaar; touchscreens missen de precisie om betrouwbaar op de ene link te klikken in plaats van de andere. De oplossing om simpelweg alle links uit te schakelen stelde zich voor, maar dan verlies je de toegang tot de vrij leuke kennis-check-vragen. Dus heb ik het simpelweg geleden.

De inhoud van het leerboek - Inleidende hoofdstukken

Het leerboek was min of meer de perfecte presentatie van materiaal voor mijn niveau. Het boek begint met mooie, lichte inleidings- en motivatiehoofdstukken voordat het in hoofdstuk 3, Hardware and its Habits, echt van start gaat. Hier leren we op hoog niveau hoe moderne CPU's werken: wat ze snel maakt en wat ze traag maakt, compleet met een reeks humoristische illustraties.

Sectie 3.2.1 - Hardware System Architecture was voor mij het meest interessant, omdat we door een vereenvoudigd verslag worden geleid van een CPU-core die naar een geheugenadres schrijft dat niet in zijn cache bestaat. Hier is één gemiste kans: ik had veel baat gehad bij een basisuitleg van het MESI-protocol, aangezien ik vrijwel geen intuïtie had over hoe CPU-caches concurrente lees- en schrijfbewerkingen bemiddelen. Ik kwam achter het bestaan van MESI door online te zoeken om deze sectie beter te begrijpen; MESI wordt in dit boek alleen in de appendix genoemd. Mijn begrip van de rest van het boek is echter aanzienlijk verbeterd door dit te weten.

Het leren over MESI leerde me ook dat meerdere CPU-cores niet letterlijk gelijktijdig naar dezelfde datalocatie kunnen schrijven. Een x86-CPU schrijft niet direct naar het geheugen, maar schrijft alleen naar zijn cache (de cachewaarde wordt vervolgens uiteindelijk naar het geheugen geflusht). Een x86-CPU-core kan alleen naar een specifiek adres schrijven wanneer hij exclusief eigendom heeft van de cacheline die dat adres bevat. Als een andere core tegelijkertijd naar dat adres probeert te schrijven, moet hij wachten tot het exclusieve eigendom van de cacheline naar hem is verplaatst. Letterlijk gelijktijdige schrijfbewerkingen vinden dus niet plaats. Het is echter mogelijk dat schrijfbewerkingen worden 'gescheurd' (torn writes) als de data die wordt geschreven over meer dan één cacheline verspreid is.

Hoofdstuk 4, getiteld Tools of the Trade, was werkelijk verbijsterend. Hier leren we dat als je parallelle programma's schrijft zonder de nodige voorzorgsmaatregelen, de compiler ongelooflijk creatieve optimalisaties zal proberen, wat resulteert in volledig onzinnig gedrag.

Sectie 4.3.4.1, Shared-Variable Shenanigans, behandelt verschrikkelijke incidenten zoals:

• load tearing
• store tearing
• load fusing
• store fusing
• code reordering
• invented loads
• invented stores (bijzonder ernstig)
• store-to-load transformations
• dead-code elimination

Vervolgens, uitgaande van het feit dat je code de compilatie ongeschonden heeft overleefd, beschrijft het hoofdstuk de onzin die de CPU kan uithalen tijdens de feitelijke uitvoering van je programma. Deze dubbele problematiek maakte het voor mij moeilijk om helder na te denken over parallelle programma's buiten de vertrouwde mutexes of message-passing om.

Het enige punt van kritiek op dit hoofdstuk is dat het zeer specifiek is voor een Linux-kernel-context. Ik had graag willen leren over het werk dat C++11 en C11 hebben verricht om parallel programmeren te formaliseren met zaken als std::memoryorder. Deze kregen slechts korte paragrafen in secties 4.2.6 en 4.2.7, Atomic Operations (C11) en Atomic Operations (Modern GCC). Ik kwam uit het hoofdstuk met het vage idee dat de macro's ACCESSONCE() en WRITE_ONCE() dingen simpelweg casten naar volatile* en dat dit genoeg was om de compiler af te schrikken. Zeer interessante historische ontwikkelingen, zoals het debat over de vraag of onschadelijke data-races fouten waren, werden volledig overgeslagen.

De inhoud van het leerboek - Hoofdhoofdstukken

Hoofdstuk 5, Counting, is waarschijnlijk het paradepaardje van het boek. Het was ook het laatste hoofdstuk dat ik in detail heb gelezen. Het hoofdstuk behandelt ongeveer tien verschillende manieren om een programma te schrijven waarin meerdere threads een teller verhogen. De overduidelijke, niet-defecte implementatie, waarbij elke thread atomaire increment-instructies gebruikt, wordt vroegtijdig terzijde geschoven door te laten zien hoe slecht deze presteert. Dit is waar mijn externe kennis van MESI echt nuttig was.

Het hoofdstuk culmineert in iets dat een signal-theft limit counter wordt genoemd, wat ik eerlijk gezegd niet volledig begrijp. Ik denk dat als ik zelf een teller zou schrijven, ik waarschijnlijk niet zo ver zou gaan. Ik hield wel van array-gebaseerde per-thread statistische tellers, vanwege hun gelijkenis met conflict-free replicated datatypes uit de wereld van gedistribueerde systemen. Ze waren ook een uitstekend middel om te leren over de prestatie-impact van false sharing — je kunt niet zomaar alle thread-specifieke tellers in één aaneengesloten array plaatsen en denken dat het goed is.

Na hoofdstuk 5 heb ik de rest van het materiaal voornamelijk gescand op zoek naar interessante onderwerpen. Sommige hoofdstukken waren vrij conceptueel en spraken over eigendom (ownership), partitionering, uitgestelde verwerking (deferred processing) en andere zaken die gemakkelijk te vertalen zijn vanuit gedistribueerde systemen.

Het hoofdstuk over formele verificatie maakte gebruik van Promela en Spin, wat ik als TLA⁺-gebruiker niet gemotiveerd was om te leren. Het hoofdstuk over validatie had een goede sectie, 11.6.4, over het jagen op Heisenbugs. Lock-free programmeren wordt pas echt behandeld in hoofdstuk 14, Advanced Synchronization, en op dat punt was ik klaar om over te stappen naar een leerboek dat zich specifiek richt op lock-free programmering en datastructuren. Hoofdstuk 15 behandelt tenslotte geheugenvolgorde (memory ordering), maar ik was toen al overgestapt op externe bronnen om mijn verwarring hierover op te lossen.

Eindbeoordeling

Hoewel ik slechts de eerste vijf hoofdstukken diepgaand heb gelezen, vind ik dit leerboek uitstekend. Ik zeg dit omdat het me echt een enorme dorst heeft gegeven om meer te leren over parallel programmeren. Tijdens de lunch op het werk worstel ik vaak om mezelf tegen te houden om mijn collega's te bestoken met alle onzin die ik heb geleerd.

Zoals:

• Wist je van het falen bij het formaliseren van release-consume ordering?
• Of hoe basis aligned loads & stores met mov atomair zijn op x86?
• Of out-of-thin-air waarden?
• Of het ongelooflijk zwakke geheugenmodel van de DEC Alpha?
• Of hoe release-acquire semantiek werkt?
• Of hoe deterministic simulation testing (nog) niet zinvol lock-free algoritmen kan testen?
• Of hoe atomics op ARM (pre-v8) kunnen worden onderbroken (pre-empted)?

Er is een goudmijn aan komisch onintuïtieve onzin te vinden. Als volgende stap wil ik meer leren over high-performance garbage collection. Ik sta open voor aanbevelingen!