Por qué fastDOOM es tan rápido

• En una IBM PS/1 486-DX2 de 66 MHz, que en 1993 era una PC de gama alta, el DOOM original lograba 21.5 fps en demo1, mientras que fastDOOM subía hasta 30.1 fps en las mismas condiciones, mostrando la diferencia que puede hacer la optimización de un port para DOS
• fastDOOM nació a partir de PCDOOM v2, que combinaba el núcleo de Linux DOOM, el I/O de Heretic, APODMX y un I/O gráfico en Mode Y basado en el desensamblado inverso de DOOM.EXE
• Tras compilar y medir 52 releases y 3,042 commits, quedó claro que la mejora de rendimiento no vino de un compilador moderno por sí solo, sino de la acumulación de pequeñas optimizaciones
• Entre las mejoras más grandes están omitir el renderizado de la barra de estado, hacer inline de FixedDiv, optimizar el recorrido del BSP, omitir renderizado de visplanes, eliminar indirecciones de punteros y separar ejecutables por renderer
• El modo gráfico más conveniente depende de la CPU y del bus: en CPUs lentos conviene Mode Y, mientras que en CPUs más rápidas y entornos VLB/PCI pueden rendir mejor Mode 13h o VESA direct, aunque siguen existiendo limitaciones como VESA 2.0

---

La diferencia de rendimiento que se ve en una 486-DX2

• En una IBM PS/1 486-DX2 66 MHz “Mini-Tower” modelo 2168, al ejecutar el DOOM original con doom.exe -timedemo demo1, el resultado es 1710 gametics in 2783 realtics
  • DOOM no muestra los fps directamente, así que hay que calcular 1710/2783*35, lo que da como resultado 21.5 fps
• En la misma máquina, al ejecutar fdoom.exe -timedemo demo1, se obtiene 1710 gametics in 1988 realtics, es decir, 30.1 fps
• En mapas más pesados, como demo1 de doom2, sube de 16.8 fps en el original a 24.9 fps en fastDOOM, lo que lo hace 48% más rápido
• Eso sí, se eliminó el soporte para joystick y network gameplay, así que no es un port que conserve todas las funciones intactas

El linaje del código del que salió fastDOOM

• DOOM se desarrolló originalmente en una NeXT Workstation y estaba dividido en la mayor parte del código central y un pequeño subsistema de I/O, con una estructura fácil de portar
• La versión comercial para DOS usaba I/O para DOS escrito por id Software, pero no pudo liberarse tal cual como open source en 1997 por su dependencia de DMX, una biblioteca de sonido propietaria
• El código que se publicó fue la versión para Linux, organizada por Bernd Kreimeier mientras trabajaba en un proyecto de libro para explicar el motor
• La versión DOS PCDOOM v2 se reconstruyó con la siguiente combinación
  • el núcleo de Linux DOOM
  • el I/O de Heretic
  • APODMX para imitar a DMX
  • i_ibm.c, el I/O gráfico reconstruido por ingeniería inversa a partir del desensamblado de DOOM.EXE
• fastDOOM tomó como punto de partida este PCDOOM v2

Seguimiento del cambio de rendimiento por releases y commits

• Victor “Viti95” Nieto publicaba fastDOOM con frecuencia, etiquetaba cada release y administraba los commits para que cada uno hiciera una sola cosa
• El historial Git de fastDOOM está compuesto por 3,042 commits, lo que permitió rastrear el cambio de rendimiento commit por commit
• Se descargaron 52 releases de fastDOOM, PCDOOM v2 y el DOOM.EXE original, y se generó con un programa en Go un RUN.BAT para ejecutar -timedemo demo1, montándolo con mTCP NETDRIVE para las pruebas
  • Las condiciones fueron DOOM.WAD, sound on y screen size 10
  • Se ejecutó toda la suite 5 veces y se graficó el promedio de fps
• Aunque PCDOOM v2 fue compilado con OpenWatcom 2, la mejora frente al DOOM.EXE original no fue tan grande, así que el avance de fastDOOM es difícil de explicar solo por usar un compilador moderno
• El gráfico del tamaño de archivos muestra que el trabajo inicial fue orientado a aligerar el código mediante limpieza y eliminación
  • bf0e983: eliminación de sound recording
  • 5f38323: eliminación de cadenas de error code
  • 8b9cac5: reemplazo de TASM por NASM

Cambios por release que elevaron el rendimiento

