[racket] Perlin and simplex noise - optimizing Racket code

From: Neil Toronto (neil.toronto at gmail.com)
Date: Fri Apr 12 00:50:57 EDT 2013

On 04/11/2013 07:06 PM, JP Verkamp wrote:
> Excellent timing :) and thanks for the feedback.

No problem!

> Then I saw Float. At the moment, I'm not sure what the difference is
> between Flonum, Float, and Real, but using Flonum and Real have about
> the same runtime and Float is about twice as fast.*Why would that be the
> case?*

There shouldn't be any difference. AFAIK, Float is a synonym for Flonum.

The Real type is equivalent to (U Flonum Single-Flonum Exact-Rational). 
A Real is anything you can apply `abs' to without raising an error.

> *Is there a difference in build-flomap* between returning a flomap or a
> flvector or (Vectorof Float)?* I can't seem to get the latter working...

The issue with (Vectorof Flonum) is that it's *not a subtype* of 
(Vectorof Real), even though Flonum is a subtype of Real.

Say you returned a (vector 0.0 0.0 0.0) and *also* stored a reference to 
it somewhere. Then `build-flomap*' named it `v' and did this to it:

   (vector-set v 0 3/4)

which is legal because `build-flomap*' knows it's a (Vectorof Real). If 
it was typed in your code as a (Vectorof Flonum), that would be unsound.

TR has no way to know that `build-flomap*' won't change the vector you 
return to it, so it has to be very conservative. Mutable data structures 
in TR are *invariant*.

You may have been expecting it to be *covariant* like an immutable data 
structure. (Listof Flonum) *is* a subtype of (Listof Real).

> After the Float/Real/Flonum changes, I ended up writing this code:
> (: perlin (case-> (Real -> Real)
>                    (Real Real -> Real)
>                    (Real Real Real -> Real)))
> (define (perlin x [y 0.0] [z 0.0])
>    (perlin^ (real->double-flonum x)
>             (real->double-flonum y)
>             (real->double-flonum z)))
> (: perlin^ (Float Float Float -> Float))
> (define (perlin^ x y z)
>    ...)
> *Are there any obvious pitfalls I'm missing with this approach?*

Nope. It might not work out with more precise `case->' types, though, 
e.g. if you wanted to return exact values given exact arguments.

> *Alternatively, when is this cost paid?* If it's at compile time, that's
> really not a big deal. If it's runtime, that's something I want to avoid.

Compile-time only.

> *As a side note, is it possible to type optional parameters inline?*

It's not possible, and it bothers me as well.

> .... I tried this:
> (: perlin (Real [Real] [Real] -> Real))
> That doesn't work.

Racket macros and languages don't generally distinguish paren shapes. 
(It's hard to preserve that syntax property as macros expand.) IOW, this 
works because `[...]' isn't special:

(: build-perlin-image (Integer Integer (#:scale Real) -> flomap))

>       * Using shadowing instead of `set!' allows Racket's JIT to generate
>         faster code, especially when the mutated value is a flonum.
> *Won't a series of defines already do this?* I replaced the 3 set!s in
> simplex with lets, but it didn't seem to actually change the runtime any.

I've noticed it making a difference in tight loops that accumulate a 
flonum value.

> The Optimization Coach is really nice. I had to look up what the colors
> meant, but after that it's been most helpful.
> Although there is a lot more red when using Real instead of Flonum, but
> the runtimes seem about the same. Is it doing more optimizations than it
> appears or is there still more room to eek out some additional
> performance? Changing Real to Float makes everything nice and green.

I'm not sure. I'd expect green code to execute faster. Try running it in 
DrRacket with debug info turned off (use the Language dialog) or from 
the command line. If that doesn't change anything, there's probably one 
or two expensive things left.

Neil ⊥

Posted on the users mailing list.