Parsear protobuf a más de 2 GB/s: diseño de un intérprete de alta velocidad en C usando tail calls (2021)

• Con la incorporación de musttail en Clang, ahora es posible aprovechar tail calls garantizadas también en lenguajes de la familia C, y al aplicarlo a un parser de protobuf se demostró un rendimiento de más de 2 GB/s
• La clave está en hacer que las llamadas a funciones se parezcan más a un jmp que a un call, reduciendo el uso de pila de llamadas consecutivas de O(n) a O(1) y tratándolas como si fueran un bucle
• El wire format de protobuf debe interpretar etiquetas/valores y ramificarse hacia campos en orden arbitrario, por lo que la estructura tradicional while + switch tiene un problema de optimización similar al dispatch de opcodes de un intérprete
• El parser experimental de upb conecta pequeñas funciones de parser mediante tail calls, en lugar de usar una sola función grande, evitando en la ruta rápida uso de pila, spills de registros y prólogos/epílogos
• Este enfoque tiene limitaciones: si se mezclan non-tail calls, la calidad del código empeora mucho, y musttail es una extensión no estándar; para desplegar un parser rápido en la práctica hacen falta disciplina de llamadas y medidas de portabilidad

---

Parsing protobuf de alta velocidad abierto por musttail de Clang

• En la rama main de Clang se agregó el atributo de sentencia [[clang::musttail]] / __attribute__((musttail)), que permite obtener una garantía de tail call en C, C++ y Objective-C
• Aquí, tail call no se usa como técnica de programación funcional, sino como una herramienta de optimización para reducir el costo de ramificación en parsers e intérpretes
• Al aplicar esta técnica al parsing de protobuf, en upb pull/310 se demostró un rendimiento de parsing de más de 2 GB/s
  • Se presenta como un resultado más de dos veces más rápido que el mejor nivel anterior
  • Como varias técnicas contribuyeron en conjunto, no es correcto interpretar que “solo las tail calls lo hicieron 2 veces más rápido”
  • Las tail calls son uno de los elementos clave que hicieron posible esta mejora de rendimiento
• Los cambios posteriores se tratan en A Tail Calling Interpreter For Python (And Other Updates)

Por qué una tail call se comporta como una estructura iterativa

• Una tail call es la última llamada a función que se realiza justo antes de que una función retorne
• Cuando se aplica la optimización de tail calls, el compilador genera una instrucción jmp en lugar de un call normal
  • Se omite la creación de un nuevo stack frame y el guardado de la dirección de retorno
  • El llamador f() salta directamente al llamado g()
  • g() retorna directamente a la función que había llamado a f()
• Gracias a esta propiedad, una tail call puede sustituir una estructura iterativa
  • Incluso con n tail calls consecutivas, el uso de pila baja de O(n) a O(1)
  • Al desaparecer el overhead de call, las llamadas a funciones pueden tratarse como ramificaciones normales
• La idea no es nueva: se remonta al artículo de Guy Steele de 1977 y a los “Lambda Papers” de 1975 a 1980
• Clang ya podía optimizar tail calls en builds optimizados como -O2, pero el comportamiento anterior era más bien best-effort
  • En builds sin optimización, es muy probable que se compile como un call real
  • Para usar tail calls de forma segura como estructura iterativa, la optimización debe estar garantizada en todos los modos de build
  • musttail ofrece esa garantía

El mismo cuello de botella en bucles de intérpretes y parsers protobuf

• Mike Pall, de LuaJIT, escribió el intérprete de LuaJIT 2.x en assembly en vez de C, y lo considera una de las principales razones de que sea un intérprete rápido
• Los compiladores de C enfrentan dos problemas en particular en el bucle principal de un intérprete
  • A medida que la función crece y el flujo de control se vuelve complejo, al asignador de registros le cuesta mantener datos importantes en registros
  • Si la ruta rápida y la ruta lenta se mezclan dentro de la misma función, la ruta lenta también degrada la calidad del código de la ruta rápida
