7 de febrero de 2016

Microbenchmarks comparing = and eq? in Racket

Comparing = and eq?

The other day I wanted to compare the difference in the execution time between = and eq? in Racket when both arguments are fixnum, i.e. small integers. I used two almost equal microbenchmarks. The strange thing is that in one case when I made the change the time difference was almost 3 seconds and in the other it was only 0.3 seconds. So I started to investigate more ...

 The goal of the experiment was to see what happens if you have a program with something like
(lambda (vec)
  (when (= (vetor-length vec) 3)
    (something-interesting-with vec ...)))

 As (vector-length v) it is a fixnum, it is the same to use eq? and =, but = is nicer, it is more idiomatic. Is it possible to improve Racket optimizer to make this change during compilation? How much time can we gain?

 Using eq? is faster because it simply compares pointers, or in this case the value of the fixnum. (Pointers have even addresses, the finums are represented internally as an odd "pointer", the number n is represented by 2*n+1). Then the implementation of eq? is reduced to something like a = in C or its equivalent in assembler.

 Instead = has to consider that the values to compare may been fixnum, or flomums or bignum or complex or ... and convert from one to another if necessary. So it seems that it will take a little longer to run.

To measure this, we will compare how long it takes to run:
(for ([i (in-range 1000000000)])
  (= x 3))))
(for ([i (in-range 1000000000)])
  (eq? x 3))))

using a value of x that is a fixnum. In this case, we will make x to be (vector-length vec), where vec is a vector of length 3.

 The problem is that the value calculated inside the for is discarded. That always makes me nervous in microbenchmarks. So let's try also with for/and, that doesn't calculate anything interesting in this case, but at least it formally look's at the result of the expression that is inside the for.

The program

Let's go directly to the full program:
#lang racket

(define-syntax-rule (gc/time label expr)
  (begin
    (collect-garbage)
    (collect-garbage)
    (collect-garbage)
    (display label)
    (time expr)))
 A macro to measure the time. The recommendation is to call three times the garbage collector to clean everything, including finalizers, if any is present. I think it is not necessary in this case, but it doesn't hurt. 
(define vec (if (zero? (random 2))
              (vector 1 2 3)
              (vector 3 2 1)))
(set! vec vec)
We define vec as a vector of length 3. We use an odd way to confuse the optimizer.

 Actually, I guess that using just set! is enough to confuse the optimizer. Because set! marks the variable as mutable and that disables almost all optimizations.		 
(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))))
)
 We repeat the measurements 7 times, to get lucky. With for/and and for, with = and eq?.

 Each copy defines its own x, so that the information discovered in one measurement does not affect the other measurements.

Results

The first and most important thing to remember measuring the time from the command line using
    racket file.rkt
