Cómo crear un intérprete rápido para un lenguaje dinámico

• Incluso un intérprete que recorre el AST directamente puede lograr grandes mejoras de rendimiento solo con representación de valores, cachés en línea, modelo de objetos, watchpoints y optimizaciones iterativas de detalle
• La línea base de Zef, casi sin considerar el rendimiento, era 35 veces más lenta que CPython 3.10, 80 veces más lenta que Lua 5.4.7 y 23 veces más lenta que QuickJS-ng 0.14.0, pero tras 21 etapas de optimización logró una aceleración de 16.646 veces
• El mayor salto se produjo al rediseñar el modelo de objetos y combinarlo con cachés en línea; luego, el acceso basado en Storage y Offsets, la especialización cacheada del AST y la aplicación de watchpoints para vigilar sobreescrituras de nombres aportaron una mejora adicional de 4.55 veces
• Otras mejoras acumuladas incluyeron eliminar el dispatch basado en cadenas, introducir Symbol, cambiar la estructura de paso de argumentos, especializar getter y setter, usar rutas cortas en la tabla hash, y especializar literales de arreglo junto con sqrt y toString
• Incluyendo el port a Yolo-C++, registró una velocidad 66.962 veces mayor que la línea base; es 1.889 veces más rápido que CPython 3.10 y 2.968 veces más rápido que QuickJS-ng 0.14.0, pero no es apto para cargas de trabajo de larga duración porque no libera memoria

---

Introducción y metodología de evaluación

• El objetivo de la optimización es un intérprete que recorre el AST directamente, con la meta de llevar el lenguaje dinámico Zef, creado por diversión, a un nivel capaz de competir con Lua, QuickJS y CPython
  • Más que centrarse en compiladores JIT o en el ajuste fino de un GC maduro, se enfoca en optimizaciones aplicables incluso partiendo sin bases previas
  • Las técnicas tratadas son representación de valores, caché en línea, modelo de objetos, watchpoint y aplicación repetida de optimizaciones sensatas
• Solo con las técnicas del artículo se logró una gran mejora de rendimiento sin SSA, GC, bytecode ni código máquina
  • 16 veces de aceleración según el contenido principal
  • 67 veces de aceleración al incluir el port incompleto a Yolo-C++
• La evaluación de rendimiento usa la suite de benchmarks ScriptBench1
  • Los benchmarks incluidos son Richards OS scheduler, DeltaBlue constraint solver, N-Body physics simulation y Splay binary tree test
  • Se usaron ports existentes para JavaScript, Python y Lua
  • Los ports de Python y Lua de Splay fueron generados con Claude
• El entorno experimental es Ubuntu 22.04.5, Intel Core Ultra 5 135U, 32GB RAM, Fil-C++ 0.677
  • Lua 5.4.7 fue compilado con GCC 11.4.0
  • QuickJS-ng 0.14.0 usó el binario de GitHub releases
  • CPython 3.10 usó la versión provista por Ubuntu
• En todos los experimentos se usó el promedio de 30 ejecuciones mezcladas aleatoriamente
• La mayoría de las comparaciones se realizó entre el intérprete Zef compilado con Fil-C++ y otros intérpretes construidos con el compilador Yolo-C

El intérprete original de Zef

• Se indica que fue escrito casi sin considerar el rendimiento, y que solo hubo dos decisiones tomadas conscientemente con ese fin

• Representación de valores

  • Usa tagged value de 64 bits
    • Los valores que puede contener son double, entero de 32 bits y Object*
  • Los double se representan con un desplazamiento de 0x1000000000000
    • Se presenta como una técnica aprendida de JavaScriptCore
    • En la literatura se la denomina NuN tagging
  • Los enteros y punteros usan su representación nativa
    • Depende de la suposición de que el valor del puntero no será menor que 0x100000000
    • Se indica explícitamente que es una elección arriesgada
    • Se menciona que una alternativa habría sido poner a los enteros una etiqueta en bits altos de 0xffff000000000000
  • Esta representación permite implementar una ruta rápida basada en pruebas de bits para operaciones numéricas
  • Una ventaja aún más importante es evitar la asignación en heap para números
  • Al crear un intérprete nuevo, es importante elegir bien desde el inicio la representación básica de valores, ya que cambiarla después es muy difícil
  • Se propone como punto de partida para implementar un lenguaje de tipado dinámico un tagged value de 32 o 64 bits

• Elección del lenguaje de implementación

  • Se eligió una variante de C++ como lenguaje capaz de incorporar suficiente optimización
  • Se indica explícitamente que no elegiría Java por su límite en optimizaciones de bajo nivel
  • También explica que no elegiría Rust debido al estado global mutable y a la representación de heap con referencias cíclicas necesarias para implementar un lenguaje con GC
    • Menciona que podría usarse Rust en parte o en todo si se acepta una configuración multilenguaje o mucho código unsafe

• Decisiones equivocadas desde la perspectiva de ingeniería de rendimiento

  • Uso de Fil-C++
    • Permitía desarrollar rápido y ofrecía GC gratis
    • Reporta violaciones de seguridad de memoria con información de diagnóstico y stack trace
    • No hay comportamiento indefinido
    • El costo en rendimiento suele ser de alrededor de 4 veces
  • Intérprete recursivo que recorre el AST
    • Estructura basada en el método virtual Node::evaluate sobrescrito en múltiples lugares
  • Abuso de cadenas
    • El nodo AST Get guarda un std::string que describe el nombre de la variable
    • Esa cadena se usa en cada acceso a variable
  • Abuso de tablas hash
    • Al ejecutar Get, se consulta un std::unordered_map con una clave de tipo cadena
  • Búsqueda de scopes basada en cadenas de llamadas recursivas
    • Permite anidamiento y closures en casi cualquier estructura
    • En un anidamiento como función F dentro de la clase A y función G dentro de la clase B, un método de A puede ver campos de A, variables locales de F, campos de B y variables locales de G
    • La implementación original resolvía esto con funciones recursivas de C++ que consultaban distintos objetos de scope

