Lessons learned from writing a Conway's Game of Life implementation in big-bang

[Christopher Lemmer Webber]

Hello all,

Last night out of curiosity I started lazily adding some code to see how
long it would take me to write a game of life implementation in Racket.
Not exactly a challenging expidition game-authoring-wise, but a fun
little exercise anyway. You can see and play with the results here:

https://gitlab.com/dustyweb/racket-life

(Don't expect astounding code or anything.)

Here were my takeaways:

- Racket is a real joy, especially due to its inclusion of its picture
language, to write this kind of thing in. I started playing with
this very idly last evening and was very quickly pulled in.

- The icons library is a hidden gem in Racket... bitmap-render-icon
is a lovely way in particular to create the kinds of sprites you use
in puzzle games :)

- The HTDP big-bang system is, from a programming perspective, a lot of
fun to code in. I can easily see how it would be great to teach
with.

- It was easy to get an implementation of Conway's Game of Life going
and have it even be fairly pretty within almost no time. However, as
observed here:
https://groups.google.com/forum/#!topic/racket-users/yjRuIxypUQc
the functional drawing system isn't very fast once you get a lot of
objects on the screen. Fortunately I found it was possible to not
have to convert all my code, only the to-draw bit... I converted
it to a bitmap canvas that I blitted to imperatively.

- But even this was not fast enough... I found that a 50x50 graph was
terribly slow. I found that even just creating the 1000x1000 px
bitmap every frame was very expensive, even before blitting to it, so
I stuck the bitmap in a parameter and kept it around between frames.

- I then found out that the bitmap wasn't changing suddenly... I'm
guessing big-bang has an optimization where (since it's expecting a
functional program) if it sees an object that's eq? to the previous
object come out of to-draw, it doesn't draw it. So instead I
allocated two bitmaps as parameters and switched between which one I
was blitting to. That effectively tricked big-bang into blitting
to my reused bitmap every time ;)

- With those optimizations in place, a 30x30 grid on my
10-year-old-laptop would run at full speed, and a a 50x50 tile grid
(1000x1000 pixels) rendered at about 10FPS... a barely tolerable, but
tolerable speed, for something like this ;)

- It seems that the blitting of bitmaps to the canvas (I didn't do
anything smart to "only blit the ones that changed", which would
speed this up certainly by a lot) is by far the slowest part of
my code, so I figured maybe it would be faster if I drew rects on
the canvas instead of blitting my pretty icon-derived bitmaps.
To my surprise it became 50% slower!

I guess completely redrawing 2500 sprites per frame is just a lot for
the vanilla canvas. I see there's an opengl canvas... maybe I should
try that.

Obviously there's "the most correct" optimization to do, given that I've
already gone down the route of committing imperative-rendering sins: I
ought to keep around the previous graph and see if it changed at all and
only blit the ones that actually changed. Well, I'm sure that would
make things lightning fast ;)

I'm not sure if that's interesting to anyone at all. But I will say,
Racket really is a joy to work with! Thanks for making a toolbox so
much fun I accidentally lose a number of hours to something like this :)

- Chris

[Matthias Felleisen]

Thanks for the feedback.

Yes, b-b was designed for middle school, high school and college
freshman courses. But like all software, it eventually escapes and
makes it into the “real world”.

[ ASIDE What does this tell you about the terrible
training that most students get and use to produce
code in industry during co-op and internships?]

The drawback of b-b for “real” applications is that (1) it checks
way too many things (2) when something fails it works hard to
deliver error messages that are useful for beginners (as in the
kinds of students mentioned above).

As I have said before, I need to design a path from b-b for students
to a b-b for “adults”.

Alternatively, you could use Jay McCarthy’s replacement package
for b-b, which may already live up to your performance expectations.
I don’t have time to experiment but I am really interested on how it
would work out.

Again thanks for the feedback — Matthias

> --
> You received this message because you are subscribed to the Google Groups "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Andrew Kent]

In case you didn't see, there's a blog post (by Jay) about writing Conway's game of life in Racket. It spends some time talking about various optimizations to get performance:

http://jeapostrophe.github.io/2013-11-18-life-post.html

[Jay McCarthy]

FYI the package lux is like Big Bang and the package mode-lambda is like 2htdp/image. Right now, however, I am working on raart for doing ANSI user interfaces. 

--

-=[     Jay McCarthy               http://jeapostrophe.github.io    ]=-

-=[ Associate Professor        PLT @ CS @ UMass Lowell     ]=-

-=[ Moses 1:33: And worlds without number have I created; ]=-

[Hendrik Boom]

On Fri, Jan 05, 2018 at 08:09:59AM -0800, Andrew Kent wrote:
> In case you didn't see, there's a blog post (by Jay) about writing Conway's
> game of life in Racket. It spends some time talking about various
> optimizations to get performance:
>
> http://jeapostrophe.github.io/2013-11-18-life-post.html

Long ago in the 60's, on an old PDP-11 running an early Unix, I
implemented a Live using quad-trees for storage after I noticed by
drawing on a lengthy printout that at each level of the quadtree, only
about half of the quads has objects in them. The empty ones I could
leave out of storage and not do much computation with them (except at
the edges in case they wee to come back to life).

I could get simply *huge* Life patterns on this rather small machine (by
today's standards) without running out of RAM. I did have to rescale
the screen display several times. A pixel ended up meaning something
like "there is something in this 8x8 block".

Well, what had to be used as a pixel on an ascii-text-only terminal.

-- hendrik

[Christopher Lemmer Webber]

Wow! These libraries are great! Excited to discover about them :)

I'm also excited to see the ANSI user interface one, as a fan of
roguelikes (and ascii art)!

[Laurent]

On Fri, Jan 5, 2018 at 5:42 PM, Hendrik Boom <hen...@topoi.pooq.com> wrote:

Long ago in the 60's, on an old PDP-11 running an early Unix, I
implemented a Live using quad-trees for storage after I noticed by
drawing on a lengthy printout that at each level of the quadtree, only
about half of the quads has objects in them.  The empty ones I could
leave out  of storage and not do much computation with them (except at
the edges in case they wee to come back to life).

I could get simply *huge* Life patterns on this rather small machine (by
today's standards) without running out of RAM.  I did have to rescale
the screen display several times.  A pixel ended up meaning something
like "there is something in this 8x8 block".

Well, what had to be used as a pixel on an ascii-text-only terminal.

Must have been incredible at the time!

Can you tell how close to the 1980's HashLife algorithm [1] your implementation was? It seems quite related at least. The first time I saw these exponential speed ups, I was blown away. People seeing your implementation likely felt similarly.

I would love to see a clean Scheme/Racket implementation of HashLife. 

[1] https://en.wikipedia.org/wiki/Hashlife, impressively implemented in Golly [2] 

[2] http://golly.sourceforge.net/