and not inside DrRacket. (DrRacket has many features enabled to make it easier to debug, and consumes a lot of memory, so it changes the times of the measurements.)

 For this kind of measurements, I prefer that the number of repetitions is big enough to make each measured take between 5 and 10 seconds. Normally less than 5 seconds is very noisy (less than 1 second is vvveeerrryyy noisy (less than 100 ms is ridiculously noisy)). More than 10 seconds is boring. With 1000000000 repetitions I get a reasonable range on my computer. (Note: With a faster computer, you may have to use a larger number. But in Racket 32 bit the largest fixnum is 1073741823, and it's better to nest two fors than using a counter that is a bignum. Otherwise a large part of the time would be spent in bignum calculations and that would mask the time difference between eq? and =.)

 These are the results, using Racket 6.3, sorted in each column from lowest to highest:
 = + for/and eq? + for/and    = + for  eq? + for
time (ms) 10561 10421 7504 4665
(sorted) 10608 10421 7535 4695
10640 10467 7566 4695
10655 10483 7597 4696
10858 10593 7613 4727
11060 10764 7894 4789
11607 10795 8065 4852
average (ms) 10855.6 10563.4 7682.0 4731.3
diff: = vs eq? 292.1 2950.7
2.7% 38.7%
sigma (ms) 374.4 158.7 196.5 61.2


Time comparison, sorting the measurements

Starting the time axis from 0
When we compare the versions that use for, the difference between = and eq? is 2950.7ms on average (it´s a 38.7%). It is much larger than the sigmas, so clearly there is a improvement.

 When we compare the versions that use for/and, the difference between = and eq? is 292,1ms on average (it's a 2.7%). It's almost the same size as the sigmas, so we should call a statistician for an analysis. I get p = 0.093 with two tails, and p = 0.047 with one tail. It's not enough for a Nobel prize, but it's ok for a blog article. I swore I didn't not repeat all this 10 times. (Note: To reduce the p we should increase the amount of repetitions, I guess it would be enought to get 30 aproximately, this is left as an exercise.)

 As I said, I was very surprised that in one case the difference is 293.1ms and in the other case it's 2950.7ms. What's going on?

Decompiling

To understand what happens we need to compile and decompile the file, to see what is the real code that runs in each case. (Note: Actually, Racket has a JIT stage with some additional optimizations, so there could be more surprises. There is a package to look at the code in assembler, but it is more difficult to interpret the assembler code, except for very short functions..)

 The idea is to run
    raco make file.rktkt
    raco decompile filerkt
Or to read everything easily:
    raco make file.rkt
    raco decompile file.rkt > file-dec.rktd

 OK, the decompiled code is long and quite incomprehensible. The decompiler tries to transform back the internal structures to something that looks enough like a Racket so that you can understand it, but there are still some parts where the internal structures are visible. Furthermore, almost all variable names are lost, so the decompiler invents one for them using the internal variable type and number.

 To understand better what is happening, I cleaned up the automatic version, I put cute names to variables, and I fixed the format and some details. My hand decompiled version has a lot of  creativity, but I think it keeps the spirit of the automatic version enough to understand what is the difference between the program that uses for and for/and.

Header and main loop

The program structure after compiling, decompiling and creatively cleanup is:
#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...))
 Totally fake header. It's doesn't look like the decompiled version at all, but it has all the necessary definitions to make possible to compile the rest of the program. 
(define-syntax-rule (gc/time label expr)
  'looong-expanded-version...)
 The definition of the macro is expanded and occupies many lines in the decompiled program. We don't need it now, so let's replace it creatively by this. 
(define vec (if (zero? (random 2))
              (vector 1 2 3)
              (vector 3 2 1)))
(print-values (set! vec (#%checked vec)))
The print-values is necessary here because low level Racket doesn't show the expressions calculated on the module, unlike the high-level behavior.

 The #%checked is there to check that vec has already been defined, and otherwise generate an error. The compiler does not put too much effort into the mutable variables, so instead of deciding whether or not it is necessary to check it, the compiler adds a check just in case.		 
(define (lift_eq_plain)
  ...)
(define (lift_=_plain)
  ...)
(define (lift_eq_and)
  ...)
(define (lift_=_and)
  ...)
 The expressions that we want to time are lifted and they appear as definitions.

 And each one is explicitly expressed as a lambda, but I hid them in a define.  For some reason, they are in reverse order.

This is the most interesting part, so I'll leave the details for later ...		 
(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_=_and))


         (collect-garbage)
         (collect-garbage)
         (collect-garbage)
         (display "eq: and:  ")
         (time (lift_eq_and))


         (collect-garbage)
         (collect-garbage)
         (collect-garbage)
         (display "=:  plain: ")
         (time (lift_=_plain))


         (collect-garbage)
         (collect-garbage)
         (collect-garbage)
         (display "eq: plain: ")
         (time (lift_eq_plain))


         (for-loop (void) (fx+ r 1))))
     ret)))
 This is the main loop, where we repeat everything 7 times. The macro that enclosed the code to measure the time is expanded and it calls the lifted functions that are defined above.

 Actually, time is also a macro that is expanded. But to get a code that is not so long, I unexpanded it creatively.

 The condition of the main loop appears here with a fx+ and fx<, but they really unsafe-fx+ and unsafe-fx<. The problem is that the decompiled code with so many unsafe is horrible. So I changed them creatively to fx+ and fx< and I put a require that renames them in the fake header.

 The #%sfs-clear is used to clean the variable. This cleanup is not visible from Racket and is only used when the compiler realizes it will never use that variable again. In this case the variable is (void) so it doesn't matter if it is cleaned or not. If it were a variable with a large value, for example (make-vector 1000), this clean up is important for recursion to not exhaust all the memory with variables that are no longer going to be used.

 The (let for-loop (...) ..) is also expanded in a letrec and a lambda. I unexpanded it because for me it is easier to understand.

 Where it says (void), it is actually a #<void>, because the code has the value instead of the function call.

