Miljarden driehoeken in minuten

Begin dit jaar bracht NVIDIA hun nieuwe raytracing-technologie uit, RTX Mega Geometry, samen met een indrukwekkende Zorah-demo. Deze demo werd gedistribueerd als een Unreal Engine-scène van ongeveer 100 GB, die alleen geopend kan worden in een speciale branch van Unreal Engine: NvRTX. De demo toonde de toepassing van nieuwe, via de driver ontsloten raytracing-functies, specifiek clustered raytracing, in combinatie met de Nanite clustered LOD-pipeline. Hiermee kan een zeer gedetailleerde scène worden gestreamd en weergegeven met volledige raytracing, zonder gebruik te maken van de Nanite proxy-meshes die Unreal Engine momenteel voor raytracing genereert.

Omdat dit te specifiek was voor Unreal Engine, kon ik hier niet veel mee experimenteren. Maar begin september bracht NVIDIA een update uit voor hun open-source vklodclusters sample, waarin onder andere de Zorah-scène als glTF-bestand was opgenomen. Dit wekte natuurlijk mijn nieuwsgierigheid en leidde ertoe dat ik aanzienlijke tijd heb besteed aan het verbeteren van de ondersteuning voor hiërarchische geclusterde LOD in meshoptimizer.

Technologie

Het vervolg van dit artikel is makkelijker te begrijpen als je een redelijk begrip hebt van Nanite. Zo niet, dan raad ik Nanite: A Deep Dive door Brian Karis et al. aan voor de details; ik zal hier slechts de basisstroom samenvatten.

Uitgaande van een driehoeksmesh met waarschijnlijk zeer veel driehoeken, is onze taak:

1. Een hiërarchische structuur genereren die deze mesh op elk detailniveau (level of detail) kan representeren.
2. Delen van deze structuur streamen op het juiste detailniveau.
3. De zichtbare delen van de mesh renderen op het juiste detailniveau.

Het is belangrijk dat de structuur meerdere detailniveaus in verschillende regio's van de mesh kan representeren; dit maakt het mogelijk om te schalen naar grote modellen terwijl het detail passend wordt verdeeld. Ook moet het efficiënt renderen. De gekozen structuur is een graaf (DAG) van clusters; elk cluster is een kleine set driehoeken (bijvoorbeeld tot 128) en representeert een klein stuk van de mesh op een bepaald detailniveau. De structuur bevat clusters op verschillende detailniveaus, en de runtime-code is verantwoordelijk voor het streamen en renderen ervan om de visuele fout te minimaliseren — een cluster wordt pas vervangen door een grover cluster als de resulterende visuele fout onder de 1 pixel ligt (en de overgang wordt verborgen door TAA of andere temporele filters).

Er zijn drie lastige onderdelen aan deze techniek: het genereren van de structuur vanuit de zeer gedetailleerde mesh, het comprimeren van de resultaten om streaming efficiënt te maken, en het real-time renderen van de resultaten. We gaan het alleen kort hebben over het eerste deel.

Om de structuur te bouwen, wordt een mesh gesplitst in een set clusters. Naburige clusters worden samengevoegd in iets grotere groepen; elke groep wordt onafhankelijk vereenvoudigd, waarbij de randen van de groep behouden blijven. De resulterende groep wordt vervolgens weer gesplitst in meer clusters en het proces herhaalt zich totdat er geen toelaatbare clusters meer over zijn. Er zit veel nuance in hoe de algoritmen worden gecombineerd om te voorkomen dat er kieren ontstaan tussen clusters op verschillende detailniveaus, en er zijn veel afwegingen voor de individuele algoritmen — dit is gemakkelijk het onderwerp van een scriptie (en er zijn er inderdaad al meerdere over geschreven).

