Hell will freeze

Hace un tiempo, después de atiborrarme de libros sobre .NET, me plantee el objetivo de escribir alguna aplicación más o menos seria que pusiese la plataforma a prueba. Dio la casualidad que hacía poco había descubierto POV Ray, y lo estaba usando para generar imágenes para los cursos a distancia. En uno de esos momentos de curiosidad (¿cómo habrán hecho X?) descargué el código fuente, lo imprimí... y me encontré con un proyecto escrito en PaleoC, impermeable a las ideas de la Programación Orientada a Objetos y, para serle sincero, mayormente inmantenible (los responsables del proyecto, por supuesto, no compartirán mi opinión).

¿UN AS EN LA MANGA?

Si ha visitado esta página en el último año, ya imaginará que estoy contando los orígenes de XSight RT. Pero lo que quiero contarle ahora es un detalle al que le he dado poca publicidad: comencé a desarrollar XSight RT pensando que tenía un as muy particular en la manga. Un as que nunca llegué a usar.

De entrada, había pensado que la plataforma .NET sería, efectivamente, demasiado ineficiente para que un algoritmo de ray tracing funcionase... de no mediar ideas nuevas en su diseño. La idea radical, este caso, consistía en generar un programa ejecutable para cada escena. Un ray tracer "normal" construye una escena en memoria mediante la típica composición de objetos. En una escena con una esfera, dos cubos y una fuente de luz, se inicializa un árbol con objetos que representan a la esfera, los dos cubos y la fuente de luz. Luego, esta escena se "interpreta". Hay un algoritmo genérico, por ejemplo, que recorre la escena suministrando un rayo como parámetro, para descubrir las intersecciones del rayo. Supongamos, por simplicidad, que la lista de objetos es lineal. Podemos entonces comparar, a cierto nivel abstracto, dos "programas" como los siguientes:

Ray tracer	IL
sphere x0, 1 box x1, x2 diff scale 0.8 trans d0 ...	ldarg.0 ldfld Origin ldarg.0 ldfld Center sub ...

No estoy inventando la sopa de ajo. Aunque no soy partidario de obsesionarse con identificar "patrones", a este tipo de situación, la "pandilla de los cuatro" la llamaría patrón de intérprete (¡detesto la clasificación del libro original, entre otras razones, por imprecisa!). Y siempre que hay un intérprete por medio, salta la idea de compilar de alguna forma el programa subyacente. Esa era mi "estupenda" idea.

Por fortuna, no fue necesario llegar a tanto. La implementación básica resultó ser lo suficientemente rápida como para no exasperar al usuario medio. Luego fui añadiendo mejoras en varios frentes:

En primer lugar, en los algoritmos propios del ray tracing y los cálculos de intersecciones.

Ejemplo: para calcular las intersecciones entre un toro (la rosquilla) y un rayo, hay que resolver una ecuación de cuarto grado. Si recuerda algo de Algebra, sabrá que para resolver una ecuación de cuarto grado usando el método de Vieta, o el método original de Ferrari, hay que resolver primero una ecuación ligeramente más simple, de tercer grado. El truco está, sin embargo, en que la ecuación de tercer grado tiene una forma muy particular, que hace innecesarias varias comprobaciones exigidas por el caso general. Además, una ecuación de tercer grado puede tener una o tres soluciones, y esto complica el prototipo del método necesario para el caso general... sin contar con la necesidad de hallar las tres raíces. En cambio, si lo que queremos es resolver una ecuación de cuarto grado, ¡sólo necesitamos la primera solución!

Otra área en la que si pegas una patada sale petróleo, es en la manipulación algebraica de escenas.

