inmensia

Sigo analizando el rendimiento de js-openctm y tratando de ver donde puedo recortar un poco de tiempo de proceso. Después de realizar las optimizaciones obvias para reducir la cantidad y complejidad del código que se ejecuta dentro de los bucles más largos, he llegado al punto en que no encuentro forma de ganar una forma substancial de ciclos de reloj sólo y exclusivamente a base de realizar cambios en el código. Y es que definitivamente: ¡necesito un JavaScript ninja en mi vida!

El verdadero caballo de batalla es sin duda el proceso de descompresión, pero eso es harina de otro costal. En lo que me estoy centrado es en las funciones que tardan más, y más concretamente en la que se encarga de restaurar las normales. Si está leyendo este blog he de suponer que sabe lo que es una normal, pero por si las dudas, una imagen vale más que mil palabras. O al menos eso dicen.

En la primera imagen puede verse un render del dragón de Standford que he hecho dibujando las normales en cada vértice. Las normales son vectores que salen perpendiculares a la superficie, por lo que parece como si al modelo le hubiese salido pelo. En la segunda imagen he puesto una ampliación de la cola, que parece un cactus.

El problema con las normales en OpenCTM es que resulta muy costoso restaurarlas, hay que hacer un montón de raíces cuadradas para calcular longitudes y normalizar vectores, y la función Math.sqrt es una total y absoluta "JavaScript perfomance killer". Sobre todo para modelos con millones de polígonos.

Además, analizando más en detalle el proceso. Resulta que hay algunas operaciones un poco discutibles. Por ejemplo, para restaurar las normales que vienen dentro de un fichero, el primer paso que se realiza es: ¡calcular las normales!. A ver si me explico. En el fichero vienen unas normales, pero no son las definitivas, sino que están almacenadas de forma relativa a las normales "nominales" del modelo. Así que para restaurarlas, primero hay que calcular esas normales "nominales". Siendo la normal "nominal" de un vértice la suma de todas las normales de las caras que comparten dicho vértice. Es decir, ¡las normales tal y como se han calculado toda la vida!.

La pregunta del millón es: si de todas formas se tienen que calcular las normales, ¿para qué queremos las del fichero? Pues la única explicación es que las normales que vengan en un fichero no tienen porque ser las mismas que las calculadas de la forma habitual. Para verificar este punto he tenido que ir depurando paso a paso un fichero concreto de ejemplo (en formato MG2, que no tiene porque almacenar con una precisión 1:1) y viendo los valores que obtenía por un procedimiento y otro. Y efectivamente, se obtienen valores distintos.

Por lo que a mi respecta, para mis propósitos concretos, no tiene sentido almacenar las normales en los ficheros. Sólo sirve para aumentar el tamaño de los ficheros y el tiempo necesario para descomprimirlos y procesarlos. Es mucho más rápido calcular las normales en el cliente. Además, el proceso que utiliza OpenCTM no es del todo eficiente. En un primer bucle calcula las normales que comparten un mismo vértice. Y en un segundo bucle las normaliza dividiéndolas por su longitud (raíz cuadrada al canto). El problema es que en el primer bucle también normaliza (otra raíz cuadrada al canto), cuando esto no es estricta y necesariamente necesario hacerlo. Y para rematar la faena, el proceso de restauración posterior implica realizar una nueva raíz cuadrada para cada normal.

Analizando lo que hace el proceso de restauración he conseguido reordenar el código para hacerlo más eficiente, detectando algunos casos especiales que he podido aislar en su propio flujo de ejecución de forma independiente. Un 30% de reducción de tiempo de proceso en general, que no está nada mal. No obstante, el cuello de botella sigue siendo el cálculo de las normales "nominales", que además no puedo modificar, ya que si lo hago se producen desviaciones con respecto a los valores que obtiene el SDK.

Así que al final, lo dicho: "No guardar las normales en el fichero, es mejor calcularlas online".

Buscando alguna forma de mejorar el rendimiento de js-lzma se me ha ocurrido probar con un "minificador". Originalmente estos programas se utilizaban para ofuscar el código, pero a medida que las librerías escritas en JavaScript fueron creciendo se empezó a apreciar el trabajo que hacían reduciendo el tamaño final de los ficheros que los clientes tenían que descargarse desde el servidor. Hoy en día además tienen el valor añadido de que son capaces de evaluar el código y generar una nueva versión más óptima "en algunos casos".

He probado con el Closure Compiler, pero más allá de la reducción del código, y una ligera optimización debido a la reducción del nombre de los literales, no he visto ninguna gran mejoría en el apartado de rendimiento. Es más, confrontando el código original contra el minificado tan poco he visto cambios significativos. Eliminación de paréntesis innecesarios, alguna sentencia cambiada para aprovechar características particulares de JavaScript, y poco más. Tampoco esperaba milagros, ni aun siendo hoy Viernes Santo.