Sinds de release van Nanite in 2021 zijn meerdere engines dit verwerkingsparadigma gaan overnemen. Een open-source bibliotheek voor geometrieverwerking waar ik tegenwoordig aan werk, meshoptimizer, heeft sinds 2024 een voorbeeld van hoe verschillende algoritmen gecombineerd kunnen worden om deze structuur te bouwen[^1]. Met een end-to-end voorbeeld werd het veel makkelijker om de algoritmen te verbeteren en te experimenteren met varianten van de techniek — zou ik die voorbeeldcode wellicht kunnen gebruiken om de Zorah-scène te verwerken?

Een gevoel van schaal

De screenshots van de demo zien er prachtig uit, maar dat niveau van getrouwheid vereist veel werk aan texturen, shading en belichting naast Nanite. Gelukkig maken wij ons alleen zorgen over het geometrie-gedeelte; dat zou ons werk makkelijk maken, toch?

Zoals vermeld heeft NVIDIA een glTF-scène voor Zorah gepubliceerd als onderdeel van hun open-source Vulkan-samples. Laten we daar eens naar kijken:

• Bestand: zorahmainpublic.gltf.7z
• Driehoeken: 1,64 miljard (18,9 miljard met instancing)
• Grootte op schijf: 36,1 GB
• Render cache: 62 GB op schijf (kan worden gedownload of gegenereerd)

... oh. Een glTF-bestand van 36 GB dat alleen geometrie bevat — sterker nog, het bevat voor de overgrote meerderheid van de meshes geen vertex-attributen, alleen posities! (De sample-code leidt normalen voor shading af uit de posities in de shader-code).

Het importeren van dit glTF-bestand in Blender duurt ongeveer 10 minuten voordat het geheugen opraakt[^2]. Natuurlijk is Unreal Engine veel sneller — wat betekent dat de UE-import van dit bestand in minder dan 5 minuten het geheugen uitput en crasht![^3] Overduidelijk is de verwerking zeer geheugenintensief en is 192 GB RAM in feite niet genoeg voor iedereen.

Gelukkig hoeven we dit bestand niet te importeren: we moeten alleen de NVIDIA sample-code draaien die dit bestand verwerkt. Een poging om dat begin september te doen met 16 threads, liep echter ook vast door een tekort aan geheugen. Experimenteel ontdekte ik dat ik de verwerkingscode betrouwbaar kon draaien met 8 threads (--processingthreadpct 0.25), mits er niets anders op het systeem draaide, aangezien het proces ongeveer 180+ GB RAM verbruikte. Met 7 threads was het mogelijk om de computer ondertussen nog een beetje te gebruiken... gedurende de ongeveer 30 minuten die het proces in beslag nam.

Nu je voorbereid bent op hoe groot deze scène is, is het tijd om te praten over een reeks optimalisaties die dit geheel iets praktischer maken.

Baseline

Om de hiërarchische structuur te bouwen hebben we clusterisatie (om meshes in clusters te splitsen), partitionering (om clusters te groeperen) en vereenvoudiging (om een clustergroep te reduceren tot minder driehoeken) nodig. Gelukkig biedt meshoptimizer algoritmen voor alle drie.

Sinds versie 0.25 bevat meshoptimizer twee hoofdalgoritmen voor clusterisatie: één gebouwd voor rasterisatie en mesh shaders, die probeert het aantal geproduceerde meshlets te minimaliseren door geometrie strak in te pakken, en één gebouwd voor raytracing en nieuwe clustered raytracing extensies. De eerste is de afgelopen 8 jaar geëvolueerd; de tweede is relatief nieuw en specifiek ontwikkeld nadat NVIDIA hun RTX Mega Geometry-werk publiceerde[^4]. De reden voor twee algoritmen is dat clusterisatie bij raytracing zeer gevoelig is voor waar precies de clustergrenzen liggen — een optimale clusterisatie maakt het mogelijk om individuele clusters te nemen, micro-BVH-bomen voor elk cluster te bouwen, één BVH-boom over alle resulterende clusters te bouwen en de stralen door deze structuur te traceren. De vklodclusters sample heeft alleen raytracing-optimale clusters nodig, maar mijn oorspronkelijke demo gebruikte raster-geoptimaliseerde clusters, dus we beginnen daarmee.