Up to now, we explained the meaning of all functions defined in the fake header, and the difference between the true version and header's version. It remains to explain the macro #%let/closed.

 I also hope it is clear that I made several changes that simplify the code, but they correspond to things that are expanded in the actual decompiled version.

Comparing the versions with for/and

Let's compare the versions that use for/and, changing = by eq?
Version with = and for/and Version with eq? and for/and 
(define (lift_=_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_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))))

The first thing we notice is that they are almost the equal. This is not very surprising. So the difference in time is only due to the change of = by eq?.

 It is the equivalent to analyze either versions. The automatic decompiled version has two lambdas in each panel. I liked the MIT notation that hides the lambdas, so one of them is hidden inside the define. I hid the other lambda in a named let.

During the first expansions, for/and becomes a letrec and lambda (and some ifs obviously). The lambdas are inlined, so the final code looks similar to a loop unrolling.

 The first 4 cycles are in the white part. It's visible how it checks 4 times if (= x 3). It isn't visible that it checks if (fx< i 1000000000) because the value of i is known, then it becomes something like (fx< 1 1000000000) that is clearly #t, so (if (fx< 1 1000000000) tb fb) disappears. So the counter i starts from 4 rather than starting from 0.

 The cyan part makes the other 999999996 loop iterations. Again, due to inlining, each function for-loop  tests the conditions 4 times before calling itself recursively. This reduces the number of actual function calls, that are expensive.

 The for-loop function has 3 arguments, which is 1 more than expected:
  • The counter i_, which obviously must be there.
  • The value t4_ to return if we are just at the last iteration.
  • The value x4_ that is equals the value of x. When for-loop is called recursively the value of x_ is equal to the previous value of x_ that was x. (Got that?)
This is a very nice trick. Instead of using the value of x that is defined outside, the function uses the value of x_ that is an argument, but they actually have the same value. With this change the function for-loop doesn't have to use any external local variables, it just uses its arguments and internal variables. This makes it a closed closure (what normal people call function) and it can be implemented more efficiently.

 In the handmade decompilation I defined the function for-loop using a #%let-loop/closed which is a macro that simply becomes a named let. Actually, as it is a closed closure, it is defined by a special structure %#closed. The idea is that as it doesn't dependent on the local variables, so it can be implemented as if it were a separate function defined with a define. With this it possible to create fewer closures and everything goes faster. There are some details that still do not understand ... But the decompiler inserts the definition here instead of putting it in a separate define, so I'm not lying too much in this part.

Comparing the versions with for

Let's compare the versions that use for, changing = by eq?
Version with = and for Version with eq? and for 
(define (lift_=_plain)
  (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_plain)
  (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_))))

The first thing we noticed is that they are shorter than the previous versions. Let me count ... The former versions had 39 lines and these have 34 and 20.

 Let's consider first the version that use for and =.

In the for/and we have to use an if to see if the result (= x 3) is #f, in the version with for the value of (x = 3) is ignored. So the if disappears and is replaced by a begin. That change saves time and therefore the version with for and = is faster.

 Now the first 5 cycles are outside the for-loop function so the counter i starts from 5. In addition, the for-loop includes 5 cycles in each recursion in the cyan part. I guess there is an additional inlining because it's smaller. I don't think this changes the runtime too much.

 The for-loop function has again 3 arguments:
  • The counter i_, which obviously must be there.
  • The value t5_ to return if we are just at the last iteration, which is not very useful because it's always (void).
  • The value x_ that is equals the value of x, to use the same trick that we used in the other functions to get a closed closure.
