Comparando = y
eq?
El otro día quería comparar la diferencia en el
tiempo de ejecución de = y
eq? en Racket cuando ambos argumentos son fixnum, o
sea números enteros chicos. Lo extraño es que usando dos microbenchmarks casi
iguales, en un caso al hacer el cambio la diferencia de tiempo era de así 3
segundos y en la otra de casi 0,3 segundos. Así que me puse a investigar más ...
El objetivo es ver que pasa si en un programa uno tiene algo como
(lambda (vec)
(when (= (vetor-length vec) 3)
(algo-interesante-con vec ...)))
Como (vector-length v) es un fixnum es lo mismo usar eq? que =, pero el = queda más lindo, es más idiomático. ¿Es posible mejorar el optimizador de Racket para que haga el cambio durante la compilación? ¿Cuánto tiempo se gana?
Usar eq? es más rápido porque simplemente compara los punteros, o en este caso el valor del fixnum. (Los punteros de verdad tienen direcciones pares, los finum se representan internamente como un "puntero" impar, el número n se representa por 2*n+1). Entonces eq? se reduce a algo como un = en C o su equivalente en assembler.
En cambio = tiene que tener en cuenta que los valores a comparar pueden ser fixnum, o flomums, o bignum o complejos o ... y convertirlos de uno en otro en caso de ser necesario. Así que parece que algo más va a tardar.
Para medir esto, vamos a comparar cuánto tarda:
(for ([i (in-range 1000000000)])
(= x 3))))
(for ([i (in-range 1000000000)])
(eq? x 3))))
tomando un valor de
x que sea un fixnum. En este caso,
vamos a hacer que x
sea (vector-length vec), en dónde
vec es un vector
de largo 3.El problema es que el valor calculado adentro del for se descarta. Eso siempre me pone nervioso en las microbenchmarks. Así que mejor probemos también con for/and que no calcula nada interesante en este caso, pero al menos formalmente mira el resultado de la expresión que está adentro del for.
El programa
Vamos directamente al programa completo:#lang racket
(define-syntax-rule (gc/time label expr)
(begin
(collect-garbage)
(collect-garbage)
(collect-garbage)
(display label)
(time expr)))
|
Una macro para medir los tiempos. La recomendación es llamar tres veces al garbage collector para limpiar todo, incluyendo finalizadores si hay alguno dando vuelta. Creo que en este caso no hace falta, pero no daña. |
(define vec (if (zero? (random 2)) (vector 1 2 3) (vector 3 2 1))) (set! vec vec) |
Definimos
vec como
un vector de largo 3.
Usamos una manera rara para confundir al optimizador. En realidad, supongo que con sólo usar el set! alcanzaría para confundir al optimizador. Porque set! marca la variable como modificable (mutable) y eso deshabilita casi todas las optimizaciones. |
(for ([r (in-range 7)])
(gc/time "=: and: "
(let ([x (vector-length vec)])
(for/and ([i (in-range 1000000000)])
(= x 3))))
(gc/time "eq: and: "
(let ([x (vector-length vec)])
(for/and ([i (in-range 1000000000)])
(eq? x 3))))
(gc/time "=: plain: "
(let ([x (vector-length vec)])
(for ([i (in-range 1000000000)])
(= x 3))))
(gc/time "eq: plain: "
(let ([x (vector-length vec)])
(for ([i (in-range 1000000000)])
(eq? x 3))))
)
|
Repetimos
7 veces las mediciones, para tener suerte. Con
for/and y con
for, con
= y con
eq?, Cada copia define su propia v, para que la información descubierta en una medición no afecte las otras mediciones. |
Resultados
Lo primero y más importante es recordar medir los tiempos desde la línea de comando usandoracket archivo.rkt
y no desde DrRacket. (DrRacket tiene habilitadas muchas funciones para hacer más fácil el debugueo, y consume mucha memoria, así que modifica los tiempos que uno obtiene al medir.)
Para este tipo de mediciones, prefiero una cantidad de repeticiones de manera que cada tiempo medido esté entre 5 y 10 segundos. Normalmente menos de 5 segundos es muy ruidoso (menos de 1 segundos es mmmuuuuyyy ruidoso (menos de 100 ms es ridículamente ruidoso)). Más de 10 segundos hace que me aburra. Con 1000000000 repeticiones los tiempos me dan en un rango razonables en mi computadora. (Nota: Con una computadora más rápida, quizás haya que usar un número más grande. Pero en Racket de 32 bits el fixnum mas grande es 1073741823, así que quizás sea mejor anidar dos for que usar un contador del tipo bignum. Si no, una parte grande del tiempo se gasta en hacer cuentas con los bignum del contador y eso tapa la diferencia de tiempos entre eq? y =.)
Los resultados, usando Racket 6.3, ordenados en cada columna de menor a mayor son:
| = + for/and | eq? + for/and | = + for | eq? + for | |
| tiempos (ms) | 10561 | 10421 | 7504 | 4665 |
| 10608 | 10421 | 7535 | 4695 | |
| 10640 | 10467 | 7566 | 4695 | |
| 10655 | 10483 | 7597 | 4696 | |
| 10858 | 10593 | 7613 | 4727 | |
| 11060 | 10764 | 7894 | 4789 | |
| 11607 | 10795 | 8065 | 4852 | |
| promedio (ms) | 10855,6 | 10563,4 | 7682,0 | 4731,3 |
| dif: = vs eq? | 292,1 | 2950,7 | ||
| 2,7% | 38,7% | |||
| sigma (ms) | 374,4 | 158,7 | 196,5 | 61,2 |
 |
