[racket] Perlin and simplex noise - optimizing Racket code

On 04/11/2013 12:54 PM, Vincent St-Amour wrote:
> At Thu, 11 Apr 2013 13:07:27 -0400,
> JP Verkamp wrote:
>>
>> [1  <multipart/alternative (7bit)>]
>> [1.1  <text/plain; UTF-8 (7bit)>]
>> Partially out of curiosity and partially in my ongoing quest to try out
>> game development in Racket, I've implemented a pure Racket version each for
>> Perlin and simplex noise. It's pretty much a direct translation of the code
>> from this PDF, originally in C:
>> http://webstaff.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf
>>
>> Here is a blog post with some pretty pictures but little actual code:
>> http://blog.jverkamp.com/2013/04/11/perlin-and-simplex-noise-in-racket/
>>
>> Here's just the code:
>> https://github.com/jpverkamp/noise
>>
>> It's definitely not pure / functional, but I think it's relatively easy to
>> read (or as easy as noise functions can be).
>>
>> ...
>>
>> - using Typed Racket -- Theoretically this will allow the compiler to
>> choose the correct functions as above and avoid having to do any runtime
>> checks at all, although I'm not sure how much of that has been implemented.
>
> I had a quick look at your code, and I think Typed Racket should be able
> to help. The TR optimizer can specialize numeric operations, which
> removes runtime checks and allows the Racket compiler to unbox
> intermediate results.

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.

Using "#lang typed/racket #:no-optimize" on both files, I get this:

   > (flomap->bitmap (time (build-perlin-image 256 256)))
   cpu time: 288 real time: 288 gc time: 68
   - : (Instance Bitmap%)
   <a bitmap>

Using "#lang typed/racket", I get this:

   > (flomap->bitmap (time (build-perlin-image 256 256)))
   cpu time: 284 real time: 283 gc time: 60
   - : (Instance Bitmap%)
   <a bitmap>

Two lessons:

  1. The code will need to be specialized to flonums and fixnums for
     TR's optimizer to do any real good.

  2. Converting it to all typed code - critically, using a typed image
     library - made it a lot faster anyway.

To explain #2: `images/flomap' was developed to do the low-level work 
behind rendering Racket's icons, and takes full advantage of TR's and 
the JIT's optimizations. Perhaps more importantly, because 
"noisy-image-test.rkt" is statically checked, `build-flomap*' can 
blindly accept its callbacks' return values.

Some tips:

  * Annotation examples:

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

    (: grad3 (Vectorof (Vectorof Fixnum)))

    (: 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.)

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

  * Using shadowing instead of `set!' allows Racket's JIT to generate
    faster code, especially when the mutated value is a flonum.

I'm sure you can get this to generate 256x256 flomaps at interactive speeds.

Unfortunately, converting from a flomap to a bitmap takes a lot of time: 
I'm measuring 90ms for a 256x256 image. I don't know why this is.

> To get the most of the TR optimizer, you can try the Optimization Coach
> DrRacket plugin. It reports the specializations that TR is doing and
> points out specialization opportunities that would require code/type
> changes to be safe.

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.

Neil ⊥