• Hacer timedemo a los 3,042 builds completos podía tomar unos 9 días, así que el benchmark a nivel commit se centró en v0.1, v0.6, v0.8, v0.9.2 y v0.9.7, donde los aumentos de velocidad fueron mayores

• fastDOOM v0.1

  • v0.1 está compuesto por 220 commits
  • El parche más importante es e16bab8 del build 36
    • La “Crispy optimization” convierte en no-op el renderizado cuando el porcentaje de la barra de estado no cambió, evitando el renderizado del scrap buffer y el blit a pantalla
    • Ese único cambio elevó el rendimiento en 2 fps
  • a9359d5 del build 167 hace inline de FixedDiv como macro
  • 9bd3f20 del build 207 toma optimizaciones de PSX Doom para mejorar el recorrido del BSP
  • dc0f48e del build 212 hace inline de la función de renderizado de superficies horizontales R_MakeSpans
  • De todos los commits, 100 fueron commits de eliminación, o sea, cerca de la mitad fue borrado de código

• fastDOOM v0.6

  • v0.6 está compuesto por 33 commits
  • 22819fd del build 342 omite renderizados innecesarios de visplane
  • 40e0d4b del build 359 y ccd296f del build 360 reducen la indirección del player pointer
  • f29e665 del build 369 hace inline del screenspace line splitter

• fastDOOM v0.8

  • v0.8 está compuesto por 282 commits
  • Como el sistema de sonido era inestable, el timedemo se hizo sin sonido y luego se corrigieron los fps
  • Este release estaba enfocado en el text-mode renderer, y hubo regresiones en los builds 670 y 730 al perder la Crispy optimization
  • Las mejoras principales fueron
    • f279b7d: separación de ejecutables por renderer como FDOOM.EXE y FDOOM13H.EXE
    • 1874ee8: desactivación de debugging del compilador
    • 6aae724: restauración de la Crispy optimization
    • 1366ebf: compilar menos código cuando es posible

• fastDOOM v0.9.2 y v0.9.7

  • v0.9.2 tiene 110 commits, y sus cambios principales fueron la optimización de la comparación de skyflatnum, la optimización de R_DrawColumn para Mode Y y la limpieza del código de R_DrawSpan
  • v0.9.7 fue presentado como un release de 293 commits, pero la salida del comando muestra 294
  • En este release, ni siquiera múltiples rondas de benchmark lograron reducir el ruido
  • Los cambios principales incluyen pruebas de cambios en x86 ASM, selección de CPU para 386SX y optimización de CR2, optimización de ESP para R_DrawSpan386SX, código basado en renderizado ASM fuzz column y eliminación de comparaciones CMP por iteración de loop

Cuándo elegir Mode 13h, Mode Y o VESA direct

• fastDOOM explora múltiples optimizaciones para distintas combinaciones de CPU y buses de video, incluyendo 386, 486, Pentium, Cyrix e ISA, VLB y PCI
• En la IBM PS/1 486-DX2 de 66 MHz, una optimización que usaba Mode 13h en vez de Mode Y resultó más lenta

• Mode 13h

  • El hardware se encarga de distribuir los datos entre los cuatro bancos de VRAM de VGA, así que para la CPU se ve como un framebuffer lineal único de 320x200
  • Como no se puede hacer double buffering en la VRAM, hay que usar buffering en RAM y luego copiar otra vez a VRAM, así que se escriben los bytes dos veces
  • El motor debe bloquearse en VSYNC

• Mode Y

  • Permite acceder a cada banco VGA por separado, así que se puede hacer triple buffering en VRAM y escribir cada byte directamente en VRAM una sola vez
  • La selección de banco requiere la instrucción lenta OUT
  • Es posible replicar píxeles horizontales escribiendo a dos bancos VGA a la vez mediante latch, lo que permite un modo low-detail
  • El renderizado del Specter invisible requiere leer de vuelta desde VRAM, por lo que es mucho más lento
  • Según la explicación de John Carmack, DOOM usaba un modo planar entrelazado similar a Mode X en el modo VGA de 320×200×256, y rotaba entre tres display pages
  • Hacer texture mapping directo sobre video memory podía dar entre 10% y 15% más velocidad en muchas tarjetas de video
  • También permitía page flip sin tearing, a diferencia del buffering en memoria principal
  • Heretic salió en 1994 y, con los cambios de hardware de ese momento, Mode 13h se volvió una opción más atractiva, así que Raven modificó el motor de DOOM en esa dirección
  • fastDOOM ofrece varios ejecutables al usuario
  • FDOOM.EXE
  • FDOOM13H.EXE
  • FDOOMVBD.EXE