Toen de democode oorspronkelijk werd geschreven, was deze bedoeld om nuttig te zijn voor het werken aan de onderliggende algoritmen, niet om herbruikbaar te zijn. Het kostte tijd om dit om te bouwen naar code die makkelijk te volgen is en een eenvoudige, schone interface biedt; de code neemt de mesh en veel configuratieparameters als input en produceert groepen clusters via een callback. Deze conversie naar herbruikbare code leverde op zichzelf al prestatievoordelen op — naast het elimineren van redundante STL-kopieën (in tegenstelling tot meshoptimizer zelf gebruikt deze code nu STL voor het gemak), was het ook nuttig om over te stappen op een interface waarbij de aanroeper vertex-attributen apart communiceert. De Zorah-scène gebruikt grotendeels meshes met alleen posities, dus we moeten geen tijd verspillen aan het verwerken van normalen of andere attributen. De nieuwe interface integreert ook recente toevoegingen aan vereenvoudiging, zoals de permissive mode, iets wat buiten het bereik van dit artikel valt. Een minimaal voorbeeld is nu vrij klein en eenvoudig:

clodConfig config = clodDefaultConfigRT(128);
clodMesh cmesh = {};
cmesh.indices = &indices[0];
cmesh.index_count = indices.size();
cmesh.vertex_count = vertex_count;
cmesh.vertex_positions = positions.data();
cmesh.vertex_positions_stride = sizeof(float) * 3;
clodBuild(config, cmesh,
[&](clodGroup group, const clodCluster* clusters, size_t cluster_count) -> int {
...
});

Wat overblijft is het laden van de glTF-scène en het uitvoeren van de code op elke individuele mesh. Mijn testcode slaat de resulterende data niet op op schijf — dus dit is geen exacte vergelijking, aangezien het opslaan van data extra kosten en serialisatie met zich meebrengt. We komen hier aan het einde op terug. Natuurlijk gebruiken we meerdere threads om de data te verwerken en cgltf om het bestand in het geheugen te laden.

Het bestand is 36 GB; om te voorkomen dat we het hele bestand synchroon in het geheugen laden voordat het proces start (en een vlakke overhead van 36 GB hebben), gebruiken we memory mapping. Ik heb een kleine PR bijgedragen aan cgltf om het werken met memory-mapped buffers iets makkelijker te maken.

Ten slotte moeten we de meshes re-indexeren; het bronbestand in glTF heeft enkele zeer grote meshes met zeer inefficiënte indexering (bijv. 90 miljoen vertices voor 30 miljoen driehoeken) — dit maakt het niet alleen moeilijker om een kwalitatief goede vereenvoudiging te krijgen, maar vertraagt ook onze verwerkingstijden, aangezien het aantal vertices in de mesh soms belangrijk is.

Met deze aanpassingen voltooit een klein programma op Linux met 16 threads de verwerking van het bestand in ongeveer 9m 20s, met een geheugengebruik van ~54,6 GB RAM. Dit is met de rasterisatie-geoptimaliseerde setup; als we overschakelen naar de nieuwe raytracing-geoptimaliseerde clusterizer, komen we op ~7m 10s en ~57,6 GB RAM.

Aan de ene kant is dit niet zo slecht. Aan de andere kant zijn 7-9 minuten nog steeds vrij lang; een kop koffie halen duurt niet eens zo lang. Tijd om te kijken of we dit kunnen verbeteren.

Problemen met sparsiteit

Met de Superluminal profiler kunnen we proberen te begrijpen waar de tijd naartoe gaat. Laten we zowel rasterisatie- als raytracing-builds draaien om duidelijke hotspots te vinden...

• Rasterisatie: [Profiler data]
• Raytracing: [Profiler data]

Hmm, dat is een enorme hoeveelheid tijd voor een memset! (We komen later terug op andere problemen).

