Hoe dicht kan pure functionele programmering bij C komen?

lean-zip verslaat elk compressieniveau dat miniz_oxide biedt; we zijn in staat om dezelfde compressie te leveren met een hogere doorvoersnelheid. Op de snelste instelling zijn we 15% sneller en is de output 8,8% kleiner.

Het artikel merkt echter ook op dat hoewel ze Rust's miniz_oxide wisten te overtreffen, ze geen partij waren voor de "eindbaas" van DEFLATE-prestaties: libdeflate, geschreven in C.

lean-zip is hier zeker niet de beste: libdeflate blaast het onverwacht weg (onverwacht omdat dit een zeer zorgvuldig afgestelde implementatie is die gebruikmaakt van architectuurspecifieke SIMD, waar we in Lean niet bij kunnen).

Hier komt Roc in beeld, een functionele programmeertaal (maar geen theorem prover) met een expliciete focus op runtime-prestaties.

De slogan van Roc is "Fast, Friendly, Functional", waarbij "Fast" op de eerste plaats staat omdat zowel een snelle uitvoering als een snelle compilatie altijd centrale doelen zijn geweest. Roc is geen volwassen taal (het is nog weken verwijderd van de eerste genummerde release, 0.1.0), en in het beginnende ecosysteem van pakketten is er bijna geen optimalisatiewerk verricht. Toch dacht ik, gezien het taalontwerp, de langdurige optimalisaties en de gloednieuwe compiler-implementatie, dat Roc al over een voldoende basis beschikte om het op te nemen tegen de kampioen: libdeflate.

Ik heb daarom veel tijd besteed aan prestatie-optimalisaties voor roc-deflate, een pakket dat Niclas Ahden schreef (en gebruikt in betaald productiewerk) voor DEFLATE-compressie. Ik verwachtte niet dat ik de prestaties van libdeflate over de hele linie zou verslaan, maar ik wilde zien hoe dicht het kon komen op de non-streaming API's (aangezien roc-deflate streaming nog niet heeft geïmplementeerd), gebruikmakend van het klassieke Silesia-corpus voor benchmarking en de verificatie dat het identieke outputs produceerde.

Minder dan 10% langzamer

Dit is de huidige stand van de benchmarks, uitgevoerd op een 2021 M1 MacBook Pro (waar ik het optimalisatiewerk deed) en op een AMD Ryzen 9 3900X Ubuntu-machine voor een x64-vergelijking.

roc-deflate voerde deze 144 benchmarks gemiddeld langzamer uit dan libdeflate; in het mediane geval 8,9% langzamer op de Ryzen 3900X en 2,6% op de M1 MacBook Pro.

Compressie op Silesia-corpus: M1 MacBook Pro

(Medianen over 15 runs, in MB/s)

