9 de septiembre de 2016

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.