5 de febrero de 2014

If what??? in the Racket's bytecode

Introduction

In the previous article we counted how many times each primitive function appears in the Racket bytecode . This time, the idea is to analyze the functions that appear as conditions in the if. Specifically, we will look what functions that are replacing what in expressions like (if (what ?) ? ?).  It is important to remember that we are analyzing the bytecode, so we analyze the result of multiple macro expansions steps and multiple optimization steps, so the values we get are very different from those obtained by analyzing the source code. We will apply this analysis to all the .zo files in the Racket directory (version 5.3.6).

At the same time, we will also analyze if there are other strange things are in the condition of the if.

Changes in Code 

We modify slightly the code we used in the last article. The main changes are in the explore-exp function:


{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))]
    [...])}

If there is an struct of the type application or apply-values inside of if, it corresponds to a function call, so we store it using the function that is in the (current-explore-found) parameter (we should have considered also call-with-values, but they appear very seldom).

If inside the if there is a branch, then it means that there is another if, we store what is in then and else, using the filter-simple-values ​​function that allows us us to keep the simple values ​​that appear there and replace the other things '?.

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


If there is any other struct inside the if, then the condition is more complex, for example there is a let or begin.

Finally, if there is something else, it has to be a simple value , such as #t, #f a fixnum , ..., also the write them down.
We need to store all the founded items in a single hash, so we wrap them in a list in which the first element indicates where we found it. These list can't be compared with eq?, we need to compare them with equal?, so we change the main program to keep everything in a hash instead of hasheq.

Results

Functions that appear more often in the place of what in expressions of the form (if (what ?) ? ?).


Pos. Count Name
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?

Almost everything listed here are Boolean predicates, which by convention end in ?, there are also <, = and >, that are also Boolean predicates, but for historical reasons have not the ? . Nothing too surprising. The only exception in this list is stx-null, that is " almost" Boolean sometimes returns null and sometimes it returns #f. The next most common non Boolean functions are:


Pos. Count Name
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")

Regarding unbox and hash-ref, I hope someone had stored a Boolean value in a box or in a hash. Something similar happens with regexp-match . Regarding alt-memq and alt-member, they are "almost" Boolean , if the result is negative they return #f and if the result is positive they return a value that may be useful.

Counting what are the other things that may appear inside the if we have this table (with an example of how would the decompiled version be, where v is a local value).


Pos. Count Name Example
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 ((...) ...) ...)
Sometimes this kind of complex conditions appear in the original code, but sometimes they appear in the expansion and optimization steps. For example something as innocent as an or is transformed into:

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

After expansion (cleaned version to improve clarity, for example the two let are actually let-values)
(let ([x (random 1)]
      [y (random 2)])
  (if (let ([or-part x])
        (if or-part or-part y))
    3 4))

After optimization (cleaned version to improve clarity, for example the names of the variables are lost)
(let ([x (random 1)])
  (let ([y (random 2)])
    (if (if x #t y) 3 4)))

To see the general behavior, we plot the number of times each type of thing appears in the test position of if. The Boolean predicates are marked with a cross and the other things with a blue circle. Most are Boolean predicates, but between the first items (v ...) and  (if ...) appear interleaved with null?, eq? and pair?. The distribution can be approximated by y = 3.02E5 x-1.60.


Weird results

Reviewing the other things that may appear in the if we found :


Pos. Count Name Example
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! ? ?) ? ?)

For example, void and set-box! appear only 3 and 2 times (the position is not very accurate, because there are many draws). It could be possible to optimize the code, but I don't think it's worthwhile because they appear very seldom.

The other cases are stranger, because the optimizer specifically optimized such code... The answer will appear in  the next article.

¿¿¿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.