• El wire format de protobuf también tiene una estructura parecida a la de un intérprete
  • El wire format es una secuencia de pares etiqueta/valor
  • La etiqueta contiene el número de campo y el wire type
  • La etiqueta funciona de manera similar a un opcode que indica cómo parsear los datos de ese campo
  • Como los números de campo pueden venir en orden arbitrario, hay que estar listo para despachar hacia cualquier parte del código
• Los parsers protobuf tradicionales suelen tener una estructura con un switch dentro de un bucle while, y durante la mayor parte de la existencia de protobuf este enfoque se usó como una solución de primer nivel
• En el parsing real, casi en cualquier etapa pueden ocurrir excepciones como un wire type que no coincide, datos corruptos o llegar al final del buffer
  • La ruta rápida debe mantenerse lo más corta y estable posible
  • Los casos difíciles requieren código fallback más grande y complejo, y a veces también llamadas a funciones out-of-line

Diseño del parser de upb basado en tail calls

• El parser experimental de upb no usa una sola función de parsing grande, sino que separa cada operación en una función pequeña
• Cada función llama a la siguiente operación mediante una tail call
  • Gracias a la convención de llamadas de x86-64, los argumentos comunes de parsing se pasan en registros
  • Todas las funciones de parsing usan el mismo conjunto de argumentos, reduciendo los movimientos de valores entre llamadas
• La función de parser de ejemplo para un campo fixed-width de 4 bytes opera con el siguiente flujo
  • Decodifica la información del campo desde data
  • Si el wire type no coincide, hace MUSTTAIL return hacia fallback()
  • Salta la etiqueta y guarda los datos en el mensaje
  • Después de leer la siguiente etiqueta, hace una tail call a dispatch(), que ramifica hacia el parser de campo adecuado
• El assembly generado por Clang no tiene prólogo, epílogo, spill de registros ni uso de pila en la ruta rápida
  • Los únicos puntos de salida son jmp hacia fallback o dispatch
  • Como los argumentos ya están en los registros correctos, tampoco hace falta código adicional para pasar parámetros
• Conceptualmente, esta estructura ve un gran bucle de intérprete como una sola función compleja, pero su implementación real lo divide en funciones por bloques básicos y pasa el flujo de control mediante tail calls
• Separar la ruta rápida y la ruta lenta en funciones distintas reduce la posibilidad de que cambios en el código fallback alteren la calidad del código de la ruta rápida
  • Si hace falta, se puede impedir el inlining con noinline
  • La secuencia de assembly de la ruta rápida puede quedar prácticamente fija

Calidad de generación de código C vista en el ejemplo de LuaJIT

• Si se aplica el mismo patrón al ejemplo de LuaJIT, se puede obtener en C un resultado cercano al assembly escrito a mano
• La función de ejemplo ADDVN realiza las siguientes operaciones
  • Extrae de la instrucción el registro y el índice de constante
  • Si falla la comprobación de tipo, va al fallback
  • Suma la constante al valor del registro
  • Lee el siguiente opcode y hace una tail call a la función de la tabla de opcodes
• Las mejoras pendientes en el assembly generado son relativamente pequeñas
  • Aparece un jmp separado después de una rama condicional
  • En lugar de jmp qword ptr [rsi + 8*rax], carga en rax y luego usa jmp rax
• Estos puntos se tratan como pequeños problemas de generación de código que podrían mejorarse en Clang

Limitaciones: non-tail calls y portabilidad

• El mayor punto de atención de este enfoque es que, si dentro de una función aparece una non-tail call, la calidad del assembly empeora notablemente
  • Una sola non-tail call obliga a crear un stack frame
  • Muchos datos pueden terminar derramándose a la pila como spills
• Para evitarlo, hace falta una disciplina en la que las otras llamadas a funciones se inlineen o se realicen solo como tail calls
• En el parsing de protobuf, el manejo de varint es una dificultad representativa
  • El caso común y rápido es un varint de 1 byte
  • Los varint más largos no son errores, pero son casos poco frecuentes
  • Si se inlinea este manejo excepcional, puede empeorar la calidad del código de la ruta rápida
  • Si se hace una tail call a una función fallback, no es fácil reanudar la operación original después del manejo, por lo que el fallback debe completar la operación hasta el final
  • Como resultado, aparecen duplicación de código y complejidad
