[racket] Style and Performance question

From: Matthew Flatt (mflatt at cs.utah.edu)
Date: Tue May 10 19:51:49 EDT 2011

I think all of your questions have been covered in the thread, but I'll
answer them again to offer a few extra opinions and to summarize the

At Mon, 9 May 2011 18:38:41 -0500, Patrick King wrote:
> I now show the "approved" solution, and my own, both edited a bit to cleanly
> present my questions.
> (define epsilon 1e-7)
> ; The "approved" solution
> (define (approved-sqrt y)
>   (let loop [(x (/ y 2))]
>     (if (< (abs (- (* x x) y)) epsilon) x
>       (loop (- x (/ (- (* x x) y) (+ x x)))))))
> ; My solution
> (define (my-sqrt y)
>  (let loop [(x (/ y 2))]
>    (let [(error (- y (* x x)))]
>      (if (< (abs error) epsilon) x
>          (loop (+ x (/ error 2 x)))))))
> I haven't timed the two, as I'm more interested in the "big picture" than
> this particular function.
> Question 1: Is my use of the temporary "error" worth it in terms of
> performance (the approved solution calculates (* x x) twice)? If it's not
> worth it, how big does the calculation have to become before it does? Can
> the compiler make such a temporary live only in a register?

For generic arithmetic on values other than fixnums, the local binding
is likely worthwhile, mostly because it avoids repeated boxing of the
arithmetic result. (At least for now; see below on plans for CSE.)

I also find the code easier to read with the local binding.

>    Question 1a: How creeped are you by my changing the meaning of error for
> these few lines? I find myself doing stuff like this, in the name of my idea
> of readability, a lot.

It didn't bother me or even occur to me that you were shadowing the
usual `error' binding. Still, it's probably better to avoid shadowing
bindings like `error' when you notice.

> Question 2: The approved solution favored (/ ... (+ x x)) over my (/ ... 2
> x). Cost of division versus readability. Wasn't a conscious decision of mine
> at the time, but now I'm curious. How smart is the compiler when presented
> with a division by 2?

The "strength" of arithmetic operations --- such as devision versus
addition --- is unlikely to matter. The big effects are (1) using
inexacts versus exact rationals, where inexacts tend to be faster, (2)
mixing inexacts and exacts, which is slower than just inexacts, and (3)
using flonum-specific operations (or Typed Racket with the `Float'
type) versus generic operations, where flonum-specific operations can
be much faster because they enable unboxing in the compiler.

> With multiple recalls of the same value?

The Racket compiler does not currently perform common-subexpression
elimination (CSE). As it happens, I've been thinking about adding a CSE
pass, but it's difficult to predict whether that will happen next week
or next year.

Posted on the users mailing list.