Wat is Data-Oriented Game Engine Design?

Je hebt misschien gehoord van data-georiënteerd game-engine-ontwerp, een relatief nieuw concept dat een andere mindset voorstelt voor het meer traditionele objectgerichte ontwerp. In dit artikel zal ik uitleggen waar DOD over gaat en waarom sommige ontwikkelaars van game-engines denken dat dit het ticket kan zijn voor spectaculaire prestatiewinsten.

Een beetje geschiedenis

In de beginjaren van game-ontwikkeling waren games en hun engines geschreven in old-school talen, zoals C. Ze waren een nicheproduct en het uitpersen van elke laatste klokcyclus uit trage hardware was op dat moment de hoogste prioriteit. In de meeste gevallen haperde slechts een bescheiden aantal mensen aan de code van een enkele titel en kenden ze de hele codebase uit hun hoofd. De tools die ze gebruikten, waren goed voor hen geweest, en C bood de prestatievoordelen die hen in staat stelden het maximale uit de CPU te halen - en omdat deze games nog steeds door de grote grenzen werden vastgehouden door de CPU, met een eigen framebuffer, dit was een heel belangrijk punt.

Met de komst van GPU's die het rekenwerk op de driehoeken, texels, pixels, enzovoort doen, zijn we minder afhankelijk geworden van de CPU. Tegelijkertijd heeft de spelindustrie een gestage groei gekend: steeds meer mensen willen steeds meer games spelen, en dit heeft op zijn beurt geleid tot steeds meer teams die samen kwamen om ze te ontwikkelen.. 

De wet van Moore laat zien dat hardwaregroei exponentieel is, niet lineair met betrekking tot tijd: dit betekent dat om de paar jaar het aantal transistoren dat we op een enkel bord passen, niet constant verandert - het verdubbelt!

Grotere teams hadden betere samenwerking nodig. Al snel vereisten de game engines, met hun complexe niveau, AI, ruiming en renderlogica, dat de codeerders gedisciplineerder moesten zijn, en hun favoriete wapen was objectgeoriënteerd ontwerp.

Zoals Paul Graham ooit zei: 

Bij grote bedrijven wordt software meestal geschreven door grote (en vaak veranderende) teams van middelmatige programmeurs. Object-georiënteerd programmeren legt een discipline op aan deze programmeurs die voorkomen dat een van hen teveel schade aanricht.

Of we het nu leuk vinden of niet, dit moet tot op zekere hoogte waar zijn - grotere bedrijven begonnen grotere en betere games te implementeren, en naarmate de standaardisatie van tools opkwam, werden de hackers die aan games werkten onderdelen die gemakkelijker konden worden geruild. De deugd van een bepaalde hacker werd steeds minder belangrijk.

Problemen met objectgericht ontwerpen

Hoewel objectgericht ontwerpen een leuk concept is dat ontwikkelaars helpt bij grote projecten, zoals games, verschillende lagen van abstractie maken en iedereen aan hun doellaag werken, zonder zich zorgen te hoeven maken over de implementatiedetails van de onderliggende laag, is het gebonden aan geef ons sommige hoofdpijn.

We zien een explosie van parallelle programmeercodeerders die alle processorcores verzamelen die beschikbaar zijn om razendsnelle rekensnelheden te produceren, maar tegelijkertijd wordt game scenery steeds complexer en willen we die trend bijbenen en toch de frames blijven leveren - per seconde verwachten onze spelers, we moeten het ook doen. Door alle snelheid te gebruiken die we hebben, kunnen we deuren openen voor geheel nieuwe mogelijkheden: de CPU-tijd gebruiken om het aantal gegevens dat naar de GPU wordt verzonden helemaal te verminderen, bijvoorbeeld.

In objectgeoriënteerd programmeren, houd je status binnen een object, wat je vereist om concepten zoals synchronisatieprimitieven te introduceren als je er vanuit meerdere threads aan wilt werken. Je hebt één nieuw niveau van indirectie voor elke virtuele functie die je belt. En de geheugentoegangspatronen gegenereerd door code geschreven op een object-georiënteerde manier kan vreselijk zijn - Mike Acton (Insomniac Games, ex-Rockstar Games) heeft een geweldige reeks dia's die terloops een voorbeeld uitleggen. 

Op dezelfde manier zei Robert Harper, een professor aan de Carnegie Mellon University, het zo: 

Objectgeoriënteerd programmeren is [...] zowel antimodulair als antiparallel van aard en daardoor ongeschikt voor een modern CS-curriculum..

