Immutable data trees in JavaScript

London, 2014-02-12

(The talk was recorded: video)


Where I come from?

Clojure

Clojure (stealing from)

Why immutability?

Why immutability?

avoid side effects of one thing changing state of another

Why immutability?

Why immutability?

Different ways of sharing state

…with a convention

Send data as-is

with a convention No1

data belongs to the sender,
receiver shouldn’t modify

Send data as-is

with a convention No2

data belongs to the receiver,
sender shouldn’t modify

Send data as-is

with a convention No3

both sender and receiver can modify
:(

Conventions, meh

A newcomer will break it

Conventions, meh

Conventions, meh

(third-party code)

Computer!

program computers, not people

…with Object.freeze

Object.freeze (ES5)

has to be done recursively for full immutability

Object.freeze

…with a function

Protecting data in JavaScript

secure and portable way:

MVCC

Multi-Version Concurrency Control (MVCC)

MVCC

MVCC in DBs

Clojure’s persistent data structures

MVCC

Clojure’s persistent data structures

Clojure’s structure sharing

Clojure’s structure sharing

Clojure’s persistent data structures

How it works?

(and making peace with immutability)


v0 = ["a", "s", "d", "f"]

Let’s make a binary tree


{ 00: "a"
  01: "s"
  10: "d"
  11: "f" }

(keys in binary code)


0 | 0 "a"
0 | 1 "s"
1 | 0 "d"
1 | 1 "f"

(divide keys to 1 bit sized chunks)

Store data in a binary tree

(each chunk of the key is an address for one level of the tree)

{ 0: { 0: "a",
       1: "s" },

  1: { 0: "d",
       1: "f" } }

Lookup performance

2 (4 elements, log24 = 2)


{ 0: { 0: { 0: "a",
            1: "s" },

       1: { 0: "d",
            1: "f" } },

  1: { 0: { 0: "g",
            1: "h" }

       1: { 0: "j",
            1: "k" } } }

Lookup performance

3 (8 elements, log28 = 3)


{ 00: { 00: "a",    10: { 00: "q",
        01: "s",          01: "w",
        10: "d",          10: "e",
        11: "f" },        11: "r" },

  01: { 00: "g",    11: { 00: "t",
        01: "h",          01: "y",
        10: "j",          10: "u",
        11: "k" },        11: "i" } }

Lookup performance

2 (16 elements, log416 = 2)

Lookup performance

2 lookups

Lookup performance

What happens if we

?

Lookup performance (5 bit)

3 lookups


depth = ⌈key_bits / chunk_bits⌉ node_size = 2chunk_bits chunk_bits = log2node_size depth = ⌈log2size / log2node_size⌉ logAB / logAC = logCB depth = ⌈lognode_sizesize⌉


depth = ⌈lognode_sizesize⌉ chunk_size = 5 node_size = 25 = 32 size = 32768 depth = ⌈log3232768⌉ = 3

Lookup performance

function lookups (bits, size) {
  return Math.ceil(
    Math.log(size)
    /
    Math.log(Math.pow(2, bits))
  )
}

lookups(5, 32768) // 3
lookups(5, 1024)  // 2
lookups(1, 16)    // 4

Lookup performance (5 bit)

log32N

Mutation

v1 = v0.set(10, "z")

Mutation


v1 = v0.set(10, "z")
v0 = { 0:     { 0: “a”, 
            -   1: “s” },
           -
       1:  -  { 0: "d",
           -    1: “f” } }
          -         -
v1 = { 0:           -
       1: { 0: “z” -
            1: ---

Mutation performance (5 bit)

33 * log32N ~ log32N

A case for MVC frameworks

MVC frameworks need to know when to update the view

Have my data changed?

A case for MVC frameworks

mutable data:

A case for MVC frameworks

immutable:

A case for MVC frameworks

Using immutable data might actually speed up you MVC application.

MVC MVCC

Choice is yours

In a functional program…

data made immutable as soon as received (HTTP request, file read)

In a functional program…

profiler: find bottlenecks
critical parts made mutable if needed

In a functional program…

mutable data considered a type of premature optimisation

Immutable data in JavaScript

Quick reminder

already immutable:

Existing libraries (mori, …)

mori

Ancient Oak

an experiment with interface and implementation

Ancient Oak

Clojure-style MVCC library for plain JavaScript data trees

(with emphasis on trees)

Ancient Oak

Ancient Oak

returns a function (the getter) with various update/iterate methods

Ancient Oak

=> I({ a: 1, b: [ 2, 3 ] })

<= { [Function get]
     set:   [Function set],
     patch: [Function patch],
     map:   [Function map],
     … }

Ancient Oak

Easy in, easy out

data = I({ a: 1, b: [ 2, 3 ] })

=> data.dump()
<= { a: 1, b: [ 2, 3 ] }

Ancient Oak

Every node of the tree is a tree on its own.

tree = I({ a: 1, b: [ 2, 3 ] })

=> tree("b")
<= { [Function get]
     … }

Ancient Oak’s types

1:1 mapping between native JavaScript types and immutable ones

(Array, Object)

Array (Ancient Oak)

Object (Ancient Oak)

unsorted map, string keys

Ancient Oak assumptions

Ancient Oak

API: get

data = I({ a: 1, b: [ 2, 3 ]})
data         // function…
data("a")    // 1
data("b")    // function…
data("b")(1) // 3

API: dump & json

data = I({ a: 1, b: [ 2, 3 ]})

=> data.dump()
<= { a: 1, b: [ 2, 3 ] }

=> data.json()
<= '{"a":1,"b":[2,3]}'

API: set

v0 = I({ a: 1, b: [ 2, 3 ] })
v1 = v0.set("c", 5).set("a", 4)

=> v0.dump()
<= { a: 1, b: [ 2, 3 ] }

=> v1.dump()
<= { a: 4, b: [ 2, 3 ], c: 5 }

API: rm

remove an address from the tree

v0 = I({ a: 1, b: { c: 3, d: 4 } })
v1 = v0.rm("b", "d")

=> v1.dump()
<= { a: 1, b: { c: 3 } }

API: update

apply a function on a value

v0 = I({ a: 1, b: 2 })
v1 = v0.update("a", function (v) {
  return v + 1
})

=> v1.dump()
<= { a: 2, b: 2 }

API: patch

apply a diff on the whole tree

v0 = I({ a: 1, b: [ 2, 3 ] })
v1 = v0.patch({
  a: 2,
  b: { 0: 4, 3: 5 }
})

=> v1.dump()
<= { a: 2,
     b: [ 4, 3, , 5 ] }

API: iteration

API: map

returns the same type of collection as the original (object/array)

v0 = I({ a: 1, b: 2 })
v1 = v0.map(function (v) {
  return v + 1
})

=> v1.dump()
<= { a: 2, b: 3 }

API: data as a function

data = I({a: 1, b: 2, c: 3})

=> [ "a", "b", "c"].map(data)
<= [ 1, 2, 3 ]

Contributions welcome

Resources