• El Mode 13h y VESA direct de fastDOOM

  • El Mode 13h de fastDOOM renderiza primero sobre un framebuffer lineal en RAM y, cuando termina toda la escena, lo copia a VRAM
  • Como no fuerza VSYNC, puede haber flickering
  • En buses ISA lentos de 8 bits se usa copia diferencial para transferir solo los píxeles modificados
  • En buses más rápidos, como ISA de 16 bits, VLB o PCI, se copia todo el backbuffer con REP MOVS
  • Según las pruebas de Viti95, el mejor modo para CPUs 486 es el VESA direct mode de 320×200, es decir, FDOOMVBD.EXE
    • Combina las ventajas de Mode Y con el código de renderizado optimizado de Heretic
    • Evita la instrucción OUT salvo una vez por frame al cambiar de buffer
    • Requiere una tarjeta gráfica VLB o PCI con LFB habilitado y soporte para VESA 2.0, y es más lento en modos low-detail y potato-detail
  • La IBM 2168 no soporta VESA 2.0, así que al ejecutar FDOOMVBP.EXE y FDOOMVBD aparece un error

Intentos que no funcionaron y la impresión general

• También se probaron los flags por procesador de OpenWatcom, 4r/4s y 3r/3s, pero terminaron siendo descartados
  • Se probaron tanto los flags para 386 como para 486 de wcc386, y al final la versión para 386 siempre parecía ser más rápida
• Viti95 también tiene como objetivo cambiar el compilador de fastDOOM de OpenWatcom v2 a DJGPP, es decir, GCC
  • Porque en el mismo código fuente, GCC parece generar código más rápido
  • O bien sería deseable que OpenWatcom v2 mejorara para cerrar esa brecha de rendimiento
• El rendimiento de fastDOOM es resultado de aprovechar mejoras previas de Crispy, PSX, GBA y Lee Killough, y de sumar una gran cantidad de optimizaciones nuevas
• Algunas ideas y parte del código de Ken Silverman también llegaron a funciones de renderizado para CPUs UMC Green, logrando grandes mejoras de velocidad en ese hardware
• fastDOOM es un caso donde no hubo un cambio mágico único, sino miles de pequeñas optimizaciones acumuladas que lo convirtieron en un port para DOS más rápido que el DOOM original

[GN⁺]

Opiniones en Hacker News

• Es un buen ejemplo de que los cuellos de botella casi nunca están donde uno espera, así que hacen falta profiling y mediciones.
  ¿El renderizado del porcentaje en la barra de estado? Para alguien experto que conoce bien la arquitectura de Doom quizá era relativamente obvio, pero antes de medir jamás habría imaginado que fuera el cuello de botella.

  • Por ejemplo, hubo un caso en el que una app estaba usando sin explicación 60% de CPU y 25% de GPU, y resultó ser por una pequeña animación CSS.
    https://www.granola.ai/blog/dont-animate-height
  • También recuerda a un caso de optimización en Super Mario World para SNES, donde mostrar la puntuación del jugador era muy ineficiente y consumía alrededor de 1/6 del tiempo de frame.
    En el peor caso, mostrar el puntaje en la barra de estado consumía casi 1/6 de todo el frame, bajando el umbral a partir del cual se notaba la lentitud; el parche cambió la forma de guardar y mostrar el puntaje para que fuera casi de tiempo constante, haciéndolo incluso un poco más rápido que el mejor caso anterior.
    https://www.smwcentral.net/?p=section&a=details&id=35746
  • Desde el punto de vista de un desarrollador de juegos, este tipo de ralentizaciones son comunes.
    El renderizado de la UI puede ser crítico por la transparencia, las capas, el redibujado y, sobre todo, por provocar asignaciones de memoria; comparar el valor anterior con el nuevo antes de redibujar ayuda muchísimo.
    También hubo un proyecto en CSS donde las capas y la transparencia eran el cuello de botella, y en ese caso lo clave fue reducir la cantidad de capas.
  • Mi ejemplo favorito es el problema de los tiempos de carga de GTA Online, que al final se debía a un manejo incorrecto de un archivo JSON de 10 MB, y lo rastreó alguien externo a la organización.
    Redujo una carga de 6 minutos a menos de 2 minutos.
    https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times...
  • Me recuerda al incidente en el que npm era 2 veces más lento de lo normal por culpa de una vistosa barra de progreso en la terminal.
    https://news.ycombinator.com/item?id=10974929