Over OOP praten zoals dit is lastig, omdat OOP een enorm scala aan eigenschappen omvat, en niet iedereen is het eens met wat OOP betekent. In die zin heb ik het meestal over OOP zoals geïmplementeerd door C ++, omdat dat momenteel de taal is die de wereld van de game-engine enorm domineert.

Dus we weten dat games parallel moeten worden omdat er is altijd meer werk dat de CPU kan doen (maar niet hoeft te doen), en uitgavencycli die wachten tot de GPU klaar is met verwerken, zijn gewoon verspilling. We weten ook dat gemeenschappelijke OO-ontwerpbenaderingen ons vereisen om dure lockcontentie te introduceren en tegelijkertijd cache-locaties kunnen schenden of onnodige vertakkingen kunnen veroorzaken (wat kostbaar kan zijn!) In de meest onverwachte omstandigheden.

Als we geen gebruik maken van meerdere kernen, blijven we dezelfde hoeveelheid CPU-bronnen gebruiken, zelfs als de hardware willekeurig beter wordt (meer kernen heeft). Tegelijkertijd kunnen we GPU tot het uiterste duwen, omdat het, door ontwerp, parallel is en in staat is om elke hoeveelheid werk gelijktijdig aan te nemen. Dit kan interfereren met onze missie om spelers de beste ervaring op hun hardware te bieden, omdat we deze duidelijk niet ten volle benutten.

Dit werpt de vraag op: moeten we onze paradigma's helemaal herzien?

Enter: Data-georiënteerd ontwerp

Sommige voorstanders van deze methodologie hebben riep het datageoriënteerde ontwerp, maar de waarheid is dat het algemene concept al veel langer bekend is. Het uitgangspunt is eenvoudig: bouw je code rond de datastructuren en beschrijf wat je wilt bereiken in termen van manipulaties van deze structuren

We hebben dit soort gesprekken eerder gehoord: Linus Torvalds, de maker van Linux en Git, zei in een Git-mailinglijst dat hij een groot voorstander is van "het ontwerpen van de code rond de gegevens, en niet andersom", en crediteert dit als een van de redenen voor het succes van Git. Hij gaat zelfs door met het argument dat het verschil tussen een goede programmeur en een slechte is of ze zich zorgen maakt over gegevensstructuren of de code zelf.

De taak lijkt in eerste instantie contra-intuïtief, omdat je van je mentale model ondersteboven moet worden. Maar denk er op deze manier aan: een game, tijdens het hardlopen, legt alle input van de gebruiker en alle krachtige stukken van de game vast (degene waar het zinvol zou zijn om de standaard te verlaten alles is een object filosofie) vertrouw niet op externe factoren, zoals netwerk of IPC. Voor zover je weet, gebruikt een game gebruikersgebeurtenissen (muis verplaatst, joystickknop ingedrukt, enzovoort) en de huidige spelstatus, en karnt deze naar een nieuwe set gegevens, bijvoorbeeld batches die naar de GPU worden verzonden. PCM-voorbeelden die naar de geluidskaart worden verzonden en een nieuwe spelstatus.

Deze 'data-karnen' kan worden opgedeeld in veel meer subprocessen. Een animatiesysteem neemt de volgende keyframe-gegevens en de huidige status en produceert een nieuwe status. Een deeltjessysteem neemt de huidige toestand (deeltjesposities, snelheden, enzovoort) en een tijdvoortzetting en produceert een nieuwe toestand. Een ruimingsalgoritme neemt een set kandidaat-renderables en produceert een kleinere set renderables. Bijna alles in een game-engine kan worden beschouwd als het manipuleren van een stuk data om een ​​ander stuk data te produceren.

Processors houden van localiteit van referentie en gebruik van cache. Dus, in data-georiënteerd ontwerp, hebben we de neiging om, waar mogelijk, alles in grote, homogene matrices te organiseren en, waar mogelijk, goede, cache-coherente brute-force-algoritmen uit te voeren in plaats van een potentieel liefhebber (die een betere Big O-kosten, maar slaagt er niet in om de architectuurbeperkingen van de hardware waaraan het werkt over te nemen). 

Wanneer dit per frame (of meerdere keren per frame) wordt uitgevoerd, levert dit potentieel enorme prestatiebeloningen op. Bijvoorbeeld, de mensen van Scalyr rapporteren het zoeken naar logbestanden met 20 GB / sec met behulp van een zorgvuldig gemaakte maar een naïef klinkende brute-force lineaire scan. 