• En la actualización del 2025-01-27 se agregó una forma de mitigar este problema mediante convenciones de llamadas
  • __attribute__((preserve_most)) es una convención de llamadas que puede usarse en funciones fallback; traslada al callee la responsabilidad de preservar casi todos los registros y mueve el costo de spills al lado del fallback
  • El bug de crash de Clang relacionado con este atributo fue corregido en 2023
  • __attribute__((preserve_none)) es una convención de llamadas que puede usarse en funciones con tail calling; elimina la carga de preservar registros y usa más registros para argumentos
  • De las dos opciones, preserve_none se considera la mejor por ser menos intrusiva
• Otra limitación es que musttail es una extensión no estándar del compilador
  • Se espera que se extienda a GCC, Visual C++, etc. y que se estandarice, pero no es algo cercano
  • Cuando no hay musttail, hace falta al menos un return real por cada iteración conceptual del bucle
  • upb aún no implementa este fallback, y se prevé que hará falta una macro que, según la disponibilidad de musttail, haga una tail call hacia el dispatch o simplemente retorne

Estado de adopción en upb y posibilidades de expansión

• El parser de más de 2 GB/s fue enviado a upb, una pequeña biblioteca protobuf escrita en C
• Ese código funciona completamente y pasa todos los protobuf conformance tests, pero al momento de escribir no se había hecho rollout en ningún lado
• Este diseño no se implementó en la versión C++ de protobuf
• Más adelante, con la actualización de upb para usar musttail, se eliminó una de las grandes barreras para llevar el parser rápido a producción
• La misma técnica también podría aportar ventajas de rendimiento importantes a intérpretes de lenguajes principales escritos en C, como Python, Ruby, PHP y Lua

[GN⁺]

Opiniones de Hacker News

• Hay una propuesta para el estándar de C con sintaxis para llamadas de cola, con la forma return goto (expression);
  Lo que me gusta más que el [[musttail]] estándar es que garantiza que termina la vida útil de los objetos locales. Así se vuelve implementable sin un análisis de escape amplio
  [0] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3266.htm#5...

  • Me pregunto por qué return goto es más fácil de implementar. [[musttail]] también parece terminar la vida útil de los objetos locales
    Al revisarlo rápido, dice que la función llamada en posición de cola debe tener el mismo tipo que el destino de la llamada. Es una condición para garantizar que no haga falta convertir el valor de retorno y que se mantengan el espacio para pasar argumentos y la convención de llamada
    Una queja que vi con frecuencia sobre [[musttail]], que implementé en Clang, es que esta restricción es innecesariamente estricta. Algunas arquitecturas permiten llamadas de cola aunque los tipos no coincidan por completo: https://github.com/llvm/llvm-project/issues/54964
    Es cierto decir “entonces el código deja de ser portable”, pero la optimización de llamadas de cola en sí misma no es inherentemente portable. Por ejemplo, algunos targets, como WASM sin la extensión de llamadas de cola, básicamente no admiten optimización de llamadas de cola
  • Que vuelva a tomar fuerza el impulso de agregar nuevas funciones a C es emocionante, pero también bastante inquietante
    Me entusiasma porque hay cambios y agregados que realmente deberían entrar, e incluso ideas que habría que aclarar, pero el ciclo agresivo de actualizaciones de C++ parece haber terminado como poner un parche encima de otro parche
    El problema aparece especialmente cuando las funciones interactúan mal entre sí mucho antes de lo esperado. Espero que el proceso de estandarización no dependa solo de documentos de justificación, sino que pruebe suficientemente las funciones en bases de código grandes y diversas, y que elija de forma muy conservadora