Bestand	L1 libdeflate	L1 roc-deflate	L2 libdeflate	L2 roc-deflate	L3 libdeflate	L3 roc-deflate	L4 libdeflate	L4 roc-deflate	L5 libdeflate	L5 roc-deflate	L6 libdeflate	L6 roc-deflate	L7 libdeflate	L7 roc-deflate	L8 libdeflate	L8 roc-deflate	L9 libdeflate	L9 roc-deflate	L10 libdeflate	L10 roc-deflate	L11 libdeflate	L11 roc-deflate	L12 libdeflate	L12 roc-deflate
dickens	230.57	202.92	161.68	143.60	130.85	122.04	119.94	113.71	95.14	90.27	70.60	72.83	54.23	56.93	37.50	39.56	34.82	36.73	12.07	12.97	8.85	10.10	7.35	8.59
mozilla	248.31	225.79	184.55	168.37	169.26	158.29	158.07	148.77	133.06	125.87	107.04	107.54	75.96	79.18	39.17	43.00	27.51	30.48	14.87	14.67	10.27	10.53	7.97	8.22
mr	312.26	277.57	204.86	182.07	171.11	159.07	156.88	149.00	129.45	122.34	96.85	98.92	66.46	70.19	43.21	45.70	38.60	40.95	16.07	15.47	8.76	8.19	4.26	3.83
nci	601.03	529.49	453.14	409.82	415.29	382.21	376.70	356.47	287.09	311.35	221.32	246.59	157.22	174.91	83.68	91.28	58.64	64.32	7.51	7.19	4.82	4.74	3.51	3.48
ooffice	169.98	153.99	128.05	118.08	118.92	111.14	113.68	107.59	95.87	89.73	82.91	81.43	70.52	70.27	52.45	52.69	47.26	48.05	18.09	18.02	13.56	14.03	11.45	11.99
osdb	284.01	257.14	203.10	185.41	183.10	171.27	164.59	156.41	140.08	133.37	122.89	122.02	117.53	115.95	106.76	101.66	106.10	101.46	16.97	17.23	12.91	13.62	11.40	12.21
reymont	281.14	245.80	207.66	183.69	169.42	157.19	152.16	142.45	120.63	115.52	79.91	84.85	46.77	51.20	24.87	27.81	20.65	22.85	8.64	9.63	6.49	7.71	5.59	6.87
samba	344.00	309.79	249.57	228.02	223.27	209.86	207.97	197.17	170.75	167.01	129.19	134.11	91.00	96.46	55.69	60.04	43.95	47.64	14.74	14.59	8.46	8.68	5.92	6.03
sao	160.21	145.28	112.78	105.68	100.60	95.51	94.48	89.37	83.22	76.99	67.48	66.36	59.49	59.40	51.86	51.65	51.18	50.68	24.08	22.93	19.43	18.87	18.10	17.74
webster	268.58	239.18	198.86	181.07	173.36	162.75	158.64	151.15	125.60	123.12	96.76	101.16	71.34	75.99	45.55	48.78	40.57	43.36	10.10	11.18	6.77	8.07	5.82	7.11
x-ray	145.93	134.66	117.18	107.00	116.62	105.93	116.63	106.32	102.48	90.40	102.50	90.67	102.43	90.26	91.30	81.01	91.69	80.68	34.15	32.15	26.05	24.93	23.50	22.60
xml	476.83	419.07	352.59	323.17	324.65	300.31	294.31	278.53	229.70	237.29	178.60	194.35	128.20	141.60	80.95	86.27	68.13	73.29	11.46	10.73	6.60	6.51	4.19	4.18

Compressie op Silesia-corpus: Ryzen 3900X Ubuntu

(Medianen over 7 runs, in MB/s)

