Martin's In memory Build System in 140 lines of TypeScript

News
1

Hi community,
@Martin_Huschenbett did some live coding to build a dynamic on-demand incremental computation engine (aka an in-memory build system) with monadic dependencies in less than 150 lines of TypeScript.

This is a topic he tinkered with in his spare time lately and he thought he’d share some of his aha moments with you.

Here is the video:

4 Likes
2

Great job as always Captain (@Martin_Huschenbett) :slight_smile:

1 Like
3

Very interesting @Martin_Huschenbett. I developed an almost identical build system in a previous life, together with a task scheduler to run the resulting graph asynchronously. That was key in browser as JS is single-threaded and the DOM doesn’t update during computation. So the scheduler always ran one task (a call to rule), and then scheduled the next loop using a timeout so that control could return to the browser.

In that context I didn’t have the luxury of having setters on the build system itself that allowed me to maintain a global “time”. Instead of a value, input nodes contained a fetch function that pulled input data from somewhere (a file, say).

What I found developing that is that maintaining just the immediate dependency graph as you do in your implementation led to snowballing in that scenario. You can avoid this using your global time:

        const node = nodes.get(file)!;
        if (node.updated_at === this.now) {
            return node;
        }

If you don’t have such a global time or version, you have to go to your dependencies and check whether their clocks (or values) have moved forward. They in turn go to their dependencies, etc. That’s equivalent to what you do in your next lines of code:

        let dependencies_changed = false;
        for (const dep of node.dependencies) {
            if (this.update_node(dep.layer, dep.file).change_at > node.updated_at) {
                dependencies_changed = true;
                break;
            }
        }

        if (!dependencies_changed) {
            node.updated_at = this.now;
            return node;
        }

The problem is that if you have a simple network of just layers with 10 files each, and each file depends on each file of the underlying layer, you end up with 10^10 comparison checks on time, even if nothing has changed.

The way around that is too track the input dependencies of each node and then start by pulling on them. Effectively, this is automatically calling set_value on each input before proceeding. I might send you a PR to demonstrate what I mean.

1 Like