Cómo analizar protobuf a más de 2 GB/s: por qué terminé amando las tail calls en C (2021)

• Tail Call: una llamada a función que se realiza justo antes de que la función retorne. Cuando ocurre la optimización de Tail Call, se usa la instrucción jmp para reducir la pila de llamadas.
• Ventajas:
  • Reduce el uso de memoria de la pila de O(n) a O(1).
  • Elimina el overhead de rendimiento de las llamadas a función, por lo que puede usarse como una estructura eficiente de control iterativo.

Problemas del bucle de intérprete

• Problemas:
  • A medida que la función crece y el flujo de control se vuelve más complejo, es más difícil mantener datos importantes en los registros.
  • Si se mezclan la ruta rápida y la ruta lenta, la calidad del código se degrada.

Mejora del bucle de intérprete usando Tail Call

• Solución: usar Tail Call para separar cada tarea en funciones pequeñas, y que cada función invoque la siguiente tarea mediante Tail Call.
• Ventajas:
  • Permite controlar la asignación de registros.
  • Separa la ruta rápida y la ruta lenta para mantener la calidad del código.
  • Hace posible optimizar secuencias de instrucciones independientes.

Limitaciones

• Problema cuando hay llamadas que no son Tail Call: si existen llamadas que no son Tail Call, se crean stack frames y los datos se guardan en la pila, lo que degrada el rendimiento.
• Manejo de excepciones complejo: cuando el manejo de excepciones es complejo, aumentan la duplicación de código y la complejidad.
• Problemas de portabilidad: como el atributo musttail no es un estándar, no todos los compiladores lo soportan.

Resumen de GN⁺

• La optimización de Tail Call juega un papel importante en la mejora del rendimiento y muestra grandes resultados especialmente en el parsing de Protobuf.
• Esta técnica también puede aplicarse a intérpretes de lenguajes principales escritos en C (Python, Ruby, PHP, Lua, etc.).
• El problema de portabilidad del atributo musttail sigue siendo un reto por resolver.
• Entre los proyectos con funcionalidades similares están el intérprete LuaJIT y wasm3 WebAssembly.

[GN⁺]

Opiniones en Hacker News

• La propuesta del estándar de C incluye llamadas de cola en la forma return goto (expression);

  • A diferencia de estandarizar [[musttail]], esto garantiza la vida útil de los objetos locales y no requiere un análisis de escape amplio

• Para los entusiastas de Rust, hubo un RFC antiguo para agregar la palabra clave become

  • Se pospuso para enfocarse en los objetivos de la edición 2018, pero recientemente volvió a discutirse
  • Podría reaparecer

• En C++, la forma principal en que los intérpretes aceleran la ejecución es usando goto calculado

  • Puede evitar problemas de convención de llamadas
  • Usar estilo de goto calculado o estilo de cola puede reducir la presión sobre el predictor de saltos

• El problema de cambiar de contexto usando llamadas de cola requiere funciones que usen la convención de llamadas

  • Se desperdician registros para restaurar el estado al finalizar la función
  • El blog del remake de luajit ofrece alternativas y análisis

• Se espera que el atributo [[musttail]] llegue a GCC, Visual C++ y otros compiladores populares

  • El atributo [[musttail]] está en proceso de incorporarse a GCC

• Al mencionar el soporte en C++, se señala que en C++ casi no hay llamadas de cola

  • Por ejemplo, devolver un objeto de una clase con destructor no es una llamada de cola

• Se preguntan qué ocurre si una función [[musttail]] de C++ lanza una excepción

  • Preguntan si la pila de excepciones queda completamente separada

• Se menciona que los ejemplos simples no necesitan __attribute__((musttail)) para generar buen código

  • Probablemente no importe demasiado la velocidad de una llamada a una función de manejo de errores
  • Cierta estructura genera una tabla de saltos confiable

• Se preguntan qué tan rápido sería usar un trampolín para llamar en un bucle externo a un puntero de función que se devuelve

  • Este enfoque tiene la ventaja de ser C portable

• Hay una petición para aclarar un ejemplo de una ruta de excepción envuelta con [[musttail]]

  • Se explica por qué [[musttail]] evita la creación de marcos de pila y el volcado de registros
  • La creación del marco de pila y el volcado de registros solo ocurren cuando realmente se llama a la ruta de excepción
  • Como la ruta de excepción se llama rara vez, no afecta mucho el rendimiento
  • Debido a los efectos de la predicción de saltos, la posibilidad de trabajo adicional puede volver más lenta la ruta rápida