El tamaño del código se reduce hasta prácticamente un 50%, lo que está bastante bien. Así que en líneas generales se puede decir que el minificador hace realmente bien su trabajo. No obstante, antes de utilizar este tipo de herramientas es conveniente leerse la documentación. El principal problema es que a veces eliminan más código de la cuenta o no son capaces de compilar el código original por algún tipo de dependencia.

Por ejemplo, las interfaces públicas pueden llegar a desaparecer si no tenemos cuidado, ya que el minificador cambia el nombre a todos los objetos. En mi caso concreto, la librería se expone a través de una variable "LZMA", y para conseguir que se conserve ese nombre he tenido que añadirlo de forma explícita con la siguiente declaración:

El minificador no cambia nunca el nombre de las propiedades a las que se accede por su nombre, por lo que el resultado final de la minificación es algo parecido a lo siguiente:

Siendo "g" (o cualquier otro) el nombre minificado de LZMA.

Otro punto a tener en cuenta son las interfaces de los objetos que no están declaradas dentro del propio código que se está minificando. Por ejemplo, en la librería se están utilizando objetos de tipo "stream" de los que se esperan que tengan implementados los métodos "readByte" y "writeByte". Eso no puede saberlo el minificador, por lo que genera un error al intentar compilar el código. Una solución sencilla es volver a cambiar el código de forma parecida al caso anterior.

Este código:

Hay que cambiarlo por este otro:

De forma que en el código minificado se respeta el nombre de los métodos originales:

Resumiendo, útil para las liberaciones finales, pero hay que manejarlo con tiento.

WebGL tiene una limitación en la función DrawElements por la que sólo se pueden utilizar buffers de 8 o 16 bits para los índices. Lo que implica que es necesario cortar las mallas con muchos vértices para poder representarlas. Ya tenía noticias de esta limitación, pero la verdad es que hasta ahora no me había importado demasiado. Me ha empezado a dar problemas en unas pruebas que estoy haciendo con js-openctm y ficheros con mallas muy densas.

Estoy haciendo pruebas con mallas de más de 1 millón de triángulos, y el problema es que cuando los índices superan el límite de 65.535 ya no se representan correctamente. La solución obvia es dividir la lista de índices en varias sublistas, ajustar los valores de las sublistas al rango 0-65.535, y realizar una llamada a DrawElements para cada sublista en vez de una sola con la lista original.

En la primera imagen de las tres que acompañan este post se puede ver el famoso "Happy Buda" de Standford, con 1.087.716 triángulos para ser exactos, tal cual lo estoy renderizando con WebGL en el navegador, y justo a su lado el mismo modelo, pero con un color distinto aplicado a cada una de las submallas que he tenido que generar para poder representarlo.

Cambiar la lista de índices originales no me parece algo trivial, ya que puede implicar tener que reorganizar los vértices, normales, y todos los demás atributos de la malla, con el consiguiente gasto de tiempo y reserva de memoria intermedia. E incluso en el peor de los casos puede que sea necesario duplicar vértices, ya que pueden darse situaciones en las que un triángulo tenga un vértice al principio de la lista y otro al final, y duplicar sea la solución más efectiva.

Mirando algunas implementaciones por ahí, he visto que algunos optan por cortar a saco, sin mucho miramiento, sin tener en cuenta los casos especiales y, para mi sorpresa, ¡les funciona!. El truco está en aprovechar la "coherencia" espacial de los modelos, en la distribución que normalmente tienen los triángulos dentro de la malla.

En la segunda imagen, con el Buda de perfil, se aprecia claramente porque no hay ningún problema en cortar la lista sin prestar atención a nada más para este modelo en particular. Todas las submallas contienen triángulos que están conectados unos con otros dentro de regiones muy claramente acotadas del espacio. En este caso, como los cortes de un sandwich helado.

Con los modelos propios, o con los que se puede suponer como estará organizada la malla, se pueden tomar este tipo de decisiones tan drásticas. Pero si se intenta hacer un visor genérico entonces si que sería conveniente buscar la forma correcta de hacer las subdivisiones.

Un hombre sabio dijo una vez que "los algoritmos son para la gente que no sabe comprar módulos de memoria", y yo no tengo palabras para explicar cuanta verdad encuentro en ello. Bueno, vale, la verdad es que eso de hacer algoritmos se me da muy mal y esa frase me sirve de consuelo. Incluso en esta era de Internet en la que se puede encontrar todo tipo de papers y código, me cuesta elaborar un algoritmo que me deje satisfecho. Y lo que es peor, que deje "satisfecho" al problema.

