¿Qué es el Diseño de Motor de Juego Orientado a los Datos?

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

Es posible que haya oído hablar del diseño de motores de juegos orientados a datos, un concepto relativamente nuevo que propone una mentalidad diferente al diseño orientado a objetos más tradicional. En este artículo, explicaré de qué se trata el DOD, y por qué algunos desarrolladores de motores de juegos creen que podría ser el boleto para ganancias de rendimiento espectaculares.

Un poco de historia

En los primeros años del desarrollo del juego, los juegos y sus motores estaban escritos en lenguajes de la vieja escuela, como C. Eran un producto de nicho, y exprimir hasta el último ciclo de hardware lento era, en ese momento, la máxima prioridad. En la mayoría de los casos, solo había un número modesto de personas pirateando el código de un solo título, y conocían la base de código completa de memoria. Las herramientas que estaban usando les habían estado prestando un buen servicio, y C proporcionaba los beneficios de rendimiento que les permitían sacar el máximo provecho de la CPU, y como estos juegos todavía estaban vinculados por la CPU, atrayendo a sus propios búferes de cuadros, este fue un punto muy importante.

Con el advenimiento de las GPU que hacen el trabajo de cálculo de números en triángulos, téxeles, píxeles, etc., hemos llegado a depender menos de la CPU. Al mismo tiempo, la industria del juego ha experimentado un crecimiento constante: cada vez más personas quieren jugar más y más juegos, y esto a su vez ha llevado a que más y más equipos se unan para desarrollarlos.

La ley de Moore muestra que el crecimiento del hardware es exponencial, no lineal con respecto al tiempo: esto significa que cada dos años, el número de transistores que podemos caber en una sola placa no cambia en una cantidad constante, ¡se duplica!

Los equipos más grandes necesitaban una mejor cooperación. En poco tiempo, los motores del juego, con su nivel complejo, Inteligencia Artificial, sacrificio y lógica de representación requirieron que los codificadores fueran más disciplinados, y su arma de elección fue el diseño orientado a objetos.

Como dijo Paul Graham una vez:

En las grandes compañías, el software tiende a estar escrito por grandes (y frecuentemente cambiantes) equipos de programadores mediocres. La programación orientada a objetos impone una disciplina a estos programadores que evita que cualquiera de ellos haga demasiado daño.

Nos guste o no, esto tiene que ser cierto hasta cierto punto: las compañías más grandes comenzaron a implementar juegos más grandes y mejores, y cuando surgió la estandarización de las herramientas, los piratas informáticos que trabajaban en juegos se convirtieron en partes que podían intercambiarse más fácilmente. La virtud de un hacker particular se volvió cada vez menos importante.

Problemas con el diseño orientado a objetos

Si bien el diseño orientado a objetos es un concepto agradable que ayuda a los desarrolladores de grandes proyectos, como los juegos, a crear capas de abstracción y hacer que todos trabajen en su capa objetivo, sin tener que preocuparse por los detalles de implementación de los que están debajo, está obligado a danos algunos dolores de cabeza

Vemos una explosión de codificadores de programación paralelos que recogen todos los núcleos de procesador disponibles para ofrecer velocidades de cómputo ardientes, pero al mismo tiempo, el escenario del juego se vuelve cada vez más complejo, y si queremos mantenernos al día con esa tendencia y aún entregar los fps que nuestros jugadores esperan, tenemos que hacerlo también. Al usar toda la velocidad que tenemos a mano, podemos abrir puertas para posibilidades completamente nuevas: usar el tiempo de la CPU para reducir por completo el número de datos enviados a la GPU, por ejemplo.

En la programación orientada a objetos, mantiene el estado dentro de un objeto, lo que requiere que introduzca conceptos como primitivas de sincronización si desea trabajar desde múltiples subprocesos. Tiene un nuevo nivel de indirección para cada llamada de función virtual que realice. Y los patrones de acceso a la memoria generados por el código escrito de una manera orientada a objetos pueden ser terribles, de hecho, Mike Acton (Insomniac Games, ex-Rockstar Games) tiene un gran conjunto de diapositivas que explican casualmente un ejemplo.

