Het Probleem

Het probleem is dat besturingssystemen nuttige optimalisatiepotentie op verschillende vlakken mislopen, omdat waardevolle informatie over afhankelijkheden en resources — die wordt verzorgd door compilers, build-systemen en pakketbeheerders — niet met elkaar of met andere delen van het systeem wordt gedeeld.

Ik ga beschrijven waar ik oorspronkelijk dacht dat het probleem begon en eindigde, en hoe het uiteindelijk veel uitgebreider bleek te zijn dan ik aanvankelijk dacht. Daarnaast bespreek ik enkele specifieke voorbeelden van interessante optimalisatiemogelijkheden (werkelijke programmaprestaties, besparing van schijfruimte, eenvoudiger softwareontwikkeling, transparenter systeembeheer en betere scheduling) die ontstaan wanneer communicatie tussen systeemcomponenten mogelijk wordt.

De compiler en het build-systeem

Ik merkte het probleem voor het eerst op toen ik het build-systeem van moderne talen vergeleek met dat van de veel oudere fundering van de meeste besturingssystemen: C. In een moderne taal (zoals Rust, Go of Zig) zijn de compiler en het build-systeem nauw geïntegreerd. Dit maakt het leven voor gebruikers makkelijker, omdat ze geen build-systeem hoeven te kiezen en een gestandaardiseerde manier hebben om software te bouwen over alle projecten heen die de taal gebruiken.

Naast het gebruiksgemak biedt deze integratie voordelen die de meeste moderne talen nog niet eens volledig benutten. Om deze voordelen uit te leggen, gebruik ik het voorbeeld van een hypothetisch build-systeem voor C dat nauw geïntegreerd is met de C-compiler.

In elk bestaand build-systeem voor C worden alle compilatie-eenheden (.c-bestanden) volledig onafhankelijk van elkaar gecompileerd naar hun outputs (.o-bestanden), in aparte processen die door het build-systeem worden gestart. Voor de compiler betekent dit dat de enige context die hij heeft over het programma de individuele compilatie-eenheid is die hij op dat moment verwerkt. De optimalisatie is dus beperkt tot zaken die volledig binnen die ene eenheid besloten liggen.

Een simpel voorbeeld van hoe dit problematisch kan zijn:

/four.c/

int xfour(int x)
{
    return x * 4;
}

/main.c/

extern int xfour(int);
int main(void)
{
    return xfour(3);
}

In dit voorbeeld hebben we twee bestanden. De compiler compileert elk bestand individueel zonder kennis van het andere bestand. De compiler doet zijn best om ervoor te zorgen dat de vermenigvuldiging met 4 de best mogelijke assembly-instructies gebruikt, maar hij heeft geen idee dat de aanroeper het getal 3 zal doorgeven. Als hij echter kennis zou hebben van beide bestanden, zou hij weten wat er aan de functie wordt doorgegeven en zou hij main kunnen optimaliseren tot iets veel simpeler:

int main(void)
{
    return 12;
}

Dit wordt whole program optimisation genoemd en is technisch volledig mogelijk en vrij gebruikelijk. Dit staat bekend als LTO (link-time optimization). Echter, ik ben van mening dat het moment waarop dit gebeurt — tijdens het linken — niet het ideale tijdstip is voor whole-program optimalisatie.

De werking van LTO is als volgt: de compiler compileert elke .c-eenheid onafhankelijk naar een .o-bestand dat compiler-IR (Intermediate Representation) bevat en voert een best-effort optimalisatie uit op elke eenheid. Vervolgens ontvangt de linker elk .o-bestand met de IR, gebruikt deze voor whole-program optimalisatie en linkt ze tot één artefact (een executable of library).

Stel je nu een build-systeem en een compiler voor die zijn samengevoegd tot één geheel. Hiermee weet het build-systeem waar elke compilatie-eenheid zal eindigen zonder te hoeven wachten tot de link-fase. Denk aan een build-beschrijving als deze:

exe four {
    sources: [ "four.c", "main.c" ]
}