Bestand	L1 libdeflate	L1 roc-deflate	L2 libdeflate	L2 roc-deflate	L3 libdeflate	L3 roc-deflate	L4 libdeflate	L4 roc-deflate	L5 libdeflate	L5 roc-deflate	L6 libdeflate	L6 roc-deflate	L7 libdeflate	L7 roc-deflate	L8 libdeflate	L8 roc-deflate	L9 libdeflate	L9 roc-deflate	L10 libdeflate	L10 roc-deflate	L11 libdeflate	L11 roc-deflate	L12 libdeflate	L12 roc-deflate
dickens	191.10	182.30	138.50	121.20	112.90	100.80	100.80	91.90	82.40	73.50	65.40	57.80	49.60	45.20	32.10	30.00	29.00	27.10	12.10	12.30	8.80	9.50	7.40	8.10
mozilla	235.50	204.50	162.80	144.50	152.80	132.50	144.50	126.60	120.00	105.70	102.90	89.40	76.10	67.20	41.40	36.80	29.10	26.30	14.80	13.70	10.30	9.90	8.00	7.80
mr	261.70	228.90	153.40	145.30	132.10	125.30	123.40	117.60	103.10	96.60	81.60	74.10	56.30	52.40	35.80	33.90	32.50	30.60	16.20	14.70	9.30	8.30	4.70	4.10
nci	387.30	428.60	286.50	326.40	304.30	301.90	254.00	282.80	250.40	247.90	203.10	188.20	150.20	141.70	80.70	75.50	58.50	54.40	7.30	6.80	4.70	4.50	3.40	3.30
ooffice	167.90	144.60	120.40	105.10	113.00	97.90	109.70	95.50	89.30	77.50	78.50	70.60	69.10	61.10	50.40	45.60	45.00	41.20	18.20	16.80	13.70	13.00	11.50	11.20
osdb	254.70	222.30	175.30	155.00	164.00	148.80	151.90	138.00	128.80	116.60	118.80	107.80	113.80	106.10	97.80	90.20	95.30	90.80	16.10	15.50	12.30	12.30	10.90	11.10
reymont	229.60	217.30	156.80	146.00	128.00	120.80	118.90	106.80	94.60	86.20	71.00	60.90	39.90	36.20	20.60	19.50	16.90	15.90	8.70	9.00	6.50	7.10	5.60	6.30
samba	291.00	270.30	210.50	188.40	191.40	169.40	178.70	159.20	152.10	133.00	120.10	105.40	85.90	76.50	53.40	49.00	41.60	38.70	14.40	13.60	8.40	8.30	5.90	5.80
sao	157.40	138.50	104.20	94.10	94.50	84.80	89.10	81.50	74.80	68.10	64.40	59.20	53.10	52.80	46.60	44.50	45.60	43.30	23.30	20.60	18.90	17.00	17.70	15.80
webster	207.00	213.90	163.50	151.60	143.70	133.90	129.70	125.00	112.20	100.10	91.80	81.30	66.10	59.40	40.00	37.10	33.90	31.70	10.00	10.20	6.70	7.30	5.80	6.40
x-ray	142.20	130.80	111.60	95.50	112.20	95.10	111.30	95.60	93.70	82.10	94.80	83.20	94.20	81.60	78.30	72.10	78.60	72.70	34.70	29.40	26.80	23.00	24.60	21.00
xml	411.30	353.80	258.40	248.60	209.90	231.70	201.50	215.50	198.40	182.10	168.30	149.50	119.90	108.40	72.60	66.40	57.90	54.80	10.80	9.80	6.20	6.00	4.00	3.90

Hoewel we de kampioen gemiddeld niet hebben verslagen, is een mediane vertraging in de enkelvoudige percentages wild, zeker vergeleken met een zorgvuldig afgestelde SIMD-gestuurde C-bibliotheek. Het is eerlijk gezegd een resultaat waarvan ik vooraf niet wist of het haalbaar was, aangezien Roc een functionele taal is met automatisch geheugenbeheer die strijdt tegen code die geen bounds-checks hoeft uit te voeren. (Bounds-checks hebben een kostprijs, maar overigens: de laatste keer dat een overgeslagen bounds-check in C-compressiecode leidde tot een grote Remote Code Execution-kwetsbaarheid, was gisteren.)

De grafiek toont meer detail dan alleen het mediane gat. Bij de worst-case inputs was roc-deflate 18% langzamer dan libdeflate, maar bij de best-case inputs was roc-deflate iets meer dan 18% sneller! Dat komt niet omdat Roc een magische optimalisatie heeft waar C geen toegang toe heeft; het is simpelweg omdat de twee implementaties verschillend zijn. Hoewel roc-deflate gemiddeld langzamer is, is het voor bepaalde inputs toevallig sneller. Hoewel het dus mogelijk is om een snelheidswinst te behalen door over te stappen van libdeflate naar roc-deflate, moet je dit gemiddeld genomen niet verwachten.

