Experiment project for testing out zig prior to doing some more development with it.
The goal for the project (except learning some zig) is to make a genetic algorithm that will try to mimic an image with some shape.
Ideally it will have a graphical progress tracker, and in the best of all worlds runnable in the browser.
Built with Zig 0.16.
To build and run the app (skip the run if you just want to build it):
zig build run
The default optimization is Debug. Pass --release=fast (recommended for native) or --release=safe / --release=small for a release build.
Currently still under construction, but works. Will be the main way to use the app once finished.
zig build wasm
The compiled .wasm together with the necessary web files will be output in the zig-out/web directory.
Simple way to take a look is running a local file server from that directory (python -m http.server).
The optimization level is shared with the native build and defaults to Debug. For a small .wasm use --release=small:
zig build wasm --release=small
web/nginx.conf is a minimal config that serves the build output from zig-out/web. Copy index.html, index.html.br, the thumbnail PNGs and images.json into the server's root (/var/www/pale).
It uses brotli_static on, which serves the pre-compressed index.html.br directly and requires the ngx_brotli module (not bundled with stock nginx). On Debian/Ubuntu install it via apt:
sudo apt install libnginx-mod-http-brotli-static
sudo nginx -t && sudo systemctl reload nginx
zig build test # unit tests for the shared library + native exe
zig build wasm-exports-test # native Debug smoke-test of the wasm export surface
wasm-exports-test builds wasm_exports.zig for the host (forced to Debug, single_threaded) and exercises every exported function through std.testing.allocator, so leaks, double-frees, and out-of-bounds access surface immediately.
Part of this project will be optimizing the both the algorithm, but also the efficiency of evaluating the solutions, and the program as a whole.
The measurements are not going to be too precise, as they will be run on my computer locally, and not in some kind of reproducable environment. The problem is highly dependent on randomness, so a streak of favorable rolls can yield a much fitter solution.
To counter the fact that the evaluations are going to be run on my laptop locally, I will make sure to run the evaluation with the laptop plugged in, with performance mode enabled, and with only the single terminal open.
To counter the randomness factor I will re-run the process 10 times and take the mean of all the values.
| Attempt | Avg. time run | Avg. iterations | Avg. iter/sec | Avg. normalized error | Result | Commit hash |
|---|---|---|---|---|---|---|
| Naive mutations and evaluation | 60.03 s | 10567 | 176.1 | 0.08733 |  |
f2f32b3 |
| Same naive, but load all the pixels at once | 60.03 s | 15070 | 251.1 | 0.07870 |  |
48ea0fd |
| Naive, but with rate limited frame rendering, meaning more time for evaluation | 60.01 s | 15871 | 264.4 | 0.07797 |  |
430aad8 |
| Evaluating only changed parts of the solution | 60.02 s | 53224 | 886.8 | 0.05114 |  |
18ae1a1 |
| Replace image.clearBackground with image.drawRectangle | 60.02 s | 561248 | 9351 | 0.04184 |  |
20af03e |
| Remove upper bound for number of rects, and introduce deletion pressure | 60.02 s | 1022705 | 17040.34 | 0.03524 |  |
3c200c6 |
| Add swap mutation | 60.02 s | 919213 | 15315 | 0.03478 |  |
fe4547e |
| Pull texture update out of busy loop | 60.02 s | 1058167 | 17631 | 0.03451 |  |
7a87185 |
| Introduce area downward pressure | 60.02 s | 3467283 | 57690 | 0.03134 |  |
2e99ee1 |
| Fix partial evaluation, and apply to evolution | 60.02 s | 3282308 | 54683 | 0.03107 |  |
cbc8c36 |
| Unify move and resize mutations | 60.02 s | 3053116 | 50869 | 0.03139 | |
18b3976 |
| Add split + mutate mutation | 60.02 s | 2799116 | 46637 | 0.02858 |  |
6932280 |
NOTE: At some point (after the Pull texture update out of busy loop) I noticed that there is an issue with the partial evaluation I was doing (it was an one-off error). To rectify that I re-ran all of the previous runs, but at the end added a total re-evaluation of the best solution, and used the value that it gave (I did not fix the evaluator because that would possibly change the results too much, and I don't want to re-write history). To make it easier to navigate to the commit which the entry in the table is referencing, I will add a commit hash for each row (previously this could be done with git blame).