[racket] Style and Performance question

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Tue May 10 10:05:35 EDT 2011

1. I reran the timing experiments:
	build a list of 1,000 random naturals in [0,10)
	run a loop 100 times 
	that computes the sqrt for the entire list for each iteration 

The rough results are: 

  -- untyped, exact rationals: ~10,000 msec 
  -- untyped, inexact numbers: ~200 msec
  -- typed, inexact numbers: ~90msec 

If you run typed, exact rationals you seem to get something a tad faster than 10,000 but it's not worth writing home about. 

SO: a factor of 50 is due to inexact numbers and a factor of 2 is due to types. (A factor of 2 is a good one.)

2. The addition in lieu of the multiplication is consistently the fastest version of the three I mentioned last night: 

  (: the-sqrt : Real -> Real)
  (define (the-sqrt y)
    (let loop [(x (/ y 2.0))]
      (let [(error (- y (* x x)))]
        (if (< (abs error) epsilon) 
            (loop (+ x (/ error (+ x x))))))))

Our compiler should probably implement reduction of strength optimizations based on this one experiment alone. The savings here are over 10%. 

3. As for my mistake: I had typed sqrt as Float -> Exact-Rational for reasons that escape me now. If you do so, 

  (: my-sqrt : Float -> Exact-Rational)
  (define (my-sqrt y)
    (let loop [(x (/ y 2))]
      (let [(error (- y (* x x)))]
        (if (< (abs error) epsilon) 
            (loop (+ x (/ error 2 x)))))))

the type checker highlights x. In response I changed BOTH the 2 and the Exact-Rational and made the quickly forgotten mental note that I mentioned last night. 

-- Matthias

Posted on the users mailing list.