20 de septiembre de 2010

Microoptimización

En la próxima versión de Linux hay una microoptimización de código que me ha parecido interesante. El problema se origina en dos funciones con switch()s que contienen una cantidad considerable de cases, los cuales a su vez contiene varios ORs en cada uno: "case BPF_ALU|BPF_ADD|BPF_X".

Dado un switch(variable) con un montón de cases, el compilador normalmente no lo traduce a ensamblador tal y como los concibe el programador, es decir, como una secuencia de condiciones "si variable=A saltar a dirección x, si variable=B saltar a dirección y", sino como una especie de salto: "saltar a dirección x+variable". Sin embargo, parece ser que todos esos ORs de las funciones citadas impiden al compilador hacer su optimización (es más, según he leido en la wikipedia, parece ser que la misma secuencia de números que puede contener la variable puede afectar a la optimización).

Con lo cual esas funciones son ensambladas como una lista gigantesca de condiciones de 567 bytes de longitud. Sin embargo, eliminando los ORs se consigue que gcc optimize correctamente el código y todo sea como debiera de ser. Nótese que poner por separado todos esos ORs supone tener que crear un case adicional para cada uno, es decir, aumentar el número de líneas de código, pero contando la optimización lograda sigue siendo una mejora.

Estas cosas naturalmente no merece la pena ni mirarlas por regla general, pero si se trata de una parte del código cuyo rendimiento es crítico, como parece ser el caso, pues quizás si. El otro día recuerdo haber leído un artículo (lamento no poder recuperar el enlace) de un experto en análisis que afirmaba que la parte del código más importante para el rendimiento de un programa solía ser el 1% de todo el código, y que normalmente los programadores no suelen analizarlo, a pesar de que se pueden lograr mejoras notables con pequeñas optimizaciones. No es mala advertencia, desde luego.


Y si han llegado hasta aquí tal vez les interese saber que ya se pueden ver las primeras capturas de cómo se está portando QT (también se está portando GTK, tengo entendido) para funcionar de manera nativa en Wayland, que es un servidor gráfico alternativo a X.org basado en las últimas tecnologías gráficas de Linux.

5 comentarios:

  1. Anónimo10:04 p. m.

    :O...

    Una linea puede cambiar todo en eso hay mucha razón.

    Ahora me podré a investigar sobre Wayland.

    ResponderEliminar
  2. Anónimo10:50 p. m.

    No se si esta solución serviría en este caso completo pero cuando he tenido este tipo de problemas en secciones críticas he optado por insertar directamente código en ensamblador con el ensamblado correcto.

    ResponderEliminar
  3. Anónimo12:03 a. m.

    tenes que tener en cuenta que linux corre en diferentes plataformas por lo cual deverias crear un codigo en ensamblador para cadauna de ellas

    ResponderEliminar
  4. Anónimo10:55 p. m.

    Cierto, no lo pensé por que obviamente no tuve ese problema, optimizar código ensamblador plataforma por plataforma puede ser infernal y no es precisamente una solución a largo plazo

    ResponderEliminar
  5. En este caso es algo más que una pequeña optimización. Se pasa de complejidad O(n) a complejidad O(1), y teniendo en cuenta que la estructura generada es bastante gorda y que ese código se usa en los sockets, puede mejorar bastante el rendimiento de red, aunque me gustaría ver benchmarks completos (pero estoy seguro que los de NASDAQ lo agradecerán, que por lo que leí en la LWN están siempre buscando como bajar la latencia unos nanosegundos).

    ResponderEliminar