Om duidelijk te zijn: het prestatieplafond van C ligt hoger dan dat van Roc. Voor elke input waar roc-deflate momenteel beter presteert, kan C-code dat gat dichten. Het omgekeerde is niet waar; Roc-code is geheugenveilig, maakt gebruik van automatic reference counting, controleert grenzen (bounds checks) en ondersteunt geen Rust-stijl unsafe om hiervan af te wijken. Deze eigenschappen geven Roc-code sterkere veiligheidsgaranties dan code geschreven in C, Zig, Rust en andere talen die volledige toegang tot de hardware toestaan — en de prijs die het betaalt voor die garanties is een lager prestatieplafond.

Natuurlijk kunnen we niet extrapoleren vanuit dit ene resultaat hoe dicht Roc in het algemene geval bij C kan komen, maar er is nu iets gedemonstreerd waarvan niemand wist dat het haalbaar was. Voor zover ik weet, is dit de meeste optimalisatie-inspanning die tot nu toe in een Roc-pakket is gestoken. Hoewel ik enthousiast ben over dit resultaat, ben ik me er volledig van bewust dat we pas weten hoe goed dit generaliseert wanneer we een breder scala aan real-world Roc-codebases hebben geoptimaliseerd.

Wat het prestatieverschil oplevert

Een voor de hand liggende vraag is: "Waarom genoegen nemen met een lagere snelheid?" Als je C-prestaties zou kunnen halen, waarom zou je dan niet gewoon libdeflate zelf gebruiken en dat resterende gat dichten?

Een pure Roc-implementatie heeft verschillende voordelen ten opzichte van een pure C-implementatie:

• Geheugenveiligheid: Roc-code is volledig geheugenveilig en heeft geen taalprimitieven waarmee je hiervan kunt afwijken. Deze code kan C-prestaties benaderen omdat de optimalisatie-pipeline van Roc heeft vastgesteld dat veel bounds-checks en reference counting-operaties bewijsbaar veilig waren om weg te optimaliseren. Compressiepakketten geschreven in pure Roc hebben geen toegang tot de ongecontroleerde geheugenoperaties die gisteren de Brotli Remote Code Execution-kwetsbaarheid veroorzaakten.
• Geen zijeffecten: Het typesysteem van Roc leidt af welke functies puur zijn en welke zijeffecten kunnen hebben. Pure functies gebruiken een "dunne pijl" in hun type, zoals Bool -> Bool, terwijl functies met effecten een "dikke pijl" gebruiken, zoals Bool => Bool. Roc dwingt dit af en staat geen uitzonderingen toe. Wanneer je dus ziet dat de functies van roc-deflate alleen dunne pijlen in hun annotaties hebben, weet je dat het echt pure functies zijn.
• Beveiliging van de toeleveringsketen: Roc heeft geen willekeurige FFI (Foreign Function Interface), wat betekent dat je er zeker van kunt zijn dat de pure functies van roc-deflate niet eens kunnen proberen I/O uit te voeren of willekeurig geheugen te benaderen. Gezien de explosie van supply chain-aanvallen is het waardevol om te weten dat de schade die een kwaadwillende actor kan aanrichten met een pure functie in een gecompromitteerd Roc-pakket beperkt is tot het retourneren van een verkeerde waarde, het crashen van het programma of het verspillen van systeembronnen. Roc-pakketten ondersteunen bovendien geen build-scripts, wat de vector was die twee maanden geleden werd gebruikt om het populaire Rust-pakket arrayref succesvol te compromitteren.
• Portabiliteit: Pure Roc-functies zijn ontworpen om extreem deterministisch te zijn: ze retourneren altijd dezelfde waarden bij dezelfde argumenten — niet alleen op dezelfde machine, maar op elk doel waarvoor je de code compileert. (De functies kunnen crashen of niet termineren, maar dat gedrag moet ook deterministisch zijn over verschillende targets.) De enige manier waarop een pure Roc-functie zich anders zou moeten gedragen op twee verschillende systemen, is als één systeem halverwege de uitvoering uit het geheugen raakt.

Als een van deze garanties in de praktijk niet standhoudt, kan dat alleen komen door een defect in de Roc-compiler, het platform waarop de applicatie draait, of de onderliggende hardware. De type-systemen dwingen dit af.

