[racket] Perlin and simplex noise - optimizing Racket code

From: JP Verkamp (racket at jverkamp.com)
Date: Thu Apr 11 22:06:30 EDT 2013

Excellent timing :) and thanks for the feedback.

I realize this email has gotten pretty extensive. :) Open questions are in

 I just tried converting the code to Typed Racket using types loose enough
> to ensure only functions needed to be annotated (i.e. mostly (Vectorof
> Fixnum) and Real). I also changed it to use `images/flomap', which is
> written in Typed Racket, instead of `picturing-programs', which is untyped
> and doesn't have a typed interface. (That basically meant changing
> `build-image' to `build-flomap*', and returning flvectors instead of colors
> from the callbacks.) It took me about 10 minutes and was straightforward.
> It would be a good first TR experiment.

Real will work? (Well, considering you did it I'd assume so.) For whatever
reason, I assumed that I would have to use Flonum to get the floating point
optimizations, but that leads to the issues I had with 0 not typechecking
from the other email.

In any case, I actually ran it. In practice, Real has essentially the same
performance as Flonum without the annoying issue with 0, so that's good. So
then when would you specifically want to use Flonum instead of Real?

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?*

I didn't actually know that images/flomap existed. I was looking for
something that built an image from a generator function and
picturing-programs was the only one that I could find. That's one downside
of the Racket documentation (really documentation in general) is that it
can occasionally be hard to find exactly what you're looking for if you
don't know what it's called.

*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...

With the fastest code I've written, it's down to:
   perlin: cpu time: 297 real time: 294 gc time: 109
  simplex: cpu time: 156 real time: 159 gc time: 47
   colors: cpu time: 514 real time: 530 gc time: 171

Overall, it's about 10x faster than it was originally. That's not so

Interestingly, for me at least it doesn't seem to make any difference if I
create the images or not. I'm still getting the same runtime if I just call
perlin/simplex 65025 times and do nothing with it.

   (: perlin (case-> (Real -> Real)
>                      (Real Real -> Real)
>                      (Real Real Real -> Real)))
>    Be aware that `case->' types slow down type checking. (The function
>    body is checked once for each case.)

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?*

*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.

*As a side note, is it possible to type optional parameters inline?* It
seems possible if it's both optional and a keyword, like this:

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

But not just with an optional parameter. I tried this:

(: perlin (Real [Real] [Real] -> Real))

That doesn't work.

 * Use (exact-floor x) instead of (inexact->exact (floor x)) so TR will
>    know that the result is an Integer. Use `fl' from `math/flonum' to
>    keep from having to type `real->double-flonum' everywhere. Don't use
>    `exact->inexact' in TR code. (See the `fl' docs for why not.)

Another instance of not knowing that something exists. :)

>  * 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.

> Yes, do this. The only other option is examining fully expanded code in
> the Macro Stepper and rediscovering the Optimization Coach's advice on your
> own, which would be un-fun.

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130411/49b4fc90/attachment-0001.html>

Posted on the users mailing list.