[racket] deceptive perfomance for typed racket in integer division

At Tue, 11 Dec 2012 16:43:25 +0000 (UTC),
daniel rupis wrote:
>  Anyway, my point was that I was expecting something more from typed racket.
> Since typed racket use types (like declaring type in sbcl) I was expected better
> perfomance, that's all.

There's a big difference between Typed Racket and types in SBCL.

Typed Racket, by design, never sacrifices safety; it only optimizes when
it can prove that the optimization is safe.

This means that, to get TR to specialize your code for fixnums, you need
to use fixnum types explicitly (which is roughly equivalent to the
`(type (integer 0 300000) I J)' in your original program).

To specialize an operation on fixnums, TR also needs to prove that its
results don't exceed fixnum range. This is hard to prove in general, and
limits the applicability of the optimization.

Here's a quick TR version that uses fixnum types:

    #lang typed/racket
    (define: (divisible-rec (i : Nonnegative-Fixnum) (j : Nonnegative-Fixnum))
        : Boolean
      (cond ((= j 1) #f)
            ((zero? (modulo i j)) #t)
            ((zero? j) (error "can't happen"))
            (else (divisible-rec i (sub1 j)))))
    (define: (divisible (n : Positive-Fixnum)) : Boolean
      (divisible-rec n (sub1 n)))
    (define: (total-primes (k : Index)) : Integer
      (for/sum: : Integer ([n : Positive-Integer (in-range 2 (add1 k))])
        (if (divisible (assert n fixnum?)) 0 1)))
    (time (displayln (total-primes 30999)))

On my machine, this runs in 3.320s (down from 4.004s for the integer
version).

To help TR guarantee that everything stays within fixnum range, I had to
add a few runtime checks, which add some overhead. TR successfully
specializes all arithmetic operations in the program (confirmed using
Optimization Coach).

If you're willing to give up Racket's usual safety guarantees, you can
use unsafe operations, as in Pierpaolo's version. This is roughly
equivalent to `(optimize (speed 3) (safety 0))' in your original program.

Vincent