| Comparación de tiempos, ordenando las mediciones. |
 |
| Empezando el eje de los tiempos en 0 |
Cuando comparamos las versiones que usan for/and, la diferencia entre = y eq? es de 292,1ms en promedio, o sea un 2,7%. Es casi del mismo tamaño que los sigmas, así que habría que llamar a un estadístico para que lo analice. A mí me da p=0,093 con dos colas y p=0,047 con una cola. No servirá para un premio Nobel, pero alcanza para un artículo en un blog. Juró que no repetí todo esto 10 veces. (Nota: Para achicar los p habría que aumentar las cantidades de las repeticiones, supongo que con unas 30 alcanzan, queda como ejercicio.)
Como dije, lo que me sorprendió es que un caso el cambio es de 293,1ms y en en el otro el mismo cambio es de 2950,7ms. ¿Qué está pasando?
Descompilando
Para entender qué pasa no va a quedar más remedio que compilar y descompilar el archivo, para ver cuál es el código que se está ejecutando en cada caso. (Nota: En realidad Racket tiene una etapa más de JIT con algunas optimizaciones adicionales, así que podría haber más sorpresas. Hay un paquete para mirar el código en assembler, pero es más difícil de interpretar el código salvo para funciones muy cortas.)La idea es ejecutar
raco make archivo.rkt
raco decompile archivo.rkt
O para poder leer todo mejor:
raco make archivo.rkt
raco decompile archivo.rkt >archivo-dec.rktd
OK, el código descompilado e largo y medio inentendible. El descompilador trata de volver de las estructuras internas a algo que se parece lo suficiente a Racket para que se pueda entender, pero igual hay algunas partes en las que las estructuras internas son visibles. Además casi todos los nombres de variables se pierden, así que el descompilador les inventa uno usando el tipo interno de la variable y un número.
Para que se entienda mejor lo que está pasando, lo que hice fue limpiar el resultado, ponerle nombres más lindos a las variables, acomodar el formato y esas cosas. Mi versión a mano del descompilado tiene bastante creatividad, pero creo que mantiene el espíritu de la versión automática lo suficiente para entender cuál es la diferencia entre el programa que usa for y el que usa for/and.
Encabezado y ciclo principal
La estructura del programa después de compilarlo, descompilarlo y limpiarlo creativamente es:#lang racket
(require (only-in racket/unsafe/ops [unsafe-fx+ fx+]
[unsafe-fx< fx<]))
(define (print-values v) v)
(define (#%checked x) x)
(define (#%sfs-clear x) x)
(define-syntax-rule (#%let/closed name vars body ...)
(let name vars body...))
|
Encabezado totalmente trucho (¿falso?). Se parece muy poco a lo que hay en el descompilado, pero tiene las definiciones necesarias para que el resto del programa compile. |
(define-syntax-rule (gc/time label expr)
('looong-expanded-version...)
|
La definición de la macro está expandida y ocupa muchas líneas en el programa descompilado. Ya no la necesitamos, así que creativamente reemplacémosla por esto. |
(define vec (if (zero? (random 2)) (vector 1 2 3) (vector 3 2 1))) (print-values (set! vec (#%checked vec))) |
El print-values es necesario porque a bajo nivel Racket no muestra las expresiones que hay en el módulo, a diferencia del
comportamiento a alto nivel. El #%checked sirve para revisar si vec ya fue definido, y en caso contrario generar un error. El compilador no le pone mucho esfuerzo a las variables modificables, así que en vez de decidir si es necesario el chequeo o no, simplemente lo agrega por las dudas. |
(define (lift_eq?_for)
...)
(define (lift_=_for)
...)
(define (lift_eq?_for/and)
...)
(define (lift_=_for/and)
...)
|
Las expresiones a las que le queremos medir los
tiempos están lifteadas y aparecen como definiciones. Además cada una ya está expresada explícitamente como una lambda Por alguna razón están en el orden inverso. Como es la parte más interesante, dejemos los detalles para después ... |
(print-values
(let for-loop ([ret (void)]
[r 0])
(if (fx< r 7)
(begin
(#%sfs-clear ret)
(begin
(collect-garbage)
(collect-garbage)
(collect-garbage)
(display "=: and: ")
(time (lift_=_for/and))
(collect-garbage)
(collect-garbage)
(collect-garbage)
(display "eq: and: ")
(time (lift_eq?_for/and))
(collect-garbage)
(collect-garbage)
(collect-garbage)
(display "=: plain: ")
(time (lift_=_for))
(collect-garbage)
(collect-garbage)
(collect-garbage)
(display "eq: plain: ")
(time (lift_eq?_for))
(for-loop (void) (fx+ r 1))))
ret)))
|
Este es el loop principal en el que repetimos todo
7 veces.
La macro que encerraba el código para medir los tiempos está expandida y
llama a las funciones lifteadas que están definidas antes. En realidad time también es una macro y está expandida. Pero para que el código no se alargue tanto la desexpandí creativamente. La condición del loop principal aparece con un fx+ y un fx<, pero en realidad deberían ser unsafe-fx+ y unsafefx=. El problema es que el código descompilado con todos los unsafe queda horrible. Así que creativamente los cambié por fx+ y fx< y puse un require que los renombra en el encabezado trucho. El #%sfs-clear sirve para limpiar la variable. Esto no es visible desde Racket y sólo se usa cuando el compilador se da cuenta que nunca más se va a usar esa variable. En este caso la variable vale (void) así que no importa si se la limpia o no. Si fuera una variable más grande, por ejemplo (make-vector 1000), esta limpieza es importante para que la recursión no agote toda la memoria con variables que ya no se van a usar. El (let for-loop (...) ..) también está expandido en una letrec y una lambda. Lo desexpandí así porque a mi me resulta más fácil de entender. En donde dice (void) debería decir #<void> porque en el código está el valor en vez de la llamada a la función. |
Con esto queda explicada que significan todas las funciones definidas en el encabezado trucho, y la diferencia entre la versión verdadera y la del encabezado. Sólo queda explicar la macro #%let/closed.
Además espero que haya quedado claro que en la descompilación adicional manual hice varios cambios que simplifican la lectura pero que corresponden a cosas que están expandidas en la función verdadera.
Comparando las versiones con for/and
Comparemos las versiones que usan for/and, cambiando = por eq?| Versión con = y for/and | Versión con eq? y for/and |
|---|---|
(define (lift_=_for/and)
(let ([x (vector-length (#%checked vec))])
(let ([t1 (= x 3)])
(if t1
(let ([t2 (= x 3)])
(if t2
(let ([t3 (= x 3)])
(if t3
(let ([t4 (= x 3)])
(if t4
(#%let/closed for-loop ([x_ x] [t4_ t4] [i4_ 4])
(if (fx< i4_ 1000000000)
(let ([t5_ (= x_ 3)])
(if t5_
(let ([i5_ (fx+ i4_ 1)])
(if (fx< i5_ 1000000000)
(let ([t6_ (= x_ 3)])
(if t6_
(let ([i6_ (fx+ i5_ 1)])
(if (fx< i6_ 1000000000)
(let ([t7_ (= x_ 3)])
(if t7_
(let ([i7_ (fx+ i6_ 1)])
(if (fx< i7_ 1000000000)
(let ([t8_ (= x_ 3)])
(if t8_
(for-loop x_ t8_ (fx+ i7_ 1))
#f))
t7_))
#f))
t6_))
#f))
t5_))
#f))
t4_))
#f))
#f))
#f))
#f))))
|
(define (lift_eq?_for/and)
(let ([x (vector-length (#%checked vec))])
(let ([t1 (eq? x 3)])
(if t1
(let ([t2 (eq? x 3)])
(if t2
(let ([t3 (eq? x 3)])
(if t3
(let ([t4 (eq? x 3)])
(if t4
(#%let/closed for-loop ([x_ x] [t4_ t4] [i4_ 4])
(if (fx< i4_ 1000000000)
(let ([t5_ (eq? x_ 3)])
(if t5_
(let ([i5_ (fx+ i4_ 1)])
(if (fx< i5_ 1000000000)
(let ([t6_ (eq? x_ 3)])
(if t6_
(let ([i6_ (fx+ i5_ 1)])
(if (fx< i6_ 1000000000)
(let ([t7_ (eq? x_ 3)])
(if t7_
(let ([i7_ (fx+ i6_ 1)])
(if (fx< i7_ 1000000000)
(let ([t8_ (eq? x_ 3)])
(if t8_
(for-loop x_ t8_ (fx+ i7_ 1))
#f))
t7_))
#f))
t6_))
#f))
t5_))
#f))
t4_))
#f))
#f))
#f))
#f))))
|
Lo primero que notamos es que son casi iguales, no hay nada muy sorprendente. Así que la diferencia en tiempos se debe sólo al cambio de = por eq?.
Es lo mismo analizar cualquiera de las dos versiones. En la versión descompilada automática aparecen dos lambdas en cada panel. Siempre me pareció más clara la notación MIT que esconde las lambdas, así que una está escondida adentro del define. A la otra la escondí en un named let.
Inicialmente el for/and se transforma en un letrec y una lambda (y algunos ifs obviamente). Las lambdas se inlinean, así que queda algo parecido a un loop unrolling.
Los primeros 4 ciclos están en la parte blanca. Se ven que chequean 4 veces si (= x_ 3). No se ve que chequea si (fx< i 1000000000) porque el valor de i es conocido, entonces se transforma en algo como (fx< 1 1000000000) que es claramente #t, así que el (if (fx< 1 1000000000) tb fb) desaparece. Por eso que el contador i empieza en 4 en vez de empezar de 0.
La parte turquesa es la que realiza las otras 999999996 iteraciones del ciclo. Nuevamente, por los inlineamientos cada función for-loop prueba 4 veces antes de volver a llamarse recursivamente. Así se ahorran llamados a función que son caros.
La función for-loop tiene 3 argumentos, que son 1 más de los que uno espera:
- El contador i_ , que obviamente tiene que estar.
- El valor t4_ a devolver si llegamos justo a la última iteración.
- El valor de x_ que es igual al valor de x. Al llamarse recursivamente queda que el valor de x_ es igual al valor anterior de x_ que era x. (¿Se entiende?)
En la descompilación a mano definí la función for-loop usando un #%let/closed que es una macro que simplemente se transforma en un named let. En realidad como es una closure cerrada está definida por una estructura especial %#closed. La idea es que como no depende de las variables locales entonces de la puede implementar como si fuera una función independiente definida con un define. Con esto se logra crear menos closures y todo anda más rápido. Hay algunos detalles de esto que todavía no entiendo ... Pero el descompilador la intercala acá en vez de ponerla en una define independiente, así que yo no estoy mintiendo demasiado en esta parte.
Comparando las versiones con for
Comparemos las versiones que usan for, cambiando = por eq?| Versión con = y for | Versión con eq? y for |
|---|---|
(define (lift_=_for)
(let ([x (vector-length (#%checked vec))])
(begin
(= x 3)
(= x 3)
(= x 3)
(= x 3)
(= x 3)
(#%let/closed for-loop ([x_ x] [t5_ (void)] [i5_ 5])
(if (fx< i5_ 1000000000)
(begin
(= x_ 3)
(let ([i6_ (fx+ i5_ 1)])
(if (fx< i6_ 1000000000)
(begin
(= x_ 3)
(let ([i7_ (fx+ i6_ 1)])
(if (fx< i7_ 1000000000)
(begin
(= x_ 3)
(let ([i8_ (fx+ i7_ 1)])
(if (fx< i8_ 1000000000)
(begin
(= x_ 3)
(let ([i9_ (fx+ i8_ 1)])
(if (fx< i9_ 1000000000)
(begin
(= x_ 3)
(for-loop x_ (void) (fx+ i9_ 1)))
(void))))
(void))))
(void))))
(void))))
t5_)))))
|
(define (lift_eq?_for)
(let ([unused_x (vector-length (#%checked vec))])
(#%let/closed for-loop ([t10_ (void)] [i10_ 10])
(if (fx< i10_ 1000000000)
(begin
(#%sfs-clear t10_)
(let ([i11_ (fx+ (#%sfs-clear i10_) 1)])
(if (fx< i11_ 1000000000)
(let ([i12_ (fx+ i11_ 1)])
(if (fx< i12_ 1000000000)
(let ([i13_ (fx+ i12_ 1)])
(if (fx< i13_ 1000000000)
(let ([i14_ (fx+ i13_ 1)])
(if (fx< i14_ 1000000000)
(for-loop (void) (fx+ i14_ 1))
(void)))
(void)))
(void)))
(void))))
t10_))))
|
Lo primero que notamos es que son más cortas que las anteriores. Déjenme que cuente ... Las anteriores tenían 39 líneas y estas tienen 34 y 20.
Veamos primero la versión que usa for y =.
En el for/and hay que usar un if para ver si el resultado de (= x_ 3) es #f, en la versión con for se ignora el valor de (= x 3). Así que desaparece ese if y queda sólo un begin.
Eso ahorra mucho tiempo y por eso la versión con = y for es más rápida.
Ahora los los primeros 5 ciclos están afuera de la función for-loop por eso el contador i empieza de 5. Además el for-loop que también incluye 5 ciclos en cada recursión en la parte turquesa. Supongo que como es más chica se inlinea una vez más. No creo que esto cambie mucho el tiempo de ejecución.
La función for-loop tiene nuevamente 3 argumentos:
- El contador i_ , que obviamente tiene que estar.
- El valor a devolver t5_ si llegamos justo a la última iteración, que es medio inútil porque siempre vale (void).
- El valor de x_ que es igual al valor de x, para usar el mismo truco que en las otras funciones y tener una closure cerrada.
Veamos ahora la versión que usa for y eq?.
Ahora los los primeros 10 ciclos están afuera de la función for-loop por eso i empieza de 10. Además el for-loop que también incluye 5 ciclos en cada recursión en la parte turquesa. Supongo que como es más chica se inlinea todo un poco más. (¿10 = 2 * 5?)
Como eq? nunca nunca nunca genera un error (cuando una la llama con dos argumentos), entonces (eq? x_ 3) se puede tachar, junto con el begin que hacía falta antes para sostener el (= x_ 3). Es más, como x nunca se usa, el compilador la marca con un flag especial para que el resultado no se guarde. Esto no ahorra mucha memoria en este caso, pero puede ser útil si x fuera un vector grande o algo así.
A diferencia de las anteriores, la función for-loop tiene sólo 2 argumentos:
- El contador i_ , que obviamente tiene que estar.
- El valor a devolver t10_ si llegamos justo a la última iteración, que es medio inútil porque siempre vale (void).
- El valor de x no se usa, así que no hace falta agregar el argumento x_.
Conclusiones
En vez de cambiar el = por un eq? se lo podría cambiar por un unsafe-fx=. Supongo que eq? y unsafe-fx= hacen lo mismo, que es equivalente a un = en C o su versión en assembler. Me gusta unsafe-fx= un poco más. Generalizando la misma idea, se podría cambiar el < por un unsafe-fx< y así con todos los comparadores.En un caso realista si uno calcula (= x 3) probablemente el programa haga algo con el resultado, así que es mucho más realista la mejora de la primera comparación usando for/and que la segunda que usa for.
Cambiando el = por el eq? obtuvimos un 2,7% de reducción en una microbenchmark. En un caso más realista esperaría que el resto de las cuentas sea más interesante y ocupe más tiempo, así que supongo que la mejora se reduciría a un 1% o 0,5%, al cambiar todas la operaciones por su análogo unsafe. Este valor del 1% coincide con algunos experimentos hechos a mano antes, así que suena bien, pero no tengo una medición sistemática.
La implementación de = es más complicada que la de eq? porque tiene que considerar muchos tipos de números y sus conversiones. Sin embargo la diferencia de tiempo es poca. Mirando los resultados supongo que la primera comparación está relacionada con el caso en que ambos argumentos son fixnum. Esto tiene sentido por como se representan los fixnum, ya que en otro caso hay que mirar si los argumentos son puntero de verdad (pares) o "punteros" de mentira representan un fixnum (impares). Debería mirar la implementación ...
Estimado futuro lector: Estas mediciones fueron hechas usando Racket 6.3. Ya es tarde para que se incluya en la versión 6.4, pero probablemente esté en la versión 6.5. La idea es que uno puede escribir código lindo que anda igual de rápido que el feo. Así que si usted mide y da lo mismo usar = que eq?, probablemente el optimizador esté haciendo el cambio automáticamente.
Para pensar
- Medir todo muchas más veces y ver como mejoran las estadísticas. (Yo voto por 30 al menos.)
- Ejecutar la versión descompilada, para ver que pasa en una "segunda vuelta" de compilación. (Parece que anda más o menos igual, no tuve paciencia para esperar a que termine.)
- Probar algunas variantes, por ejemplo poner vector-length adentro del ciclo. (El análisis se complica un poco porque el optimizador aprende que v es un vector y empieza a optimizar vector-length.)
(let ([v vec])
(for/and ([i (in-range 1000000000)])
(= (vector-length v) 3))))