• Quizá no sea el público objetivo real, pero NETDRIVE de mTCP me pareció interesante.
  No sabía que incluso en una época tan antigua hubiera opciones útiles de almacenamiento en red, y al buscar encontré https://www.brutman.com/mTCP/mTCP_NetDrive.html, que está buenísimo.
  Según dicen, NetDrive es un controlador de dispositivo que permite acceder desde DOS a una imagen de disco remota alojada en otra máquina como si fuera un dispositivo local montado con una letra de unidad.

  • A principios de los 90, en el laboratorio de computación de la escuela había unas 25 Mac Plus conectadas en cadena por AppleTalk a una Mac II, y todas las Plus montaban el sistema de archivos desde la Mac II.
    Era lentísimo, así que los estudiantes perdían entre 5 y 10 minutos al comienzo de la clase esperando a que abriera el procesador de textos; las Xerox Alto también usaban montajes de red para sus unidades.
    Si hay red, tarde o temprano alguien va a querer copiar archivos, y la forma más cómoda es hacer que parezca un sistema de archivos local.
    DOS no tenía redes integradas, así que en ese aspecto estaba atrasado y había mucho que hacer a mano.
  • Hay un truco limpio para arrancar DOS por red desde un destino iSCSI con iPXE.
    Permite acceso de lectura y escritura a un dispositivo de bloques en red sin controladores ni configuración del lado de DOS, aunque si se usa como si fuera un recurso compartido se rompe rápido; se parece más a un dispositivo de bloques.
    Se siente como magia, pero parece que iPXE parchea el BIOS para enviar los accesos a disco vía iSCSI.
  • Me pregunto si en la época de DOS existían NAS o montajes WebDAV.
    FTP y telnet obviamente existían, pero me da curiosidad si los montajes remotos se usaban en la práctica o si eran inviables por el bajo ancho de banda.

• El hilo de GitHub en el que participa Ken Silverman es un tesoro.
  Es sorprendente ver al autor de FastDOOM y a Ken profundizar en la eficiencia de registros de 486 y ciclos de reloj tan esotéricos.
  Da gusto que todavía haya gente ocupándose de que Doom reciba mejoras de rendimiento.

  • Hacía muchísimo que no pensaba en KenS; en los 90 estuvo muy activo en la escena de modding de Duke3D.
    Ese scripting fue literalmente mi primera “programación” y, en cierto sentido, le debo a KenS toda mi carrera y mi patrimonio, lo cual es genial.
  • El año pasado, mientras hacía un motor de renderizado 2.5D parecido, le mandé un email a Ken Silverman sobre una parte poco conocida del Build Engine, y me respondió como si hubiera estado trabajando en eso ayer.
  • Ahí hay verdaderas joyas.
    En particular, me gustó la idea de usar CR2 y CR3 como registros scratchpad en el 386SX, donde el acceso a memoria es muy lento, y en el 386DX sin caché.
    La técnica de usar ESP como contador de bucle sin desactivar interrupciones también es genial: garantiza que siempre apunte a una ubicación válida de la pila.

• Una función de FastDOOM que no se trató mucho aquí son todos esos modos de video raros
  Modo texto IBM MDA: https://www.youtube.com/watch?v=Op2tr2lGK6Y
  EGA y Plantronics ColorPlus: https://www.youtube.com/watch?v=gxx6lJvrITk
  CGA clásico azul y rosa: https://youtu.be/rD0UteHi2qM
  CGA 320x200x16 usando el hack “ANSI from Hell”: https://www.youtube.com/watch?v=ut0V1nGcTf8
  Hercules: https://www.youtube.com/watch?v=EEumutuyBBo
  La mayoría parece correr más lento que VGA por cosas como el remapeo de colores

  • Me gustaría que también soportara Tandy Graphics Adapter
    No me gustaría tener que correrlo en CGA y, si todavía la tuviera, probablemente necesitaría una build 286 para mi Tandy 1000 TL/2
  • Es realmente genial y muestra muy bien por qué estos aspectos de un juego deberían estar separados
    Me recuerda a la Clean Architecture “moderna” de las aplicaciones backend
  • El modo texto IBM MDA es horrible... por eso está bueno