• Si te interesa el lado de Rust, hay un RFC antiguo que intentaba agregar la palabra clave become, que ofrecería optimización de llamadas de cola garantizada
  Originalmente se postergó para enfocarse en los objetivos de la edición 2018, y esa decisión fue correcta, pero recientemente la idea volvió a revisarse. Podría regresar
  [0]: https://github.com/rust-lang/rfcs/pull/1888
  [1]: https://github.com/rust-lang/rfcs/pull/3407

• La forma en que los intérpretes suelen obtener este tipo de mejora de velocidad en C++ es usando computed goto. Así no hay ruido relacionado con la convención de llamada en el camino de un opcode al siguiente
  La razón principal por la que el enfoque de computed goto o el de llamadas de cola es más rápido que el clásico bucle con switch es que reduce la carga del predictor de saltos. Estáticamente hay una rama indirecta por opcode, y ya no se trata de una estructura con una sola rama indirecta estática

  • Como dice el artículo, incluso usando computed goto, el grafo de flujo de control de la función se vuelve demasiado complejo, por lo que la asignación de registros para variables usadas con frecuencia es frágil
    Si cada función es pequeña y recibe las variables importantes como argumentos, la asignación de registros se vuelve mucho menos frágil
  • Me da curiosidad eso de “estáticamente hay una rama indirecta por opcode”. Sería bueno que explicaran con un poco más de detalle qué significa frente a una sola rama indirecta y cómo se logra
  • Escuché que este enfoque pasó de moda hace un tiempo. La idea era que los predictores de saltos se volvieron lo suficientemente buenos como para que ya no hiciera falta
    Aunque me pregunto si eso sigue siendo cierto cuando el intérprete crece

• El problema que queda al usar llamadas de cola para cambios de contexto es que se usan funciones que deben seguir una convención de llamada. Lamentablemente se desperdician registros para restaurar el estado al salir de la función
  Hay un análisis detallado y una alternativa usando un compilador intermedio en el blog del remake de LuaJIT: https://sillycross.github.io/2022/11/22/2022-11-22/

  • En los últimos años vi varios lenguajes quitar una capa JIT y luego volver a agregarla. Parte de eso se debe a la capacidad de los programadores y a las lecciones aprendidas, pero otra parte también se debe a cambios de generaciones de CPU
    Como con todo lo demás en ciencias de la computación, cuando cambia el equilibrio de costos entre tipos de operaciones, el mejor algoritmo puede volver a ser uno que se usaba hace 15 o 20 años. Por eso la programación tiene mucho de moda. Que algo reviva no significa que no haya motivos, pero sigue siendo un problema olvidar por qué la vez anterior no fue una panacea
    Si el JIT principal se vuelve más rápido o más lento, cambia la relación entre el costo de ejecución y el beneficio, y también se ajustan los umbrales que lo disparan. Entonces cambia la cantidad de código que se ejecuta en otras capas, y el costo amortizado de esas capas también puede empeorar. Es como equilibrar un péndulo doble
    Si se puede hacer que una capa JIT sea lo suficientemente rápida y burda, se puede saltar el intérprete por completo. Desde afuera, parece que la carga cognitiva de cuadrar las cuentas entre un intérprete y un par de JIT es alta, así que algunos lenguajes parecen haber dejado el intérprete en espera y usado un JIT optimizado para tiempo de compilación más que para velocidad de salida
    No recuerdo qué lenguaje era, pero tengo entendido que al menos un equipo terminó eliminando también el compilador intermedio por este problema de equilibrio. Era mejor enfocarse en dos cosas que manejar tres
  • Clang incorporó recientemente una nueva convención de llamada que abarata mucho este tipo de llamadas de cola. Evita que el llamador tenga que preservar algunos registros
    Siempre me confundo con el nombre, pero debe ser preserve_all o preserve_none. El problema es desde el punto de vista de quién se habla de preservar