Bij een beschrijving als deze weet het build-systeem dat zowel four.c als main.c zullen resulteren in één output genaamd four. Het kan dit doorgeven aan de compiler, die vervolgens whole-program optimalisatie kan uitvoeren voordat de objecten worden gelinkt. Hoewel ik oorspronkelijk dacht dat dit veel sneller zou zijn dan LTO, denk ik nu dat het ongeveer hetzelfde zou zijn, aangezien het grootste deel van het werk in LTO de optimalisatie zelf is. Wel zou het op implementatieniveau iets sneller kunnen zijn, omdat je voorkomt dat IR als .o-bestanden naar schijf moet worden geschreven.

Er zijn echter andere voordelen aan een build-systeem dat met de compiler kan communiceren. Als meerdere .c-bestanden dezelfde headers #include, kan het systeem voorkomen dat dezelfde headers herhaaldelijk worden geparsed en dat er telkens een AST (Abstract Syntax Tree) voor wordt gebouwd. Men kan zelfs IR en AST's vrijer cachen tussen bestanden.

Bovendien geeft kennis van het gehele programma voldoende informatie om incrementele compilatie op een veel kleinere schaal uit te voeren dan gebruikelijk is bij C. Normaal gesproken gebeurt incrementele compilatie op basis van tijdstempels van elke compilatie-eenheid. Maar als je alle eenheden die samen één output (library/executable) vormen als één geheel behandelt — wat je weet uit de build-graph van het build-systeem — kun je incrementele compilatie op functieniveau uitvoeren, vergelijkbaar met wat Rust al doet met zijn request-based compilatiesysteem.

Na dit te hebben uitgedacht, was mijn volgende gedachte hoe dit systeem gecombineerd zou kunnen worden met een build-bewuste pakketbeheerder.

De compiler, het build-systeem en de pakketbeheerder

De meeste moderne talen bevatten een vorm van pakketbeheer, zodat ontwikkelaars afhankelijkheden eenvoudig en geautomatiseerd kunnen beheren. C heeft dit niet echt, behalve in beperkte mate. De meeste C-programma's met afhankelijkheden verwachten dat je een systeem-pakketbeheerder hebt (denk aan apt, apk, pacman, dnf, xbps, pkgin) die de benodigde libraries en headers levert.

Dit is niet hetzelfde als wat talen als Go doen, waarbij de broncode van de afhankelijkheid wordt opgehaald, automatisch wordt gecompileerd en vervolgens de vers gecompileerde kopie wordt gebruikt. Het huidige C-systeem verwacht dat er een vooraf gecompileerd pakket beschikbaar is vanuit een remote repository. Ik denk dat dit minder dan ideaal is. Enerzijds dwingt het de gebruiker om binaire artefacten te vertrouwen die hij zelf niet heeft gemaakt, maar belangrijker is dat we voor maximale whole-program optimalisatie het gehele programma moeten optimaliseren, inclusief de libraries die we linken.

Dit is technisch mogelijk met LTO, mits de libraries statische archieven van objecten met IR zijn. Dit brengt echter problemen met zich mee: IR geproduceerd door verschillende compilers is niet compatibel, en statische libraries die door de meeste systeem-pakketbeheerders worden gedistribueerd (indien überhaupt gedistribueerd), bevatten geen IR maar zijn normale objectbestanden. LTO kan dan niet worden uitgevoerd.

Een betere oplossing zou een pakketbeheerder zijn waarbij de pakketten weten hoe ze zichzelf moeten bouwen en hoe hun afhankelijkheden (en de zaken die van hen afhankelijk zijn) gebouwd moeten worden.

Ik noem dit "afhankelijkheidskennis over pakketgrenzen heen" (dependency knowledge across package boundaries). Hier zijn enkele voorbeelden van waarom dit voordelig is. Stel dat het voorbeeld met de vermenigvuldiging van eerder nu zo is dat four.c onderdeel is van een library genaamd libfour. Voor whole-program optimalisatie zouden we een statisch archief moeten compileren dat het IR-object four.o bevat. Dit is lastig te distribueren omdat het alleen werkt met de specifieke compiler die wordt gebruikt.

Stel je nu een systeem voor waarbij de compiler, het build-systeem en het pakketbeheer communiceren. Beschouw een build-beschrijving als deze:

package libfour {
    out {
        library four {
            sources: [ "four.c" ]
        }
    }
}

package four-exe {
    out {
        exe four {
            sources: [ "main.c" ]
            link: [ @libfour:out:four ]
        }
    }
}