• Características de la implementación original

  • A pesar de las malas decisiones, fue posible implementar con poco código un intérprete de lenguaje bastante complejo
  • El módulo más grande es el parser
  • El resto es relativamente simple y claro

• Rendimiento inicial

  • El intérprete original era 35 veces más lento que CPython 3.10

  • 80 veces más lento que Lua 5.4.7

    • 23 veces más lento que QuickJS-ng 0.14.0

Tabla general del progreso de optimización

• La tabla resume los cambios de rendimiento desde Zef Baseline hasta Zef Change #21: No Asserts, y también Zef in Yolo-C++
  • Las columnas de comparación son vs Zef Baseline, vs Python 3.10, vs Lua 5.4.7, vs QuickJS-ng 0.14.0
• En la fila final, Zef Change #21: No Asserts es 16.646 veces más rápido que la línea base

  • 2.13 veces más lento que Python 3.10

  • 4.781 veces más lento que Lua 5.4.7

    • 1.355 veces más lento que QuickJS-ng 0.14.0

• Zef in Yolo-C++** es 66.962 veces más rápido que la línea base

  • 1.889 veces más rápido que Python 3.10

  • 1.189 veces más lento que Lua 5.4.7

    • 2.968 veces más rápido que QuickJS-ng 0.14.0

Etapa inicial de optimización

• Optimización #1: llamada directa de operadores

  • El parser ya no crea operadores como nodos DotCall con nombre de operador, sino que genera nodos AST separados para cada operador
  • En Zef, a + b y a.add(b) son lo mismo
    • Originalmente, a + b se parseaba como DotCall(a, "add") con el argumento b
    • En cada operación aritmética ocurría una búsqueda del string con el nombre del método del operador
    • DotCall pasaba el string a Value::callMethod
    • Value::callMethod hacía múltiples comparaciones de strings
  • Después del cambio, el parser genera nodos Binary<> y Unary<>
    • Usando templates y lambdas, se proveen overrides distintos de Node::evaluate para cada operador
    • Cada nodo llama directamente a la ruta rápida de Value para ese operador
    • Por ejemplo, a + b llama a Binary<lambda for add>::evaluate y luego a Value::add
  • El efecto en rendimiento fue una mejora de 17.5%
    • En este punto, el rendimiento era 30 veces más lento que CPython 3.10
    • 67 veces más lento que Lua 5.4.7
    • 19 veces más lento que QuickJS-ng 0.14.0

• Optimización #2: llamada directa de operadores RMW

  • Los operadores normales se aceleraron, pero las formas RMW como a += b seguían usando dispatch basado en strings
  • Se cambió el parser para que generara nodos separados para cada caso RMW
  • El parser pide que el nodo LValue se reemplace a sí mismo como RMW mediante una llamada virtual makeRMW
  • Los LValue que se convierten en RMW son Get, Dot y Subscript
    • Get corresponde a lectura de variable id
    • Dot corresponde a expr.id
    • Subscript corresponde a expr[index]
  • Cada llamada virtual usa el macro SPECIALIZE_NEW_RMW
    • SetRMW es id += value
    • DotSetRMW es expr.id += value
    • SubscriptRMW es expr[index] += value
  • La especialización de operadores del cambio #1 usa dispatch con lambdas
  • Para RMW se usa un enum
    • Se eligió así porque había que manejar las tres rutas get, dot y subscript, y pasar el enum por varios lugares
    • Al final, la función template Value::callRMW<> hace el dispatch real de la llamada al operador RMW
  • El efecto en rendimiento fue una mejora de 3.7%
    • En este punto, el rendimiento era 29 veces más lento que CPython 3.10
    • 65 veces más lento que Lua 5.4.7
    • 18.5 veces más lento que QuickJS-ng 0.14.0
    • 1.22 veces más rápido que el punto de partida

• Optimización #3: evitar la verificación de IntObject

  • Un cuello de botella era que la ruta rápida de Value usaba isInt(), y su isIntSlow() interno hacía una llamada virtual a Object::isInt()
  • La representación original de valores tenía cuatro casos
    • tagged int32
    • tagged double
    • IntObject para int64 que no pueden representarse como int32
    • todos los demás objetos
  • Incluso en el caso de IntObject, el dispatch de métodos enteros estaba a cargo de Value
    • Esto era para mantener todas las implementaciones de operaciones aritméticas en un solo lugar: Value
  • Después de la optimización, la ruta rápida de Value solo considera int32 y double
    • La lógica de manejo de IntObject se movió al propio IntObject
    • Se evitó la llamada a isInt() que ocurría en cada dispatch de método
  • El efecto en rendimiento fue una mejora de 1%
    • En este punto, el rendimiento era 29 veces más lento que CPython 3.10
    • 65 veces más lento que Lua 5.4.7
    • 18 veces más lento que QuickJS-ng 0.14.0
    • 1.23 veces más rápido que el punto de partida

• Optimización #4: Symbol

  • Originalmente, el intérprete usaba std::string en casi todas partes
  • Los lugares donde usar strings resultaba costoso eran Context::get, Context::set, Context::callFunction, Value::callMethod, Value::dot, Value::setDot, Value::callOperator<>, y la familia de Object::callMethod
  • Con esta estructura, en vez de hacer una simple búsqueda en hash table, se hacía una búsqueda en hash table con claves string, repitiendo durante la ejecución hashing y comparación de strings
  • La optimización reemplazó las búsquedas basadas en strings por punteros a objetos Symbol con hash-consing
  • Se agregó una nueva clase Symbol
    • Implementada en symbol.h y symbol.cpp
    • Symbol y string pueden convertirse mutuamente
    • Al convertir un string a Symbol, se hace hash consing con una hash table global
    • Como resultado, basta con comparar la identidad de punteros Symbol* para determinar si es el mismo símbolo
  • En lugar de literales string, se usan símbolos preparados de antemano
    • Por ejemplo, en lugar de "subscript", se usa Symbol::subscript
  • Muchas firmas de funciones cambiaron de const std::string& a Symbol*
  • El efecto en rendimiento fue una mejora de 18%
    • En este punto, el rendimiento era 24 veces más lento que CPython 3.10
    • 54 veces más lento que Lua 5.4.7
    • 15 veces más lento que QuickJS-ng 0.14.0
    • 1.46 veces más rápido que el punto de partida

