[racket] Perlin and simplex noise - optimizing Racket code

[JP Verkamp]

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

What I'm wondering though is if someone with a bit more experience in optimizing Racket code could take a look at it. I know that it should be possible to get a bit more speed; it's almost all number crunching, mostly floating point math but with a few integer only bits (those are causing the most trouble...). At the moment, I can think of at least three routes for optimization although I'm probably missing something:

- using (racket/floum) -- I've tried just blindly replacing * + - / with fl* fl+ fl- fl/ (and fixing the numerous errors that crop up), but it doesn't seem to result in much of a speedup at all. I think that this is a combination of still requiring runtime checks on the values and having to convert between exact/inexact, but I'm not sure. 

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

- using the FFI to bind to a native C interface -- This would probably be the fastest in the end, but I'd like to do as much in pure Racket as I can for the time being (although it would be interesting to learn how to do this). Not to mention that a part of me rejects that it wouldn't be possible for Racket to at least match C code in a perfect world. 

Right now the code takes about 1-2 seconds to generate a 256x256 image. Optimally, that should run in near realtime, although I would be happy just getting it into the tens or even hundreds of ms range. A part of that time is turning the noise into a color (for testing), but even without that it still takes about 1 second on my machine for simplex noise.

Thanks for any feedback!

JP

[Robby Findler]

Just based on past experience and not a careful look at your code, I think that it is safe to say that TR is the way to go here. That's going to have the best bang for your buck as a tradeoff of simple-to-do vs spedup-gained.

Robby

____________________
  Racket Users list:
  http://lists.racket-lang.org/users

[Robby Findler]

Oh and one other thought: in case you didn't find them yet, you probably want to use this function:

http://docs.racket-lang.org/reference/generic-numbers.html?q=current-random#%28def._%28%28quote._~23~25kernel%29._current-pseudo-random-generator%29%29

and friends, so you can be sure that other code that might also use random doesn't interfere with your code.

Very nice post, btw!

Robby

[Jens Axel Søgaard]

In functions such as


(define (mix a b t)
  (+ (* (- 1 t) a) (* t b)))

(define (fade t)
  (* t t t (+ (* t (- (* t 6) 15)) 10)))


use floating point constants:

(define (mix a b t)
  (+ (* (- 1. t) a) (* t b)))

(define (fade t)
  (* t t t (+ (* t (- (* t 6.) 15.)) 10.)))

/Jens Axel

2013/4/11 JP Verkamp <rac...@jverkamp.com>

____________________
  Racket Users list:
  http://lists.racket-lang.org/users

--
--
Jens Axel Søgaard

[Vincent St-Amour]

At Thu, 11 Apr 2013 13:07:27 -0400,
JP Verkamp wrote:
>
> [1 <multipart/alternative (7bit)>]
> [1.1 <text/plain; UTF-8 (7bit)>]

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.

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.

Vincent

[Neil Toronto]

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 ⊥

[JP Verkamp]

Thanks for the advice! It's certainly been an interesting journey into Typed Racket... :)

Here are the results thus far (for a 256x256 perlin, simplex, and colored-simplex image).

Original:
  cpu time: 1139 real time: 1134 gc time: 232
  cpu time: 780 real time: 773 gc time: 124
  cpu time: 1950 real time: 2044 gc time: 328

Typed:
  cpu time: 640 real time: 653 gc time: 110
  cpu time: 546 real time: 542 gc time: 62
  cpu time: 1342 real time: 1364 gc time: 218

So it's definitely a good start.

Unfortunately, there are a few oddities that I'm not sure how to deal with.

1) Which is more idiomatic / easier for Typed Racket to deal with:

(: mix (Flonum Flonum Flonum -> Flonum))

(define (mix a b t)

  ...)

(define: (mix [a : Flonum] [b : Flonum] [t : Flonum]) : Flonum

  ...)

Right now, I'm using the former, but I'm not sure I'm happy with it.

2) How can I deal with integer values (specifically 0) to a function with flonum types?

Specifically, perlin (and simplex) have the type:\

(: perlin
   (case-> (Flonum -> Flonum)
           (Flonum Flonum -> Flonum)
           (Flonum Flonum Flonum -> Flonum)))

But if I try to do something like this:

(perlin (* 1.0 (/ 0 256)))

I get this error:

Type Checker: No function domains matched in function application:
Domains: Flonum Flonum Flonum
         Flonum Flonum
         Flonum
Arguments: Zero

Basically, (* 1.0 (/ 0 256)) is 0, not 0.0. For the timing tests above, I worked around this with real->double-flonum but that seems suboptimal (they types are leaking). Is there something I'm missing there?

3) How do I type a color% / bitmap%?

I tried typing noisy-image-test.rkt, but I kept running into this. I can use Any, but it seems like objects should be typeable. No luck finding out how though.

I'll keep hacking at it, but that's what I have for the moment.

JP

[JP Verkamp]

Excellent timing :) and thanks for the feedback.

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

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

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.

[Neil Toronto]

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.

[Vincent St-Amour]

At Thu, 11 Apr 2013 20:14:48 -0400,

