Cosa è il Data-Oriented Design in un Game Engine

() translation by (you can also view the original English article)

Potreste aver sentito parlare del design di motori di gioco data-oriented, un concetto relativamente nuovo che propone una mentalità diversa dalla progettazione orientata agli oggetti più tradizionale. In questo articolo, vi spiego cosa è il DOD e perché alcuni sviluppatori di motori di gioco ritengono che potrebbe essere il biglietto da visita per uno spettacolare miglioramento delle prestazioni.

Un po 'di storia

Nei primi anni dello sviluppo dei giochi, i giochi e i loro motori erano scritti in linguaggi vecchio stile, come il C. Erano prodotti di nicchia, e spremere ogni ciclo di clock di hardware fino all'ultimo era, al momento, la massima priorità. Nella maggior parte dei casi, c'era solo un modesto numero di persone che maneggiavano il codice in un singolo titolo, e sapevano tutto il codice a memoria. Gli strumenti che usavano servivano bene allo scopo ed il C forniva notevoli vantaggi in termini di prestazioni per spingere al massimo le CPU, e questo era molto importante poiché questi giochi, lavorando con i frame buffer, erano comunque molto vincolati alle CPU stesse.

Con l'avvento delle GPU che hanno fatto esplodere il numero di triangoli, di texel, di pixel, e così via, siamo venuti a dipendere molto meno dalle CPU. Allo stesso tempo, l'industria del gioco ha visto una crescita costante: sempre più persone vogliono giocare a molti più giochi e questo a sua volta ha portato ad un maggior numero di team per svilupparli.

La Legge di Moore mostra che la crescita esponenziale dell'hardware non è lineare rispetto al tempo: ciò significa che ogni due anni, il numero di transistor possiamo stare su una singola scheda non cambia costantemente ma raddoppia!

Grandi team necessitano di una migliore cooperazione. In poco tempo, i motori di gioco, con il loro livello di complessità, AI, culling, e la logica di rendering hanno richiesto programmatori sempre più disciplinati, e la loro arma preferita è diventata la progettazione orientata agli oggetti.

Come ha detto una volta Paul Graham:

Nelle grandi aziende, il software tende ad essere scritto da grandi (e spesso mutevoli) squadre di programmatori mediocri. La programmazione orientata agli oggetti impone una disciplina per questi programmatori che impedisce a ciascuno di loro di fare troppi danni.

Che ci piaccia o no, questo è stata la realtà per alcune aziende di che hanno sviluppato e distribuito i giochi più grandi e migliori, e come è emersa la standardizzazione dei loro strumenti, gli smanettoni che programmavano giochi sono dovuti diventare parte di questo processo per non rischiare di essere tagliati fuori. La virtù di un particolare smanettone è diventata sempre meno importante.

I problemi con l'Object-Oriented design

La progettazione orientata agli oggetti è un bel concetto che aiuta gli sviluppatori di grandi progetti, come ad esempio i giochi, creando diversi livelli di astrazione e mantenendo tutti concentrati sul loro livello di destinazione, senza dover preoccuparsi dei dettagli di implementazione di quelli sottostanti, ma è comunque destinata a darci qualche mal di testa.

Vediamo una esplosione di sviluppatori di programmazione parallela che raccolgono tutti i core del processore disponibili per fornire calcoli a velocità fiammanti, ma, allo stesso tempo, lo scenario dei giochi diventa sempre più complesso, e se vogliamo stare al passo con i tempi fornendo i frame rate che i nostri giocatori si aspettano, dobbiamo farlo anche noi. Utilizzando tutte le velocità che abbiamo a portata di mano, siamo in grado di aprire le porte a nuove possibilità: sfruttando il tempo di CPU per ridurre il numero di dati inviati alla GPU, ad esempio.

Nella programmazione orientata agli oggetti, si mantiene lo stato all'interno di un oggetto, questo richiede l'introduzione di concetti come primitive di sincronizzazione se si desidera lavorarci con più thread. Si ha un nuovo livello di indirezione per ogni chiamata di funzione virtuale fatta. E i modelli di accesso alla memoria generati da un codice scritto in modo orientato agli oggetti possono essere terribili, anzi, Mike Acton (Insomniac Games, ex-Rockstar Games) ha una eccezionale serie di diapositive che casualmente lo spiegano con un esempio.

