27 de abril de 2014

Eliminando los extraños #t y #f de los if's en el bytecode de Racket

Introducción

En el articulo anterior habíamos analizado qué cosas aparecían en condiciones de los if en el bytecode de Racket. Esto es el código que queda después de varios pasos de expansión de las macros y varios pasos de optimización, así que pueden aparecer cosas inesperadas.
En particular era extraño que hubiera cosas como (if #t ? ?) (if #f ? ?) y (if (not ?) ? ?). No solo es extraño porque parecen cosas fáciles de optimizar, si no que el optimizador explícitamente los tiene en cuenta y los trata de eliminar.
El optimizador es importante porque permite escribir código claro y lindo, y que el código que se ejecute sea eficiente sin que uno se preocupe por inlinear las optimizaciones obvias (y las no tan obvias). (De esta manera el 99% del tiempo se puede trabajar en modo "código lindo", y usar el 1% de código feo sólo para las partes críticas que realmente necesitan velocidad.)
En general el optimizador anda muy bien y al mirar el código optimizado se ven pocas cosas que quedaron sin optimizar. Es más, muchas veces al escribir un programa pequeño queda compilado a (print #t) o algo equivalente.

Buscando un ejemplo

Lo primero es buscar de dónde vienen estas construcciones extrañas. Agregando un displayln aquí y allá, el programa del articulo anterior nos muestra las cosas raras y en qué archivo estaban. Hay un ejemplo en mred\private\check.rkt. Usando decompile se puede ver el problema está en la función check-non-negative-integer/false, que está definida (sin expandir ni optimizar) como:
#lang racket

(define (-check-non-negative-integer who i false-ok?)
  (when (or i (not false-ok?))
    (unless (and (integer? i) (exact? i) (not (negative? i)))
      (raise-argument-error [...]))))

(define (check-non-negative-integer who i)
  (-check-non-negative-integer who i #f))

(define (check-non-negative-integer/false who i)
  (-check-non-negative-integer who i #t))
Después de varias simplificaciones y expansiones a mano queda un ejemplo mucho más claro.
#lang racket
  
{define (check my-false)
  (if (if (random 1) #t my-false) 2 3)}

(check #f)
Al optimizar queda en el bytecode (versión descompilada y limpiada para mantener la claridad)
#lang racket

{define check
  (#%closed check
    {lambda (my-false)
      (if (if (random 1) #t my-false) 2 3)})}

(print-values (if (random 1) (if #t 2 3) 3))
El ejemplo todavía es medio enredado, pero lamentablemente no lo pude arreglar más :(. Utiliza una función auxiliar, el #f tiene que estar como un argumento, pero cada vez que intento simplificar más el ejemplo, el problema desaparece. Al descompilarlo, se ve como queda un #t como condición de un if, pero no se optimiza. Si reemplazamos la #t resaltada por #f o (not (random 4)) aparece el mismo problema.
(Por otro lado, también tenemos que (random 1) siempre da 0, pero como tienen efectos secundarios (cambia el estado interno del generador de números al azar) entonces es difícil de optimizar. Hay algunos trucos para poner triste al optimizador y poder ver código optimizado que no sea una constante. Yo prefiero usar (random 7) porque usando distintos valores de 7 se puede distinguir de dónde vino cada parte. En general, en los test de Racket usan (read), que también tiene efectos secundarios y es difícil de optimizar.)

El origen del problema

Una de las partes más curiosas en el ejemplo es que aparece (if (If ? #t ?) ? ?) y esto se transforma en (if ? (If #t ? ?) ?). Justamente, hay una parte del optimizador que transforma (if (if M N #f) M2 K) en (if M (if N M2 K) K), cuándo K es un valor simple que se puede duplicar sin problemas. Todas las cosas que aparecen en (if (if M N #f) M2 K) ya están optimizadas. En particular, si M era originalmente de la forma #t, #f o (not ?) entonces en el if central ya deberían estar aplicadas las optimizaciónes
(if #t X Y)  -->  X
(if #f X Y)  -->  Y
(if (not P) X Y)  -->  (if P Y X)
Además, en la misma expresión N y #f están optimizados para un contexto booleano, porque sólo van a ser usados para decidir qué hace el if de afuera. En este contexto hay algunas optimizaciones adicionales, pero no todas las que se aplican directamente en la condición del if.
En la nueva expresión (if N M2 K) también tiene sus partes optimizadas por separado. Incluso, como ya dijimos, el N está optimizado en un contexto booleano. El problema es que la expresión nunca se optimiza en conjunto, así que si N es de la forma #t, #f o (not ?), la expresión (if N M2 K) queda sin optimizar en conjunto. Esto puede hacer que aparezcan los (if #t ? ?), (if #f ? ?) y (if (not ?) ? ?).

Viejas y nuevas optimizaciones

Al optimizarse los if, van sufriendo varias optimizaciones. Los detalles son medio largos. Esta es una lista de las optimizaciones que están en Racket y algunas que estuve probando en mi repositorio.  
a: [boolean] (if M #t #f)  -->  M
b: [boolean] (if v v X)  -->  (if v #t X)
c: [new] (if v X v)  -->  (if v X #f)

d: (if (not P) X Y)  -->  (if P Y X)
d: (if #t X Y)  -->  X
e: (if #f X Y)  -->  Y

f: (if v v #f)  -->  v
g: (if <omitable> v v)  -->  v

h: (if (if M N #f) P K) => (if M (if N P K) K)
i: [new] (if M (if (not Q) P K) K) => (if M (if Q K P) K)
j: [new] (if M (if #t P K) K) => (if M P K)
k: [new] (if M (if #f P K) K) => (if M K K)
Hay algunas simplificaciones y espero no haberme olvidado de ninguna. Las primera optimizaciones se realizan sólo para expresiones en un contexto booleano y están marcadas con [boolean].
Probé agregar algunas optimizaciones en mi repositorio. Las optimizaciones nuevas que probé están marcadas con [new],
Las v indican variables locales y las K constantes que se pueden duplicar. Las optimizaciones "d" y "j" son un poco más generales, porque en vez de #t puede ser algún valor que no sea #f. Las nuevas optimizaciones "i", "j" y "k" sólo se aplican al resultado de "h", no en general.  (Ahora que lo miro, podría haber agregado una copia de "f" y "g" para los resultados de "h", pero ya eran muchas copias y me estaba aburriendo.)
Otra idea para optimizar el código es dar vuelta las optimizaciones "a", "b" y "c", así se van agregando #t y #f y la optimización "a" se puede aplicar en mas casos, reduciendo la cantidad de if en el código final.
c: [new] (if v X v)  -->  (if v X #f)
b: [boolean] (if v v X)  -->  (if v #t X)
a: [boolean] (if M #t #f)  -->  M

Para estas optimizaciones, la parte relevante del código después de reordenar queda:
  /* Convert (if <id> expr <id>) to (if <id> expr #f) */
  if (SAME_TYPE(SCHEME_TYPE(t), scheme_local_type)
      && SAME_TYPE(SCHEME_TYPE(fb), scheme_local_type)
      && (SCHEME_LOCAL_POS(t) == SCHEME_LOCAL_POS(fb))) {
    b->fbranch = fb = scheme_false;
  }
  
  if (context & OPT_CONTEXT_BOOLEAN) {
    /* Convert (if <id> <id> expr) to (if <id> #t expr) */
    if (SAME_TYPE(SCHEME_TYPE(t), scheme_local_type)
        && SAME_TYPE(SCHEME_TYPE(tb), scheme_local_type)
        && (SCHEME_LOCAL_POS(t) == SCHEME_LOCAL_POS(tb))) {
      b->tbranch = tb = scheme_true;
    }

    /* For test position, convert (if <expr> #t #f) to <expr> */
    if (SAME_OBJ(tb, scheme_true) && SAME_OBJ(fb, scheme_false))
      return scheme_optimize_expr(t, info, context);
  }

Versiones para compilar y testear

El código de las optimizaciones está en C. Tarda bastante en compilar, así que hay que tener paciencia y tratar de no equivocarse, porque un error en general significa unas horas extra recompilando
Para medir las diferencias vamos a contar cuántas veces aparecen algunas combinaciones de if en el bytecode de la versión 6.0.0.1 de Racket (head del git, de enero de este año, los resultados pueden variar según la versión exacta, espero que poco).
En general, para analizar los valores que aparecen en los if quedaron clasificados en #f, #t, v (variable local), #<void>, "", #"", K (constantes: números, strings y bytes no vacías)

Resultados de a-b-c

Primero veamos haciendo sólo cambios en las optimizaciones marcadas con a-b-c. Probamos cuatro versiones:
  • con sólo "a"
  • con "a-b", este es código sin modificaciones que usa Racket
  • con "b-a", en el orden inverso
  • con "c-b-a", en el orden inverso y agregando "c" 
Ejemplo sólo "a" "a-b" "b-a" "c-b-a"
(if v ? ?) 146592 146592 146592 146594
(if (let (v ?) ?) ? ?) 10158 10158 10158 10158
(if #t ? ?) 13 13 13 13
(if #f ? ?) 8 8 8 8
(if (if ? ? #f) ? ?) 24260 24261 24259 24275
(if (if ? ? #t) ? ?) 11343 11343 11343 11343
(if (if ? v #f) ? ?) 313 313 313 313
(if (if ? #t #f) ? ?) 159 159 159 159
(if (if ? #f #t) ? ?) 27 27 27 27
(if (null? ?) ? ?) 110065 110068 110068 110062
(if (not ?) ? ?) 1937 1937 1937 1937
(if ? ?) 305625 305637 305633 305649
(if ? #f) 114308 114299 114299 114556
(if ? v) 75536 75537 75537 75268
(if v ?) 63714 63533 63534 63534
(if #t ?) 19502 19669 19672 19672
(if ? #t) 12607 12607 12607 12607
(if #f ?) 11389 11389 11389 11389
(if v #f) 7494 7499 7499 7499
(if #t #f) 1598 1604 1601 1601
(if #f #t) 223 223 223 223
  • La optimización "b" transforma unos 170 apariciones de (if v v ?) en (if v #t ?).
  • Análogamente, la optimización "c" transforma unos 260 apariciones de (if v ? v) en (if v ? #f).
  • Yo esperaba que al intercambiar las optimizaciones "a" y "b" se pudieran componer, de manera que se transforme (if v v #f) en (if v #t #f) en v, pero no aparecen muchos de estos casos.
  • (Si eliminamos la optimización "a", aparecen como 5000 "nuevos" (if ? #t #f), muy mala idea.)

Resultados de h-i-j-k

Acá probamos otras tres versiones,  haciendo sólo cambios en las optimizaciones marcadas con h-i-j-k.
  • sin "h"
  • con "h", este es el código sin modificaciones que usa Racket
  • con "h-i-j-k", o sea optimizando el resultado de "h"
Ejemplo sin "h" sólo "h" "h-i-j-k"
(if v ? ?) 146030 146594 146618
(if (let (v ?) ?) ? ?) 9981 10158 10166
(if #t ? ?) 0 13 0
(if #f ? ?) 0 8 0
(if (if ? ? #f) ? ?) 30214 24260 24262
(if (if ? ? #t) ? ?) 10965 11343 11343
(if (if ? v #f) ? ?) 470 313 315
(if (if ? #t #f) ? ?) 221 159 159
(if (if ? #f #t) ? ?) 23 27 27
(if (null? ?) ? ?) 110004 110065 110071
(if (not ?) ? ?) 1526 1937 1820
(if ? ?) 305830 305634 305643
(if ? #f) 119928 114301 114295
(if ? v) 72762 75537 75523
(if v ?) 62971 63535 63537
(if #t ?) 19654 19672 19675
(if ? #t) 12483 12607 12602
(if #f ?) 11380 11389 11391
(if v #f) 7668 7499 7499
(if #t #f) 1664 1601 1596
(if #f #t) 227 223 219
  • Con respecto a los (if #t ? ?) y (if #f ? ?), al comparar las distintas versiones, vemos que la optimización "h" que teníamos como candidato a culpable es la culpable. Los if con #t y #f No aparecen cuándo no está "h" y optimizando el resultado de "h" vuelven a desaparecer.
  • Sin embargo hay varios (if (not ?) ? ?) en todas las versiones. Es más, al optimizar el resultado de "h" no desaparecen todas las nuevas apariciones. Me gustaría investigar su origen y ver cómo se los puede eliminar, porque aparecen mas de 1500 veces.

Ideas y comentarios

  • Lo más razonable hubiera sido utilizar la función interna del optimizador scheme_optimize_expr o optimize_branch para optimizar el segundo if del resultado de aplicar "h". Sería más elegante porque no haría falta repetir el código y además con este método se aplicarían todas las otras optimizaciones, aunque sería un poquito más lento. El problema es que para llamar a estas funciones hay que utilizar estructura Optimize_Info que contiene información sobre el estado del programa que se está optimizando. Aunque intente varias veces no pude armarla correctamente.
  • Hay muchos (if ? #f #t), quizás se los pueda reemplazar por (not ?). Hice algunas microbenchmarks para medir la diferencia de velocidad, y no vi casi ninguna diferencia. Sin embargo el cambio quizás ayude a que se puedan realizar otras optimizaciones. Algo similar con (if ? #t #f) aunque no se cuál sería el nombre de la función asociada.
  • Hay 31 apariciones de (if (if ? #<void> ?) ? ?) y 11 apariciones de (if (if ? '() #f) ? ?). Se podrían tratar de optimizarlos, pero lo más probable es que no valga la pena porque son muy pocos.
  • Al recompilar, la cantidad de veces que aparece cada cosa cambia un poco. Muy extraño. No afecta mucho los resultados, pero hay que ser cuidadoso al comparar valores muy cercanos.
  • Hay exactamente un (if (if ? 1 0) ? ?). No busqué el código que lo produce, pero a simple vista parece un (if (bool->binary ?) ? ?), suponiendo que existiera bool->binary. ¿Será un error o simplemente una coincidencia extraña producida por todas las expansiones intermedias?