Wanneer we objecten verwerken, moeten we ze beschouwen als "zwarte dozen" en hun methoden noemen, die op hun beurt toegang hebben tot de gegevens en ons krijgen wat we willen (of wijzigingen aanbrengen die we willen). Dit is geweldig om te werken voor onderhoudbaarheid, maar niet wetend hoe onze gegevens zijn opgemaakt, kan schadelijk zijn voor de prestaties.

Voorbeelden

Bij gegevensgericht ontwerpen denken we allemaal aan data, dus laten we iets doen dat ook iets anders is dan wat we gewoonlijk doen. Beschouw dit codefragment:

void MyEngine :: queueRenderables () for (auto it = mRenderables.begin (); it! = mRenderables.end (); ++ it) if ((* it) -> isVisible ()) queueRenderable (* it ); 

Hoewel veel vereenvoudigd, is dit algemene patroon wat vaak wordt gezien in object-georiënteerde game-engines. Maar wacht even - als veel renderables niet echt zichtbaar zijn, komen we veel vertakkingen tegen die ervoor zorgen dat de processor een aantal instructies weggooit die ze hadden uitgevoerd in de hoop dat een bepaalde tak werd overgenomen. 

Voor kleine scènes is dit duidelijk geen probleem. Maar hoe vaak doe je dit specifieke ding, niet alleen bij het in de wacht zetten van renderables, maar bij het doorlopen van scènelichten, schaduwkaartsplitsingen, zones en dergelijke? Wat dacht je van AI of animatie-updates? Vermenigvuldig alles wat u in de scène doet, bekijk hoeveel klokcycli u uitschakelt, bereken hoeveel tijd uw processor beschikbaar heeft om alle GPU-batches af te leveren voor een stabiel 120FPS-ritme, en u ziet dat deze dingen kan schaal aanzienlijk. 

Het zou grappig zijn als een hacker die aan een web-app werkt zelfs rekening hield met dergelijke minuscule micro-optimalisaties, maar we weten dat games real-time systemen zijn waar de beschikbare middelen ongelooflijk krap zijn, dus deze overweging is niet misplaatst voor ons.

Om dit te voorkomen, laten we er op een andere manier over nadenken: wat als we de lijst met zichtbare renderables in de engine zouden houden? Natuurlijk, we zouden de nette syntax van opofferen myRenerable-> hide () en nogal wat OOP-principes schenden, maar we kunnen dit dan doen:

void MyEngine :: queueRenderables () for (auto it = mVisibleRenderables.begin (); it! = mVisibleRenderables.end (); ++ it) queueRenderable (* it); 

Hoera! Geen verkeerde vertakkingen en aanname mVisibleRenderables is leuk std :: vector (wat een aaneengesloten array is), we hadden dit net zo goed als een fast kunnen herschrijven memcpy oproep (met een paar extra updates van onze gegevensstructuren, waarschijnlijk).

Nu kun je me uitschelden over de pure cheesiness van deze codevoorbeelden en je hebt helemaal gelijk: dit is vereenvoudigd veel. Maar om eerlijk te zijn, ik heb nog niet eens gekrast. Denken aan datastructuren en hun relaties opent ons voor een hele reeks mogelijkheden waar we nog niet eerder over hebben nagedacht. Laten we een aantal van hen als volgende bekijken.

Parallellisatie en vectorisatie

Als we eenvoudige, goed gedefinieerde functies hebben die op grote gegevensbrokjes werken als basisbouwstenen voor onze verwerking, is het gemakkelijk om vier of acht werkdraden te spawnen en elk van hen een stuk gegevens te geven om alle CPU's te behouden kernen bezig. Geen mutexes, atomic of lock contention, en als je de data eenmaal nodig hebt, hoef je alleen maar op alle threads mee te doen en te wachten tot ze zijn voltooid. Als u gegevens parallel moet sorteren (een zeer frequente taak bij het voorbereiden van dingen die naar de GPU moeten worden verzonden), moet u hier vanuit een ander perspectief over nadenken: deze dia's kunnen helpen.