Wat hier gebeurt is dat beide clusterizers een array gebruiken, geïndexeerd door de vertex-index, om bij te houden of een vertex is toegewezen aan een huidig meshlet. Dit bespaart ons de moeite om telkens door de 64-128 vertices te zoeken wanneer we willen controleren of het toevoegen van een driehoek aan het meshlet het aantal vertices zou verhogen. Helaas is deze code:

memset(used, -1, vertex_count * sizeof(short));

... alleen snel zolang het aantal vertices klein is — niet wanneer we herhaaldelijk subsets van een mesh met 30 miljoen driehoeken clusteriseren! Opmerkelijk genoeg bestond er een soortgelijk probleem, maar minder ernstig, in de simplifier. Als onderdeel van het werk om meshoptimizer vriendelijker te maken voor geclusterde LOD-gevallen in 2024, heb ik een meshoptSimplifySparse flag toegevoegd. Deze gaat ervan uit dat de input-indexbuffer een kleine subset van de mesh is en probeert O(vertexcount) werk koste wat kost te vermijden... behalve dat er een klein probleem overbleef, waarbij een bit-array voor soortgelijke filtering werd geïnitialiseerd:

memset(filter, 0, (vertex_count + 7) / 8);

Natuurlijk is 1 bit per vertex veel goedkoper om te vullen dan 16... maar dit telt nog steeds op bij meshes die de 100 miljoen driehoeken naderen. Voorheen was de grootste enkele mesh die ik had getest 6 miljoen driehoeken en 3 miljoen vertices — een orde van grootte kleiner dan individuele meshes in deze scène.

Er zijn manieren om deze code onafhankelijker te maken van het aantal vertices — bijvoorbeeld door dynamisch over te schakelen naar een volledige hashmap — maar dat brengt extra kosten en complexiteit met zich mee. Laten we voor nu kijken wat er gebeurt als we alle problemen oplossen door alleen de array-elementen te initialiseren die door de indexbuffer worden gebruikt wanneer sparse access (indexcount < vertexcount) wordt gedetecteerd. Na het opnieuw draaien van de code met deze fixes[^5], krijgen we 3m 31s voor de raster-versie en 3m 57s voor de raytrace-versie. Vooruitgang!

Je zult merken dat de mate van winst hier niet overeenkomt met de informatie die de profiler rapporteert. Er zijn een paar factoren die hieraan bijdragen; bijvoorbeeld dat de profiler in dit geval aanzienlijke overhead heeft. Maar belangrijker is dat de tijdverdeling die de profiler rapporteert voor al het werk is dat over alle threads gebeurt, terwijl de wall clock time voor de gehele verwerking afhangt van de traagste thread. Dat brengt ons bij...

Threads balanceren

In plaats van te kijken naar de verdeling van functies die tijd kosten, focussen we op de vraag of we threads goed gebruiken. Bij het uitvoeren van het executable vanuit de terminal kun je /usr/bin/time -v gebruiken om het CPU%-gebruik te zien; voor ons is dat 1240-1260% afhankelijk van de modus — met andere woorden, we gebruiken iets meer dan 12 threads aan geaggregeerde rekenkracht.

Laten we met Superluminal nauwer kijken naar de resultaten: [Grafiek].

... ah ja, dit is niet geweldig. Als we kijken naar de verdeling van het aantal driehoeken per mesh in deze scène, zien we een aanzienlijke onbalans: een paar meshes hebben tientallen miljoenen driehoeken, maar de meeste hebben er veel minder. Als we pech hebben, beginnen we pas laat in het proces met de grote meshes als ze niet vooraan in de wachtrij voor de thread pool staan; we zien hier in de "overhang" inderdaad een grote mesh die ~48s nodig heeft om alleen de clusters voor het eerste DAG-niveau te bouwen. We moeten meshes zoals deze als eerste verwerken.

Hoewel volledig algemene oplossingen voor scheduling-problemen zeer ingewikkeld zijn, hebben we hier geen algemene oplossing nodig. De tijd die nodig is om één mesh te verwerken is een functie van het aantal driehoeken, dus we kunnen de meshes simpelweg sorteren op driehoekenaantal in aflopende volgorde. Dit zorgt ervoor dat we de duurste meshes eerst verwerken.