In deze beschrijving hebben we twee pakketten. Het @-symbool is een referentie naar een ander pakket. We weten dus dat four-exe expliciet afhankelijk is van de library four uit het andere pakket, en we weten precies welke bronbestanden er in die library zitten. Op deze manier communiceert de pakketbeheerder met het build-systeem om kennis over de pakketgrenzen heen te geven. Het build-systeem kan deze informatie vervolgens doorgeven aan de compiler om whole-program optimalisatie op veel grotere schaal uit te voeren.

Deze communicatie tussen de drie componenten heeft nog meer voordelen. Stel dat de ontwikkelaar van libfour het bestand four.c aanpast. In een typisch systeem zou je de nieuwe versie ophalen uit de repository (waarschijnlijk een nieuwe versie van de shared library) en hopen dat programma's die erop linken niet breken. In dit systeem zou de pakketbeheerder het build-systeem precies vertellen wat er is veranderd. Het build-systeem kan vervolgens een graph berekenen van exact wat opnieuw gecompileerd moet worden en wat niet. De compiler kan dan incrementele compilatie op een nog kleinere schaal uitvoeren door elke compilatie-eenheid van de uiteindelijke output als één geheel te behandelen, en zo incrementele compilatie op functieniveau te doen in plaats van op bestandsniveau.

Verder zou je een declaratief systeem kunnen gebruiken om te bepalen welke pakketten je wilt, wat incrementele reconfiguraties mogelijk maakt:

system {
    packages: [
        @four-exe,
        @wm,
        @terminal,
    ]
    config {
        @wm:fancy-effects = off
    }
}

Het systeem zou dan alle exacte afhankelijkheden op bestandsniveau van al deze pakketten kunnen berekenen, alles kunnen bouwen met whole-program optimalisatie en dit onveranderlijk (immutable) op je systeem kunnen installeren. Als je vervolgens de fancy-effects in het wm-pakket wilt aanzetten, zou alleen het deel van dat pakket dat afhankelijk is van die config-optie opnieuw gecompileerd worden, waarna het systeem atomair wordt bijgewerkt. Zo kunnen we veilige en atomaire incrementele upgrades en reconfiguraties hebben, in tegenstelling tot typische systemen met mutabele status telkens wanneer een shared library in-place wordt geüpdatet.

Dit leek de logische grens van het systeem. De compiler, het build-systeem en de pakketbeheerder zijn gerelateerde componenten. Maar ik realiseerde me dat er ook onwaarschijnlijkere componenten zijn die een plek zouden kunnen hebben in een systeem als dit. Hoe ver kunnen we gaan met het toepassen van compiler- en afhankelijkheidsinformatie om het besturingssysteem te optimaliseren?

De compiler, het build-systeem, de pakketbeheerder en het bestandssysteem

Een neveneffect van mijn hypothetische systeem is dat alles statisch gelinkt moet worden om whole-program optimalisatie over pakketgrenzen heen mogelijk te maken. Op typische moderne POSIX-systemen is alles echter dynamisch gelinkt. De redenen hiervoor zijn meestal dat updates eenvoudiger zijn (je vervangt een library in-place) en dat het schijfruimte bespaart, omdat een library slechts één keer op schijf staat in plaats van in elk executable dat deze linkt.

Ik heb al uitgelegd hoe incrementele compilatie over pakketgrenzen snelle en onopvallende upgrades mogelijk maakt, maar het probleem van de schijfruimte blijft bestaan. Ik denk dat dit opgelost kan worden door de communicatie uit te breiden naar het bestandssysteem.

Stel dat we twee executables hebben die beide libfour linken en dingen met vier vermenigvuldigen. Door statische linking staat libfour waarschijnlijk twee keer op schijf. Echter, omdat ons build-systeem precies weet wat er tegen libfour linkt, wat de inhoud van libfour is en waar de twee executables op schijf staan, kunnen we deze informatie doorgeven aan het bestandssysteem. Een aangepaste implementatie van het bestandssysteem zou dan de twee kopieën van libfour op schijf kunnen dedupliceren.

