Introducción
Siguiendo con la idea de los artículos anteriores, vamos a contar cuántas veces aparece expresiones cuyo resultado se ignora en el bytcode de Racket. En general, los programas de Racket son casi funcionales, por una cuestión de estilo. Casi siempre la parte útil de cada función es el resultado que devuelven y no tienen efectos colaterales. Pero cuando es conveniente se utilizan efectos colaterales localmente, encerrados adentro de una función que es funcional cuando uno la mira desde afueraEs 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. Estos pasos incluyen inlineado de funciones y propagación de constantes, por lo que pueden aparecer expresiones que serían ridículas en el código fuente como (box? (list (f 1) (f 2) (box 7)). Es más, en esos casos se optimizan porque el resultado seguro que es #f y entonces queda (begin (f1) (f 2) (box 7) #f). Y ese (box 7) está de más, porque nunca genera un error ni tiene efectos colaterales, así que en el mismo paso eso se optimiza a (begin (f 1) (f 2) #f). (En realidad, quizás a (begin (values (f 1)) (values (f 2)) #f) si el optimizador no está seguro que f devuelva un sólo valor.)
La rutina que optimizar las cosas que se ignoran sólo elimina los llamados a funciones innecesarios. Esto es bueno porque elimina un montón de constructores y así al ejecutarse el programa no es necesario crear objetos que se van a destruir inmediatamente. Por ejemplo en (begin (cons (f) 'z) (if (h) 0 1)) #f) se elimina el cons, pero no se elimina el if y queda (begin (f) (if (h) 0 1) #f), porque el 'z se puede ignorar. Sería mejor eliminar también el if y que quede (begin (f) (h) #f) porque como ignoramos el resultado del if no importa si da 0 o 1. Pero cada regla de reducción adicional hace que la optimización sea más lenta y complicada.
La pregunta del millón es cuántas de estas cosas quedan después de todas las optimizaciones, a ver si vale la pena ponerse a optimizar los if o son muy poquitos y se puede ignorar. Además que tipo de funciones quedan en las expresiones que son ignoradas, como para ver si se están escapando cosas interesantes.
Programa para contar las expresiones
El programa es una versión acortada de decompile, similar a la que usamos en artículos anteriores. La parte interesante es cómo maneja los begin (representados con seq), los begin0 (representados con beg0) y los let en los que la variable se ignora (representados con un let-one, con el flag de unused? en #t).{define (explore-expr expr globs stack closed)
(match expr
[(struct let-one (rhs body type unused?))
(let ([id (or (extract-id rhs) (gensym (or type (if unused? 'unused 'local))))])
(when unused?
((current-explore-found)
(list '|let-unused;| (decompilex-expr rhs globs stack closed))))
(explore-expr rhs globs (cons id stack) closed)
(explore-expr body globs (cons id stack) closed))]
[(struct seq (exprs))
(begin
(for ([expr (in-list (reverse (cdr (reverse exprs))))])
((current-explore-found)
(list '|begin;| (decompilex-expr expr globs stack closed)))
(explore-expr expr globs stack closed))
(explore-expr (last exprs) globs stack closed))]
[(struct beg0 (exprs))
(begin
(explore-expr (car exprs) globs stack closed)
(for ([expr (in-list (cdr exprs))])
((current-explore-found)
(list '|begin0;| (decompilex-expr expr globs stack closed)))
(explore-expr expr globs stack closed)))]
[...]
[else (void)])}
Cuando encuentra una expresión cuyo resultado se va a ignorar, llama
a decompilex-expr
(con una x
de más, porque no es la decompile-expr
de verdad) que lo traduce a algo más amigable. Y después lo pasa al
programa principal llamando a la función que está en el parámetro
current-explore-found,
que se encarga de guardarlos, clasificarlos y contarlos.{define (decompilex-expr expr globs stack closed)
(match expr
[(struct toplevel (depth pos const? ready?))
(if ready? (if const? '#%topcr '#%topr) (if const? '#%topc '#%top))
#;(list-ref/protect globs pos 'toplevel)]
[(struct primval (id))
(hash-ref primitive-table id (lambda () (error "unknown primitive")))]
[(struct localref (unbox? offset clear? other-clears? type))
(if clear? '%clear-localref '#%localref)]
[(struct branch (test then else))
(list 'branch (filter-simple-values then) (filter-simple-values else))]
[(struct application (rator rands))
(list 'application (decompilex-var rator globs stack closed) (length rands))]
[(struct apply-values (proc args-expr))
(list 'applicationv (decompilex-var proc globs stack closed) 'v)]
[else (car (or (prefab-struct-key expr) (list expr)))])}
Esto trata de decompilar la expresión sólo un poquito,
como para poder entenderla y clasificarla mejor. Por ejemplo, a los llamados
a función los agrega la cantidad de parámetros. En los casos en que hay un accesos a variables locales esta rutina les agrega si al acceder a la variable se limpia la referencia. Esta limpieza es necesaria para que los programas muy recursivos (aka normales) puedan ejecutarse. Antes de llamar a la función se trata de eliminar las referencias a las variables que no se van a volver a usar. De esta manera el garbage colector puede eliminarlas y recuperar la memoria. En general esto es en el último acceso a la variable, pero en algunos caso uno de los pasos de la compilación tiene que agregar estas marcas. Entonces el acceso a las variables tiene un efecto colateral muy sutil, que no se ve internamente en el programa, pero permite seguir haciendo recursiones mas veces. Por ejemplo en
{define (too-much-zeros n) (let ([z (random n)]) (if (zero? n) (display z) (too-much-zeros n)))}las z se irían acumulando por más que nunca se van a volver a usar. Al compilarlo, el programa se transforma a algo equivalente a (versión limpiada para mejorar la claridad):
{define (too-much-zeros n) (let ([z (random n)]) (if (zero? z) (display z) (begin (#%sfs-clear z) (too-much-zeros n))))}
Resultados
Para contar las expresiones utilicé el repositorio de Racket, de los últimos días de noviembre justo antes de la Gran Escisión. Contemos primero las expresiones ignoradas que no son aplicaciones de funciones. En la tabla se indica la cantidad de veces que aparece cierto tipo de expresión y un ejemplo representativo descompilado. En los ejemplos, v es una variable local y u es una variable no utilizada.| Cantidad | Ejemplo |
|---|---|
| 2827 | (begin (#%sfs-clear v) ... _) |
| 1504 | (begin0 _ (#%sfs-clear v) ...) |
| 87 | (begin (if ? #<void> ?) ... _) |
| 20 | (begin (if ? ? #<void>) ... _) |
| 18 | (begin (if ? ? ?) ..._) |
| 81 | (begin (let ([u ?]) ...) ... _) |
Por simplicidad, el método que expliqué para detectar las expresiones a las que se les ignora el resultado es medio naive y no detecta cosas ignoradas anidadas. Por ejemplo en (begin (begin x Y) z) es claro que no importa el resultado de Y, pero el programa anterior no lo sabe. Otro ejemplo es (begin (if x Y Z) w) en que en realidad no se tiene en cuenta ni el resultado de Y ni el de Z. Para arreglar esto, hay que agregar un argumento adicional a explore-expr que indique si la expresión a analizar va ser ignorada y propagar este argumento recursivamente. Esto alarga un poquito el programa, pero no es nada sorprendente. Con esta modificación contamos más expresiones ignoradas. En la siguiente tabla comparamos la cantidad de expresiones encontradas con cada método, junto con un ejemplo representativo del código decompilado. En los ejemplos, v es una variable local y u es una variable no utilizada.
| Pos | Cant. Dir. | Cant. Exp. | Ejemplo (Directo) |
|---|---|---|---|
| 1 | 202 | 202 | (begin (set-box! ? ?) ... _) |
| 2 | 85 | 85 | (let ([u (_tok-val:ref@(lib "parser-tools/cfg-parser.rkt") ?)]) ... ) |
| 3 | 72 | 80 | (begin (v ?) ... _) |
| 4 | 0 | 32 | (begin (raise-syntax-error ? ? ? ?) ... _) |
| 5 | 0 | 29 | (begin (raise-type-error ? ? ?) ... _) |
| 6 | 29 | 29 | (begin (set-mcdr! ? ?) ... _) |
| 7 | 29 | 29 | (let ([u (_stx-car:P@(lib "racket/private/stx.rkt") ?)]) ... ) |
| 8 | 18 | 24 | (begin (v ? ?) ... _) |
| 9 | 0 | 23 | (begin (error ? ? ?) ... _) |
| 10 | 17 | 17 | (begin (namespace-variable-value ? ? ?) ... _) |
| 11 | 11 | 17 | (begin (fprintf ? ? ?) ... _) |
| 12 | 11 | 17 | (begin (fprintf ? ?) ... _) |
| 13 | 0 | 17 | (begin (printf ? ?) ... _) |
| 14 | 5 | 15 | (begin (_check-type ? ? ?) ... _) |
| 15 | 5 | 15 | (begin (hash-set! ? ? ?) ... _) |
| 16 | 11 | 11 | (begin (vector-set! ? ? ?) ... _) |
| 17 | 0 | 8 | (begin (raise-type-error ? ? ? ? ?) ... _) |
| 18 | 5 | 8 | (begin (? ? ?) ... _) |
| 19 | 6 | 7 | (begin (? ? ? ? ?) ... _) |
| 20 | 7 | 7 | (begin (apply ? ? ?) ... _) |
| 21 | 0 | 7 | (begin (error ? ?) ... _) |
| 22 | 0 | 7 | (begin (for-each ? ?) ... _) |
| 23 | 1 | 6 | (begin (? ? ? ?) ... _) |
| 24 | 5 | 5 | (begin (_check-sigs:P@(lib "racket/private/unit-runtime.rkt") ? ? ? ?) ... _) |
| 25 | 0 | 5 | (begin (_idY21.62:f@(lib "syntax/boundmap.rkt") ? ? ? ?) ... _) |
| 26 | 5 | 5 | (begin (_check-unit:P@(lib "racket/private/unit-runtime.rkt") ? ?) ... _) |
| 27 | 5 | 5 | (let ([u (cadr ?)]) ... ) |
En ambos métodos de conteo el tipo de cosas que aparece son similares. La mayor diferencia es que en el segundo aparecen muchas más funciones que generan un error. Debería analizarlo con más cuidado, pero supongo que corresponden a códigos como
{define (f l)
(unless (list? l)
(error 'error))
(something-useful-with l))}
que se expande a algo como (versión limpiada para mejorar
la claridad){define (f l)
(begin
(if (list? l)
#<void>
(error 'error))
(something-useful-with l))}
El primer metodo no se da cuenta que cualquiera de los resultado de
ambas ramas del
if
se van a ignorar, pero el segundo método si. Esta es una
construcción muy usual en el código fuente de Racket, así que supongo que es la
causa de la mayoría de las diferencias.La moraleja es que (¿casi?) todas las expresiones a las que se les ignora el resultado están por algún efecto colateral y no hay una idea obvia para optimizar alguna de ellas y eliminarla o reducirla.