Dit is ook een goed moment om de geheugenlimieten te noemen. Experimenteel weten we nu dat het ~60 GB kost om deze scène op 16 threads te verwerken — een deel van de reden waarom onze verwerking nu veel sneller is, is dat het minder geheugen kost, waardoor we naar meer threads kunnen schalen. Maar wat als het systeem waarop we moeten draaien slechts 40 GB RAM heeft?[^6] Ideaal gezien gebruik je een limiter die slechts een bepaald vast aantal driehoeken "tegelijk" toestaat te verwerken. Dit kan worden geïmplementeerd met een std::atomic (met yields/sleeps om onnodig CPU-verbruik te voorkomen) of een counting semaphore. Voor deze scène stellen we de geheugenlimiet in op 60+ GB om te voorkomen dat we de uitvoering knijpen — 192 GB RAM is immers ruim voldoende.

Hoe dan ook, we sorteren de meshes en draaien de code opnieuw. Dit is het nieuwe thread-schema: [Grafiek].

... geweldig. Hoewel er nog steeds een paar kleine gaten in het schema zitten, zien we nu dat de thread-uitvoering perfect gebalanceerd is over 16 threads — /usr/bin/time rapporteert 1574% CPU-benutting. De grote meshes vooraan plaatsen betekent dat kleinere meshes de gaten aan het einde efficiënt kunnen opvullen. Natuurlijk, als de input-scène slechts één of twee meshes heeft, moet onze parallellisme-strategie veranderen — maar voor deze scène is "extern" parallellisme (waarbij de as het aantal meshes is) het beste, omdat we geen data tussen verschillende threads hoeven te delen.

De uitvoeringstijd is nu veel beter: 2m 56s voor rasterisatie en 3m 07s voor raytracing. Opmerkelijk is dat het piekverbruik van het geheugen eigenlijk iets lager is (~45 GB voor de raytracing-versie in plaats van ~54 GB vóór het sorteren). Dit is niet erg intuïtief — normaal gesproken verwacht je dat het piekverbruik wordt bereikt wanneer elke thread de grootste mesh verwerkt — maar er is waarschijnlijk een verklaring die ik nu mis; dit zal zeker afhangen van de details van de systeem-allocator.

We zijn al een heel eind gekomen; ~3 minuten verwerkingstijd is een respectabel getal, zelfs als we de resulterende data niet serialiseren. Dat is alles dan, tot de volgende keer!

Nog snellere clusterisatie

... natuurlijk zijn we nog niet klaar. Toevallig was ik net voordat NVIDIA de nieuwe asset-bestanden uitbracht bezig met prestatieverbeteringen voor beide clusterizers. Alle resultaten tot nu toe zijn gepresenteerd met meshoptimizer v0.25 (plus sparsity-fixes), maar we moeten eigenlijk testen op de nieuwste master-branch, die twee belangrijke verbeteringen bevat voor de prestaties van de clusterizer.

Voor de raster-geoptimaliseerde clusterizer bleken in sommige gevallen bepaalde interne boom-zoekfuncties steeds over dezelfde data te zoeken. Ik ga hier niet te diep op in omdat dit artikel al lang wordt, en het beïnvloedt deze levels niet zo acuut (besparing van ~3%); vanaf nu focussen we op raytracing-geoptimaliseerde structuren. Bij het profileren van de huidige code die ~3m 07s duurt, zien we dat de nieuwe spatiale clusterizer (meshopt_buildMeshletsSpatial) verantwoordelijk is voor tweederde van de runtime. Gelukkig kunnen we in dit geval naar één functie wijzen als bron van de meeste problemen: bvhComputeArea.