Del mismo modo, Robert Harper, profesor de la Universidad Carnegie Mellon, lo expresó de esta manera:

La programación orientada a objetos es [...] antimodal y antiparalela por su propia naturaleza, y por lo tanto no apta para un currículo moderno de CS.

Hablar de OOP como este es complicado, porque OOP abarca un amplio espectro de propiedades, y no todos están de acuerdo con lo que significa OOP. En este sentido, estoy hablando principalmente de OOP tal como lo implementó C ++, porque ese es actualmente el idioma que domina enormemente el mundo de los motores de juego.

Entonces, sabemos que los juegos deben ser paralelos porque siempre hay más trabajo que la CPU puede hacer (pero no tiene que hacer), y pasar ciclos esperando que la GPU termine de procesar es simplemente un desperdicio. También sabemos que los enfoques de diseño de OO comunes nos obligan a introducir una costosa contención de bloqueo y, al mismo tiempo, pueden violar la localidad de caché o provocar una bifurcación innecesaria (¡lo que puede ser costoso!) En las circunstancias más inesperadas.

Si no aprovechamos los núcleos múltiples, seguimos usando la misma cantidad de recursos de CPU, incluso si el hardware mejora arbitrariamente (tiene más núcleos). Al mismo tiempo, podemos llevar la GPU a su límite porque, por diseño, es paralela y puede asumir cualquier cantidad de trabajo simultáneamente. Esto puede interferir con nuestra misión de proporcionar a los jugadores la mejor experiencia en su hardware, ya que claramente no lo estamos utilizando con todo su potencial.

Esto plantea la pregunta: ¿deberíamos repensar nuestros paradigmas por completo?

Ingrese: Diseño orientado a datos

Algunos defensores de esta metodología lo han llamado diseño orientado a datos, pero la verdad es que el concepto general se conoce desde hace mucho más tiempo. Su premisa básica es simple: construya su código alrededor de las estructuras de datos, y describa lo que quiere lograr en términos de manipulaciones de estas estructuras.

Hemos escuchado este tipo de charla antes: Linus Torvalds, el creador de Linux y Git, dijo en una publicación de la lista de correo Git que es un gran defensor de "diseñar el código alrededor de los datos, no al revés", y acredita esto como una de las razones del éxito de Git. Continúa afirmando que la diferencia entre un buen programador y uno malo es si ella se preocupa por las estructuras de datos o el código en sí.

La tarea puede parecer contradictoria al principio, porque requiere que inviertas tu modelo mental. Pero piénselo de esta manera: un juego, mientras se ejecuta, captura toda la información del usuario, y todas las partes de rendimiento pesado (aquellas en las que tendría sentido abandonar el estándar, la filosofía todo es un objeto) no confíe en el exterior factores, tales como la red o IPC. Por lo que usted sabe, un juego consume eventos del usuario (mouse movido, botón del joystick presionado, etc.) y el estado actual del juego, y los convierte en un nuevo conjunto de datos, por ejemplo, lotes que se envían a la GPU. Muestras de PCM que se envían a la tarjeta de audio y un nuevo estado del juego.

Este "batido de datos" se puede dividir en muchos más subprocesos. Un sistema de animación toma los siguientes datos de fotogramas clave y el estado actual y produce un nuevo estado. Un sistema de partículas toma su estado actual (posiciones de partículas, velocidades, etc.) y un avance en el tiempo y produce un nuevo estado. Un algoritmo de eliminación requiere un conjunto de candidatos generados y produce un conjunto más pequeño generados. Se puede pensar que casi todo en un motor de juego manipula una porción de datos para producir otra porción de datos.

