Elm core libs in WebAssembly

Show and Tell
11

The trick is that immutable data NEVER points to younger values… At any time we can scan the last values created and free those that are not pointed to from the same set

A while back there was a thread about improving the performance of List.append, which lead me to research methods in how to optimize (essentially) right folds. As most CS problems, this was already solved in the seventies and is called Tail recursion modulo cons (even though it’s not limited to Cons)

Here is a concrete example (in C) of what this could look like:

void List_Map (void* (*f)(void*), List *list, List *result) {
    // case list of 
    if (list->tag == 0) { // [] ->
        List_Nil(result); // []
    } else { // x :: xs ->
        void *x = list->head;
        List *xs = list->tail;
 
        // f x :: map f xs
        List *tail = malloc(sizeof(List));

        // +++ we swapped the execution order of the next 2 lines +++

        // List_Cons is a constructor that doesn't dereference its arguments,
        // and can therefore not observe that we did not fully construct the tail yet
        List_Cons(f(x), tail, result);
        // now this function is tail-recursive!
        //`clang -O` and `g++ -O2` already compile this to the "loopified" version!
        List_Map(f, xs, tail);
    }
}

I wanted to try and implement a prototype version of this based on the Elm compiler, but Evan seemed to be in the middle of refactoring stuff for 0.19.1, so I decided to wait until the release before I tried it again.

Of course, this is all extremly hypothetical at the moment, but I think it would be a shame to prevent these kinds of optimizations. But maybe it’s worth it!

If we could always reverse the allocation order like this, would it be still possible by looking the other way instead?

My idea for a garbage collector for Elm always looked like this:

  • There is a single “entry” reference, the current model. The compiler can emit special code to traverse the old model and the new one to find differences.
  • 2 memory arenas: 1 for old values, 1 temporary for new ones.
  • If we find the same reference in a field, we can skip it entirely.
    If we find a different reference in the new model, mark the old value as dead, and the new value as live. Traverse recursively.
  • Free all dead values from the old arena, copy all live values from the new arena to the old one.
  • Free the whole new arena.

I guess this is similar to what Ocaml / V8 are doing?

1 Like