Looking carefully, the function checks 1000000000 times that (= x 3) does not generate an error, and when it's completely sure, it returns (void). This is faster than previous versions that checked that (= x 3) doesn't generate an error and that the value was not #f.

 Let's look now at the version that use for and eq?.

 Now the firs 10 cycles are outside the function for-loop so i starts from 10. In addition, the for-loop includes 5 cycles in each recursion in the cyan part. I guess there is even more inlining because the funtion is even smaller. (10 = 2 * 5?)

 As eq? never never never fails (when called with two arguments), then (eq? x_ 3) can be omitted, along with the begin that was needed to hold the (= x 3). Moreover, as x is never used, the compiler marks it with a special flag so that the result is not saved. This may not save much memory in this case, but it can be useful if x were a large vector or something.

 Unlike the previous functions, for-loop has only 2 arguments:
  • The counter i_, which obviously must be there.
  • The value t10_ to return if we are just at the last iteration, which is not very useful because it's always (void).
  • The value of x is not used, so it's not necessary to add an extra argument x_.
Actually, this function just counts to 1000000000 and returns (void). Obviously faster.

Conclusions

Instead of changing the = for eq?, we could change it for unsafe-fx=. I suppose that eq? and unsafe-fx= do the same calculation, which is equivalent to a = in C or it's version in assembler. I like unsafe-fx= a little more. Generalizing the same idea, we could change the < for unsafe-fx< and in a similar way many other comparators.

 In a realistic case, if we calculate (= x 3) the program probably will do something with the result, so it's much more realistic the improvement of the first comparison using for/and than the change in the second using for.

 By changing = for eq? we obtained a 2.7% reduction in a microbenchmark. In a more realistic case I expect the remaining calculations to be more interesting and take more time, so I guess that the improvement will be reduced to 1% or 0.5%, after changing all the operations for its unsafe analog. This 1% improvement is similar to the improvement obtained in some handmade previous experiments, so it sounds good, but I have no systematic measurement.

 The Implementation of = is more complicated than the implementation of eq? because it has to consider many types of numbers and their conversions. But the time difference is small. I guess the first comparison is related to the case were both arguments are fixnum. This makes sense because the way fixnum are represented, because otherwise the implementation has to look if the argument are actual pointer (even) or fake "pointers" (odd) that represent fixnum. I should look at the implementation ...

 Dear future reader: These measurements were made using 6.3 Racket. In a future version, the optimizer may change automaticaly = to unsafe-fx= under the hood, when it's safe and the change makes sense. It's too late include this in version 6.4,  but it will probably be in version 6.5. The idea is to be able to write nice code that runs as fast as the ugly code. So, if you repeat the measurements and the run time with = and eq? are equal, probably the optimizer is already making the change automatically.

To think about

  • Measure everything many more times and see if the statistics improve. (I vote for at least 30 times.)
  • Run the decompiled version, to see what happens in a "second round" of compilation. (It seems that the runtimes are more or less equal, I had no patience to wait for it to finish.)
  • Try some variants, for example put the vector-length inside the cycle. (The analysis is more complicated because the optimizer learns that v is a vector and begins to optimize vector-length.)
    (let ([v vec])
      (for/and ([i (in-range 1000000000)])
        (= (vector-length v) 3))))
Etiquetas: ,

Microbenchmarks comparando = y eq? en Racket


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 usando
   racket 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, la diferencia entre = y eq? es de 2950,7ms en promedio, o sea un 38,7%. Es mucho mayor que las sigmas, así que claramente hay un cambio.

 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?)
Este es un truco muy lindo. En vez de usar el valor de x que esta definido afuera, la función usa el valor de x_ que es un argumento, y que en realidad son iguales. Con este cambio tenemos que la función for-loop no usa variables locales externas, sólo usa sus argumentos y variables internas. Esto hace que sea una closure cerrada (lo que la gente normal llama función) y se la puede implementar más eficientemente.

 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.
En el fondo, la función se fija 1000000000 veces que (= x_ 3) no genere un error, y cuando está bien segura devuelve (void). Esto es más rápido que las versiones anteriores que se fijaban que (= x_ 3) no genere un error ni que el valor sea #f.

 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_.
En el fondo, la función cuenta hasta 1000000000 y devuelve (void). Obvio que es más rápida.

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))))
Etiquetas: ,
Suscribirse a: Entradas ( Atom )