Conceptueel gezien ligt de kern van de spatiale clusterizer dicht bij een sweep BVH builder. Voor elk niveau van de boom moeten we het beste splitsvlak bepalen; om dat te doen moeten we de kosten analyseren van het plaatsen van een splitsvlak door het zwaartepunt van elke driehoek langs elke van de cardinale assen. Deze kosten kunnen worden berekend door de bounding boxes van de driehoeken zes keer te accumuleren — drie assen maal twee richtingen, links en rechts; de resulterende kosten kunnen worden berekend uit het oppervlak van de resulterende AABB's.

void bvhComputeArea(float* areas, const BVHBox* boxes, const int* order, size_t count)
{
    BVHBox accuml = { {FLT_MAX, FLT_MAX, FLT_MAX}, {-FLT_MAX, -FLT_MAX, -FLT_MAX} };
    BVHBox accumr = accuml;
    for (size_t i = 0; i < count; ++i)
    {
        areas[i] = boxMerge(accuml, boxes[order[i]]);
        areas[i + count] = boxMerge(accumr, boxes[order[count - 1 - i]]);
    }
}

Deze casus is interessant omdat de prestatiekenmerken van bvhComputeArea veranderen op verschillende niveaus van de verwerking. Bij het clusteriseren van grote meshes zijn de initiële aanroepen van bvhSplit (een recursieve functie) bezig met de hele mesh, waarbij de lokaliteit van de AABB-traversal niet ideaal is. Hierdoor verwachten we dat de functie memory bound is. Wanneer de recursieve aanroepen uiteindelijk bij een paar duizend driehoeken komen, worden de toegangspatronen zeer lokaal omdat de "actieve" boxes gemakkelijk in L2 en zelfs L1 passen.

De reden waarom dit belangrijk is, is dat ik aanvankelijk dacht de situatie te kunnen verbeteren door de hoeveelheid geheugen per box te verminderen. Dit verbeterde de hogere niveaus echter niet dramatisch (waarschijnlijk omdat de lokalisatie nog steeds slecht was) en verslechterde de lagere niveaus omdat het opslaan van AABB's op een andere manier dan een paar floats extra cycli kost om te decoderen. Na enkele pogingen met verschillende box-representaties gaf ik het op en probeerde ik iets dat eigenlijk niet had moeten werken: het simpelweg converteren van de relevante code (boxMerge functie) naar SSE2. Een box heeft twee hoeken die elk in een SSE2-register kunnen worden geladen; min/max accumulatie kan gebruikmaken van dedicated MINPS/MAXPS instructies; en we kunnen het oppervlak van de box berekenen met een moderate hoeveelheid shuffle crimes (bij gebrek aan een dedicated DPPS instructie, die SSE4.1 vereist). Hetzelfde kan worden gedaan met NEON voor ARM-servers of Macs.

De resulterende SIMD-code is vrij eenvoudig en bestaat uit slechts 20 regels per architectuur. Het is niet de beste SIMD-code ter wereld — we gebruiken slechts 3 floats aan berekening terwijl de hardware veel bredere vectoren zou kunnen gebruiken — maar helaas is het moeilijk om de data zo te herschikken dat de layout SIMD-optimaal is, omdat de volgorde van de boxes te vaak verandert. Toch, als we de code opnieuw draaien, gaan we van 3m 07s naar 2m 51s — een algehele versnelling van ~9%![^7] Dit brengt onze raytracing-geoptimaliseerde code op één lijn met de rasterisatie-geoptimaliseerde versie, maar we zijn er nog niet helemaal.

Zoals vermeld raken de vroege niveaus van de recursie mogelijk een limiet van het geheugensysteem. Het is dan logisch dat als de volgorde van de bounding boxes in het geheugen — die overeenkomt met de volgorde van de driehoeken in de input-indexbuffer — coherenter was, we verdere versnelling zouden zien.

Wat we kunnen doen is de driehoeken ruimtelijk sorteren met een Morton-volgorde; gelukkig biedt meshoptimizer een functie die precies dat doet: meshopt_spatialSortTriangles. Deze functie roepen heeft een kostprijs — maar zolang de winst in clusterisatietijd groter is dan de extra moeite om de driehoeken te sorteren, is dit een goed idee. Na het proberen hiervan op die scène komen we op 2m 44s — een verdere versnelling van ~5% voor één extra regel code. Mooi!