De reden waarom we hier zo hard aan hebben gewerkt, wordt duidelijker als je de vraag omdraait: zou je gegarandeerde geheugenveiligheid, gegarandeerde afwezigheid van zijeffecten, gegarandeerd deterministisch gedrag over alle targets en de beveiligingsvoordelen van het ontbreken van exploiteerbare build-scripts opofferen... voor een gemiddelde snelheidswinst in de enkelvoudige percentages?

Het antwoord daarop kan per use case verschillen — de eigen compiler van Roc wil bijvoorbeeld de maximale prestaties die de hardware kan leveren — maar ik wed dat veel lezers begrijpen waarom we zo enthousiast zijn over dit resultaat.

Roc-specifieke optimalisaties

De meeste optimalisaties die de cijfers van roc-deflate verbeterden, kwamen voort uit algemene optimalisatietechnieken die breed toepasbaar zijn over verschillende talen. (Ik raad altijd de Performance-Aware Programming Series van Casey Muratori aan). Sommige technieken waren echter Roc-specifiek, en die wil ik hier als referentie noemen.

Vermijd onnodig delen (Avoid Unnecessary Sharing)

Een van de meest effectieve optimalisaties van Roc is opportunistic mutation (wat Koka "Functional but In-Place" noemt). Vanuit een prestatie-perspectief is het cruciaal om onnodig delen te vermijden, zodat waarden uniek blijven en dus in aanmerking komen voor in-place mutatie.

Bounds checks verplaatsen (Hoist Bounds Checks)

In Roc kun je niet handmatig bounds-checks uitschakelen (zoals bij het ophalen van een waarde uit een dynamisch verzameling), in tegenstelling tot C, Zig en Rust. De compiler van Roc kan ze echter weglaten als hij weet dat ze gegarandeerd zullen slagen. Bounds-checks zijn het kostbaarst binnen lussen. Je kunt veel winnen door iets toe te voegen als if collection.len() <= highestindexused { return 0 } voordat de lus begint. Dit voegt een extra check toe die redundant lijkt, maar het stelt de optimizer in staat om kostbaardere checks binnen de lus veilig te verwijderen.

Lookup-tabellen compileren (Build Lookup Tables at Compile Time)

De compile-time evaluatie van Roc kan worden gebruikt om lookup-tabellen tijdens het compileren samen te stellen, zolang deze niet afhangen van runtime-inputs. Omdat hun lengtes compile-time bekend zijn, kun je zaken doen als Ok(entry) = lookup_table.get(5) voor een uitputtende pattern match. De compiler weet dat dit geldig is, waardoor runtime bounds-checks die bij niet-constante tabellen nodig zouden zijn, worden vermeden.

Overweeg Wrapping Arithmetic

In Roc wordt a + b omgezet naar a.plus(b). Voor een integer zoals U64 bevat U64.plus een overflow-check, terwijl pluswrap dat niet doet. Hoewel plus de veiligere standaard is, hebben overflow-checks een runtime-kostprijs, aangezien CPU's wrapping integer arithmetic in één instructie kunnen uitvoeren. Wanneer de compiler kan bewijzen dat overflow niet zal optreden, worden beide geoptimaliseerd naar dezelfde instructies, maar wanneer dat niet kan, kan pluswrap een snelheidswinst opleveren.

Ruimte voor verbetering

Ik ben er zeker van dat er nog mogelijkheden zijn om de prestaties van roc-deflate te verbeteren — vooral op x64-CPU's — en dat de optimalisatie-pipeline in de Roc-compiler verder kan groeien.

Op dit moment heb ik het gevoel dat de meest voor de hand liggende verbeteringen zijn doorgevoerd. Voor mijn deel zal ik me richten op de aanstaande Roc 0.1.0 release. Er is acht jaar aan gewerkt, dus ik ben erg blij dat we eindelijk een genummerde release hebben!