immutable.rs

PERSISTENCE

WILL BE

REWARDED

@bodil

WHAT IS A DATA STRUCTURE?

A way of organising data so that it can be accessed and modified efficiently.

  • list
  • map
  • MUTABLE VS IMMUTABLE?

    A mutable value can change (like Vec), but an immutable value is the same forever (like i32).

    PERSISTENT DATA STRUCTURES

    A data structure that persists its current state when changed.

    COMPLEXITY

    We need a way to talk about the efficiency of operations on data structures.

    Big O notation!

    CONSTANT TIME: O(1)

    Same amount of work regardless of the size of the data structure.

    LINEAR TIME: O(n)

    Number of operations proportional to the size (n) of the data structure.

    LOGARITHMIC TIME: O(log n)

    Number of operations logarithmic to the size of the data structure.

    BIG O NOTATION

    O(1) = constant time

    O(log n) = logarithmic time

    O(n) = linear time

    O(n log n) = linear × logarithmic time

    AMORTISATION

    Spreading the cost over several operations.

    THESE NAMES COMPOSE!

    cadr = car of cdr = second element

    caddr = car of cdr of cdr = third element

    cddr = cdr of cdr = third element onward

    caar = car of car = first element of first element

    head →
    tail →

    TRIES

    and the hardest problem in computer science

    TRIES

    Tries are prefix or radix based search trees.

    Henceforth: RADIX TREES

    Phil Bagwell

    Rich Hickey

    Why can't we just have a data structure without any tradeoffs?

    DO YOU HAVE A MOMENT TO TALK ABOUT

    RELAXED RADIX BALANCED TREES

    RRB TREES

    Push/pop: O(logₖ n)

    Lookup: O(logₖ n)

    Concat: O(logₖ n)

    Split: O(logₖ n)

    WHY?

    REASONING

    Immutable values make it easier to reason about your program!

    (the Haskell defence)

    THREAD SAFETY

    If a value never changes, you can't have race conditions when changing it.

    EVOLVING STATE

    Recursive algorithms can backtrack easily

    Stateful apps can replay state

    THEY'RE FASTER!

    Cloning is always O(1)!

    SO VEC IS P COOL

    Its big O isn't that great, but -

    It's unbeatable with cache locality

    Chunking techniques let us lean on that

    MUTABLE ALWAYS BEATS IMMUTABLE

    Clojure has "transients" for this.
    Haskell has the ST monad.

    🐮 ALL YOU NEED IS COW 🐮

    
      fn Arc::make_mut(this: &mut Arc<T>) -> &mut T
            

    🐄 COW IS ALL YOU NEED 🐄

    MUTABLE WITH IMMUTABLE GUARANTEES

    If you're the sole owner, you're always mutable.

    LET'S TALK BIG O

    RRB vectors do complex things smarter than Vec

    With chunking, simpler ops can perform at Vec like speeds

    And at small sizes, it literally is Vec!

    Memory footprint is only slightly worse than Vec

    WHAT ABOUT MAPS

    Maps should perform close to std::collections

    …if I've done my job right

    Still a slightly worse memory footprint

    DESIGN CHOICES

    As complete as Haskell (and Clojure)

    But should feel like Rust

    Nobody is going to use a library with bad documentation.

    ABOUT THE ARCS

    Im wraps values in Arc to avoid a Clone constraint.

    It's slow, so maybe leave it to the user.

    Arc-less seems to speed things up a LOT!

    Thank you!

    immutable.rs

    bodil.lol/persistence/

    @bodil

    BELKA & STRELKA

    READING LIST

    Okasaki: Purely Functional Data Structures

    L'Orange: Understanding Clojure's Vectors

    Bagwell: Ideal Hash Trees

    Hinze, Paterson: Finger Trees

    Acar, Charguéraud, Rainey: Chunked Sequences

    Stucki, Rompf, Ureche, Bagwell: RRB Vector