Una optimización "mágica" para bibliotecas dinámicas en GNU/Linux

Tengo un proyecto con una batería de casos de prueba que tarda horas en completarse. Esta semana encontré una opción de compilación que con un mínimo esfuerzo me redujo el tiempo total de la prueba en 37% (muchísimo!). Y por supuesto que no es -O# (sería muy obvio), y tampoco es LTO (pero algo tiene que ver). Es algo un poco más escondido y menos obvio, que al menos yo no sabía, así que lo comparto.

 

Algunas cuestiones conocidas sobre las bibliotecas dinámicas

Para empezar, esto aplica cuando el trabajo pesado está separado en una biblioteca dinámica (un .dll o .so). Un ejecutable que utiliza una biblioteca dinámica es básicamente un ejecutable incompleto, donde algunas llamadas a funciones no está resueltas en el ejecutable simplemente porque las funciones no están ahí. Simplificando mucho, se puede imaginar como una llamada a través de un puntero a función, cuyo valor es nullptr. Es trabajo del sistema operativo asignarle el valor adecuado a ese puntero al momento de cargar en memoria el ejecutable y sus bibliotecas. Para ello, debe encontrar esa función dentro de la biblioteca adecuada. Por esto, cada binario de biblioteca dice de alguna manera qué funciones ofrece.

Para hablar con un poquito más de propiedad, en lugar de "función" hay que decir "símbolo" (puede ser otra cosa, como una variable global por ej), y cuando un binario "dice tener" una función en realidad se dice que "exporta" ese símbolo, o que ese símbolo es "visible".

Hay que notar que un binario puede tener muchos más "símbolos" de los que dice exportar. Puede haber funciones visibles que como parte de su código llamen a otras funciones auxiliares no visibles (ocultas) de ese mismo binario. Para hacer una analogía con el control de acceso en clases en C++, sería como cuando un método público (símbolo visible) invoca a un método privado (símbolo oculto) de la misma clase (biblioteca/binario).

Y aquí hay una diferencia importante entre sistemas operativos. Por razones históricas, los símbolos que definamos en nuestro código* (y si no usamos argumentos de compilación "raros"), por defecto serán ocultos en Windows, mientras que en GNU/Linux serán visibles. Por esto vemos/necesitamos cosas como __declspec(dllexport) "decorando" las funciones que deben ser públicas en un archivo .dll (en Windows).

*La excepción es cuando definimos una función como static o al símbolo dentro de un namespace anónimo; no será visible de ninguna manera, ya esas son las formas estándar de C++ para explicitar que el símbolo no debe "salir" de esa unidad de compilación.

Hasta aquí pareciera que todo esto podría tener alguna incidencia en el tiempo de carga de un ejecutable. Si todo es visible, hay muchos más símbolos, y entonces encontrar el adecuado para corregir ese "puntero" será más costoso. Pero tenemos que hablar de programas/bibliotecas realmente muy grandes para que esto se note. En cualquier caso, una vez cargado el binario y sus bibliotecas, no parece haber motivo para que varíe la velocidad del programa según la visibilidad de los símbolos. Peeeero.... aquí termina mi conocimiento previo y empieza la novedad.

Todo esto surgió de mirar esta excelente charla. En el video están mucho mejor explicados todos los detalles.
Y aquí un PDF muy técnico con todavía más detalles.

Algunas cuestiones no tan conocidas sobre las bibliotecas dinámicas

Resulta que toda llamada a una función de una biblioteca dinámica en GNU/Linux termina siendo indirecta por tres motivos: 

• Que el loader deba corregir un solo "puntero" al encontrar el símbolo, aunque esa función se invoque muchas veces: Entonces el programa cliente cuando debe invocar a la función no salta directamente al comienzo de la función (lo cual implicaría "corregir" esa dirección de comienzo en todas las llamadas), sino que lo hace a través de un puntero global (entonces solo se corrige ese único puntero).
• Que la resolución de símbolos sea lazy: Esto es, para que se resuelvan al primer uso y evitemos tener que resolver todo en ejecuciones donde no sería necesario. Entonces al cargar el ejecutable no se corrige nada, sino que ese puntero inicialmente apunta al código que hace la corrección, y luego de la primer ejecución queda apuntando a la verdadera función de la biblioteca.
• Algo conocido en inglés como to interpose: (sería interponer en castellano, pero no creo que se use) cuando se reemplaza un símbolo de una biblioteca por el de otra.