• Optimización #5: inlining de Value

  • La clave fue permitir el inlining de funciones importantes
  • Casi todos los cambios giran en torno a la introducción del nuevo header valueinlines.h
  • La razón de separarlo de value.h en otro header es que usa headers que necesitan incluir value.h
  • El efecto en rendimiento fue una mejora de 2.8%
    • En este punto, el rendimiento era 24 veces más lento que CPython 3.10
    • 53 veces más lento que Lua 5.4.7
    • 15 veces más lento que QuickJS-ng 0.14.0
    • 1.5 veces más rápido que el punto de partida

Rediseño del modelo de objetos y la estructura de caché

• Optimización #6: modelo de objetos, caché inline y watchpoint

  • Se reorganizó a gran escala cómo funcionan Object, ClassObject y Context para reducir el costo de asignación de objetos y evitar búsquedas en tablas hash durante el acceso
  • Este cambio combina tres funciones: modelo de objetos, caché inline y watchpoint

• Modelo de objetos

  • Antes se asignaba un objeto Context para cada ámbito léxico
    • Cada Context tenía una tabla hash con las variables de ese ámbito
  • Los objetos tenían una estructura más compleja
    • Cada objeto tenía una tabla hash que mapeaba las clases de las que es instancia a Context
  • Esta estructura era necesaria por la herencia y los ámbitos anidados
    • Cuando Bar hereda de Foo, Bar y Foo hacen closure sobre ámbitos distintos
    • También pueden tener campos privados distintos con el mismo nombre
  • La nueva estructura introduce el concepto de Storage
    • Los datos se almacenan según Offsets
    • El offset lo determina algún Context
  • Context sigue existiendo, pero se crea de antemano en el pase resolve del AST en lugar de hacerlo al crear el objeto o el ámbito
  • Cuando realmente se crea un objeto o ámbito, solo se asigna Storage según el tamaño calculado por ese Context

• Caché inline

  • Técnica que recuerda el tipo dinámico de expr visto por última vez y el último offset al que se resolvió name en una ubicación de código como expr.name
  • Es una técnica clásica que suele explicarse en el contexto de JIT, pero aquí se aplica al intérprete
  • La información recordada se implementa construyendo con placement construct nodos AST especializados sobre el nodo AST normal

• Componentes de la caché inline

  • CacheRecipe
    • Rastrea qué hizo un acceso específico y si se puede cachear
  • Se insertaron llamadas a CacheRecipe en varios puntos de Context, ClassObject y Package
    • Recolectan información del proceso de acceso
  • Funciones de evaluación de AST como Dot::evaluate pasan el CacheRecipe obtenido de la operación polimórfica que realizaron, junto con this, a constructCache<>
  • constructCache
    • Compila una nueva especialización de nodo AST según CacheRecipe
    • Genera varios nodos AST especializados con maquinaria de plantillas
    • Si es acceso a una variable local, hace una carga directa desde el storage recibido
    • Verifica con un class check si es la misma clase vista por última vez
    • Después hace una llamada directa a función a la última función vista
    • Si hace falta, combina chain step y watchpoint
  • Cada nodo AST que puede cachearse tiene su propia variante cacheada
    • Primero intenta una llamada rápida mediante el objeto cache
    • El tipo del objeto cache lo determina constructCache<>

• watchpoint

  • Se muestra un ejemplo con una variable x en un ámbito léxico, una clase Foo dentro de ese ámbito y un método de Foo que accede a x
  • Si dentro de Foo no existe una función o variable llamada x, parecería que puede leer directamente la x exterior
  • Sin embargo, una subclase podría agregar un getter x
  • En ese caso, el resultado del acceso debería ser ese getter, no la x exterior
  • Para manejar esta posibilidad de cambio, la caché inline instala un Watchpoint en tiempo de ejecución
  • En el ejemplo se usa un watchpoint para vigilar si ese nombre fue sobreescrito

• Por qué se implementaron las tres funciones al mismo tiempo

  • Solo con el nuevo modelo de objetos es difícil lograr una mejora significativa si la caché inline no funciona bien
  • La caché inline tampoco aporta mucho sin watchpoint, porque es difícil manejar de forma segura muchas condiciones de caché
  • El nuevo modelo de objetos y watchpoint deben funcionar bien en conjunto

• Progreso de implementación y partes difíciles

  • Se comenzó escribiendo una versión simple de CacheRecipe y diseñando Storage y Offsets cercanos a la forma final
  • Una de las tareas más difíciles fue reemplazar la forma de implementar las clases intrínsecas
  • Ejemplo con arreglos
    • Antes, ArrayObject::tryCallMethod implementaba todos los métodos interceptando la llamada virtual a Object::tryCallMethod
    • En el nuevo modelo de objetos, Object ya no tiene vtable ni métodos virtuales
    • En su lugar, Object::tryCallMethod delega a object->classObject()->tryCallMethod(object, ...)
    • Por lo tanto, para ofrecer métodos de Array, fue necesario crear la propia clase de Array con esos métodos
  • Como resultado, gran parte de la funcionalidad intrínseca pasó de estar dispersa por toda la implementación a concentrarse en makerootcontext.cpp
  • Se consideró un resultado positivo porque la caché inline también se aplica sin cambios a las funciones nativas/intrínsecas de los objetos
  • El efecto en rendimiento fue de una mejora de 4.55x
    • En este punto el rendimiento era 5.2 veces más lento que CPython 3.10
    • 11.7 veces más lento que Lua 5.4.7
    • 3.3 veces más lento que QuickJS-ng 0.14.0
    • 6.8 veces más rápido que el punto de partida
    • Se evaluó que la desventaja de Fil-C++ frente a otros intérpretes se redujo, en general, hasta un nivel equivalente al costo propio de Fil-C

Optimización de llamadas y rutas de acceso

