Immer: postmodern immutable data structures

The tragedy of the value based architecture

a presentation
brought to you by
Juanpe Bolivar
https://sinusoid.es

1. Let's imagine for a second that we are building some interactive desktop software.

At the core of our design there is the data model. This is, an in-memory representation of the state that is meaningful to the user, this is, the document.

In this architecture, our data-model is a tree of simple types (structs, vectors, maps...) that we pass around by value.

2. We can thus implement our application logic as simple pure functions that take in a document and return a new document. This function has no side effects, and is trivial to test.

3. One of the often advertised advantages of such design is that undo becomes trivial to implement: we just keep a vector of all the previous states.

4. It is also easy to program asynchronously. For the UI, we can have a separate thread. It is easy to build a device like get_document() to pass the document to it by value some kind of channel. We can just loop and render the new states as they come.

5. Likewise, in one line of code, can have an auto-save feature that saves the document asynchronously.

6. Adding other kinds of concurrent representations of the document, like audio, is equaly simple.

But there is a problem.

We are making copies everywhere! While this works for small documents, doing this for software with complex and megabytes-big documents is gonna make everything very slow.

1. So we decide that we can instead do our application logic in-place, passing our document by reference

2. But this means that we are no longer thinking of the document as a value, but as an object identity, as a location where we store things

3. Now we need locks to avoid data races between rendering and application logic.

4. And to avoid stopping our whole system for rendering, we build another stateful intermediate representation, as a view hierarchy.

5. And to make sure everything is in sync, the data model needs to notify other people via observers and everyone is calling eachother indirectly.

6. And for the undo history we need now a command pattern, where from the app logic, we build this sequence of reversible transformations and hope for the best.

7. And asynchronous saving is just too complicated now, let's just show a (8) spinning sandclock, users are already used to them...

9. But nothing is going to save us from the flying spagetty monster that our code has suddenly turned into...

mutability ⇒ ( pass by value ⇒ copying )

root cause cause problem

But why did did we abandon our beautiful initial picture?

Because of copying

And as C++ developers we are hard-wired to believe that passing by value implies copying.

But this does not need be the case! We could think of an alternative world where we allocate our value in the heap and just pass a reference to it. The reason we can not do that, is that in C++ everything is mutable. Thus, the only way we can pass a value to someone and ensure that it does not go away when someone else mutates the object where it is stored, is to copy it!

Thus, mutability is our root problem, it's only under mutability assumption, that passing by value implies copying.


const auto v0 = vector<int>{};
const auto v1 = v0.push_back(15);
const auto v2 = v1.push_back(16);
const auto v3 = v2.set(0, 42);


assert(
    v2.size() == v0.size() + 2
 && v3[0] - v1[0] == 27);

immutable data structure

one with all methods
marked const

persistent data structure

old values are preserved

structural sharing

no copying
compact history
fast comparison

We can start atacking the problem of mutability at the basic building block of our data model: the data structures.

We could have a magical vector type that is immutable, this is, all its methods are const.

We can use the push_back on a const instance, and it will return a new vector with the value appended. Like this, and like this.

To update an element of the vector we we don't use assignment, but the `set` method, that again, returns a new vector.

A nice property of such API is that it is persistent. Old values are preserved and we can make statements, in code, that relate old values and new values.

But this API can also be implemented with structural sharing! This is, the new values don't need to copy all the data, but only the parts that changed. Thus, we need no more copies when passing them around, the history of values can be represented in a compact form, and comparing values can often be very efficient.

immer
modern and efficient immutable data structures

https://
sinusoid.es/
immer

The tragedy of the value based architecture

a presentationbrought to you by Juanpe Bolivar https://sinusoid.es

a presentation
brought to you by
Juanpe Bolivar
https://sinusoid.es