Allocaties cachen

Tijd om de "final boss" aan te pakken: alle bovengenoemde functies moeten geheugen alloceren voor de verwerking. Gegeven 16 threads die aanzienlijke blokken geheugen alloceren, zou een ideale allocator thread-lokale buffers gebruiken om te voorkomen dat allocaties van de ene thread concurreren met die van een andere thread.

Helaas is het verwachten hiervan te optimistisch, afhankelijk van het platform. Alle experimenten tot nu toe zijn uitgevoerd op Linux. Hoewel we over het algemeen zeer redelijke prestaties krijgen met weinig concurrentie, zijn er zelfs op Linux incidentele "rode" vlekken in het thread-utilisatieoverzicht, wat aangeeft dat de thread in een busy wait staat — en bij controle blijkt dat deze inderdaad wacht tot een andere thread de allocatie afhandelt.

Ik aarzel om specifieke conclusies te trekken omdat Superluminal bij een zware thread-belasting de timings verschuift, maar we kunnen in plaats daarvan overschakelen naar het platform waar de stock-allocator minder kwalitatief is — Windows — en het sombere beeld van de thread-utilisatie observeren: [Grafiek].

Wat hier gebeurt is een ongelukkige interactie tussen multi-threaded allocaties en het standaard large block beleid. Grote blokken omzeilen de heap en worden gealloceerd via VirtualAlloc; geheugen dat op deze manier is gealloceerd is aanvankelijk duur om mee te werken[^8], dus herhaaldelijke allocaties/deallocaties veroorzaken prestatieproblemen. Omdat meerdere threads concurreren om dezelfde heap-mutex, wordt de doorvoersnelheid aanzienlijk beïnvloed.

Gelukkig is er een eenvoudige oplossing: gebruik een per-thread arena en routeer de allocaties daarheen als ze passen. meshoptimizer biedt een eenvoudige manier om allocaties globaal te overriden en garandeert dat allocatie/deallocatie-callbacks in een stack-achtige manier worden aangeroepen. Dit maakt het eenvoudig om een thread-lokale cache te implementeren: pre-alloceer een blok geheugen, bijvoorbeeld 128 MB; alloceer daaruit met een bump allocator of val terug op malloc; deallocatie kan controleren of de pointer bij de thread-lokale arena hoort en anders terugvallen op free.

Dit toepassen op Linux levert bescheiden verdere prestatieverbeteringen op; onze code draait nu in ~2m 35s — ongeveer 3,5x sneller dan onze initiële baseline, en significant beter dan ~30 minuten. Op Windows draaide de code voor deze wijziging in 4m 20s — en met de thread-cache komen we op 2m 38s, in lijn met onze Linux-versie! En de utilisatie ziet er veel beter uit.

Met wat extra inspanning is het mogelijk deze oplossing te generaliseren zodat deze eenvoudig te integreren is bovenop de standaard allocator; ik ben van plan dit toe te voegen in een toekomstige versie van meshoptimizer.

Resultaten

Zijn we nu klaar? Nou, meer of minder :) De meeste verbeteringen zijn geïntegreerd in de democode die nu wordt gedistribueerd als een single-header "micro-library" via de meshoptimizer repository: clusterlod.h. De code is ontworpen om gemakkelijk aan te passen, maar ook om direct in te pluggen.

Van de genoemde prestatieverbeteringen kan de aanroep naar meshopt_spatialSortTriangles extern worden gedaan indien nodig, en het werk aan de thread-cache is nog niet ingediend. Het zal waarschijnlijk worden opgenomen in meshoptimizer na de release van v1.0 later dit jaar.