• Optimización #7: Mejora de la estructura de paso de argumentos

  • Antes del cambio, el intérprete de Zef pasaba los argumentos de función como const std::optional<std::vector<Value>>&
  • La razón por la que se necesitaba optional era que en algunos casos límite había que distinguir entre estas dos cosas
    • o.getter
    • o.function()
  • En Zef, por lo general ambas son llamadas de función, pero existe esta excepción
    • o.NestedClass
    • o.NestedClass()
  • La primera devuelve el objeto NestedClass en sí
  • La segunda crea una instancia
  • Por lo tanto, hay que distinguir entre una llamada de función sin argumentos y una llamada tipo getter en la que el arreglo de argumentos está vacío
  • Sin embargo, la estructura anterior era ineficiente
    • El llamador hacía una asignación de vector
    • El llamado volvía a asignar un arguments scope que era una copia de ese vector
  • El cambio introduce el tipo Arguments
    • Su forma es exactamente igual al arguments scope que antes creaba el llamado
    • Ahora el llamador lo asigna directamente en esa forma
  • También en Yolo-C++ se redujo la cantidad de asignaciones al eliminar el malloc del backing store del vector
  • En Fil-C++, std::optional en sí se asigna en el heap
    • Incluso sin std::optional, pasar const std::vector<>& también implica asignación
    • Lo que se asigna en la pila se marca como si se asignara en el heap
    • También se menciona que, del lado del llamador, el vector no se dimensionaba previamente y por eso se reasignaba varias veces
  • Gran parte del cambio consistió en reemplazar firmas de función por Arguments*
  • El efecto en rendimiento fue una mejora de 1.33x
    • En este punto, el rendimiento era 3.9 veces más lento que CPython 3.10
    • 8.8 veces más lento que Lua 5.4.7
    • 2.5 veces más lento que QuickJS-ng 0.14.0
    • 9.05 veces más rápido que el punto de partida

• Optimización #8: Especialización de getters

  • Zef, al igual que Ruby, tiene los campos de instancia privados por defecto
  • Ejemplo: class Foo { my f fn (inF) f = inF }
    • Guarda el valor recibido en el constructor en la variable local f, visible solo para la instancia
  • Incluso instancias del mismo tipo no pueden acceder a la f de otro objeto
    • Ejemplo: fn nope(o) o.f
    • println(Foo(42).nope(Foo(666)))
    • La o.f dentro de nope no puede acceder a la f de o
  • La razón es que los campos funcionan según la forma en que aparecen en la cadena de scopes de los miembros de la clase
    • o.f no es una lectura de campo, sino una solicitud de llamada a un método llamado f
  • Por eso aparece con frecuencia este patrón
    • my f
    • fn f f
    • Es decir, un método llamado f que devuelve la variable local f
  • Existe una sintaxis más corta: readable f
    • Es la forma abreviada de my f y fn f f
  • Muchas llamadas de método son en la práctica llamadas a getters
  • Es un desperdicio que todos los getters funcionen evaluando el AST
  • La optimización es la especialización de getters
    • Su centro es UserFunction
    • Con el nuevo método Node::inferGetter, se infiere si el cuerpo de la función es un getter simple
  • Reglas de inferencia
    • Block::inferGetter se infiere como getter si todo lo que contiene también puede inferirse como getter
    • Get::inferGetter se infiere a sí mismo como getter y devuelve el offset que debe cargarse
    • Context::tryGetFieldOffsets devuelve un Offsets no vacío solo cuando ese campo definitivamente existe en el scope léxico donde se ejecutará el getter
    • UserFunction, si el cuerpo de la función puede inferirse como getter, se resuelve como una subclase especial de Function que solo lee directamente desde un offset conocido
  • El efecto en rendimiento fue una mejora de 5.6%
    • En este punto, el rendimiento era 3.7 veces más lento que CPython 3.10
    • 8.3 veces más lento que Lua 5.4.7
    • 2.4 veces más lento que QuickJS-ng 0.14.0
    • 9.55 veces más rápido que el punto de partida

• Optimización #9: Especialización de setters

  • En la inferencia de setters se necesita hacer pattern matching del patrón fn set_fieldName(newValue) fieldName = newValue
  • En la etapa de inferencia de UserFunction, hay que pasar el nombre del parámetro del setter
  • En la etapa de inferencia de Set, hay que verificar que no sea una escritura sobre ClassObject y también confirmar que el parámetro del setter se use como fuente del set
  • El efecto en rendimiento fue una mejora de 3.4%
    • En este punto, Zef era 3.6 veces más lento que CPython 3.10
    • 8 veces más lento que Lua 5.4.7
    • 2.3 veces más lento que QuickJS-ng 0.14.0
    • 9.87 veces más rápido que el punto de partida

• Optimización #10: Inlining de callMethod

  • Se hizo inline una función importante con un cambio de una sola línea
  • El efecto en rendimiento fue una mejora de 3.2%
    • En este punto, Zef era 3.5 veces más lento que CPython 3.10
    • 7.8 veces más lento que Lua 5.4.7
    • 2.2 veces más lento que QuickJS-ng 0.14.0
    • 10.2 veces más rápido que el punto de partida

• Optimización #11: Tabla hash

  • Cuando ocurría un inline cache miss en una llamada de método, había que bajar por ClassObject::tryCallMethod y ClassObject::TryCallMethodDirect, y ambas rutas eran grandes y complejas
  • El costo de búsqueda anterior era O(profundidad de la jerarquía)
    • En cada clase de la jerarquía se hacía una búsqueda en tabla hash para comprobar si la llamada se resolvía como función miembro
    • En cada clase de la jerarquía también se hacía una búsqueda en tabla hash para comprobar si la llamada se resolvía como clase anidada
  • El nuevo cambio introduce una tabla hash global que usa como clave la clase receptora y el símbolo
    • Con una sola búsqueda devuelve directamente el callee
    • En classobject.h, antes de bajar hasta tryCallMethodSlow, primero se consulta esta tabla global
    • En classobject.cpp, los resultados de búsquedas exitosas se registran en la tabla global
    • La implementación de la tabla hash global en sí es relativamente simple
  • El efecto en rendimiento fue una mejora de 15%
    • En este punto, Zef era 3 veces más lento que CPython 3.10
    • 6.8 veces más lento que Lua 5.4.7
    • 1.9 veces más lento que QuickJS-ng 0.14.0
    • 11.8 veces más rápido que el punto de partida