• Me llamó la atención la parte de “IBM PS/1 486-DX2 66Mhz, ‘Mini-Tower’, modelo 2168. La computadora que siempre quise de adolescente pero no podía pagar”
  Para 1992 más o menos estaba usando mi cuarta PC armada por mí, y las ferias de computación de KCS en Marlborough, MA, eran un recurso enorme para los que nos gustaba cacharrear
  Compraba piezas, armaba una PC, la usaba un tiempo, la vendía y volvía a comprar piezas
  A fines de 1992 estaba corriendo una 486-DX3 100 con un coprocesador matemático ULSI 487, y durante un tiempo fue la PC más rápida del campus, quizá la computadora más rápida
  Era más rápida que varios modelos Pentium y no tenía errores matemáticos
  Justifiqué la última build para mi tesis de honores, porque estaba simulando una planta de cogeneración a gas/diésel en una hoja de Excel de 21 páginas y los tiempos de recálculo eran demasiado largos
  Mi carrera fue Ciencias Ambientales, pero toda mi trayectoria profesional terminó siendo en computación

  • No sé si esto es para decir “wow”
    ¿Hacía falta ponérselo difícil a alguien que no pudo comprar una computadora así en 1992?
    Además, no existió un “DX3”, y el DX4, el primer 486 de 100 MHz, salió en marzo de 1994, así que eso de haberlo tenido corriendo a fines de 1992 no parece correcto
    La primera computadora de mi casa, sin contar una XT que nos dieron alrededor de 1992 y que ya estaba demasiado vieja, fue una 486-DX2 de 66MHz comprada a principios de 1995
    Incluso décadas después, me hiere un poco el orgullo ver a alguien presumir de una computadora imposible que era más rápida que la mía pese a tener una ventaja de tres años
  • Sin duda trae recuerdos
    Por 1992 era un estudiante universitario pobre y pedí un préstamo de unos 2,000 dólares en la cooperativa de crédito para comprar una 486 DX2-50
    En dinero de hoy, fue como gastar más de 4,000 dólares en una computadora bastante básica, y en esa máquina tenía arranque dual con DOS y Linux
  • ¿Un 487 en una 486DX? Pensé que el 487 solo servía con chips SX
    Buscando, parece que el 487 estándar en realidad era un 486DX completo que desactivaba y reemplazaba al 486SX
    ¿Habrá sido otro coprocesador increíble que yo no conocía?
  • “Más rápida que varios modelos Pentium y sin errores matemáticos” sí que es motivo para presumir
    Les ganó por goleada

• Además de lanzar versiones con frecuencia, Viti95 mostró una excelente disciplina con Git: un commit hace una sola cosa y cada release estaba etiquetada
  https://fabiensanglard.net/fastdoom/#:~:text=one%20commit%20...

• No entiendo qué significa Ibuprofen en “hasta conocer fastDOOM, me había resignado a tener que jugar tomando Ibuprofen”

  • Supongo que se refiere al dolor de cabeza por la baja tasa de cuadros

• Si el autor lo ve, en todo el documento el apellido de John Carmack está mal escrito como “Carnmack”

• Una forma no cínica de explicar por qué el software moderno es lento y no recibe este tipo de optimizaciones es la hipótesis de estandarización/optimización
  Cuando algo se vuelve estándar, le siguen las optimizaciones
  Porque quieres ser el más rápido sin dejar de pasar todas las pruebas del estándar
  Doom ya se volvió un juego estándar para portar a cualquier cosa, sea una CPU nueva o una tostadora, y pasa algo parecido con protocolos de email o estándares de navegador como WebRTC, QUIC, etc.
  Las apps web modernas o las apps Electron no son rápidas porque están en una etapa de exploración
  Se actualizan todos los días para nuevas necesidades de los usuarios y, en rendimiento, basta con que sean lo suficientemente rápidas como para no estorbar
  Por eso las apps de IRC son muy rápidas, pero Slack y Teams inevitablemente siempre serán lentas

• No es trivial volver a versiones anteriores y revisar mejoras y regresiones
  Algunas optimizaciones pueden introducir bugs que se descubren después, y una función necesaria también puede empeorar el rendimiento
  Por eso, tener pruebas de rendimiento que se ejecuten automáticamente antes de cada release hace la vida más fácil; si se detecta un problema de rendimiento, escribes una prueba de regresión como de costumbre
  Lo que quiero decir, en definitiva, es que hay que hacer pruebas de rendimiento