Op grotere schaal zou elk executable of elke library die de systeem-C-library statisch linkt, gededupliceerd kunnen worden naar één fysieke locatie op de schijf. In feite stelt afhankelijkheidskennis over pakketgrenzen ons in staat om een shared library op bestandsniveau te creëren. Vanuit het perspectief van het besturingssysteem zijn ze allemaal statisch gelinkt, waardoor alle voordelen van statische linking behouden blijven (eenvoudige redistributie, whole-program optimalisatie, etc.), terwijl de schijfruimte-efficiëntie van dynamische linking wordt behaald.

De compiler, het build-systeem, de pakketbeheerder, het bestandssysteem en de scheduler

Er is zelfs nog meer. Ik denk dat je het idee nu begrijpt, dus ik zal niet te veel in detail treden, maar hier zijn een paar voorbeelden.

Stel dat in een bepaald pakket veel compilatieprocessen afhankelijk zijn van een specifieke stap, zoals een gegenereerde header. Het build-systeem zou dit kunnen communiceren naar de kernel, waarna de kernel-scheduler dat proces CPU-prioriteit kan geven om het sneller af te ronden en alle andere afhankelijke taken te ontgrendelen.

Een andere situatie is wanneer de compiler duizenden C++ objectbestanden in één executable probeert te linken. Dit vereist een enorme hoeveelheid geheugen. De compiler zou dit kunnen communiceren, waarna de scheduler tijdelijk andere niet-essentiële processen kan pauzeren of minder CPU-cycli aan hen kan toewijzen om het link-proces te versnellen.

Schedulers die bepaalde processen prioriteren bestaan al, maar zij doen dit op basis van algemene informatie van het proces zelf. Als de scheduler zou kunnen communiceren met de andere componenten, zou de extra informatie het mogelijk maken om parallellisatie (althans voor taken waarvan het build-systeem/de compiler weet) veel efficiënter en nauwkeuriger uit te voeren.

Conclusie

Ik zeg niet dat deze specifieke ideeën compleet nieuw zijn. ThinLTO maakt zeer efficiënte whole-program optimalisatie mogelijk; compiler-servers en tools zoals ccache doen al een deel van wat ik beschrijf in het compiler-gedeelte; Nix en Guix hebben zeer goede ideeën over content-addressing van artefacten en slim beheer van afhankelijkheden (hoewel zij vaak andere build-systemen wrappen, waardoor hun kennis bij de pakketgrenzen stopt); en deduplicerende bestandssystemen en slimme schedulers bestaan al.

Wat ik zeg is dat geen van deze systemen echt informatie met elkaar delen, en ik denk dat dat een enorme gemiste kans is. Omdat deze systemen niet specifiek voor dit doel zijn ontworpen, is het waarschijnlijk moeilijk om ze hiervoor aan te passen. Ik heb veel meer ideeën over hoe een compleet nieuw systeem, specifiek ontworpen rond deze visie van informatie-uitwisseling tussen systeembeheer en compilatie, zou werken. Dit omvat bijvoorbeeld hoe we cryptografische verificatie van volledige-bron bootstrapping kunnen implementeren en hoe we binaire artefacten decentraal kunnen distribueren. Ik heb deze hier weggelaten omdat ze eerder complementair zijn aan het systeem dan direct gerelateerd aan het probleem van communicatie tussen componenten.

Ik heb geprobeerd dit te schrijven op een manier die begrijpelijk is voor mensen met basiskennis van besturingssystemen, build-systemen en compilers. Ik heb de compilatie van C-programma's als voorbeeld gebruikt omdat C geen standaard build-systeem of pakketbeheerder heeft, maar dit idee kan eenvoudig worden toegepast op andere talen, of zelfs op meerdere talen tegelijk.

Ik ben me ervan bewust dat veel van de ideeën die ik hier presenteer zeer ambitieus zijn en waarschijnlijk de inspanning van veel mensen vereisen om te implementeren. Desalniettemin vind ik het interessante voedsel vooren thought: hoe zou een systeem eruitzien waarin alles met elkaar communiceert en hoe zou dat de computerervaring verbeteren? Als je meer ideeën hebt over hoe andere systeemcomponenten in dit systeem zouden kunnen passen, neem dan contact met me op! Er zijn nog veel andere componenten die geïntegreerd zouden kunnen worden (init-systemen, desktop-GUI's, enz.).

6 oktober 2026 shrub