A couple of months ago I wanted to check how I feel about zig, and while looking for a trial project I remembered a lab assignment I had at university.
The goal of the assignment was to write a program that would, given an input image, spit out a list of rectangles that when drawn resemble the input image. For the lab assignment we just had to support grayscale opaque rectangles, but I wanted to make it a bit funky so I added support for colored, non-opaque rectangles (enabled by clicking the Alpha checkbox above the canvas).
You can either run it on the current placeholder, choose your own image by clicking Choose File above the canvas, or if you don't feel inspired use a photo from my collection:
In any case, if you are interested in the details, take a look on github or if you are specifically interested in how I incrementally improved the solution, take a look at the README.md.
Footnotes
e2233ac
At some point while I was optimizing the evaluation function I noticed in the flamegraph that a significant chunk of the evaluation time was spent clearing the background.
A single call to ImageClearBackground was in fact taking up more time than drawing all the rectangles of a solution.
At that point there was no transparency support, so clearing should have been as fast as drawing a rectangle over the whole canvas.
The issue ended up being an implementation detail in raylib where ImageClearBackground called memcpy for each pixel individually, whereas ImageDrawRectangleRec just did it for the first row, and then copied the whole row.
That was a problem because just the call to memcpy is expensive compared to the actual copying when the copied data is just 4 bytes.
I improved both functions by replacing the per-pixel memcpy with a loop that each iteration copies all already-filled pixels, doubling the total with each pass.
14 kB
Originally the app was written to run natively, and I only got it running in the browser later when I wanted to show it to friends.
I thought that it would be as easy as configuring the raylib emsdk build, but that produced a bloated binary of several hundred kB.
To shrink the binary size I had to drop the raylib dependency from the browser build, which would allow me to use the wasm-freestanding target.
In the native build raylib was used in 2 places.
First for the UI and target image loading (something the browser supports natively with a bit of JS + <canvas> magic).
And secondly in the actual evaluation code, where an Image was used as the render target for the tentative solutions, something that is really easy to re-implement if you only need to support clearing the canvas and drawing axis aligned rectangles.
Self-rolling the render target proved useful later on when adding non-opaque rectangle support, as implementing SIMD accelerated alpha blending was trivial because it was in my codebase.
The rewrite combined with a custom logger and --release=small brought the compressed build size of the web page to <14 kB over 5 files.
At that point I thought I was stuck, because although the total size of all the files was <14 kB gzipped, the source was split into several files and the benefit of fitting the page into the first 10 TCP packets was gone, because each file would have to be fetched separately.
I tried inlining the style/app files into a single HTML but base64 encoding the WASM killed its compressibility.
But, by pre-compressing the WASM before base64 encoding it (and undoing the same in JS) I managed to get the total size of the inlined page to <14 kB (when compressed with brotli -11).
So in case you didn't load photos from my collection by clicking the button, the whole website should be <14 kB. Funnily enough all of that was just vanity, because I control the server and I could have just bumped the initial congestion window size when serving this.