• Optimización #12: Evitar std::optional

  • En Fil-C++, std::optional necesita asignación en heap debido a una patología del compilador relacionada con union
  • En general LLVM maneja con flexibilidad los tipos de acceso a memoria de union, pero esto choca con invisicaps
    • Ocurre que los punteros dentro de un union pierden capacidades de manera difícil de predecir desde la perspectiva del programador
    • Como resultado, en Fil-C puede ocurrir un pánico por dereferenciar un objeto con null capability incluso sin error del programador
  • Para mitigar esto, el compilador de Fil-C++ inserta intrinsics para que LLVM actúe de forma conservadora al manejar variables locales de tipo union
  • Después, el pase FilPizlonator intenta hacer su propio escape analysis para volver posibles las asignaciones en registros de variables locales de tipo union
    • Sin embargo, este análisis no es tan completo como el análisis SROA general de LLVM
  • Como resultado, pasar clases que incluyen union, como std::optional, con frecuencia termina provocando asignaciones de memoria en Fil-C++
  • Este cambio evita las rutas de código que en el hot path llevan a std::optional
  • El efecto en rendimiento fue una mejora de 1.7%
    • En este punto, Zef era 3 veces más lento que CPython 3.10
    • 6.65 veces más lento que Lua 5.4.7
    • 1.9 veces más lento que QuickJS-ng 0.14.0

• 12 veces más rápido que el punto de partida

• Optimización #13: argumentos especializados

  • Todas las funciones built-in de Zef reciben 1 o 2 argumentos, y en la implementación nativa no hace falta asignar un objeto Arguments para contenerlos
  • Los setter también reciben siempre un solo argumento y, cuando se ha realizado la inferencia del setter, una implementación de setter especializada también basta con recibir directamente el argumento de valor sin un objeto Arguments
  • Con este cambio se introducen los tipos de argumentos especializados ZeroArguments, OneArgument y TwoArguments
    • Si el callee no lo necesita, el caller puede evitar asignar un objeto Arguments
  • Se necesita ZeroArguments para distinguirlo de (Arguments*)nullptr
    • Antes se usaba (Arguments*)nullptr con el significado de llamada a getter, y se mantiene esa lógica
    • Ahora ZeroArguments significa llamada a función sin argumentos
  • Muchos de los cambios consisten en convertir en plantillas las funciones que reciben argumentos
    • Se realiza una instanciación explícita para ZeroArguments, OneArgument, TwoArguments y Arguments*
    • Gran parte del código existente usaba Value::getArg como helper para extraer argumentos, y aquí se añaden overloads de argumentos especializados
    • Los cambios en el código nativo que usa argumentos fueron modificaciones relativamente directas
  • El efecto en rendimiento es una mejora del 3.8%
    • En este punto, Zef es 2.9 veces más lento que CPython 3.10
    • 6.4 veces más lento que Lua 5.4.7
    • 1.8 veces más lento que QuickJS-ng 0.14.0
    • 12.4 veces más rápido que el punto de partida

Evasión de patologías de Fil-C y especialización detallada

• Optimización #14: mejora de la slow path de Value

  • Se logró una gran mejora de velocidad con otra evasión de una patología de Fil-C
  • Antes del cambio, la slow path out-of-line de Value era una función miembro de Value y requería un argumento implícito const Value*
  • En esta estructura, el caller tenía que asignar Value en la pila
  • En Fil-C++, toda asignación en la pila es asignación en el heap
    • Por lo tanto, el código que llamaba a la slow path asignaba Value en el heap
  • Después del cambio, estos métodos se volvieron static y Value se pasa por valor
    • Como resultado, ya no se necesita una asignación separada
  • El efecto en rendimiento fue una mejora de 10%
    • En este punto, Zef era 2.6 veces más lento que CPython 3.10
    • 5.8 veces más lento que Lua 5.4.7
    • 1.65 veces más lento que QuickJS-ng 0.14.0
    • 13.6 veces más rápido que el punto de partida

• Optimización #15: eliminación de duplicación en DotSetRMW

  • Se eliminó algo de código duplicado
  • Se esperaba que la reducción de código máquina ayudara en las funciones plantilla especializadas por constructCache<>
  • El resultado real fue ningún impacto en el rendimiento

• Optimización #16: especialización de sqrt

  • El inline cache enruta bien las llamadas hacia la función deseada, pero solo funciona con objetos
  • En los no-objetos, las fast path de Binary<>, Unary<> y Value::callRMW<> dependen de verificar si el receiver es int o double
  • Este enfoque solo se aplica a operadores reconocidos por el parser
    • No se aplica a formas como value.sqrt
  • Con este cambio, Dot puede especializarse para value.sqrt
  • El efecto en rendimiento fue una mejora de 1.6%
    • En este punto, Zef era 2.6 veces más lento que CPython 3.10
    • 5.75 veces más lento que Lua 5.4.7
    • 1.6 veces más lento que QuickJS-ng 0.14.0
    • 13.8 veces más rápido que el punto de partida

• Optimización #17: especialización de toString

  • Se aplicó la especialización de toString casi del mismo modo que la optimización anterior
  • Este cambio incluye lógica para reducir la cantidad de asignaciones al convertir int a cadena
  • El efecto en rendimiento fue una mejora de 2.7%
    • En este punto, Zef era 2.5 veces más lento que CPython 3.10
    • 5.6 veces más lento que Lua 5.4.7
    • 1.6 veces más lento que QuickJS-ng 0.14.0
    • 14.2 veces más rápido que el punto de partida