Esto es interesante. La imagen adyacente es el logo que estoy usando para la sección Píldoras Orientadas a Objetos y, como era de esperar, esos cilindros chatos a los que les falta un trozo se supone que son pastillas. Pero las pastillas son, en realidad, fruto de la diferencia entre un cilindro chato y un cubo estirado. Luego, para que dé la impresión de que han caído en montón por azar, cada pastilla ha sido movida y girada de manera diferente a las demás. La rotación de una diferencia es la diferencia entre las rotaciones; suena a chino, pero es "álgebra". Y cuando se rota un cilindro sobre su propio eje de simetría, la rotación se anula, igual que cuando multiplicamos cualquier cosa por la unidad. De manera, que casi nos podemos quitar de encima la mitad de las rotaciones, excepto una: la de la pastilla vertical. Pero esa pastilla, en particular, acumulaba dos rotaciones en la descripción inicial de la escena. ¿Puede decirme usted qué ocurre cuando se rota un objeto 45 grados alrededor del eje X y luego 90 respecto al eje Y? A lo mejor la respuesta es sencilla, pero no me la sé. En la escena usé dos rotaciones consecutivas... que fueron unificadas en una durante la simplificación.

Por último, está el plano sobre el que reposan las pastillas. Como ocupa una zona "infinita", si lo ubicamos en la posición incorrecta, puede entrometerse en cada rayo que lancemos sobre la escena. Pero el simplificador de escenas se encarga de mover el plano a una posición dentro del árbol de evaluación donde no estorbe demasiado. ¿El resultado final? Cuando conecté el simplificador, el tiempo de evaluación de la escena se redujo a un 40% del tiempo de evaluación original.

UN AS EN LA MANGA

¿Por qué le cuento ahora toda esta historia? Al llegar a esta parte del proyecto, he vuelto a acordarme de mi idea "genial", y he estado pensando en cómo podría utilizarse, si es que se puede, en un ray tracer. La solución me ha parecido interesante, aunque no vaya a aplicarla en este proyecto.

Resulta que la programación orientada a objetos, si no se tiene cuidado, puede ser muy ineficiente. Incluso cuando hay cuidado, sigue habiendo ineficiencia. Hay dos problemas claros:

El énfasis en la modularidad y la reusabilidad conduce a la redundancia, porque cada módulo debe intentar funcionar en el mayor número de contextos posibles. Ese esfuerzo no sólo se pierde cuando luego el módulo se utiliza en un contexto determinado, sino que puede afectar a la propia velocidad de ejecución.

Parece de mal gusto mencionar este problema en determinados círculos profesionales. Hace poco planteaba un problema de eficiencia en cierto grupo de usuarios, y me topé con un sabihondo que cuestionaba mi necesidad de algoritmos eficientes. Me dio la respuesta típica de la gente que programa algoritmos que luego sólo ellos usan: "¿estás dispuesto a perder dos meses en optimizaciones para sacar dos segundos de ventaja en cada ejecución?". Le repliqué advirtiéndole que mi aplicación era un compilador, y que un usuario como él mismo, podría ejecutarlo unas quinientas veces al día. Con un ray tracer, el contraste es aún más notable, y merece la pena cada milisegundo arrancado al tiempo de procesamiento. Piense en una película de dibujos animados generados por ordenador. ¿Cuántos cuadros puede llegar a tener? ¿Y si ahorramos un segundo al generar cada uno de ellos?

De todos modos, poco se puede hacer para resolver este problema... de momento. Las clases y componentes con los que actualmente programamos se comportan como piezas de la ingeniería mecánica; más exactamente, como las más primitivas de ellas: tuercas, tornillos, en el mejor de los casos, como engranajes. Son piezas delicadas: si equivocamos el contexto, podemos destrozarlas, y destrozar de paso el sistema. Son piezas rígidas, además: una tuerca siempre será una tuerca. Si encaja en su sitio, su funcionamiento nunca mejorará. En todo caso, la erosión y la oxidación degradarán imperceptiblemente su funcionamiento con el paso del tiempo.

El tipo de piezas que imagino tiene que ver más con la bioingeniería. Cuando sufrimos una factura, los extremos rotos del hueso, al entrar en contacto, se sueldan. Los componentes que necesito examinan el entorno en que están siendo usados, y se adaptan automáticamente al contexto. Puede incluso que dos componentes se fundan en uno solo, si así fuese necesario. Sólo necesitamos dotar a nuestros componentes de la inteligencia de una ameba. ¿Son inteligentes las amebas? Un poco más que nuestros mejores componentes, en estos momentos.

Con el segundo problema sí tenemos varias soluciones a nuestro alcance. En realidad, se trata de un problema muy particular de la programación orientada a objetos:

