5 de febrero de 2014

¿¿¿Sí qué??? en el bytecode de Racket

Introducción

(En inglés el título queda mejor.)

En el articulo anterior habíamos contado cuántas veces aparece cada función primitiva en el bytecode de Racket. La idea es ahora concentrarnos en ver que funciones aparecen como condiciones en los if.  Específicamente, buscamos qué funciones aparecen en lugar de what en las expresiones de la forma (if (what ?) ? ?). Es importante recordar que al analizar el bytecode, estamos viendo qué queda después de múltiples pasos de expansiones de macros y múltiples pasos de optimización, así que los resultados que obtenemos son muy distintos a los que obtendrían analizando el código original. Vamos a aplicar este análisis a los archivos .zo en el directorio de Racket (versión 5.3.6).

Ya que estamos, también vamos a analizar qué cosas raras aparecen en la condición de los if.

Modificaciones del código

Modificamos ligeramente el código que usamos en el artículo pasado. Principalmente tenemos que modificar la función explore-expr:

{define (explore-expr expr globs stack closed)
  (match expr
    [...]
    [(struct branch (test then else))
     (begin
       (match test
         [(struct application (rator rands)) 
           ((current-explore-found) (list 'app (or (decompilex-var rator globs stack closed) '#%app)))]
         [(struct apply-values (proc args-expr))
          ((current-explore-found) (list 'app (or (decompilex-var proc globs stack closed) '#%app)))]
         [(struct branch (test then else))
          (let ([then (filter-simple-values then)]
                [else (filter-simple-values else)])
          ((current-explore-found) (list 'if then else)))]
         [(? struct?) 
          ((current-explore-found) (list 'expression (vector-ref (struct->vector test) 0)))]
         [else ((current-explore-found) (list 'other test))])
       (explore-expr test globs stack closed)
       (explore-expr then globs stack closed)
       (explore-expr else globs stack closed))]
    [...])}

Si adentro del if hay un struct del tipo application o apply-values, eso corresponde a llamar a la función, así que la guardamos usamos a la función que está en el parámetro (current-explore-found)  (faltaría considerar call-with-values, pero aparece poco).

Si adentro del if hay un branch entonces significa que hay otro if, guardamos que hay en then y else, usando la función filter-simple-values nos sirve para quedarnos con los valores simples que aparecen allí y reemplazar las otras cosas por '?.

{define (filter-simple-values x)
  (if (or (member x (list #t #f (void) null)) (number? x)) x '?)}

Si adentro del if hay alguna otra struct, es que la condición es más compleja, por ejemplo hay un let o un begin.

Finalmente si hay otra cosa, tiene que ser un valor sencillo, como #t, #f, un fixnum, ..., también los anotamos.

Para poder guardar todo en un solo hash, en vez de anotar sólo el nombre usamos una lista en la que el primer elemento indica en que tipo de lugar lo encontramos. Al ser listas no las podemos comparar con eq? sinó que hay que usar equal?, por lo que cambiamos el programa principal para que guarde todo en un hash en vez de hasheq.

Resultados

Funciones que aparecen más veces en el lugar de what en expresiones de la forma (if (what ?) ? ?).


Pos. Cant. Nombre
1 88255 null?
2 57209 eq?
3 38819 pair?
4 17083 list?
5 14264 _stx-pair?:P@(lib "racket/private/stx.rkt")
6 12256 =
7 10080 <
8 7672 syntax?
9 6353 unsafe-fx<
10 5441 _identifier?:P@(lib "racket/private/stx.rkt")
11 4932 equal?
12 4486 zero?
13 3978 procedure?
14 3506 _stx-list?:p@(lib "racket/private/stx.rkt")
15 3027 <=
16 2954 _stx-null/#f:P@(lib "racket/private/stx.rkt")
17 2947 string?
18 2712 >=
19 2371 _spec?:?@(lib "scribble/private/manual-class.rkt")
20 2371 _impl?:?@(lib "scribble/private/manual-class.rkt")
21 2326 _cpointer?@(quote #%foreign)
22 2169 >
23 2056 free-identifier=?
24 2050 symbol?
25 1836 eof-object?

Casi todo lo que aparece son predicados booleanos, que por convención terminan en ?, también está <, => que son del mismo tipo, pero por razones históricas no tienen el ?. Nada muy sorprendente. La única excepción en esta lista  es stx-null que es "casi" booleana, a veces devuelve #f y a veces null. Las siguientes funciones no booleans que aparecen mas veces son:


Pos. Cant. Nombre
30 1436 unbox
32 1396 _alt-memq@(lib "racket/private/list.rkt")
33 1384 hash-ref
40 847 regexp-match
43 744 _alt-member@(lib "racket/private/list.rkt")

Con respecto a unbox y hash-ref espero que alguien haya guardado un valor booleano en un box o en un hash. Algo similar pasa con regexp-match. Con respecto a alt-memq y alt-member, son "casi" booleanas, en caso negativo devuelven #f y en caso afirmativo algún valor que puede ser útil.

Al contar cuáles son las otras cosas que pueden aparecer en la condición del if tenemos esta tabla, (con un ejemplo de cómo sería la versión descompilada, en la que v es una variable local).


Pos. Cant. Nombre Ejemplo
1 113550 struct:localref (if v ...)
2 41860 struct:branch (if (if ...) ...)
3 7700 struct:let-one (if (let ...) ...)
4 7243 #%localref (if (v ...) ...)
5 1287 #%app (if ((...) ...) ...)

A veces este tipo de condiciones complejas aparecen en el código original, pero a veces se debe a los pasos de expansión y optimización. Por ejemplo algo tan inocente como un or queda


Original:
(let ([x (random 1)]
      [y (random 2)])
  (if (or x y) 3 4))

Después de expandir (versión limpiada para mejorar la claridad, por ejemplo los dos let en realidad son let-values)
(let ([x (random 1)]
      [y (random 2)])
  (if (let ([or-part x])
        (if or-part or-part y))
    3 4))

Después de optimizar (versión limpiada para mejorar la claridad, por ejemplo los los nombres de las variables se pierden)
(let ([x (random 1)])
  (let ([y (random 2)])
    (if (if x #t y) 3 4)))

Para ver el comportamiento general, graficamos ahora la cantidad de veces que aparece cada tipo de cosa en la posición de test del if. Los predicados booleanos están marcados con una cruz y las otras cosas con un círculo azul. La mayoría son predicados booleanos., aunque entre los primeros aparecen (v ...) y (if ...) intercalados con null?, eq? y pair?. La distribución se puede aproximar por y = 3.02E5 x-1.60.




Resultados extraños

Al revisar las otras cosas que pueden aparecer en la condición del if encontramos:


Pos. Cant. Nombre Ejemplo
35 1011 not (if (not ?) ? ?)
565 13 #t (if #t ? ?)
926 7 #f (if #f ? ?)
1476 3 void (if (void ?) ? ?)
1920 2 set-box! (if (set-box! ? ?) ? ?)

Por ejemplo, void y set-box! aparecen sólo 3 y 2 veces (la posición no es muy exacta, porque hay muchos empates). Se podría tratar de optimizar el código, pero por tan pocas veces no creo que valga la pena.

Los otros casos son más extraños, porque el optimizador optimiza específicamente ese tipo de código ... La respuesta queda para el siguiente artículo.