• Entiendo que el atributo musttail está en proceso de agregarse a GCC. El parche está en revisión y la semántica es compatible con Clang.

  • Me pregunto qué pasará con el atributo preserve_most. ¿Habrá posibilidad de que algo similar entre en GCC? Sin eso, las llamadas que no son de cola arruinan el intérprete.
  • Es un problema difícil. Muchas ABI no pueden hacer llamadas de cola ni siquiera en casos muy básicos, como llamadas a funciones externas con argumentos y tipo de retorno compatibles.
    Clang parece tener heurísticas que cambian la secuencia de llamada para las llamadas musttail. Por ejemplo, en i686 las convierte en llamadas noplt. Esto no aparece en la documentación de Clang: https://clang.llvm.org/docs/AttributeReference.html#musttail
    En la práctica, lo más viable es que el compilador emita un mensaje de diagnóstico cuando no pueda generar una llamada de cola. Para muchos usuarios, probablemente eso sea suficiente. Garantizar llamadas de cola como en Scheme parece poco probable.
  • GNUC tiene bastantes funciones parecidas a Scheme, así que sorprende que esté atrasado en esta.

• También se menciona el soporte para C++, pero en C++ parece que habría muy pocas llamadas de cola.
  Por ejemplo, foo() { auto a = SomeClassWithADestructor(); return bar(); } no es una llamada de cola, porque después de llamar a bar() ocurre la destrucción de a.

  • Si el compilador pudiera demostrar que no hay efectos secundarios a distancia entre esas líneas, ¿no podría llamar al destructor antes de ejecutar bar?
    Me pregunto si el estándar de C++ exige llamar al destructor al final del bloque, o si permite llamarlo en cuanto la variable ya no se usa.

• Quizá el ejemplo sea demasiado simple, pero no parece que __attribute__((musttail)) sea estrictamente necesario para generar buen código.
  Si la función de manejo de errores está en una ruta poco frecuente, la velocidad de la llamada tampoco debería importar demasiado.
  Una estructura como if (unlikely(malformed)) return error(); switch (data_type) { case x: return handle_x(); case y: return handle_y(); } parece generar de forma bastante confiable una buena tabla de saltos.

  • Es natural que los compiladores eliminen llamadas de cola desde hace mucho, pero para esta técnica “se genera de forma bastante confiable” no alcanza. Tiene que estar garantizado, o la compilación debe fallar.
    De lo contrario, esta estructura no funciona y la pila revienta de inmediato. El punto de [[musttail]] es que la eliminación de llamadas de cola es obligatoria. El compilador no tiene otra opción.
  • Como muestra el desensamblado del artículo, el motivo por el que la ruta de fallback es problemática no es qué tan rápida sea esa llamada en sí. La mera presencia de esa llamada puede hacer que el compilador cree un marco de pila para toda la función y vuelque registros ahí. Eso afecta incluso a la ruta rápida.
    Claro que la expresión “forzar” quizá no sea del todo exacta. No está establecido que el compilador deba tener una única estructura de marco de pila para todas las rutas de ejecución de una función, ni que deba usar la ABI estándar para funciones con enlace interno cuya dirección no se toma o para funciones en namespaces anónimos. Pero todos los compiladores que he visto, incluido Clang, en la práctica lo hacen así. Por eso hace falta una forma de decirle que no se preocupe por la ABI y que no pierda tiempo preservando registros entre llamadas.
    Por supuesto, la tabla de saltos se genera bien. Pero si pasas el resultado por algo como perf report y el bytecode de prueba no representa un bucle corto, verás una de dos cosas: o hay una falla de predicción de rama en cada despacho, o el compilador decide “parece que quieres escribir un intérprete” y mueve el salto indirecto al final de cada case. He visto esto en Clang. En cualquier caso, es muy probable que la asignación de registros del código resultante sea bastante mala.