El punto es que la llamada a una función de biblioteca termina siendo indirecta, como si fuera la llamada a un método virtual. Y ya sabemos (esto sí es más conocido, sobre todo para quienes programan videojuegos) que esa indirección puede afectar sensiblemente la performance: principalmente porque es un paso más que previene el inlining (entre otras optimizaciones) y porque todo salto en memoria suele ser cache-unfriendly. Resulta entonces que al poner nuestro código en una biblioteca dinámica, en GNU/Linux, por defecto estamos pagando ese costo, como si todo fuera virtual.

Ej. de la salida de "perf stat" para uno de los casos de prueba antes y después del cambio.

Pero si lo pensamos un poco más, cuando el ejecutable llama a una función de la biblioteca y esta debe hacer mucho trabajo, no se debería notar demasiado. Se puede imaginar que el costo se pagaría solo al "ingresar" a la biblioteca, pero no habría motivo para que las llamadas dentro de la biblioteca lo paguen también. Y aquí viene la segunda revelación: lo hacen igual. 

Cuando GNU/Linux debe resolver un símbolo, lo busca en todas las bibliotecas cargadas y según el orden de carga. Esto implica que puede no comenzar por la biblioteca que lo está necesitando. Entonces, si dos bibliotecas definen el mismo símbolo, ambas usarán el que se cargue primero, en lugar de cada una usar el suyo (ahí se interpone la función de la primera en las llamadas de la 2da). Esto es así por razones históricas (tiene utilidad, pero debería ser más una excepción que una regla), y es lo que obliga a que sean indirectas las llamadas a símbolos visibles aún dentro de la misma biblioteca.

La "solución"

La solución (evitar que esas llamadas sean indirectas) pasa por forzar un comportamiento más al estilo Windows: que los símbolos por defecto sean ocultos y nosotros marquemos explícitamente cuáles queremos visibles. Para lo primero, solo hay que compilar los cpps de la biblioteca con el argumento -fvisibility=hidden. Para lo segundo, en GNU/Linux hay decorar los símbolos que queremos exportar con __attribute__((visibility("default"))). En el caso de una función va antes del prototipo en su declaración; y en el caso de una clase entre la palabra class y el nombre (aunque no siempre es necesario hacer visible toda la clase, a veces alcanza con que solo algunos métodos de la clase sean visibles). Por supuesto que para hacerlo más prolijo y portable, terminamos escondiendo esto (y las __declspec(...) de Windows) en una serie de macros definidas mediante un montón de #ifdefs; es lo que hay.

El punto es que con estos "pequeños" cambios obtuve enormes ganancias* en cuanto tiempo de ejecución. Y por supuesto, aprendí un poco más de cómo funcionan las cosas por dentro, tanto en Windows como GNU/Linux, lo cual siempre es muy interesante, y a veces, como ahora, hasta útil.

 

*Anexo: Algunos detalles sobre ese increíble 37%

• Está medido sobre un código que forma parte de un software comercial de simulación, y con casos de prueba que provienen mayormente de los reportes de errores de los clientes, así que son casos de la industria y no ejemplos artificiales solo para testing. Tomé los 100 casos que más tiempo tardaban para la prueba (que varían entre 10seg y 2hr). Los speed-ups van desde 8% a 69% (es ridícula esta diferencia!).
• El proceso está acotado mayormente por el uso de CPU, y un análisis rápido con perf muestra que el principal motivo de la mejora es que simplemente baja la cantidad de instrucciones ejecutadas. Casi no cambian las estadísticas generales (se mantienen los % de utilización de CPUs, de fallos de caché, etc), solo mejora un poquito el rendimiento del predictor de saltos, y solo en algunos ejemplos se reduce mucho el trabajo de la cache L1 (menos loads, misma cantidad de misses, y solamente para L1, porque L2 da casi siempre igual).
• Esta solución funciona tan bien como digo solo cuando se combina con LTO (link-time optimizations) si no el speed-up existe pero es considerablemente menor. Hace un tiempo había probado agregar los argumentos para LTO y me sorprendió que casi no tuvo impacto. Ahora me cierra por qué.
• Estamos hablando de una biblioteca que ofrece unas pocas funciones al cliente, que hacen muchísimo trabajo cada una. Es decir, pocos símbolos públicos, muchísimos privados. Es el escenario ideal para este cambio. Si la mayor parte de la biblioteca fuera invocable directamente por el programa cliente, la ganancia tampoco sería tan grande (¿tal vez convendría explorar el argumento de compilación -Bsymbolic en ese caso?).