• Optimización #18: especialización de literales de arreglo

  • Código como my whatever = [1, 2, 3] requiere asignar un nuevo arreglo en Zef porque los arreglos pueden tener alias y ser mutables
  • Antes del cambio, en cada ejecución se recorría el AST hacia abajo y se evaluaban recursivamente 1, 2, 3 cada vez
  • Este cambio especializa el nodo ArrayLiteral para el caso de asignación de un arreglo constante
  • El efecto en rendimiento fue una mejora de 8.1%
    • En este punto, Zef era 2.3 veces más lento que CPython 3.10
    • 5.2 veces más lento que Lua 5.4.7
    • 1.5 veces más lento que QuickJS-ng 0.14.0
    • 15.35 veces más rápido que el punto de partida

• Optimización #19: mejora de Value::callOperator

  • La misma optimización que antes mejoró la velocidad al no pasar Value por referencia también se aplicó a la slow path de callOperator
  • El efecto en rendimiento fue una mejora de 6.5%
    • En este punto, Zef era 2.2 veces más lento que CPython 3.10
    • 4.9 veces más lento que Lua 5.4.7
    • 1.4 veces más lento que QuickJS-ng 0.14.0
    • 16.3 veces más rápido que el punto de partida

• Optimización #20: mejores opciones de C++

  • En Fil-C++ se desactivaron RTTI y el hardening de libc++ que no eran necesarios
  • No hubo cambios en el código C++ en sí; solo cambios de configuración del sistema de build
  • El efecto en rendimiento fue una mejora de 1.8%
    • En este punto, Zef era 2.1 veces más lento que CPython 3.10
    • 4.8 veces más lento que Lua 5.4.7
    • 1.35 veces más lento que QuickJS-ng 0.14.0
    • 16.6 veces más rápido que el punto de partida

• Optimización #21: desactivación de assert

  • Como última optimización, se aplicó la desactivación predeterminada de assertions
  • El código existente usaba la macro ZASSERT específica de Fil-C
    • Una estructura que siempre ejecutaba asserts
  • Después del cambio se usa la macro interna ASSERT
    • Los asserts solo se ejecutan cuando ASSERTS_ENABLED está configurado
  • Este cambio también incluyó otras modificaciones para que el código pudiera compilarse con Yolo-C++
  • Contra lo esperado, no hubo mejora de velocidad

Resultados y límites de Yolo-C++

• Al compilar el código con Yolo-C++, se obtuvo una mejora de velocidad de 4 veces
• Sin embargo, este enfoque no es sound y es suboptimal
  • No es sound porque las llamadas al GC de Fil-C++ existentes se convierten en llamadas a calloc
  • Como resultado, la memoria no se libera y, en cargas de trabajo que se ejecutan durante suficiente tiempo, el intérprete termina agotando la memoria
  • En ScriptBench1, el tiempo de prueba es corto, así que no ocurre agotamiento de memoria
• Es suboptimal porque el asignador real del GC es más rápido que calloc de glibc 2.35
• Por lo tanto, se menciona que si se agrega el GC real al port de Yolo-C++, podría lograrse una mejora aún mayor que 4 veces
• En este experimento se usó GCC 11.4.0
• En este punto, Zef era

  • 1.9 veces más rápido que CPython 3.10

  • 1.2 veces más lento que Lua 5.4.7

  • 3 veces más rápido que QuickJS-ng 0.14.0

    • 67 veces más rápido que el punto de partida

Datos de referencia sin procesar

• La unidad del tiempo de ejecución de los benchmarks es segundos
• La tabla incluye nbody, splay, richards, deltablue y geomean para cada intérprete

• Python 3.10

  • nbody 0.0364
  • splay 0.8326
  • richards 0.0822
  • deltablue 0.1135
  • geomean 0.1296

• Lua 5.4.7

  • nbody 0.0142
  • splay 0.4393
  • richards 0.0217
  • deltablue 0.0832
  • geomean 0.0577

• QuickJS-ng 0.14.0

  • nbody 0.0214
  • splay 0.7090
  • richards 0.7193
  • deltablue 0.1585
  • geomean 0.2036

• Zef Baseline

  • nbody 2.9573
  • splay 13.0286
  • richards 1.9251
  • deltablue 5.9997
  • geomean 4.5927

• Zef Cambio #1: Operadores directos

  • nbody 2.1891
  • splay 12.0233
  • richards 1.6935
  • deltablue 5.2331
  • geomean 3.9076

• Zef Cambio #2: RMW directos

  • nbody 2.0130
  • splay 11.9987
  • richards 1.6367
  • deltablue 5.0994
  • geomean 3.7677

• Zef Cambio #3: Evitar IntObject

  • nbody 1.9922
  • splay 11.8824
  • richards 1.6220
  • deltablue 5.0646
  • geomean 3.7339

• Zef Cambio #4: Símbolos

  • nbody 1.5782
  • splay 9.9577
  • richards 1.4116
  • deltablue 4.4593
  • geomean 3.1533

• Zef Cambio #5: Valor inline

  • nbody 1.4982
  • splay 9.7723
  • richards 1.3890
  • deltablue 4.3536
  • geomean 3.0671

• Zef Cambio #6: Modelo de objetos y cachés inline

  • nbody 0.3884
  • splay 3.3609
  • richards 0.2321
  • deltablue 0.6805
  • geomean 0.6736

• Zef Cambio #7: Argumentos

  • nbody 0.3160
  • splay 2.6890
  • richards 0.1653
  • deltablue 0.4738
  • geomean 0.5077

• Zef Cambio #8: Getters

  • nbody 0.2988
  • splay 2.6919
  • richards 0.1564
  • deltablue 0.4260
  • geomean 0.4809

• Zef Cambio #9: Setters

  • nbody 0.2850
  • splay 2.6690
  • richards 0.1514
  • deltablue 0.4072
  • geomean 0.4651

• Zef Cambio #10: callMethod inline

  • nbody 0.2533
  • splay 2.6711
  • richards 0.1513
  • deltablue 0.4032
  • geomean 0.4506

• Zef Cambio #11: Tabla hash

  • nbody 0.1796
  • splay 2.6528
  • richards 0.1379
  • deltablue 0.3551
  • geomean 0.3906