Los procesadores adoran la localidad de referencia y la utilización de la memoria caché. Entonces, en el diseño orientado a datos, tendemos, siempre que sea posible, a organizar todo en grandes y homogéneas matrices, y también, siempre que sea posible, ejecutar buenos algoritmos de fuerza bruta coherentes en caché en lugar de uno potencialmente más lujoso (que tiene una mejora el costo de Big O, pero no abarca las limitaciones de arquitectura del hardware en el que funciona).

Cuando se realiza por fotograma (o varias veces por fotograma), esto ofrece enormes recompensas de rendimiento. Por ejemplo, la gente de Scalyr informa que busca archivos de registro a 20 GB / seg usando una exploración lineal de fuerza bruta cuidadosamente elaborada pero ingenua.

Cuando procesamos objetos, tenemos que pensar en ellos como "recuadros negros" y llamar a sus métodos, que a su vez acceden a los datos y nos dan lo que queremos (o hacen los cambios que deseamos). Esto es ideal para trabajar para la mantenibilidad, pero no saber cómo se presentan nuestros datos puede ser perjudicial para el rendimiento.

Ejemplos

El diseño orientado a los datos nos hace pensar en los datos, así que hagamos algo también un poco diferente de lo que solemos hacer. Considera este pedazo de código:

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

Aunque simplificado mucho, este patrón común es lo que se ve a menudo en los motores de juegos orientados a objetos. Pero espere, si muchos de los renderizados no son realmente visibles, nos topamos con una gran cantidad de errores en las ramificaciones que hacen que el procesador descargue algunas instrucciones que había ejecutado con la esperanza de que se tomara una rama en particular.

Para escenas pequeñas, esto obviamente no es un problema. Pero, ¿cuántas veces haces esto en particular, no solo cuando haces rendables, sino cuando iteramos a través de luces de escena, divisiones del mapa de sombras, zonas, o cosas por el estilo? ¿Qué hay de las actualizaciones de IA o animación? Multiplique todo lo que hace a lo largo de la escena, vea cuántos ciclos de reloj expulsa, calcule cuánto tiempo tiene disponible su procesador para entregar todos los lotes de GPU para un ritmo constante de 120 FPS, y verá que estas cosas pueden escalar a una cantidad considerable.

Sería gracioso si, por ejemplo, un hacker que trabaja en una aplicación web incluso considerase microemociones tan minúsculas, pero sabemos que los juegos son sistemas en tiempo real donde las restricciones de recursos son increíblemente ajustadas, por lo que esta consideración no debe extraviarse.

Para evitar que esto suceda, pensemos en ello de otra manera: ¿y si mantuviéramos la lista de rendables visibles en el motor? Claro, sacrificaríamos la sintaxis ordenada de myRenerable->hide() y violaríamos algunos principios de OOP, pero podríamos hacer esto:

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

¡Hurra! No hay errores en las derivaciones, y suponiendo que mVisibleRenderables es un buen std::vector (que es una matriz contigua), podríamos haber reescrito esto como una llamada memcpy rápida (con algunas actualizaciones adicionales a nuestras estructuras de datos, probablemente).

Ahora, puedes llamarme por la crudeza de estas muestras de código y estarás en lo cierto: esto se simplifica mucho. Pero para ser sincero, ni siquiera he arañado la superficie todavía. Pensar en las estructuras de datos y sus relaciones nos abre a un montón de posibilidades en las que no habíamos pensado antes. Veamos algunos de ellos a continuación.

Paralelización y Vectorización

Si tenemos funciones simples y bien definidas que operan en grandes fragmentos de datos como bloques de construcción base para nuestro procesamiento, es fácil generar cuatro, u ocho o 16 subprocesos de trabajo y darles a cada uno de ellos una información para mantener toda la CPU núcleos ocupados. No hay mutexes, atomics o contención de bloqueo, y una vez que necesita los datos, solo necesita unirse a todos los hilos y esperar a que finalicen. Si necesita ordenar datos en paralelo (una tarea muy frecuente al preparar cosas para enviar a la GPU), debe pensar en esto desde una perspectiva diferente: estas diapositivas podrían ser útiles.