El mecanismo de llamada a métodos virtuales se lleva muy mal con las arquitecturas actuales de microprocesadores.

Ya se trate de un Pentium, un Athlon o un Opteron, las CPUs modernas dependen mucho de la memoria caché. La presencia de un salto del puntero de instrucciones (IP) exige que la máquina aplique un complejo algoritmo de predicción para mantener llena la caché de instrucciones. Este truco funciona cuando se trata de saltos inducidos por instrucciones if, while, e incluso con llamadas a métodos no virtuales. Pero cuando se trata de una llamada a un método virtual, es casi imposible que la CPU pueda adivinar dónde irá a parar el registro IP. Una llamada a método virtual utiliza el equivalente a la vieja instrucción calli (call indirect) del antiguo ensamblador del 8086.

Y en este punto, regresamos al ejemplo del ray tracer. Se lo explicaré mostrando un método virtual de la clase que se ocupa de las rotaciones en XSight RT (versión simplificada y adaptada):

protected virtual bool ShadowTest(Ray ray)
{
    ray = new Ray(inverse * ray.Origin, inverse * ray.Direction);
    return original.ShadowTest(ray);
}

Siempre hay que rotar otra figura, a la que nuestra rotación apunta con su campo original. Para saber si un rayo tropieza con la figura rotada, primero se rota el rayo, y luego se comprueba si este rayo transformado (en sentido inverso, por cierto) tropezaría con la figura original. ¿Cuál es la figura original? Puede tratarse de una esfera, de un cubo, o de otra rotación. No lo sabemos. Por eso he subrayado la llamada final, para indicar que se trata de una llamada a un método virtual. Una llamada poco eficiente.

Sin embargo, para la escena de las pastillas, queda muy claro que la rotación va a estar apuntando a una diferencia. Y las diferencias, en vez de apuntar a objetos de clases arbitrarias, van a apuntar a un cilindro y un paralelepípedo alargado. ¿Qué necesidad tenemos de llamadas a métodos virtuales aquí? La búsqueda de la mayor generalidad posible durante el diseño, la pagamos caro en el momento de la ejecución.

Podríamos resolverlo mediante fuerza bruta. Podríamos crear clases especiales para diferencias entre cubos y cubos, diferencias entre esferas y cubos, entre esferas y esferas... y así hasta el infinito. Tendríamos que usar una fuerza muy bruta, porque el número de clases necesarias crecería explosivamente, al menos si intentásemos prever todos los casos posibles.

Mi idea es otra:

Para ejecutar una escena dada, generaríamos al vuelo las clases necesarias, utilizando plantillas apropiadas. Estas clases no incurrirían en el despilfarro ocasionado por llamadas a métodos virtuales, porque siempre sabrían de qué tipo exacto es cada objeto ubicado al otro lado de una referencia polimórfica.
Determinadas figuras están actualmente programadas para que acepten una lista de tamaño variable de figuras dependientes. Este es el caso de las uniones e intersecciones. Pero, ¿para qué trabajar con listas si sabemos de antemano cuántas figuras tendremos en cada caso? En vez de usar bucles para recorrer las listas, desenrollaríamos los bucles.
Si hay que girar y luego escalar un cubo, ¿para qué necesitamos tres clases distintas y tres llamadas a métodos? ¿Por qué ese miedo cerval a hacer desaparecer clases que no necesitamos? Podríamos fundir varias clases en una cuando fuese necesario.

¿Merece la pena tanto esfuerzo? Incluso con un ray tracer programado en modo nativo y altamente optimizado, hay escenas complejas que pueden tardar horas y puede que días en generarse. En cambio, el compilador de Freya puede generar toda una aplicación en menos de un segundo, y la mayor parte del tiempo la consume leyendo el contenido de los ensamblados de referencia, porque la generación de código, hablando con propiedad, es veloz como Hacienda para despojarte de tu dinero (lo del rayo está muy gastado).

Podemos caminar sobre el mar si primero lo congelamos. Podemos entrar y salir sin quemarnos del Infierno si primero lo helamos. ¿Merece la pena? Depende de si tenemos algún asunto pendiente en el Infierno o de que nos maree navegar.