Similmente, Robert Harper, professore alla Carnegie Mellon University, si esprime così:

La programmazione orientata agli oggetti è [...] sia anti-modulare chee anti-parallela per sua natura, e quindi inadatta ad un moderno CS curriculum.

Parlare di OOP così è difficile, perché la OOP comprende un ampio spettro di proprietà, e non tutti sono d'accordo su cosa significhi OOP. In questo senso, parlo sopratutto di OOP come implementata e attuata dal C ++, perché questo è il linguaggio che domina di gran lunga il mondo dei motori di videogiochi.

Così, sappiamo che i giochi hanno bisogno sempre di un maggiore parallelismo perché c'è sempre più lavoro che la CPU può (ma non deve) fare, mentre aspetta che la GPU completi l'elaborazione. Sappiamo anche che gli approcci comuni di progettazione OO ci impongono di introdurre il costoso blocco di contesa, e, allo stesso tempo viola la località della cache o causa ramificazioni inutili (che possono essere costose!) nelle circostanze più impensate.

Se non approfittiamo del multi core, continuiamo con la stessa quantità di risorsa CPU, anche se l'hardware è decisamente migliore (ha più core). Allo stesso tempo, si può spingere la GPU al limite perché è, per come è disegnata, parallela, ed in grado di assumere qualsiasi quantità di lavoro contemporaneamente. Questo può interferire con la nostra missione di offrire ai giocatori la migliore esperienza sul loro hardware, visto che non stiamo ovviamente usando tutto il suo potenziale.

Ciò solleva la questione: dobbiamo ripensare del tutto i nostri paradigmi?

Entriamo: Design Data-Oriented

Alcuni fautori di questa metodologia l'hanno chiamata progettazione orientate ai dati, ma la verità è che il concetto generale è conosciuto già da molto tempo. La sua premessa di base è semplice: costruire il vostro codice intorno alle strutture di dati, e descrivere ciò che si vuole ottenere in termini di manipolazioni di queste strutture.

Abbiamo già sentito questo tipo di discorso prima: Linus Torvalds, il creatore di Linux e Git, ha detto in una mailing list di Git che lui è un grande sostenitore della "progettazione del codice intorno ai dati, non il contrario", e ha accreditato a questo le ragioni del successo di Git. Egli continua anche a sostenere che la differenza tra un buon programmatore ed uno cattivo è se si preoccupa delle strutture di dati o del codice stesso.

Il compito può sembrare controintuitivo in un primo momento, perché richiede di trasformare il vostro modello mentale rovesciandolo. Ma pensatelo in questo modo: un gioco, durante l'esecuzione, cattura tutto l'input dell'utente e tutti le componenti di performance pesante che lo riguardano (quelle in cui avrebbe senso scavare nella filosofia del tutto è un oggetto) non si basano su fattori esterni, come la rete o IPC. Per tutto quello che sapete, un gioco consuma eventi utente (mouse spostato, tasto del joystick premuto, e così via) e lo stato corrente del gioco, e sforna questi dati su un nuovo set di dati, per esempio elaborazioni batch inviate alla GPU, campionature PCM inviate alla scheda audio e un nuovo stato del gioco.

Questo "sfornare dati" può essere suddiviso in molti sotto-processi. Un sistema di animazione prende i dati del prossimo fotogramma chiave e lo stato attuale e produce un nuovo stato. Un sistema particellare prende il suo stato attuale (posizione delle particelle, velocità, e così via), un tempo di avanzamento e produce un nuovo stato. Un algoritmo di culling (abbattimento) prende un set di oggetti candidati al rendering e produce un insieme ridotto di questi oggetti. Quasi tutto in un motore di gioco può essere pensato come la manipolazione di un blocco di dati per la produzione di un altro pezzo di dati.

