9 de septiembre de 2016

Adding a New Primitive to the Innards of Racket

Introduction

The basic functions of Racket are implemented in C and are called primitives, for example cons, car, +, *, and many more (they are about 1500). In this article we will see how to add a new primitive.

In general, it’s not usual to add a new primitive, but this seems like an interesting exercise to understand how the other Racket primitives are implemented. Moreover, the new primitive is useful for the secret hidden type system of the optimizer of Racket (which is unrelated to the type system of TypedRacket).

The new primitive

The new primitive will be
    (strict-true? v)
Returns #t if v is #t and otherwise returns #f.

In general, it is not good Racket code style to compare something with #t. Usually the code should only see that the value is not #f. As it’s a bad style primitive, I will hide it to make it inaccessible.

(Although it is hidden, the internal test may call it by importing it from #%kernel. Anyway, to make some examples for the article, I will export it renamed as ugly-strict-true? that clearly express my opinion.)

The new primitive is similar to
    (not v)
Returns #t if v is #f and returns #f otherwise.

So the plan is to see how not is implemented, and copy its implementation.
You can look at the details and the complete code in github.

Disable cstartup.inc

The first step to add a primitive is to make Racket ignore the cstartup.inc file that is actually a .zo file with the bytecode encoded in a strange way. The content of the .zo files depends on the position of each primitive, so when you add or remove a primitive they become obsolete. In the same step we change the version number so all the .zo files are recalculated. (When the file cstartup.inc disabled everything is slower, so remember to enable it after finishing the changes.)

To disable this cstarup.inc file we have to edit the file schminc.h and put
    #define USE_COMPILED_STARTUP 0

The version number is changed in schminc.h and base/info.rkt

Adding the primitive

First you have to write the C implementation, which in this case goes in the file bool.c. There is nothing surprising here. We just look if the first argument is scheme_true, that is the internal name of the variable that has the value #t.
    static Scheme_Object *strict_true_p_prim(int argc, Scheme_Object *argv[])
    {
      return (SAME_OBJ(argv[0], scheme_true) ? scheme_true: scheme_false);
    }

Then we create a primitive to allow us to use the function in defined in C in the Racket code, and we add it the environment to be recognized for compiling the new programs in Racket.
    p = scheme_make_folding_prim(strict_true_p_prim, "strict-true?", 1, 1, 1);
    SCHEME_PRIM_PROC_FLAGS(p) | = scheme_intern_prim_opt_flags (SCHEME_PRIM_IS_OMITABLE);
    scheme_add_global_constant( "strict-true?", p, env);

This definition expresses many details about the primitive. Luckily it is like not and we can copy it.

Some of the following examples seem ridiculous, but after the original code suffers several steps Racket expansion, macros and inlining, sometimes the result looks like this.

It accepts a single argument

So we don’t need to check the number of arguments. So
    (strict-true? 1 2)
fails at run time.

It returns a single value.

This enables some optimizations, for example
    (lambda (x) (car (cons (strict-true? x) x)))
    ==>
    (lambda (x) (strict-true? x))
instead of
    ==>
    (lambda (x) (values (strict-true? x)))
in which values is used to check that the result has exactly one value.

And it also marks
    (lambda (x)
      (display x)
      (strict-true? x))
as a function that returns a single value, which helps the interpreter/JIT to avoid generating code for the case of multiple values.

We mark it as folding,

So during optimization it can participate in the constant folding, in expressions like (strict-true? #t) ==> #t.

Or more complicated cases, that use the interaction with other optimizations, such as
    (lamba (v)
      (when (vector? v)
      (strict-true? (box? v))))
    ==>
    (lamba (v)
      (when (vector? v)
      (strict-true? #f)))
    ==>
    (lambda (v)
      (when (vector? v)
      #f)

We mark it as OMITABLE,

So will automatically have some reductions as
    (lambda (x)
      (strict-true? x)
      (display x))
    ==>
    (lambda (x)
      (display x))

It’s not marked as UNARY_INLINED

The attentive reader will note that it is not marked as UNARY_INLINED, that is another flag that not has, but we'll add it soon.

Enable cstartup.inc again

Now we can recalculate the file cstartup.inc using
    make cstartup

and re-enable it modifiying the file schminc.h
    #define USE_COMPILED_STARTUP 1

While I'm preparing new code, I like to keep these steps in different commits in case I have to make a rebase and recalculate cstartup.c, but the final version is better to squash them into one.

JIT

If the primitive is simple, it is possible to add it to the list of primitives that are processed by the JIT so that the running code is compiled to machine code rather than interpreted from the bytecode. Racket uses GNU lightning with several conventions and auxiliary functions to facilitate writing code.

First we have to add a flag in the definition of strict-true? in bool.c
    p = scheme_make_folding_prim(strict_true_p_prim, "strict-true?", 1, 1, 1);
    SCHEME_PRIM_PROC_FLAGS(p) |= scheme_intern_prim_opt_flags(SCHEME_PRIM_IS_UNARY_INLINED
                                                              | SCHEME_PRIM_IS_OMITABLE);
    scheme_add_global_constant("strict-true?", p, env);
And then we add in jitinline.c
    else if (IS_NAMED_PRIM(rator, "strict-true?")) {
      generate_inlined_constant_test(jitter, app, scheme_true, NULL, for_branch, branch_short, dest);
      return 1;
    }

This case was easy because we already have the function generate_inlined_constant_test that generates the JIT code to check if the value is equal to the chosen constant, in this case scheme_true. But generally writing the implementation of a primitive for the JIT is very very painful.

To see the effect of this change, we can compare how long it takes the following program to run before and after enabling the JIT version of strict-true?. We compare it with the equivalent version for not.that in both case use the JITed code. (We use a mutable variable x, so that the optimizer is not sure about the value of x and it have to check the value in each cycle, and there is no risk that a clever optimization removes the check.)

    #lang racket / base
   
    (define x 'something-else)
    (set! x x)
   
    (time
      (for/or ([i (in-range 1000000000)])
        (not x)))
   
    (time
      (for/or ([i (in-range 1000000000)])
        (ugly-strict-true? x)))

cpu time (ms)
Before:
After:
not
4109
4109
ugly-strict-true?
9031
4110

These times include time of the the loop, if we could deduct its time the difference would be even more remarkable. Usually, I like to repeat the measurement several times to get an informal version of a statistics, but in this case each test takes about 5-10 seconds and the improvement is x2 so it’s not necessary to repeat it to be sure.

Global variable

With the changes that we have already made the primitive is completely ready. Now we can add some specific optimizations for strict-true?. Some optimizations can recognize strict-true? by name, but for others it is necessary to put strict-true? in a global variable so that it can be recognize or use from other files.

In schpriv.h we add
    extern Scheme_Object *scheme_strict_true_p_proc;

There is no official rule for the name of the global variables, but generally if it is a primitive the name is scheme_<name>_proc, where in the name of the - changes to _ and ? to _p and things like that, with a few exceptions.

In the definition in bool.c we have to save the primitive in the variable and register the variable with the garbage collector.
    READ_ONLY Scheme_Object *scheme_strict_true_p_proc;
    REGISTER_SO(scheme_strict_true_p_proc);
    p = scheme_make_folding_prim(strict_true_p_prim, "strict-true?", 1, 1, 1);
    SCHEME_PRIM_PROC_FLAGS(p) |= scheme_intern_prim_opt_flags (SCHEME_PRIM_IS_UNARY_INLINED
                                                               | SCHEME_PRIM_IS_OMITABLE);
    scheme_strict_true_p_proc = p;
    scheme_add_global_constant("strict-true?", p, env);

Optimizations

There are several interesting optimizations that we can add now. To make this article short I will not put the code here and I’ll left as an exercise for the interested reader to search for the details in the commits. All the changes are in functions in optimize.c.

Relevant predicate

We add strict-true? to the list of relevant predicates, which are the ones that are tracked by the Racket optimizer. These predicates are almost disjoint (I don’t know the technical term), so this automatically enables optimizations such as
    (strict-true? (vector 1 2 3)) ==> #f

and also
    (vector? (if x
               (begin (display x) #t)
               #t))
    ==>
    (begin
      (if x
        (begin (display x) #t)
        #t)
      #f)

Replace a variable by a constant

If the optimizer deduces that a variable verifies strict-true? then it replaces it by #t.
    (lambda (x)
      (when (strict-true? x)
        x))
    ==>
    (lambda (x)
      (when (strict-true? x)
        #t))

Add boolean? as a relevant predicate

We can also add to the primitive boolean? to the relevant predicates. The problem is that boolean? includes strict-true? and not (not is a predicate, is more evident if you write it as not? or strict-false? but for historical reasons we call it not). So we have to add code to handle unions and intersections and see if a variable that satisfies one predicate can satisfy a different predicate. Whith this change we have reductions like:
    (lambda (f)
      (boolean? (if (f)
              (begin (display 1) #t)
              (begin (display 2) #f)))
    ==>
    (lambda (f)
      (if (f)
         (begin (display 1) #t)
         (begin (display 2) #f))
      #t)

Another example that seems to be most interesting is
    (lambda (x)
      (when (boolean? x)
        (if x (box x) (vector x))))
    ==>
    (lambda (x)
      (when (boolean? x)
        (If x (box #t) (vector #f))))

Predicates are Boolean

We can also mark the result of many common predicates as a Boolean, then we have
    (lambda (v)
      (let ([x (vector? v)])
        (if x (box x) (vector x))))
    ==>
    (lambda (v)
      (let ([x (vector? v)])
        (if x (box #t) (vector #f))))

Optimization for or

The macro or is a very usual and interesting case. The expansion (without optimization) is
    (lambda (x)
      (or (symbol? x) 7)
    ==>
    (lambda (x)
      (let ([temp (symbol? x)])
        (if temp temp 7)))

With the new enhancements, the optimizer realizes that temp is Boolean and optimizes
    ==>
    (lambda (x)
      (let ([temp (symbol? x)])
        (if temp #t 7)))

It would be good to move the expression that defines temp to the place of use and get a result like
    ==>
    (lambda (x)
      (if (symbol? x) #t 7))

but the optimizer only moves expressions that define variables used once, and the optimizer does not realize that after the replacement of temp by #t, the variable temp appears only once.

Luckily, there was an ad hoc optimization for expressions like the produced by or, but it was applied only when they were in a Boolean context, such as (if (or ...) ... ...) or (not (or ...)). With some changes we can extend to (or <boolean?> ...).

Conclusion



With these changes, we would have a new primitive in Racket. It is not very useful for use directly, but it helps implement some optimizations for usual idioms, particularly for expressions that combine or and an expression with a Boolean result.

You can look at the details and the complete code in github.

Agregando una Nueva Primitiva a las Entrañas de Racket

Introducción

Las funciones básicas de Racket están implementadas en C y se las llama primitivas, por ejemplo cons, car, +, *, y un largo etcétera (son cómo 1500). En este artículo vamos a ver cómo agregar una nueva primitiva.

En general, uno no anda por la vida agregando primitivas, pero me parece un ejercicio interesante para entender cómo están implementadas las otras primitivas de Racket. Además, la nueva primitiva es útil para el sistema de tipos oculto y secreto del optimizador de Racket (que no tiene nada que ver con el sistema de tipos de TypedRacket).

La nueva primitiva

La nueva primitiva va a ser
    (strict-true? v)
Devuelve #t si v es #t y en cualquier otro caso devuelve #f.

En general, no es bueno que el código de Racket verifique algo comparándolo con #t. Normalmente el código debe sólo ver que no es #f. Cómo es una primitiva de mal gusto, la voy a ocultar para que no sea accesible.

(A pesar que está oculta, en los test internos es posible llamarla importándola desde #%kernel. De todas manera, para poder hacer algunos ejemplos en el artículo, la voy a exportar renombrada como ugly-strict-true? que expresa claramente mi opinión.)

La nueva primitiva se parece mucho a
    (not v)
Devuelve #t si v es #f y en cualquier otro caso devuelve #f.

Así que el plan es ver cómo está implementada not, y copiar la implementación.

Para más detalles, pueden ver el código completo en github.

Deshabilitar cstartup.inc

El primer paso para agregar una primitiva es hacer que Racket ignore el archivo cstartup.inc que es en realidad un archivo .zo de bytecode codificado de una manera extraña. El contenido de los archivos .zo depende de la posición de cada primitiva, así que al agregar o sacar una primitiva se vuelven obsoletos. En el mismo paso cambiamos el número de versión así, todos los archivos .zo se recalculan. (Con el archivo cstartup.inc deshabilitado todo anda más lento, así que hay que recordar habilitarlo al completar las operaciones.)

Para deshabilitar cstarup.inc esto hay que editar el archivo schminc.h y poner
    #define USE_COMPILED_STARTUP 0
El número de versión lo cambiamos en schminc.h y base/info.rkt

Agregando la primitivas

Por un lado hay que escribir la implementación en C, que en este caso va en el archivo bool.c. Nada sorprendente. Sólo nos fijamos si el primer argumento es scheme_true que es el nombre interno de la variable que tiene a #t.
    static Scheme_Object *strict_true_p_prim (int argc, Scheme_Object *argv[])
    {
      return (SAME_OBJ(argv[0], scheme_true) ? scheme_true : scheme_false);
    }

Por otro lado creamos la primitiva para poder usar desde Racket la función en C, y la agregamos al environment para que se la reconozca al compilar los nuevos programas en Racket.
    p = scheme_make_folding_prim(strict_true_p_prim, "strict-true?", 1, 1, 1);
    SCHEME_PRIM_PROC_FLAGS(p) |= scheme_intern_prim_opt_flags(SCHEME_PRIM_IS_OMITABLE);
    scheme_add_global_constant("strict-true?", p, env);

En la definición se expresan muchos detalles sobre la primitiva. Por suerte es parecida a not y nos podemos copiar.

Algunos de los próximos ejemplos parecen ridículos, pero después de que el código original en Racket sufre varios pasos de expansión, macros e inlineo, a veces se ven cosas parecidas.

Acepta un solo argumento

Así que no necesitamos controlar la cantidad de argumentos nosotros. Así que
    (strict-true? 1 2)
produce un error al ejecutarse

Devuelve un sólo valor.

Esto habilita algunas optimizaciones, por ejemplo
    (lambda (x) (car (cons (strict-true? x) x)))
    ==>
    (lambda (x) (strict-true? x))
en vez de
    ==>
    (lambda (x) (values (strict-true? x)))
en la que values se usa para verificar que el resultado tenga exactamente un valor.

Además marca a
    (lambda (x)
      (display x)
      (strict-true? x))

como una función que devuelve un solo valor, lo que ayuda al interprete/JIT a evitar generar código para el caso de valores múltiples.

La marcamos como folding,

 Así que durante la optimización puede participar en el constant folding, en expresiones como (strict-true? #t) ==> #t.

O cosas más complicadas que interactúan con otras optimizaciones, como por ejemplo
     (lamba (v)
       (when (vector? v)
         (strict-true?
(box? v))))
     ==>
     (lamba (v)
       (when (vector? v)
         (strict-true? #f)))
     ==>
     (lamba (v)
       (when (vector? v)
         #f)

La marcamos como OMITABLE

Así que automáticamente se le aplican algunas reducciones como en
     (lamba (x)
       (strict-true? x)
       (display x))
     ==>
     (lamba (x)
       (display x))

Pero no la marcamos como UNARY_INLINED

El lector atento habrá notado que no la marqué como UNARY_INLINED, que es otro flag que tiene not. Lo arreglaremos pronto.

Rehabilitar cstartup.inc

Ahora podemos recalcular el archivo cstartup.inc usando
    make cstartup
y volver a habilitarlo poniendo en el archivo schminc.h
    #define USE_COMPILED_STARTUP 1

Mientras estoy preparando el nuevo código me gusta tener estos pasos en diferentes commits en caso de que haya que hacer un rebase y recalcular cstartup.c, pero en la versión definitiva es más prolijo squasharlos en uno solo.

JIT

Si la primitiva es simple, es posible agregarla a la lista de las primitivas que procesa el JIT, de manera que el código que se ejecuta esté compilado en código máquina en vez de interpretado desde el bytecode. Para eso Racket usa GNU lightning junto con varias convenciones y funciones auxiliares para facilitar la escritura del código.

Primero hay que agregar un flag en la definición de strict-true? en bool.c
    p = scheme_make_folding_prim(strict_true_p_prim, "strict-true?", 1, 1, 1);
    SCHEME_PRIM_PROC_FLAGS(p) |= scheme_intern_prim_opt_flags(SCHEME_PRIM_IS_UNARY_INLINED
                                                              | SCHEME_PRIM_IS_OMITABLE);
    scheme_add_global_constant("strict-true?", p, env);

Y después la agregamos en jitinline.c
    else if (IS_NAMED_PRIM(rator, "strict-true?")) {
      generate_inlined_constant_test(jitter, app, scheme_true, NULL, for_branch, branch_short, dest);
      return 1;
    }

Este caso fue fácil porque está justo la función  generate_inlined_constant_test que genera el código JIT para ver si el valor es igual a la constante elegida, en este caso scheme_true. Pero en general escribir la implementación de una primitiva en el JIT es muy muy engorroso.

Para ver el efecto de este cambio, podemos comparar cuánto tarda el siguiente programa antes y después de habilitar el JIT para strict-true?. Lo comparamos con el código análogo que usa not y siempre tiene activo el JIT (Usamos una variable modificable(mutable) x, para que el optimizador no esté seguro de cuánto vale x y tenga que chequear su valor en cada ciclo, en vez de que una optimización astuta elimine el chequeo.)

    #lang racket/base
   
    (define x 'something-else)
    (set! x x)
   
    (time
      (for/or ([i (in-range 1000000000)])
        (not x)))
   
    (time
      (for/or ([i (in-range 1000000000)])
        (ugly-strict-true? x)))


cpu time (ms)
Antes:
Después:
not
4109
4109
ugly-strict-true?
9031
4110

Estos tiempos incluyen también tiempos del bucle, si lo pudiéramos descontar la diferencia sería aún más notable. En general recomiendo repetir la medición varias veces para tener una versión informal de una estadística, pero en este caso tarda como 5-10 segundos y la mejora es x2 así que no hace falta repetirla para estar seguro.

Variable global

Con los cambios que ya hicimos tenemos nuestra primitiva completamente lista. Ahora podemos aprovechar y agregar algunas optimizaciones específicas para strict-true?. Algunas optimizaciones pueden reconocer a strict-true? por nombre, pero para otras es necesario poner a strict-true? en una variable global para que se la pueda reconocer o usar desde otros archivos.

En schpriv.h agregamos
    extern Scheme_Object *scheme_strict_true_p_proc;

No hay una regla oficial para el nombre de las variables globales, pero si es una primitiva en general el nombre es scheme_<nombre>_proc, en dónde en el nombre los - pasan a _ y los ? a _p y cosas así, con alguna que otra excepción.

En la definición que aparece en bool.c hay que guardar la primitiva en la variable y registrar la variable para que la vea el garbage collector.
    READ_ONLY Scheme_Object *scheme_strict_true_p_proc;
    REGISTER_SO(scheme_strict_true_p_proc);
    p = scheme_make_folding_prim(strict_true_p_prim, "strict-true?", 1, 1, 1);
    SCHEME_PRIM_PROC_FLAGS(p) |= scheme_intern_prim_opt_flags(SCHEME_PRIM_IS_UNARY_INLINED
                                                              | SCHEME_PRIM_IS_OMITABLE);
    scheme_strict_true_p_proc = p;
    scheme_add_global_constant("strict-true?", p, env);

Optimizaciones

Hay varias optimizaciones interesantes para agregar. Por razones de espacio no voy a poner el código y queda como ejercicio para el lector interesado buscar los detalles en los commits. Son todos agregados a funciones en optimize.c y sus testeos respectivos.

Predicado relevante

Agregamos strict-true? a la lista de predicados relevantes, que son los que recuerda el optimizador de Racket. Estos predicados son casi disjuntos (no sé el termino técnico), así que esto automáticamente habilita optimizaciones como
    (strict-true? (vector 1 2 3)) ==> #f

y también
    (vector? (if x
               (begin (display x) #t)
               #t))
     ==>
    (begin
      (if x
        (begin (display x) #t)
        #t)
      #f)

Reemplazar una variable por constante

Si el optimizador deduce que una variable verifica strict-true? la reemplaza por #t.
    (lambda (x)
      (when (strict-true? x)
        x))
    ==>
    (lambda (x)
      (when (strict-true? x)
        #t))

Agregar boolean? como predicado relevante

También podemos agregar a la primitiva boolean? a los predicados relevantes. El problema es que boolean? incluye a strict-true? y not (not es un predicado, es más evidente si la escribimos como not? o strict-false? pero por razones históricas la llamamos not). 

Entonces hay que agregar a mano el código para manejar las uniones e intersecciones y ver si una variable que verifica un predicado puede verificar otro predicado distinto. 

Entonces tenemos reducciones como:
    (lambda (f)
      (boolean? (if (f)
              (begin (display 1) #t)
              (begin (display 2) #f)))
    ==>
    (lambda (f)
      (if (f)
         (begin (display 1) #t)
         (begin (display 2) #f))
      #t)

Otro ejemplo que parece que es más interesante es
    (lambda (x)
      (when (boolean? x)
        (if x (box x) (vector x))))
    ==>
    (lambda (x)
      (when (boolean? x)
        (if x (box #t) (vector #f))))

Los predicados son booleanos

También podemos marcar al resultado de muchos predicados usuales como un booleano, entonces tenemos que
    (lambda (v)
      (let ([x (vector? v)])
        (if x (box x) (vector x))))
    ==>
    (lambda (v)
      (let ([x (vector? v)])
        (if x (box #t) (vector #f))))

Optimización para or

Un caso muy usual e interesante es la macro or. La expansión (sin optimización) es
    (lambda (x)
      (or (symbol? x) 7)
    ==>
    (lambda (x)
      (let ([temp (symbol? x)])
        (if temp temp 7)))

Con la nuevas optimizaciones, el optimizador se da cuenta que temp es booleana y lo optimiza a
    ==>
    (lambda (x)
      (let ([temp (symbol? x)])
        (if temp #t 7)))

Sería bueno poder mover la expresión que define temp a la posición de uso y que quede
    ==>
    (lambda (x)
      (if (symbol? x) #t 7))


pero el optimizador sólo mueve expresiones que define variables que se usan una sola vez, y el optimizador no se da cuenta que después del remplazo de temp por #t, a variable temp queda usada una sola vez.

Por suerte ya había una optimización ad hoc para expresiones como las que produce or, pero se aplicaba sólo cuando estaban en un contexto booleano, como por ejemplo (if (or ...) ... ...) ó (not (or …)). Con algunos cambios la podemos extender a (or <boolean?> ...).

Conclusión

Con estas modificaciones, tendríamos una nueva primitiva en Racket. No es tan útil para usar directamente, pero ayuda a implementar optimizaciones para construcciones usuales, en particular para expresiones que combinan or y una expresión con un resultado booleano.

Para más detalles, pueden ver el código completo en github.