real time circle packing - now in real time!

Breathing life into what I thought was an abandonded project.


So it’s been almost a year since my last post in this series, but I’ve made some huge improvements! The render speed is now about 500ms (18x improvement)! (on my laptop anyway)

Check out the demo here:


So fast :o

How did we get here? The biggest change was to realize that copying data between the GPU and CPU is very slow. readPixels in particular is a bad thing to call in a loop as it forces the GPU to perform a sync every time, and ruins the normally pipelined GPU performance. This was avoided by just implementing the final step of drawing circles to also happen on the GPU - thereby eliminating the need to call readPixels.

Additionally, I decided to sacrifice quality for speed. Instead of outputting a 1000x1000px image, it’s now a 500x500px image. Additionally, the circle radius parameters were tweaked, and the number of desired circles was dropped.

A really unexpected find was that canvas.width/height is very slow to access. I gained approximately a 2x speedup just by caching those values.

The final improvement was to try to use typed arrays where possible, and if not possible, to at least not use arrays of objects, preferring multiple arrays of numeric types instead. This hsa to do with the JS engine’s optimizations of more efficiently representing arrays of simple types as vectors of that type. I guess current JS compilers don’t try to turn objects into structs (tested on ff and chrome). Interestingly preallocating arrays had no real performance impact. That might in part be that these arrays are too small to benefit from that, but it might also be that js uses a well performing vector implementation when it can.

When I intially made this post, I thought I was getting render speeds of <30ms, which was my goal all along, but I realized that my timing info actually didn’t account for the time taken to perform all the render calls I was making. I discovered this when trying to run this in a loop, and noticed abysmal framerates (2fps). Throwing in a gl.finish revealed that generating all the content I wanted took 500ms, matching the observed 2fps. However, hope was not lost, working on this gave me a an idea for a better implemention. See you in the next post!

Written on June 17, 2022