Al final, he decidido seguir la corriente y olvidarme de los casos difíciles y cortar la malla con un sencillo procedimiento que no consume apenas tiempo y evita tener que reservar memoria adicional ni mover cosas de un lado a otro. Básicamente lo que hago es recorrer secuencialmente la lista de índices buscando un mínimo y un máximo, cuando la diferencia entre esos dos valores es mayor que 65.535 entonces guardo la posición en la que empecé a buscar, el número de elementos que llevo recorridos, el mínimo encontrado, y vuelvo a empezar la búsqueda desde el punto en que me encuentro repitiendo este sencillo proceso hasta haber recorrido toda la lista.

Al final lo que obtengo como salida del proceso anterior es un array con tres valores para cada una de las submallas. A saber, la posición del primer índice de la submalla, el número de índices de la submalla, y el valor a restar a cada índice de la submalla para dejarlos en el rango 0-65.535. El valor a restar evidentemente es ese valor mínimo encontrado en cada iteración para cada submalla.

De esta manera se puede seguir realizando una única llamada a createBuffer para crear cada uno de los tipos de buffers (índices, vértices, normales, ...), como hasta ahora. Y lo que cambia es que se debe realizar una llamada a bindBuffer/vertexAttribPointer/drawElements para cada submalla, indicando en vertexAttribPointer un offset que apunte a ese valor mínimo encontrado para cada submalla.

En la tercera imagen se puede ver un modelo con 1.448.269 triángulos, sin textura, sólo colores por vértice, creado por la empresa Cyberware con el detalle de las submallas. Como se observa, el algoritmo propuesto también funciona con este modelo por el mismo motivo que el anterior, pero para otro tipo de disposición de mallas no está garantizado que vaya a hacerlo.

Cualquier ayuda es poca a la hora de revisar código escrito en JavaScript, sobre todo por el hecho de que los errores no suelen verse hasta no se ejecuta el programa.

Ya había utilizado anteriormente JSLint, y aunque a veces pueda parecer que es una herramienta un poco paranoica, normalmente hace bastante bien su trabajo. Es como el lint de C de toda la vida, pero para JavaScript. Gracias a ella he detectado dos problemas en la librería js-openctm.

El primer problema era una declaración de variable duplicada:

Y esto verdaderamente es un problema de mentalidad mío, que aunque ya me sé la historia del "hoisting" en JavaScript (no existe scope a nivel de bloque), aún así tiendo a declarar las variables justo en el momento que las uso por primera vez.

El segundo problema que ha detectado JSLint es referido a la colocación de unos paréntesis a la hora de ejecutar una función. Los tenía así:

Cuando deberían estar así:

En definitiva, una herramienta muy recomendable para este tipo de cosas.

Esto de hacer en JavaScript lo que toda la vida se ha hecho en C hace que uno se relaje y se le olviden los problemas clásicos. ¡Pero siguen estando ahí! Tengo que recordarme que un byte sigue siendo un byte, que un bit sigue siendo un bit, y que el orden que ocupan cada uno de ellos es importante.

Todo esto viene a cuenta de que he notado que js-openctm no era endianness safe. O sea, que sólo la he probado en mi máquina, que es little endian, y estoy casi seguro que no iba a funcionar en arquitecturas big endian.

Las especificaciones del formato OpenCTM dicen que los datos se almacenan entrelazados a nivel de byte, de forma que la secuencia:

Donde a, b, c y d son los cuatro bytes de una cantidad de 32 bits. Siendo a el byte más significativo (esto último no lo dice la documentación).

Revisando el código original del SDK de OpenCTM veo que reserva memoria para un buffer temporal, recupera todos los bytes del fichero, los recorre convirtiéndolos a los valores definitivos (instanciando un int o un float) y finalmente los vuelca en el buffer definitivo. Por su parte, en js-openctm, lo que se hace es poner directamente los bytes en su posición final dentro del buffer definitivo, evitando la reserva de memoria y los pasos intermedios.

El problema está en que en las arquitecturas big endian el primer byte a emitir al buffer definitivo deber el más significativo (a), mientras que la librería está emitiendo siempre el menos significativo (d) como corresponde a una máquina little endian, como la mía.

¿Solución? Comprobar el endianness de la máquina sobre la que se está ejecutando la librería con la típica función de toda la vida:

La función reserva un buffer de 2 bytes e instancia dos vistas sobre él. Una vista de byte y otra de entero de 16 bits. En la vista de byte se escribe un 1 en la posición 0. Y a continuación se comprueba si la vista de entero devuelve un 1. Si la máquina es little endian debe devolver un 1 (0x0001), si la máquina es big endian debe devolver un 256 (0x0100).

Con esta función, que sólo se evalúa una vez al principio, ya se puede decidir el orden correcto con el que se tienen gestionar los bytes, y la librería debería pasar a ser endianness safe, aunque me sigue faltando ejecutarla sobre una máquina big endian para comprobarlo.