JP Verkamp wrote:
> Thanks for the advice! It's certainly been an interesting journey into
> Typed Racket... :)
>
> Here are the results thus far (for a 256x256 perlin, simplex, and
> colored-simplex image).
>
> Original:
> cpu time: 1139 real time: 1134 gc time: 232
> cpu time: 780 real time: 773 gc time: 124
> cpu time: 1950 real time: 2044 gc time: 328
>
> Typed:
> cpu time: 640 real time: 653 gc time: 110
> cpu time: 546 real time: 542 gc time: 62
> cpu time: 1342 real time: 1364 gc time: 218
>
> So it's definitely a good start.
>
> Unfortunately, there are a few oddities that I'm not sure how to deal with.
>

> *1) *Which is more idiomatic / easier for Typed Racket to deal with:

>
> (: mix (Flonum Flonum Flonum -> Flonum))
> (define (mix a b t)
> ...)
>
> (define: (mix [a : Flonum] [b : Flonum] [t : Flonum]) : Flonum
> ...)
>
> Right now, I'm using the former, but I'm not sure I'm happy with it.

I tend to use the former, but both are idiomatic, and TR treats both the
same way.

> *2)* How can I deal with integer values (specifically 0) to a function with

> flonum types?
>
> Specifically, perlin (and simplex) have the type:\
>
> (: perlin
> (case-> (Flonum -> Flonum)
> (Flonum Flonum -> Flonum)
> (Flonum Flonum Flonum -> Flonum)))
>
> But if I try to do something like this:
>
> (perlin (* 1.0 (/ 0 256)))
>
> I get this error:
>
> Type Checker: No function domains matched in function application:
> Domains: Flonum Flonum Flonum
> Flonum Flonum
> Flonum
> Arguments: Zero
>
> Basically, (* 1.0 (/ 0 256)) is 0, not 0.0. For the timing tests above, I
> worked around this with real->double-flonum but that seems suboptimal (they
> types are leaking). Is there something I'm missing there?

`(* 0 anything)' is `0', this is a special case in Racket's numeric
tower. It does make reasoning about types a little tricky, because the
normal contagion rules don't apply.

`real->double-flonum' or `fl' is the right thing to use here.

> *3)* How do I type a color% / bitmap%?

>
> I tried typing noisy-image-test.rkt, but I kept running into this. I can
> use Any, but it seems like objects should be typeable. No luck finding out
> how though.

Typed Racket currently has limited support for classes and objects.
`bitmap%' and `color%' should already have types (in typed/mred), so
maybe that's enough for your needs. Better support for classes and
objects is in the works.

[Vincent St-Amour]

At Thu, 11 Apr 2013 22:06:30 -0400,

JP Verkamp wrote:
> 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.

`Real' will typecheck, but it won't be optimized. As you said, only
`Float' types allow floating-point specializations.

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

It may be that these operations were in cold code, so the specialization
did not have much impact.

The most recent version of Optimization Coach (available in the package
repository, and requires a pre-release Racket) can use profiling
information to refine its recommendations. If the operations you mention
were in cold code, the new version would not consider them worth telling
you about.

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

I don't see any. This is similar to how I would write it. You get the
benefits of optimization in `perlin^', while still accepting any real
numbers as inputs.

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

As I said above, the version of Optimization Coach that ships with the
current Racket release does not distinguish between optimizations in hot
code and optimizations in cold code. The former have a bigger impact on
performance than the latter.

If you're interested, you should try the newest version of Optimization
Coach. I'd be interested in knowing whether it provides better
recommendations for your program.

Vincent

[JP Verkamp]

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

I think the odd timing results that I got (with Real/Flonum the same and Float faster) was actually a result of other changes that I was making as I went. Float/Flonum being the same thing is a bit strange at times, since the errors don't seem particularly consistent on which they use (I expect it's whichever one was used in the particular type declaration I'm breaking and those vary). 

In case anyone is interested in the final timing here are all of the steps (running from command line Racket rather than DrRacket). I'll write up a better blog post detailing the process and the steps along the way probably this weekend.

Untyped code, generating an image, git: b2d12e4

 perlin: cpu time: 355 real time: 356 gc time: 40

simplex: cpu time: 243 real time: 242 gc time: 4

Typed code with Real, no wrapper, generating an image, git: 006faf9

 perlin: cpu time: 235 real time: 236 gc time: 15

simplex: cpu time: 147 real time: 147 gc time: 4

Typed code with Float, wrapper converting Real to Float, generating an image, git: 5da0723

 perlin: cpu time: 112 real time: 118 gc time: 23

simplex: cpu time: 106 real time: 110 gc time: 3

Originally I was confused because building the images was actually faster than just using the data directly. But then I realized that timing-tests.rkt wasn't Typed. It's kind of amazing how much that helps... Now I'm seeing about 50-60ms of overhead just to create the image which you had mentioned as well.

Typed code with Float, wrapper, not generating an image, git: 7445311

 perlin: cpu time: 41 real time: 40 gc time: 0

simplex: cpu time: 52 real time: 52 gc time: 2

I'm not sure how much better even could be done at this point. Particularly since the original code that mine is based on--In Java, not C. Oops--runs a 256x256 without making an image in ~30ms. So we're definitely in the same ballpark now.

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

Right. I was still hoping that would be how to signify optional parameters. Although that wouldn't work since the same sort of shape is used for signifying Listof/Vectorof/etc. I'm unsure if there's anything that is the only item in a list though.