El otro día estuve leyendo otro benchmark más: "Lambda Land: Functional Languages Need Not Be Slow". (¿Es un benchmark? Lindo artículo, de todas maneras). Compara Racket, Python, Rust, Julia y JavaScript intentando la conjetura de Collatz hasta 500.000.
Antes que nada, dos advertencias:
- Hay mentiras, malditas mentiras, estadísticas y benchmarks.
- La mejor manera de hacer trampa en un benchmark es cambiar el compilador.
La idea es intentar mejorar el tiempo del programa Racket siguiendo el espíritu del benchmark y luego extraer algunas ideas para mejorar el compilador y automatizar las mejoras cuando sea posible. El compilador de Racket transforma el programa a código en Chez Scheme, por lo que la mayoría de las mejoras de optimización las vamos a hacer en el compilador Chez Scheme y, con un poquito de suerte, van a hacer que los programas en los dos lenguajes sean más rápidos.
(No conozco lo suficiente los otros lenguajes como para intentar algo similar, así que ni siquiera lo voy a intentar. Me gustaría leer análisis similares.)
Cada benchmark es diferente. En mi opinión, el objetivo de este benchmark es escribir código lindo y ver qué puede hacer el compilador. Estoy más acostumbrado a benchmarks que intentan exprimir cada milisegundo y usan primitivas que parecen insultos como #3%$unsafe-fl*+!, así que este tiene un enfoque muy diferente, ya que sólo usa código lindo.
Con los cambios, los tiempos de ejecución son:
Versión del programa Segundos
Original de Lambda Land (Racket 9.0) 17.9
Rápido ahora, pero no muy lindo (Racket 9.0) 5.3
Rápido algún día y lindo (Racket 9.0) 17.8
Rápido algún día y lindo (Racket 9.3?) 4.9 (estimado?)
(Todos los tiempos medidos en la línea de comandos, fuera de DrRacket. DrRacket tiene “debugging” habilitado por defecto, lo que agrega mucho tiempo adicional a cambio de mejores mensajes de error.)
Para referencia, este es el código original con dos expresiones resaltadas, que veremos que son las más lentas:
(define (count-collatz n [cnt 1])
(cond
[(= n 1) cnt]
[(even? n) (count-collatz (/ n 2) (+ 1 cnt))]
[else (count-collatz (+ (* 3 n) 1) (+ 1 cnt))]))
Código rápido pero no tan lindo
Mi primer paso fue escribir código no muy lindo pero rápido. Pero tampoco feo, sólo un poquito feo. La idea es encontrar un equilibrio entre código lindo y rápido. Probé muchas variantes hasta que entendí que estas dos expresiones eran las más importantes para mejorar la velocidad.
Los cambios son:
Dividir la función en una parte para los fixnums y otra para los bignums.
La división / es lenta, así que la reemplazamos por unsafe-quotient (parte verde).
También even? es lento, así que dividimos la lógica y usamos otro unsafe (parte azul).
(require racket/fixnum)
(require racket/unsafe/ops)
(define (count-collatz n [cnt 1])
(if (fixnum? n)
(cond
[(= n 1) cnt]
[(zero? (unsafe-fxremainder n 2)) (count-collatz (unsafe-fxquotient n 2) (+ 1 cnt))]
[else (count-collatz (+ (* 3 n) 1) (+ 1 cnt))])
(cond
[(= n 1) cnt]
[(even? n) (count-collatz (/ n 2) (+ 1 cnt))]
[else (count-collatz (+ (* 3 n) 1) (+ 1 cnt))])))
No quedó tan feo en mi opinión, y el tiempo de ejecución pasa de 17,9 segundos a 5,3 segundos en mi computadora. Notar que la primera rama para fixnums tiene algunos trucos, pero la segunda es directamente el código original.
División y cociente
Podemos medir el tiempo de ejecución modificando la expresión verde:
Azul Verde Segundos
(even? n) (/ n 2) 17.9
(even? n) (quotient n 2) 17.8
(even? n) (fxquotient n 2) 17.3
(even? n) (unsafe-fxquotient n 2) 7.6
Pensémoslo como una cadena de transformaciones.
Cambiar / a quotient es muy difícil para el compilador. La pasada de optimización no sabe suficiente álgebra para hacer esta transformación. (Creo que esto es posible algún día en casos muy específicos como este, que usa módulo 2 y un predicado, pero para simplificar supongamos que es imposible.) Algunos de los ejemplos en otros lenguajes usan la división entera, así que creo que es “justo” usar quotient acá.
Después de este primer cambio, el tiempo mejora un poco y la diferencia con fxquotient también es pequeña. Pero la última versión con unsafe-fxquotient es mucho más rápida. La buena noticia es que, a partir de la expresión que usa quotient, es posible que una versión mejorada del compilador realice los reemplazos durante la compilación y obtenga el código más rápido.
(También probé arithmetic-shift. Hay algunas cosas extrañas que revisar.)
El predicado even?
Ahora podemos medir el tiempo de ejecución al cambiar la expresión azul:
Azul Verde Segundos
(even? n) (unsafe-fxquotient n 2) 7.6
(zero? (remainder n 2)) (unsafe-fxquotient n 2) 20.8
(zero? (fxremainder n 2)) (unsafe-fxquotient n 2) 19.6
(zero? (unsafe-fxremainder n 2)) (unsafe-fxquotient n 2) 5.3
(zero? (bitwise-and n 1)) (unsafe-fxquotient n 2) 4.9
(zero? (fxand n 1)) (unsafe-fxquotient n 2) 4.9
(not (bitwise-bit-set? n 0)) (unsafe-fxquotient n 2) 5.4
De nuevo, pensémoslo como una cadena de transformaciones.
Cambiar even? a (zero? (remainder _ 2)) es muy malo, no sé por qué. Vale la pena mirarlo más adelante. Algunos otros lenguajes usan expresiones similares, así que es un cambio "justo", pero me preocupa que sea tan lento, ya que alguien podría usarlo.
En cualquier caso, tras el primer cambio, es posible que una versión mejorada del compilador cambie la primitiva durante la compilación a fxremainder y luego a unsafe-fxremander, lo que haría que el código fuera más rápido que la versión original.
Las dos versiones siguientes con bitwise-and y fxand son ligeramente más rápidas, pero son demasiado distintas del código original, así que no las clasifico como "justas". En ambos casos, el compilador las modifica para usar el equivalente de unsafe-fxand.
La última versión con (not (bitwise-bit-set? _ 0)) es tan rápida como la versión que usa (zero? (unsafe-fxremainder _ 2)), pero usa un predicado. Esto es más amigable para la pasada de optimización, que entiende mejor los predicados que las funciones con resultados binarios. Esto podría ser relevante en un futuro lejano para permitir que el compilador reemplace / con quotient.
De todas maneras, es mejor hacer que la pasada de optimización simplemente transforme even? en la versión unsafe de la primitiva de Chez Scheme cs:fxeven?, que es tan rápida como (zero? (fxand _ 1)).
Una macro para el camino feliz
Una de las ventajas de Racket es que permite usar macros para realizar transformaciones extrañas en el código. (Si no querés que sus compañeros de trabajo y su futuro vos le odien, use las macros con sabiduría, documentalas, usá syntax-parse para obtener buenos mensajes de error y evitá usar macros cuando haya otra opción.)
Así que definimos una macro happy-path
(define-syntax-rule (happy-path test
body ...)
(if test
(begin body ...)
(begin body ...)))
Es una macro muy tonta. Cuando test es verdadero, ejecuta body... y cuando test es falso, ¡también ejecuta body... ! Lo interesante es que el compilador puede aplicar diferentes optimizaciones a cada rama. En particular, en nuestro caso, test va a ser (fixnum? n), por lo que una versión mejorada del compilador puede realizar en la primera rama todos los cambios que mencionamos antes, obteniendo así un código lindo que es rápido. La versión final es
(define (count-collatz n [cnt 1])
(happy-path (fixnum? n)
(cond
[(= n 1) cnt]
[(even? n) (count-collatz (quotient n 2) (+ 1 cnt))]
[else (count-collatz (+ (* 3 n) 1) (+ 1 cnt))])))
Conclusiones
Si sabés que todos los argumentos y el resultado son enteros, usa quotient en vez de /. Creo que es una buena recomendación para todos los lenguajes y compiladores.
Probá happy-path para que el optimizador pueda hacer mejoras en el camino más esperado, o en ambos si hay suerte. Probablemente (fixnum? n) y (flonum? n) sean tests útiles en general. Sería bueno que el compilador pudiera hacerlo por vos, pero es difícil sin duplicar el tamaño del código ejecutable y quizás obtener ninguna mejora de velocidad.
Espero que estas mejoras se incluyan en Racket 9.3 (mediados de 2026), así que usa tu máquina del tiempo y actualiza. Armé una rama de prueba de concepto [for Racket, for Chez Scheme], pero la idea es crear una versión más general de las mejoras. (Por ejemplo, si even? es mágico, es bueno que odd? también sea mágico, para mantener el equilibrio del universo y evitar sorprender a los usuarios).
Código
Original de Lambda Lang Blog
#lang racket
(define (count-collatz n [cnt 1])
(cond
[(= n 1) cnt]
[(even? n) (count-collatz (/ n 2) (+ 1 cnt))]
[else (count-collatz (+ (* 3 n) 1) (+ 1 cnt))]))
(define (count-collatz-upto n)
(for/fold
([max-seen 0])
([i (in-range 1 n)])
(max max-seen (count-collatz i))))
(displayln (format "\nDone ~a" (count-collatz-upto 5000000)))
Rápido ahora, peor no muy lindo (Racket 9.0)
#lang racket
(require racket/fixnum)
(require racket/unsafe/ops)
(define (count-collatz n [cnt 1])
(if (fixnum? n)
(cond
[(= n 1) cnt]
[(zero? (unsafe-fxremainder n 2)) (count-collatz (unsafe-fxquotient n 2) (+ 1 cnt))]
[else (count-collatz (+ (* 3 n) 1) (+ 1 cnt))])
(cond
[(= n 1) cnt]
[(even? n) (count-collatz (/ n 2) (+ 1 cnt))]
[else (count-collatz (+ (* 3 n) 1) (+ 1 cnt))])))
Rápido algún día y lindo (Racket 9.3?)
#lang racket
(define-syntax-rule (happy-path test
body ...)
(if test
(begin body ...)
(begin body ...)))
(define (count-collatz n [cnt 1])
(happy-path (fixnum? n)
(cond
[(= n 1) cnt]
[(even? n) (count-collatz (quotient n 2) (+ 1 cnt))]
[else (count-collatz (+ (* 3 n) 1) (+ 1 cnt))])))
(define (count-collatz-upto n)
(for/fold
([max-seen 0])
([i (in-range 1 n)])
(max max-seen (count-collatz i))))
(displayln (format "\nDone ~a" (count-collatz-upto 5000000)))