Als een toegevoegde bonus, kunt u binnen een thread SIMD vector-instructies (zoals SSE / SSE2 / SSE3) gebruiken om een ​​extra snelheidsboost te behalen. Soms kunt u dit alleen bereiken door uw gegevens op een andere manier te leggen, zoals het plaatsen van vectorarrays op een structuur-van-arrays (SoA) -manier (zoals XXX ... YYY ... ZZZ ... ) in plaats van de conventionele array-of-structures (AoS; dat zou zo zijn XYZXYZXYZ ... ). Ik ben hier amper aan het krabben; je kunt meer informatie vinden in de Verder lezen sectie hieronder.

Wanneer onze algoritmen de gegevens rechtstreeks verwerken, wordt het triviaal om ze te parallelliseren, en we kunnen ook een aantal snelheidsnadelen voorkomen.

Eenheidstesten die u niet wist, was mogelijk

Door eenvoudige functies zonder externe effecten kunnen ze eenvoudig worden getest. Dit kan vooral goed zijn in een vorm van regressietesten voor algoritmen die u gemakkelijk in en uit wilt wisselen. 

U kunt bijvoorbeeld een testsuite bouwen voor het gedrag van een ruimingsalgoritme, een georkestreerde omgeving opzetten en precies meten hoe deze presteert. Wanneer u een nieuw ruimingsalgoritme bedenkt, voert u dezelfde test opnieuw uit zonder wijzigingen. U meet de prestaties en de correctheid, zodat u uw beoordeling binnen handbereik hebt. 

Naarmate u meer in de data-georiënteerde ontwerpbenaderingen komt, zult u het eenvoudiger en gemakkelijker vinden om aspecten van uw game-engine te testen.

Klassen en objecten combineren met monolithische gegevens

Datageoriënteerd ontwerp staat lijnrecht tegenover object-georiënteerd programmeren, slechts enkele van zijn ideeën. Als gevolg hiervan kun je heel netjes gebruiken ideeën van data-georiënteerd ontwerp en krijg nog steeds de meeste van de abstracties en mentale modellen die je gewend bent. 

Kijk bijvoorbeeld eens naar het werk aan OGRE versie 2.0: Matias Goldberg, het brein achter dat streven, koos ervoor om gegevens op te slaan in grote, homogene matrices en functies te hebben die hele reeksen herhalen in plaats van alleen aan een gegeven te werken. , om Ogre te versnellen. Volgens een benchmark (die hij toegeeft is zeer oneerlijk, maar het gemeten prestatievoordeel kan dat niet zijn enkel en alleen vanwege dat) werkt het nu drie keer sneller. Niet alleen dat - hij behield veel van de oude, vertrouwde klassenabstracties, dus de API was verre van volledig herschreven.

Is het praktisch?

Er zijn veel aanwijzingen dat game engines op deze manier kunnen en zullen worden ontwikkeld.

Het ontwikkelingsblog van Molecule Engine heeft een serie met de naam Avonturen in data-georiënteerd ontwerp,en bevat veel nuttig advies over waar DOD werd ingezet met fantastische resultaten.

DICE lijkt geïnteresseerd in data-georiënteerd ontwerp, omdat ze het hebben gebruikt in het ruimingsysteem van Frostbite Engine (en ook significante snelheden hebben gekregen!). Sommige andere dia's bevatten ook het gebruik van gegevensgeoriënteerd ontwerp in het AI-subsysteem dat het bekijken waard is.

Daarnaast lijken ontwikkelaars zoals de eerder genoemde Mike Acton het concept te omarmen. Er zijn een paar benchmarks die bewijzen dat het veel winst oplevert, maar ik heb in de loop van de tijd niet zoveel activiteit op het gebied van datagestuurde ontwerpen gezien. Het kan natuurlijk gewoon een modegril zijn, maar het hoofdgebouw lijkt heel logisch. Er is zeker veel inertie in dit bedrijf (en in enige andere softwareontwikkeling), dus dit kan een grootschalige toepassing van een dergelijke filosofie belemmeren. Of misschien is het niet zo'n geweldig idee als het lijkt te zijn. Wat denk je? Reacties zijn van harte welkom!

Verder lezen

  1. Data-georiënteerd ontwerp (of waarom u uzelf zou kunnen fotograferen met OOP)
  2. Introductie van Data Oriented Design [DICE] 
  3. Een nogal leuke discussie over Stack Overflow 
  4. Een online boek van Richard Fabian waarin veel van de concepten worden uitgelegd 
  5. Een benchmark die de andere kant van het verhaal laat zien, een schijnbaar contra-intuïtief resultaat 
  6. Mike Acton's beoordeling van OgreNode.cpp, die enkele veelvoorkomende OOP-valkuilen voor game-engines laat zien