- El ascenso de related_post_gen en el benchmark de Neat no vino de una optimización de alto nivel, sino de un pequeño cambio de ABI: pasar los arreglos como 3 argumentos puntero en lugar de una struct de 24 bytes
- Los arreglos de Neat necesitan, además de los punteros de inicio y fin, un puntero basado en el objeto del arreglo por el conteo de referencias, así que a diferencia de los 16 bytes del arreglo de D, terminan usando la ruta de paso por memoria del ABI SystemV AMD64
- Ciertos aggregate de más de 16 bytes se copian al stack al llamar y luego se pasan por puntero, perdiendo la ventaja del paso por registros y aumentando el costo de reordenar el stack
- En el benchmark de ejemplo, si
struct Vector { double x, y, z; } se pasa como struct, 1,000 millones de ejecuciones tardan 12.3 segundos; si sus campos se pasan como argumentos individuales, baja a 5.3 segundos
- Una API de C debe seguir el ABI de C, pero para tipos internos del runtime del lenguaje, como arreglos, tuplas o sumtypes, cuando superan los 16 bytes vale la pena medir el enfoque de pasar los campos por separado
El cuello de botella que apareció en Neat
- Neat subió varios puestos en el benchmark de related_post_gen
- La mejora de rendimiento no fue resultado de un nuevo pase de optimización de alto nivel, sino de cambiar la forma de pasar arreglos
- Antes: un argumento struct con 3 punteros
- Después: los 3 punteros como argumentos separados
- Neat era más lento de lo esperado frente a D, y en el profiler se veía movimiento de grandes áreas del stack para hacer llamadas a funciones
- El cuello de botella estaba más cerca del costo de reacomodar el stack en el momento de la llamada que del cálculo en sí
Por qué el arreglo de Neat termina midiendo 24 bytes
- A diferencia del arreglo de D, Neat usa conteo de referencias
- El arreglo de Neat incluye estos 3 punteros
- puntero al inicio
- puntero al final
- puntero basado en el objeto del arreglo donde se guarda el conteo de referencias
- Tres punteros son 24 bytes, así que, a diferencia de un arreglo de 16 bytes con 2 punteros, siguen una ruta distinta en las reglas de paso de argumentos de AMD64
- La razón por la que el arreglo de D era rápido y el de Neat lento fue que, al llegar a 24 bytes, cruzó el límite de 16 bytes
El límite de 16 bytes en el ABI SystemV AMD64
- La especificación del ABI SystemV AMD64 establece que si cierto aggregate supera dos eightbytes, el argumento completo se pasa por memoria
- Para pasar una struct por memoria, el lado que llama tiene que hacer lo siguiente
- reservar en el stack un espacio del tamaño de la struct
- llenar ese espacio con el valor a pasar
- pasarle a la función un puntero a la ubicación de esa struct
- En este caso, el valor necesariamente tiene que estar en el stack, así que LLVM tiene poco margen de optimización
- El valor debe copiarse de registros al stack, y también hay que rastrear qué parte del stack está en uso y cuál puede reutilizarse
- En este rastreo de reutilización del stack, LLVM mostró un comportamiento pobre
Benchmark de vector con 3 double
- El benchmark usa un vector de 3 campos con forma
struct Vector { TYPE x, y, z; };
TYPE está definido como double- Las dos funciones hacen la misma suma, pero difieren en la forma de pasar los argumentos
vector_add_struct(struct Vector left, struct Vector right) recibe structs grandes como argumentosvector_add_fields(...) recibe left_x, left_y, left_z, right_x, right_y, right_z como argumentos individuales
mode y la duración de ejecución se reciben por línea de comandos para evitar que el optimizador pliegue toda la computación como constanteimpl.c se compila por separado para evitar el inlining
clang -O3 impl.c -c -o impl.o
clang -O3 harness.c impl.o -o benchmark
time ./benchmark 0 1000000000
time ./benchmark 1 1000000000
- El resultado fue 12.3 segundos al pasar la struct y 5.3 segundos al pasar los campos por separado
La diferencia visible en assembly
- La versión que pasa structs usa muchas instrucciones en stack shuffle
- La versión por campos tiene ventaja porque los parámetros ya entran a la función en registros SSE
- La versión que pasa structs tiene que cargar los valores desde el stack en cada llamada
- El ABI SystemV busca pasar valores por registros siempre que sea posible, pero en este caso esa ventaja desaparece por tratarse de structs de más de 16 bytes
- Considerando la cantidad de registros disponibles en AMD64, se argumenta que incluso para tipos de más de 16 bytes habría sido útil pasarlos por valor
Cuando se parece a cdecl
- El método de escribir los campos al stack y pasar un puntero termina pareciéndose al antiguo ABI x86
cdecl, que pasaba todo por stack
cdecl tenía fama de ser lento, y por eso surgieron varias convenciones de llamada para acelerarlo- El problema es que el ABI AMD64 System V, por el tamaño de la struct, en este caso termina comportándose como ese viejo esquema de paso por stack
La excepción del inlining y LTO
- En código real, este tipo de funciones puede terminar completamente inlineado
- Al activar LTO en
gcc, la diferencia de rendimiento entre ambas versiones desaparece
- En
clang, no se obtiene el mismo resultado
- No todas las funciones pueden ni deben inlinearse
Consejos para implementadores de lenguajes y optimización de API
- Al llamar una API de C, hay que seguir el ABI de C
- Pero los tipos de alto nivel internos de un lenguaje no C, aunque para el backend parezcan structs, no tienen por qué representarse obligatoriamente como una sola struct
- El implementador del lenguaje puede decidir directamente cómo pasar arreglos, tuplas, sumtypes, etc.
- En Neat se eligió pasar por campos separados estos tipos que superan los 16 bytes, y el benchmark mostró beneficios
- Si estás implementando un lenguaje en AMD64 o afinando una API, conviene medir si dividir manualmente las structs de más de 16 bytes ayuda
- Sobre todo en loops internos, la diferencia de rendimiento puede ser mayor de lo esperado
Nota adicional: structs con double y SSE
- La pregunta es por qué, si
double pertenece a la clase SSE según la especificación, la struct no se pasa en registros SSE
- La respuesta es que no se sabe por qué, pero en la práctica no se pasa así
1 comentarios
Comentarios de Hacker News
El problema aquí es la ABI SysV amd64. No hace falta usar SysV como ABI interna del lenguaje. Si no se expone a llamadores C de SysV, se puede usar la convención de llamada que uno quiera.
https://llvm.org/docs/LangRef.html#calling-conventions
Para quien tenga curiosidad, el cambio relacionado en neatlang está aquí: https://github.com/Neat-Lang/neat/commit/f4ba38cefc1e26631a5...
Parece mucho más complejo que simplemente cambiar la salida de la convención de llamada de LLVM. Probablemente el autor quería exponer estos tipos a programas C con una convención de llamada determinista.
No hay que seguir las convenciones a ciegas; basta con elegir lo que tenga más sentido para la situación concreta.
En particular, las ABI suelen inclinarse hacia la compatibilidad con CPU más antiguas, y las CPU más nuevas podrían tener margen de mejora usando cosas como registros extendidos, sin tener que reducir el tamaño de las estructuras. El software ajustado a hardware o generaciones específicas no sería tan atractivo porque dejaría de funcionar en algunas máquinas, pero sería genial tener un compilador capaz de generar ese tipo de salida cuando uno quiere optimizar el código al extremo para las capacidades de hardware de su propio sistema.
El costo de pasar argumentos muchas veces no se entiende bien, así que se agradecen artículos como este. Incluso en lugares como Google es común pasar objetos de 24 bytes por valor, y ese costo está tan distribuido por todas las funciones que no aparece claramente en los profilers.
Aunque también se exponen este tipo de tropiezos: https://github.com/ziglang/zig/issues/5973#issuecomment-1330...
La única excepción que se me ocurre es string_view.
Con mala suerte puede haber un cache miss y terminar esperando unos 100 nanosegundos mientras se trae el objeto de 24 bytes desde la memoria principal. Si se pasa el mismo objeto directamente, estará en el stack, así que es más probable que esté en caché.
Cuando pasamos por primera vez a x64, me preocupaba que los objetos vec3 de gráficos (3 floats) crecieran a 16 bytes en lugar de sizeof()=12, así que hice muchísimos benchmarks del motor gráfico.
Como era de esperarse, gracias a la alineación de lecturas de 8 bytes, 16 bytes era más rápido que 12 bytes. Tanto internamente como en la GPU. Así que vec3 se convirtió silenciosamente en vec4, y vec4 siguió existiendo aparte. Como siempre, hay que hacer benchmarks con visión de conjunto, no benchmarks locales.
Entiendo que con 16 bytes muchos accesos pueden convertirse en 2x8 bytes alineados o 1x16 bytes, en lugar de 3x4 bytes. Pero en otros accesos quizá no sea tan así, y también está el problema de la mayor presión sobre la caché.
Por sentido común, los valores que se pasan en registros pueden precargarse gracias a la ejecución especulativa, así que son más rápidos que escribir en el stack, y manipular el stack es más rápido que asignar en el heap.
Por eso el código espagueti sucio con un montón de variables globales puede ser increíblemente rápido, mientras que las funciones recursivas elegantes o los argumentos tipo tupla/estructura/lista pueden ser increíblemente lentos. El primero es mucho más fácil de optimizar como un bucle de ensamblador compacto.
Si el código elegante es O(n) y el espagueti es O(n^2), la diferencia se va a notar. También hay que considerar el mantenimiento. En cierto sentido, los compiladores existen para convertir nuestras soluciones elegantes en código espagueti.
Los objetos globales también entorpecen las optimizaciones del compilador.
Como referencia, en MSVC el tamaño de corte es de 8 bytes antes de que una estructura se pase por el stack. Esto es un detalle de la ABI, así que no conviene depender de ello en código portable.
Pero si la función no se llama con frecuencia, tampoco hace falta estresarse demasiado. Si es una función pequeña llamada con frecuencia, como en el ejemplo, lo ideal es permitir que el compilador inlinee el código mediante algo como LTO. Eso habilita optimizaciones mucho más útiles que pasar argumentos por registros.
Clasifico este tipo de textos como “el conocimiento justo para meterse en problemas”. Aunque sigas la indicación de compilar por separado para obligar al compilador a generar una función invocable mediante la ABI, LTO puede revertir este error.
Si compilas este programa con LTO, se vuelve drásticamente más rápido en ambos modos que cualquier modo del programa sin LTO. Si es un programa sensible al rendimiento, hay que perfilarlo y, solo después de optimizar los cuellos de botella al máximo, comprometerse a hacer cosas como descomponer las estructuras en argumentos.
Aplica a casi todo el código generado por compiladores. Valgrind podría medirlo, pero un profiler por muestreo probablemente no, y no hay herramientas que resalten problemas de generación de código dispersos.
En la convención de llamada cdecl predeterminada de Windows, las estructuras de más de 8 bytes no se pasan por registros [1]
[1]: https://learn.microsoft.com/en-us/cpp/build/x64-calling-conv...
En amd64, incluso usando la ABI SysV amd64, pasar y devolver por valor estructuras de más de 16 bytes es totalmente posible. Simplemente es lento.
Aun así, muchas veces pasar por valor vale la pena para que el código sea más claro. Claro que no en este caso, pero como señaló loeg, dentro de tu propio lenguaje puedes usar una ABI personalizada, como los compiladores de C++, Go, OCaml y SBCL.
En el ejemplo dado, se puede arreglar cambiando el tipo del parámetro de “struct Vector” a “const struct Vector &” y pasándolo por referencia, sin afectar al llamador.
He visto mucho código C++ con bugs de punteros que usaba punteros sin necesidad, cuando pasar por referencia habría sido suficiente y además más fácil y seguro.
Como la ABI dice que el valor se debe pasar como puntero, hay que guardarlo en algún lado para obtener ese puntero, y termina ocurriendo lo mismo que si hubieras especificado const-ref. Si conviertes el valor de la estructura en argumentos separados, los argumentos pueden pasarse por registros.
Siempre había asumido en cierta medida que LLVM limpiaría bien este tipo de cosas, pero resultó que no.
El beneficio descrito consiste en evitar por completo esa serialización de registros a pila, y pasar por referencia no parece evitarla.
Si se permite C++, tienes muchas más opciones, como argumentos por movimiento para reducir copias.
La regla práctica que siempre he escuchado en C++ es que, salvo que haya una buena razón para pasar por valor algo que no sea un tipo primitivo, hay que pasarlo por referencia, y si de verdad hace falta, por puntero.
Esto se debe tanto a la ABI como a evitar constructores de copia o de movimiento. Son detalles aburridos de bajo nivel, pero si quieres el máximo rendimiento en C++, hay que prestarles atención. Para ser claros, esto es solo una optimización de rendimiento; el código que pasa estructuras funciona correctamente, solo que es menos rápido.