I processori amano la località dei riferimento e l'utilizzo di cache. Così, nel design data-oriented, tendiamo a, per quanto possibile, organizzare tutto in grande, matrici omogenee, e, anche laddove possibile, eseguire bene, algoritmi di forza bruta con la cache al posto di uno potenzialmente più elaborato (che ha un migliore costo O Big, ma che non riesce ad abbracciare le limitazioni architetturali dell'hardware su cui gira.

Quando eseguite per ogni fotogramma (o più volte per frame), questo dà potenzialmente enormi premi di performance. Ad esempio, i ragazzi del Scalyr riportano una ricerca i file di log a 20 GB/sec con una scansione lineare accurata e artigianale ma dal sapore ingenuo e brutale.

Quando trattiamo oggetti, dobbiamo pensare a loro come a "scatole nere" e chiamare i loro metodi, che a sua volta accederanno ai dati per farci quello che vogliamo (o apportare le modifiche che vogliamo). Questo è ottimo per lavorare con la manutenibilità, ma no quando sappiamo come i nostri dati sono disposti in modo dannoso per le prestazioni.

Esempi

La progettazione data-oriented ci fa pensare tutto con i dati, quindi cerchiamo di fare qualcosa anche un po' di diverso da quello che facciamo di solito. Considerate questo pezzo di codice:

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

Sebbene semplificato molto, questo schema comune è ciò che viene spesso visto nei motori di gioco orientati agli oggetti. Ma aspettate, se un sacco di renderizzabili non sono in realtà visibili, ci imbattiamo in un sacco di previsioni sbagliate che causano la cancellazione da parte del processore di alcune istruzioni che aveva eseguito nella speranza che un ramo dell'esecuzione fosse preso.

Per le piccole scene, questo ovviamente non è un problema. Ma quante volte si fa a fare questa cosa particolare, non solo quando siamo in coda sui renderizzabili, ma anche nell'iterazione attraverso le luci di scena, nella divisione delle mappe di ombre, delle zone, o simili? Che ne dite degli aggiornamenti AI o di animazione? Moltiplicate tutto quello che fate per tutta la scena, guardate quanti cicli di clock espellete, calcolate quanto tempo il vostro processore ha a disposizione per fornire tutte le informazioni alla GPU per un ritmo 120FPS costante, e si vedrete che queste cose possono scalare ad una notevole quantità.

Sarebbe divertente se, per esempio, per uno che lavora su una web app di poco conto con micro-ottimizzazioni ridicole, ma sappiamo che i giochi sono sistemi in tempo reale in cui i vincoli di risorse sono incredibilmente stretti, quindi questa considerazione non è fuori luogo per noi.

Per evitare che ciò accada, pensiamo a esso in un altro modo: e se avessimo mantenuto l'elenco dei renderizzabili visibili nel motore? Certo, sacrificheremmo la sintassi ordinata di myRenerable->hide() e violeremmo un bel paio di principi OOP, ma potremmo fare questo:

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

Evviva! Nessun ramo di previsioni sbagliate e assumendo che mVisibleRenderables è un bel std::vector (che è un array contiguo), avremmo potuto riscriverlo come un memcpy veloce (con alcuni aggiornamenti in più per le nostre strutture dati, probabilmente).

Ora questo codice semplifica molto .. Ma ad essere onesti, non ho nemmeno ancora scalfito la superficie. Pensando alle strutture dati e alle loro relazioni ci si apre a tutta una serie di possibilità a cui non abbiamo pensato prima. Diamo un'occhiata ad alcuni di loro dopo.

Parallelizzazione e Vettorizzazione

Se abbiamo semplici funzioni, ben definite che operano su grandi blocchi di dati come blocchi di costruzione di base per la nostra trasformazione, è facile generare quattro, o otto, o 16 thread di lavoro e dare a ciascuno di loro un pezzo dei dati per mantenere tutte le CPU core occupate. No mutex, o blocchi di contesa, e una volta che avete bisogno di dati, vi basta agganciarvi a tutti i threads e aspettare che finiscano. Se avete bisogno di ordinare i dati in parallelo (un compito molto frequente quando si prepara roba da inviare alla GPU), dovete pensarlo da una diversa prospettiva e queste diapositive potrebbero aiutare.

