How to optimize this piece of Racket code?

Question

I want to calculate the sum of 1 + 1/2 + 1/3 + ... + 1/100000000 (using double float).

With SBCL, this code runs as fast as in C:

(loop for i fixnum from 1 to 100000000 sum (/ 1.0d0 i) double-float)

How can I optimize this code in Typed Racket? I've tried

#lang typed/racket

(define: (test) : Float
         (for/fold: : Float
                    ([s : Float 0.0])
                    ([i : Fixnum (in-range 1 100000001)])
                    (+ s (/ 1.0 i))))

(time (test))

This code is only a bit faster than untyped one. Can I go further?

Answer 1

If you run Optimization Coach on this like Greg suggested, it immediately tells you that the loop body is slow because the / function is doing mixed arithmetic (on a fixnum and a flonum). If you insert a (fx->fl i) in place of i it's faster (close to 2x on my machine).

Also, if you are timing this in DrRacket you will want to time it with the racket executable instead. DrRacket adds debugging instrumentation that helps during development, but isn't good for timing.

Answer 2

Here's a new version, in which I made a little helper macro for summing floats.

#lang typed/racket

(require syntax/parse/define)

(define-simple-macro (for/flsum x ... (c ...) b ... e)
  (for/fold : Float x ... ([s 0.0]) (c ...) b ... (+ s e)))

(time (for/flsum ([i : Positive-Fixnum (in-range 1 100000001)]) (/ 1.0 i)))

Note that using Positive-Fixnum as the type means we don't need any additional conversions -- Typed Racket knows that i is never 0, and so the / can always be optimized. This now runs almost exactly as fast as SBCL on my machine.

The only difference between it and the SBCL code is the need to specify that the fixnum is positive, which is required because SBCL has the same semantics for (/ 1.0 0) and (/ 1.0 0.0) -- it raises an exception, whereas Racket produces +inf.0 in the second case and an exception in the first case.

I plan to add for/flsum or something like it to Racket itself.