En toen ik dacht dat dit ongeveer het einde was, bleek deze voorbeeldcode zo nuttig dat vklodclusters (de sample die dit hele werk startte) het als optie heeft geïntegreerd! Je kunt het selecteren door --nvclusterlod 0 mee te geven. De versie in de repository van NVIDIA past de voorbeeldcode aan om optioneel "intern" parallellisme te implementeren — het vermogen om een cluster-DAG uit een enkele mesh te genereren met meerdere threads. Dit is niet nodig voor Zorah of andere grote scènes (waarbij "extern" parallellisme natuurlijker is), maar is cruciaal om sneller een DAG voor een enkele grote mesh te genereren.

Dankzij hun werk kan ik nu een andere screenshot laten zien van hetzelfde Zorah-asset, maar ditmaal draaiend in de vklodclusters sample met data gegenereerd door meshoptimizer's clusterlod.h. Gerenderd met een geometrie-pool van ongeveer 2 GB, in 26ms bij raytracing en 16ms bij rasterisatie, op een NVIDIA GeForce 3050. Niet slecht voor een GPU die al zijn stroom van het moederbord haalt zonder aparte stroomkabel!

In vklodclusters is de verwerking iets anders gestructureerd; het genereert een iets andere hoeveelheid werk en bevat ook data-serialisatie, waardoor het iets langzamer draait — ~3m 20s met alle optimalisaties. In die tijd voert het alle beschreven verwerking uit en genereert het het cachebestand van 62 GB — inclusief, ironisch genoeg, bijna 10 seconden die Linux nodig heeft om dit bestand met fopen() te openen voor schrijven, omdat het even duurt om de bestaande bestandsinhoud uit de file system cache te verwijderen. Aangezien ik mijn 7950X in eco-mode draai, noemen we het gewoon ongeveer 3 minuten.

Er zijn nog steeds mogelijkheden voor verbetering. Om een scène als deze efficiënt te streamen en weer te geven, heb je een aparte hiërarchische versnellingsstructuur nodig die snel de set clusters kan bepalen die gerenderd moeten worden; vklodclusters doet dit met bestaande meshopt functies, maar die code maakt nog geen deel uit van clusterlod.h. Ook het standaard cluster-partitioneringsalgoritme in clusterlod.h is momenteel alleen bereid om clusters te groeperen die topologisch aangrenzend zijn; dit kan soms resulteren in DAG's met te veel wortels. (Update: kort na publicatie van deze blog is dit inmiddels opgelost in de implementatie van meshoptpartitionClusters in meshoptimizer).

Ik ben blij om een betekenisvolle mijlpaal te zien voor deze code, die begon als een eenvoudige speeltuin voor clusterisatie-algoritmen.

***

Voetnoten: [^1]: Deze voorbeeldcode was gemotiveerd door het verbeteren van het virtuele geometriesysteem van Bevy. [^2]: Alle testresultaten zijn behaald op een desktop systeem: AMD Ryzen 7950X (16C/32T), 192 GB RAM (DDR5-4800), NVIDIA GeForce 3050 8 GB. [^3]: Opmerkelijk is dat de originele Unreal Engine scène waarschijnlijk is samengesteld uit individuele mesh-assets die afzonderlijk zijn geïmporteerd, wat werken op redelijkere hardware mogelijk maakte, mits je niet de hele scène in één keer hoefde te herverwerken. [^4]: NVIDIA heeft ook een library uitgebracht, nvclusterbuilder, die deze RT-bewuste clusterisatie kan uitvoeren — het nieuwe meshoptimizer algoritme gebruikt vergelijkbare ideeën maar een wezenlijk andere implementatie. [^5]: Tenzij anders vermeld, zijn alle verbeteringen aan de bibliotheekcode al gecommit naar meshoptimizer (master branch). [^6]: Ongeacht het feit dat het verwerken van een 36 GB glTF met slechts 40 GB RAM waarschijnlijk geen goed idee is. [^7]: Op Apple M4 is een significante versnelling gemeten door een soortgelijke wijziging die boxMerge naar NEON converteerde — een versnelling van 2x+ voor clusterisatie alleen. [^8]: Dit is vergelijkbaar met een probleem waar ik een decennium geleden tegenaan liep, beschreven in A queue of page faults.