• Me pregunto qué tan rápido sería usar un trampolín, es decir, devolver la siguiente función como puntero a función y llamarla desde un bucle externo. La ventaja es que es C portable.

  • C se usa con frecuencia como lenguaje destino para compiladores de lenguajes de alto nivel.
    El lenguaje de programación Scheme exige que todas las llamadas de cola no hagan crecer la pila. Por eso sus implementadores han explorado varias técnicas, incluidos los trampolines.
    No tengo una referencia para citar, pero la respuesta puede encontrarse en artículos sobre compilación de Scheme a C. Si el lenguaje destino no garantiza la optimización de llamadas de cola, el programa generado será más lento.
    Además, esta es una de las razones por las que, en particular, los implementadores de lenguajes de alto nivel se quejan de que se haya eliminado la optimización de llamadas de cola de la especificación de JavaScript. También existen soluciones que mantienen tanto la optimización de llamadas de cola como la comprobación de pila.
    https://github.com/schemedoc/bibliography/blob/master/page8....
  • Creo que la optimización de llamadas de cola es rápida porque el bucle resultante es predecible y por eso funcionan bien el prefetch de instrucciones de la CPU y el prefetch de memoria.
    Si se salta mediante un puntero a función, probablemente no sea tan predecible y sea difícil obtener el mismo beneficio.
    Claro que habría que medirlo, y yo todavía no lo he hecho.

• Escribí en C un decodificador/codificador de Protobuf, un parser de IML y bindings para Python, y tengo algo que decir sobre la medición de velocidad de parsing.
  Si esta biblioteca se ofrece solo como bindings para lenguajes administrados, aparece una variable adicional que, en términos de rendimiento, aplasta todo lo demás. No sé en Ruby o PHP, pero en Python vi una mejora de velocidad dramática cuando no se usaban enumeradores. Si se convierten los enumeradores de Protobuf en enumeradores de Python, cualquier ganancia que se pueda obtener en código C queda pisoteada por el tiempo de creación de varios objetos de Python. La diferencia es de varios órdenes de magnitud. Más aún, también se podrían implementar todas las estructuras de datos auxiliares en C y exponer a Python solo una interfaz mínima. Es difícil responder qué tan justa es esa comparación frente a código que usa las estructuras integradas de Python.
  El parser de Protobuf de Google para Python todavía puede ser “más rápido” que más de 2 GB/s. La razón es que no parsea nada salvo el mensaje de nivel superior. La estructura interna del mensaje se parsea cuando hace falta. Si el código lee de inmediato todo lo parseado, probablemente sea más lento que 2 GB/s, pero el problema es cómo comparar de manera práctica estos dos enfoques. Como los resultados reales varían según el tipo de aplicación, no hay una respuesta clara.
  En el caso general, el parsing de Protobuf no se puede hacer en streaming debido al manejo de duplicados. En la práctica, el código que parsea el contenido de Protobuf queda limitado por I/O. Esto se debe a que hay que esperar el final del mensaje antes de empezar a parsear. Por separado, según los mensajes Protobuf típicos de la aplicación, podría ser posible paralelizar el parsing, y entonces probablemente supere a la mayoría de los parsers de un solo hilo. Pero, como en los ejemplos anteriores, no se puede decir que sea una estrategia ganadora en general.
  Normalmente es mucho más eficiente combinar el parsing con la creación de objetos de dominio. Las aplicaciones casi siempre tienen que pasar por este paso. La forma en que se pueda acceder a esta funcionalidad desde el parser determina, en muchos casos, qué parser va a ganar.
  En conclusión, Protobuf, y quizá los parsers en general, no son buenos objetos para medir velocidad y comparar. Son demasiado de bajo nivel y su diseño tampoco es bueno, así que es difícil tomarlos como referencia para benchmarks de rendimiento.

  • No entiendo la parte de que “en el caso general, el parsing de Protobuf no se puede hacer en streaming debido al manejo de duplicados”.
    Me gustaría que explicaran en detalle cómo la regla de que el último campo gana impide el parsing en streaming.

• GCC y Clang tienen desde hace tiempo la opción -foptimize-sibling-calls, así que se podían obtener llamadas de cola incluso en builds de depuración.
  Por supuesto, que esta función se estandarice, esté garantizada y se pueda controlar a nivel de función es una gran mejora.
  [1] https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
  [2] https://clang.llvm.org/docs/ClangCommandLineReference.html#t...