Come bonus aggiuntivo, all'interno di un thread è possibile utilizzare le istruzioni vettoriali SIMD (come SSE/SSE2/SSE3) per ottenere un aumento di velocità aggiuntiva. A volte, è possibile eseguire questa operazione ponendo solo i dati in modo diverso, come l'immissione di un vettore array in una struttura-di-array nel modo (SoA) (come XXX...YYY...ZZZ...) piuttosto che il tradizionale Array-di-strutture (AoS, che sarebbe XYZXYZXYZ...). Sto malapena scalfendo la superficie; è possibile trovare ulteriori informazioni nella sezione Ulteriori Letture sotto.

Quando i nostri algoritmi hanno a che fare con i dati direttamente, diventa banale per loro parallelizzare, ed è possibile anche evitare alcuni inconvenienti di velocità.

Unit Testing che non sapevate essere possibili

Avere funzioni semplici, senza effetti esterni le rende facili da testare. Questo può essere particolarmente buono nella forma di test di regressione per quegli algoritmi che vorreste scambiare facilmente.

Ad esempio, è possibile costruire una suite di test per il comportamento di un algoritmo di culling, impostare un ambiente orchestrato, e misurare esattamente come si svolge. Quando si escogita un nuovo algoritmo di culling, si esegue nuovamente lo stesso test senza modifiche. Misurate le prestazioni e correttezza, in modo da poter avere la valutazione a portata di mano.

Man mano che si entra sempre più nel design data-oriented, troverete sempre più facile testare gli aspetti del vostro motore di gioco.

Combinare Classi e oggetti con Dati Monolitici

Il design Data-oriented non è affatto contrario alla programmazione orientata agli oggetti ma solo ad alcune dei suoi concetti. Di conseguenza, è possibile riuscire ad usare i concetti della progettazione data-oriented e continuare ad ottenere la maggior parte delle astrazioni e modelli mentali a cui siete abituati.

Date un'occhiata, per esempio, al lavoro su OGRE versione 2.0: Matias Goldberg, la mente dietro questo sforzo, ha scelto di memorizzare i dati in grandi matrici omogenee e di avere funzioni che eseguono iterazioni su matrici intere invece di lavorare solo su un dato, tutto col fine di accelerare Ogre. Secondo un benchmark (che lui ammette essere molto ingiusto, ma che non può essere la sola causa del vantaggio prestazionale misurato) ora funziona tre volte più veloce. Non solo, ha mantenuto un sacco del vecchio, come la familiare astrazione delle classi, per cui l'API non ha richiesto una completa riscrittura.

E' pratico?

Ci sono un sacco di prove per cui i motori di gioco saranno sviluppati in questo modo.

Il blog di sviluppo del Molecule Engine ha una serie chiamata Avventure in Design Data-Oriented, e contiene un sacco di consigli utili su dove il DOD è stato utilizzato con ottimi risultati.

DICE sembra essere interessato al design data-oriented, visto che lo hanno impiegato nel sistema di culling del Frostbite Engine (ed hanno anche ottenuto significativi incrementi di velocità!). Da loro si trovano anche altre diapositive sull'utilizzo del design data-oriented nel sottosistema della IA.

Oltre a questo, gli sviluppatori come il suddetto Mike Acton sembrano abbracciare il concetto. Ci sono un paio di punti di riferimento che dimostrano che fa guadagnare un sacco in termini di prestazioni, ma non ho visto molta attività sul fronte del design data-oriented da un po' di tempo. Potrebbe trattarsi, ovviamente, solo di una moda, ma le premesse principali sembrano avere molta logica. C'è sicuramente un sacco di inerzia in questo business (e qualsiasi altra attività di sviluppo software, in questo caso) quindi questo potrebbe ostacolare l'adozione su larga scala di tale filosofia. O forse non è una grande idea, come invece sembra essere. Cosa ne pensate? I commenti sono benvenuti!