• Zef Cambio #12: Evitar std::optional

  • nbody 0.1689
  • splay 2.6563
  • richards 0.1379
  • deltablue 0.3518
  • geomean 0.3839

• Zef Cambio #13: Argumentos especializados

  • nbody 0.1610
  • splay 2.5823
  • richards 0.1350
  • deltablue 0.3372
  • geomean 0.3707

• Zef Cambio #14: Rutas lentas de Value mejoradas

  • nbody 0.1348
  • splay 2.5062
  • richards 0.1241
  • deltablue 0.3076
  • geomean 0.3367

• Zef Cambio #15: DotSetRMW::evaluate deduplicado

  • nbody 0.1342
  • splay 2.5047
  • richards 0.1256
  • deltablue 0.3079
  • geomean 0.3375

• Zef Cambio #16: sqrt rápido

  • nbody 0.1274
  • splay 2.5045
  • richards 0.1251
  • deltablue 0.3060
  • geomean 0.3322

• Zef Cambio #17: toString rápido

  • nbody 0.1282
  • splay 2.2664
  • richards 0.1275
  • deltablue 0.2964
  • geomean 0.3235

• Zef Cambio #18: Especialización de literales de arreglo

  • nbody 0.1295
  • splay 1.6661
  • richards 0.1250
  • deltablue 0.2979
  • geomean 0.2992

• Zef Cambio #19: Optimización de callOperator de Value

  • nbody 0.1208
  • splay 1.6698
  • richards 0.1143
  • deltablue 0.2713
  • geomean 0.2810

• Zef Cambio #20: Mejor configuración de C++

  • nbody 0.1186
  • splay 1.6521
  • richards 0.1127
  • deltablue 0.2635
  • geomean 0.2760

• Zef Cambio #21: Sin asserts

  • nbody 0.1194
  • splay 1.6504
  • richards 0.1127
  • deltablue 0.2619
  • geomean 0.2759

• Zef en Yolo-C++

  • nbody 0.0233
  • splay 0.3992
  • richards 0.0309
  • deltablue 0.0784
  • geomean 0.0686

[GN⁺]

Comentarios en Hacker News

• En una línea similar, me pareció bastante interesante esta página sobre el rendimiento del intérprete de Wren
  Si el texto de Zef se centra en las técnicas de implementación, sentí que el lado de Wren también muestra cómo el diseño del lenguaje en sí contribuye al rendimiento
  En particular, me pareció bien que Wren renuncie a los dynamic object shapes, lo que permite copy-down inheritance y hace que la resolución de métodos sea mucho más simple
  Personalmente, me parece un tradeoff bastante razonable. Me hace pensar en qué tan seguido realmente hace falta agregar métodos después de que una clase ya fue creada

  • Creo que la velocidad de un intérprete o de un JIT está enormemente determinada por el diseño del lenguaje
    Hay muchas VM muy optimizadas para lenguajes dinámicos, pero siento que LuaJIT es fuerte porque Lua es un lenguaje muy pequeño y muy adecuado para optimización
    Tiene algunas funciones que son difíciles de optimizar, pero son pocas, y eso hace que valga la pena invertir esfuerzo en ellas
    En cambio, Python me parece completamente distinto. Exagerando un poco, está diseñado casi para minimizar la posibilidad de un JIT rápido, y sus múltiples capas de dinamismo hacen que optimizarlo se vea realmente difícil
    El hecho de que, incluso después de tanto trabajo durante tanto tiempo, el JIT de CPython 3.15 en x86_64 apenas sea alrededor de un 5% más rápido que el intérprete por defecto me parece una buena muestra de eso
  • Creo que este enfoque se parece a lo que siempre se hace en lenguajes donde el monkey patching se acepta de forma idiomática, especialmente Ruby
    Claro, también me viene a la mente que Ruby no es precisamente un lenguaje conocido por priorizar la velocidad por encima de todo
    Por otro lado, la idea de que cierto tipo tenga en forma cerrada el conjunto de funciones aplicables también me resulta un poco cuestionable
    Hay bastantes lenguajes donde puedes definir funciones arbitrarias y luego usarlas con sintaxis de punto como si fueran métodos sobre variables cuyo primer argumento tenga el tipo correcto
    Por ejemplo, con macros en Nim, implicit classes y type classes en Scala, extension functions en Kotlin, o traits en Rust
  • En mi experiencia, por lo general, si puedes asignarle un tipo estático a cierta expresión, puedes compilarla con bastante eficiencia
    Los lenguajes dinámicos complejos tienden a romper activamente esa posibilidad de muchas maneras, así que se vuelven más difíciles de optimizar
    Viéndolo en retrospectiva, suena bastante obvio

• Al pasar del cambio #5 al #6, que la mayor parte de la mejora de rendimiento venga de los inline caches y del modelo de objetos con hidden classes se sintió muy parecido, históricamente, a cómo se volvieron rápidos V8 o JSC
  El punto donde muere un intérprete ingenuo al final es el despacho dinámico en el acceso a propiedades, y el resto da la impresión de ser relativamente un rounding error
  También me gustó que estuviera organizado de forma que se pudiera ver cuánto aportó cada etapa por separado. Muchas veces los textos sobre rendimiento solo tiran la cifra final y ya

  • Un detalle de implementación especialmente interesante en #6 fue cómo hacer inline caching en un intérprete que recorre el AST directamente
    En un intérprete de bytecode, puedes parchear el offset estable dentro del flujo de bytecode, así que el lugar donde reescribir el IC sale de manera natural
    Pero aquí la ubicación del caché es el nodo del AST, así que me impresionó que @pizlonator usara constructCache<> para montar en el mismo lugar un nodo AST especializado encima de uno genérico
    Al final se veía como código automodificable a nivel de AST
    A cambio, este enfoque requiere mutable AST nodes, así que choca con la suposición de AST inmutables que muchos compiladores esperan para cosas como compartir subárboles o compilar en paralelo
    Para un intérprete de un solo hilo suena limpio, pero si el intérprete cambia nodos mientras el mismo AST se compila con JIT en un hilo de fondo, parecería problemático
  • Estoy de acuerdo con la dirección general, pero también creo que hay una pequeña advertencia: al final esto es el resultado sobre un benchmark específico
    En mi opinión, puede que no represente tan bien a la mayoría del código real de producción
    Lo pensé porque la parte donde la optimización de sqrt da una mejora de 1.6% me llamó mucho la atención
    Para que salga una mejora así, el benchmark ya tenía que estar gastando por lo menos ese 1.6% del tiempo ahí, y eso me sorprendió bastante
    Viendo el repo, parece que efectivamente eso pasa en la simulación de nbody