Como una ventaja adicional, dentro de un hilo puedes usar instrucciones vectoriales SIMD (como SSE / SSE2 / SSE3) para lograr un aumento de velocidad adicional. A veces, puede lograr esto colocando los datos de una manera diferente, como colocar matrices de vectores en una estructura de arreglos (SoA) (como XXX ... YYY ... ZZZ ...) en lugar de arreglo-de-estructuras convencionales (AoS; eso sería XYZXYZXYZ ...). Apenas estoy arañando la superficie aquí; puede encontrar más información en la sección de Lectura Adicional a continuación.

Cuando nuestros algoritmos manejan los datos directamente, resulta trivial paralizarlos, y también podemos evitar algunos inconvenientes de velocidad.

Pruebas unitarias que no sabías que era posible

Tener funciones simples sin efectos externos hace que sea fácil realizar una prueba unitaria. Esto puede ser especialmente útil en una prueba de regresión para algoritmos que le gustaría intercambiar fácilmente.

Por ejemplo, puede crear un conjunto de pruebas para el comportamiento de un algoritmo de eliminación selectiva, configurar un entorno orquestado y medir exactamente cómo funciona. Cuando diseña un nuevo algoritmo de eliminación selectiva, ejecuta la misma prueba nuevamente sin cambios. Mide el rendimiento y la corrección, por lo que puede tener la evaluación al alcance de la mano.

A medida que aumente la cantidad de enfoques de diseño orientados a datos, le resultará cada vez más fácil probar aspectos de su motor de juego.

Combinar clases y objetos con datos monolíticos

El diseño orientado a datos no se opone a la programación orientada a objetos, solo algunas de sus ideas. Como resultado, puede usar las ideas del diseño orientado a los datos y obtener la mayoría de las abstracciones y modelos mentales a los que está acostumbrado.

Eche un vistazo, por ejemplo, en el trabajo en la versión 2.0 de OGRE: Matias Goldberg, el cerebro detrás de ese esfuerzo, eligió almacenar datos en matrices grandes y homogéneas, y tiene funciones que iteran en arreglos completos en lugar de trabajar en un solo dato , para acelerar Ogre. Según un punto de referencia (que admite que es muy injusto, pero la ventaja de rendimiento medida no puede deberse solo a eso) ahora funciona tres veces más rápido. No solo eso, conservaba muchas de las abstracciones de clase antiguas y familiares, por lo que el API estaba lejos de ser una reescritura completa.

¿Es práctico?

Existe una gran cantidad de evidencia de que los motores de juego de esta manera pueden y serán desarrollados.

El blog de desarrollo de Molecule Engine tiene una serie llamada Adventures in Data-Oriented Design, y contiene muchos consejos útiles sobre dónde se usó DOD con grandes resultados.

DICE parece estar interesado en el diseño orientado a los datos, ya que lo han empleado en el sistema de eliminación selectiva de Frostbite Engine (¡y también ha obtenido importantes aceleraciones!). Algunas otras diapositivas de ellos también incluyen el uso de diseño orientado a datos en el subsistema AI, que vale la pena mirar también.

Además de eso, los desarrolladores como el antes mencionado Mike Acton parecen estar adoptando el concepto. Hay algunos puntos de referencia que demuestran que gana mucho en rendimiento, pero no he visto mucha actividad en el diseño orientado a datos en bastante tiempo. Podría, por supuesto, ser solo una moda pasajera, pero sus premisas principales parecen muy lógicas. Seguramente hay mucha inercia en este negocio (y en cualquier otro negocio de desarrollo de software, para el caso) por lo que esto puede estar impidiendo la adopción a gran escala de dicha filosofía. O tal vez no es una gran idea como parece ser. ¿Qué piensas? ¡Los comentarios son bienvenidos!