• Esto me resultó aún más interesante porque yo también publiqué hace poco la primera versión de mi propio AST-walking interpreter
  Mi objetivo era entender, a nivel básico, qué hace falta para construir un lenguaje interpretado
  No quería meter complejidad de optimización; solo quería enfocarme en hacer que mi propio código en Rust me resultara comprensible
  Pero me sorprendió que, solo por haber usado Rust, el rendimiento saliera bastante bien
  Además, como Rust se encarga del ownership y los lifetimes, sentí como un bonus no necesitar un garbage collector aparte
  Claro, ahora mismo todavía dependo de clone de manera bastante conservadora en cosas como closures para evitar el infierno de lifetimes, pero aun así siento que el perfil de velocidad y memoria es suficientemente bueno
  Si a alguien le interesa un tree-walking interpreter simple y fácil de entender basado en Rust, puede ver mi intérprete gluonscript

• El texto estuvo realmente muy bueno
  En especial, el arco de Arguments, o sea el flujo de #7 a #13, conectó muchísimo con mi experiencia
  Hace tiempo, al construir en Rust un async step evaluator, me metí bastante a fondo con Cow<'_, Input> porque normalmente creía que borrow me iba a dar ventajas
  En microbenchmarks se veía bien, pero en cargas reales la complejidad del discriminant de Cow y todo lo relacionado con lifetimes se propagó a cada combinator después del primer await, el inlining se vino abajo, y dejó de existir la razón por la que había usado Cow en primer lugar
  Al final cambié en el borde del evaluator a NoInput / OneInput / MultiInput(Vec), y aunque se veía tosco, terminé llegando casi exactamente al mismo punto que la separación ZeroArguments / OneArgument / TwoArguments de aquí
  Una cosa que me sigue dando curiosidad es si probaron apilar type specialization encima de la especialización por aridad en la ruta nativa
  Por ejemplo, en un estilo binario parecería posible eliminar incluso la verificación de isInt
  Mi sospecha es que tal vez el cálculo de tamaño de código no cerraba, o que del lado de objetos el IC ya se estaba comiendo suficientemente bien las rutas calientes, así que el fast path nativo no movía tanto la aguja
  Me quedé con la duda de cuál de las dos fue

• Esto me pareció realmente interesante y muy bien logrado
  Yo también hice algo parecido, pero del lado de Scheme, un lenguaje un poco más funcional
  Aquí la mayor ganancia vino de optimizar objetos, pero en mi caso la batalla principal fue optimizar closures
  Curiosamente, la forma de optimizar fue bastante parecida
  Creo que casi toda la respuesta para hacer Scheme lo bastante rápido está en Three implementation models for scheme
  Eso sí, en ese caso hay cierto paso de compilación de por medio, así que no es un modelo de interpretar directamente el AST original tal cual

• Me pareció interesante y gracias por compartirlo
  A mí también me dieron ganas de explorar este tema a fondo algún día
  Y además me causó bastante gracia e impresión que, según Github, el repo sea 99.7% HTML y 0.3% C++
  Parecía una buena prueba de que el intérprete realmente es muy pequeño

  • Se ve así porque hicieron commit del sitio generado de forma estática
    Por cómo generan el código para el navegador, la parte del sitio quedó innecesariamente grande
    Aun así, el intérprete en sí de verdad es muy pequeño

• Me dio curiosidad si al hacer este trabajo aprendieron algo que pudiera servir para mejorar fil c en sí

  • Definitivamente sentí que hace falta una mejor solución para cómo manejar unions
    Y también aprendí que el costo de manejar métodos de value objects como outline calls es bastante alto

• Vi que incluyeron Lua, pero me quedé con la idea de que también habría estado bien ver LuaJIT

  • Mi expectativa es que LuaJIT le gane completamente a Zef
    No, de hecho, considerando la ingeniería que tiene encima, hasta esperaría que así fuera
    Había muchos runtimes que podría haber incluido, pero no los puse todos
    Y también fue bastante impresionante ver que PUC Lua fuera bastante más rápido que QuickJS o Python

• Me dio curiosidad cómo es realmente la experiencia de usar Fil-C, y si tiene una utilidad práctica real en producción

  • Yo soy Fil en persona, así que primero aclaro que estoy sesgado
    Aun así, en este proyecto sí ayudó de forma bastante práctica
    Me detectó de forma determinista varios problemas de seguridad de memoria, y eso hizo que diseñar el modelo de objetos fuera mucho más fácil de lo que habría sido sin eso
    Además, C++ con GC preciso se sintió como un modelo de programación realmente bueno
    Me daba la impresión de ser unas 1.5 veces más productivo que con C++ normal, e incluso frente a otros lenguajes con GC sentía que desarrollaba alrededor de 1.2 veces más rápido
    Creo que la razón es que el ecosistema de APIs de C++ es rico, y sus lambdas, templates y sistema de clases están muy maduros
    Claro, reconozco que estoy sesgado en varios sentidos
    Yo mismo hice Fil-C++, y además llevo usando C++ como unos 35 años

• Me dio curiosidad qué es el compilador YOLO-C/C++ que se menciona en el texto
  Aunque lo busqué, no aparece mucho y parece que ni chatgpt lo conoce

  • El autor de Fil-C, que también es el autor de este lenguaje, usa la expresión Yolo-C/C++ para referirse al C/C++ común y corriente, o sea, sin Fil-C