No Touchy!

Software Architecture with Immutable Objects

A Case Study


Borislav Stanimirov / @stanimirovb

CppCon 2020

Hello, World



  #include <iostream>

  int main()
  {
      std::cout << "Hi, I'm Borislav!\n";
      std::cout << "These slides are here: is.gd/immutable\n";
      return 0;
  }

Borislav Stanimirov


  • Mostly a C++ programmer
  • 2006-2018 a game programmer
  • Since 2019 a medical software programmer
  • Open-source programmer
  • github.com/iboB

ViewRay's approach to treating cancer

5 min demo of cancer treatment workflow

What did you just see?


  • Software started from scratch in Feb 2019
  • Aims to replace the existing software
  • Browser GUI
  • C++17 backend

Birds Eye View

  • A browser client
  • ...connecting to an application server
  • ...which has multiple services and workers
    • Service: always alive. Has sessions
      • Treatment service
      • MRI service
      • ...
    • Worker: short life. Calculate something and die
      • Identify bladder
      • Calculate dose
      • ...

Going Deeper

UI Service


  • Has sessions for clients
  • Can build type-erased UI objects from the app state
  • WS Server - a layer for browsers. Reads and writes JSON
  • Theoretically we can have many other layers (say Qt)

Treatment Service


Creates a Treatment Session

  • Has a state which represents a treatment in progress
  • Fetches imaging info from the MRI Service
  • Issues start/stop to the Radiotherapy Service
  • Gathers information about the delivered dose
  • At the end saves treatment data to the database

Objects

For Business Logic

Object



  class Object {
  public:
    Data& data() { return m_data; }
    const Data& data() { return m_data; }
  private:
    Data m_data;
  };

Multiple threads. Races

std::mutex


  class Object {
  public:
    void lock() { m_mutex.lock(); }
    void unlock() { m_mutex.unlock(); }
  private:
    std::mutex m_mutex;
    Data m_data;
  };

Bad idea™ Readers will have to wait on each other

std::shared_mutex


  class Object {
  public:
    void readLock() { m_mutex.lock_shared(); }
    void readUnlock() { m_mutex.unlock_shared(); }

    void writeLock()  { m_mutex.lock(); }
    void writeUnlock()  { m_mutex.unlock(); }
  private:
    std::shared_mutex m_mutex;
    Data m_data;
  };

Let's try to work with this

std::shared_mutex


  class Object {
  public:
    void readLock() const { m_mutex.lock_shared(); }
    void readUnlock() const { m_mutex.unlock_shared(); }

    void writeLock()  { m_mutex.lock(); }
    void writeUnlock()  { m_mutex.unlock(); }
  private:
    mutable std::shared_mutex m_mutex;
    Data m_data;
  };

std::shared_mutex


  class Object {
  private:
    void readLock() const { m_mutex.lock_shared(); }
    void readUnlock() const { m_mutex.unlock_shared(); }

    void writeLock()  { m_mutex.lock(); }
    void writeUnlock()  { m_mutex.unlock(); }

    mutable std::shared_mutex m_mutex;
    Data m_data;
    friend class ObjectReadLock;
    friend class ObjectWriteLock;
  };

Object Read Lock


  class ObjectReadLock {
  public:
    ObjectReadLock(const Object& obj) : m_object(obj) {
      m_object.readLock();
    }
    ~ObjectReadLock() { m_object.readUnlock(); }

    const Object* operator->() const { return &m_object; }
    const Object* operator*() const  { return &m_object; }
  private:
    const Object& m_object;
  };

Object Write Lock


  class ObjectWriteLock {
  public:
    ObjectWriteLock(Object& obj) : m_object(obj) {
      m_object.writeLock();
    }
    ~ObjectWriteLock() { m_object.writeUnlock(); }

    Object* operator->() { return &m_object; }
    Object* operator*()  { return &m_object; }
  private:
    Object& m_object;
  };

Shared Mutex Problems


  • Writers will have to wait on each other
  • Writers will have to wait on readers
    • Our anatomical structures
    • Contouring algorithms write
    • Dose calculation reads
    • UI reads
    • Contouring algorithms may also read

CoW – Copy on Write

Classic Swift-style CoW


  template <typename T>
  class CoW {
      std::shared_ptr<T> m_data;
  public:
      const T& data() const {
          return *m_data;
      }
      T& mutableData() {
          if (m_data.use_count() > 1)
              m_data = std::make_shared<T>(*m_data);
          return *m_data;
      }
  };

Object CoW



  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
  public:
      const Object& read() const {
          return *m_object;
      }
      Object& write() {
          if (m_object.use_count() > 1)
              m_object = std::make_shared<Object>(*m_object);
          return *m_object;
      }
  };

How do we refer to objects?

Referring to Objects


ObjectWrapper myobj;
std::thread gui([]() { guiLoop(myobj); });
myobj.write().changeSomething();

...

void guiLoop(ObjectWrapper obj) {
  while (true) {
    display(obj.read().getSomething());
  }
}

Referring to Objects


ObjectWrapper myobj;
std::thread gui([]() { guiLoop(myobj); });
myobj.write().changeSomething(); // Uh oh! After this line

...

void guiLoop(ObjectWrapper obj) {
  while (true) {
    display(obj.read().getSomething()); // No way to access changed here
  }
}

Object Handle


  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
  public:
      const Object& read() const {
          return *m_object;
      }
      Object& write() {
          if (m_object.use_count() > 1)
              m_object = std::make_shared<Object>(*m_object);
          return *m_object;
      }
  };
  using ObjectHandle = std::shared_ptr<ObjectWrapper>;

Referring to Objects through Handles


ObjectHandle myobj;
std::thread gui([]() { guiLoop(myobj); });
myobj->write().changeSomething(); // Uh oh! during this line

...

void guiLoop(ObjectHandle obj) {
  while (true) {
    display(obj->read().getSomething()); // We race on the shared pointer here
  }
}

Object Handle Races


  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
  public:
      std::shared_ptr<const Object> read() const {
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      Object& write() {
          if (m_object.use_count() > 1) {
              auto newObject = std::make_shared<Object>(*m_object);
              std::atomic_store_explicit(&m_object, newObject,
                  std::memory_order_relaxed);
          }
          return *m_object;
      }
  };
  using ObjectHandle = std::shared_ptr<ObjectWrapper>;

Referring to Objects through Handles


ObjectHandle myobj;
std::thread gui([]() { guiLoop(myobj); });
myobj->write().changeSomething(); // Uh oh! during this line

...

void guiLoop(ObjectHandle obj) {
  while (true) {
    display(obj->read()->getSomething()); // We race on object contents in "Something"
  }
}

Always CoW


  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
      std::shared_ptr<Object> m_writeObject;
  public:
      std::shared_ptr<const Object> read() const {
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      std::shared_ptr<Object> writeLock() {
          m_writeObject = std::make_shared<Object>(*m_object);
          return m_writeObject;
      }
      void writeUnlock() {
          std::atomic_store_explicit(&m_object, m_writeObject,
              std::memory_order_relaxed);
      }
  };
  using ObjectHandle = std::shared_ptr<ObjectWrapper>;

Bring Back Locks


  class ObjectReadLock {
  public:
    ObjectReadLock(const ObjectHandle& handle) : m_object(handle.read()) {}

    const Object* operator->() const { return m_object.get(); }
    const Object* operator*() const  { return *m_object; }
  private:
    std::shared_ptr<const Object> m_object;
  };

...not necessarily needed

Bring Back Locks


  class ObjectWriteLock {
  public:
      ObjectWriteLock(const ObjectHandle& handle) : m_handle(handle) {
        m_object = m_handle.writeLock();
      }
      ~ObjectWriteLock() {
        m_handle.writeUnlock();
      }

      Object* operator->() { return m_object.get(); }
      Object* operator*()  { return *m_object; }
  private:
      ObjectHandle m_handle;
      std::shared_ptr<Object> m_object;
  };

Referring to Objects through Locks


ObjectHandle myobj;
std::thread gui([]() { guiLoop(myobj); });
ObjectWriteLock(myobj)->changeSomething();

...

void guiLoop(ObjectHandle obj) {
  while (true) {
    display(ObjectReadLock(obj)->getSomething());
  }
}

This can totally work if we promise to only write from a single thread

... but what if we want to write from several threads?

Multiple writers


  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
      std::shared_ptr<Object> m_writeObject; // Make this thread safe?
                                             // Where is the *real* data then?
      std::shared_ptr<const Object> read() const {
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      std::shared_ptr<Object> writeLock() {
          m_writeObject = std::make_shared<Object>(*m_object);
          return m_writeObject;
      }
      void writeUnlock() {
          std::atomic_store_explicit(&m_object, m_writeObject,
              std::memory_order_relaxed);
      }
  };
  using ObjectHandle = std::shared_ptr<ObjectWrapper>;

Heavy Artillery


  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
      std::shared_ptr<Object> m_writeObject;
      std::mutex m_accessMutex;
      std::shared_ptr<const Object> read() const {
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      std::shared_ptr<Object> writeLock() {
          m_accessMutex.lock();
          m_writeObject = std::make_shared<Object>(*m_object);
          return m_writeObject;
      }
      void writeUnlock() {
          std::atomic_store_explicit(&m_object, m_writeObject,
              std::memory_order_relaxed);
          m_accessMutex.unlock();
      }
  };
  using ObjectHandle = std::shared_ptr<ObjectWrapper>;

And these are immutable objects

Immutable?

Think std::string_view

You don't change. You replace.

In this case with a copy.

Remember the optional CoW?

What if we still want that?

Addendum A: Optional CoW

What if?


  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
      std::shared_ptr<Object> m_writeObject;
      std::mutex m_accessMutex;
      std::shared_ptr<const Object> read() const {
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      std::shared_ptr<Object> writeLock() {
          m_accessMutex.lock();
          m_writeObject = (m_object.use_count() > 1)
              ? std::make_shared<T>(*m_object);
              : m_object; // readers suffer from races
          return m_writeObject;
      }
      void writeUnlock() {
      ...

Lock on Read


  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
      std::shared_ptr<Object> m_writeObject;
      std::mutex m_accessMutex;
      std::shared_ptr<const Object> read() const {
          std::lock_guard l(m_accessMutex);
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      std::shared_ptr<Object> writeLock() {
          m_accessMutex.lock();
          m_writeObject = (m_object.use_count() > 1)
              ? std::make_shared<T>(*m_object);
              : m_object;
          return m_writeObject;
      }
      void writeUnlock() {
      ...

Lock on Read


  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
      std::mutex m_accessMutex;
      std::shared_ptr<const Object> read() const {
          std::lock_guard l(m_accessMutex);
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      std::shared_ptr<Object> writeLock() {
          m_accessMutex.lock();
          if (m_object.use_count() > 1) {
              auto newObject = std::make_shared<Object>(*m_object);
              std::atomic_store_explicit(&m_object, newObject,
                  std::memory_order_relaxed);
          }
          return m_object;
      }
      void writeUnlock() {
          m_accessMutex.unlock();
      }

Are we done?

  • While testing we get some suspicious CoWs
  • Uh-oh! Concurrent writers with no reads CoW??

  class ObjectWriteLock {
  public:
    ObjectWriteLock(const ObjectHandle& handle) : m_handle(handle) {
      m_object = m_handle.writeLock();
    }
    ~ObjectWriteLock() {
      m_handle.writeUnlock(); // we unlock the mutex but retain a ref
    }

    Object* operator->() { return m_object.get(); }
    Object* operator*()  { return *m_object; }
  private:
    ObjectHandle m_handle;
    std::shared_ptr<Object> m_object;
  };

Fix A


  class ObjectWriteLock {
  public:
    ObjectWriteLock(const ObjectHandle& handle) : m_handle(handle) {
      m_object = m_handle.writeLock();
    }
    ~ObjectWriteLock() {
      m_object.reset();
      m_handle.writeUnlock();
    }

    Object* operator->() { return m_object.get(); }
    Object* operator*()  { return *m_object; }
  private:
    ObjectHandle m_handle;
    std::shared_ptr<Object> m_object;
  };

Fix B


  class ObjectWriteLock {
  public:
    ObjectWriteLock(const ObjectHandle& handle) : m_handle(handle) {
      m_object = m_handle.writeLock().get();
    }
    ~ObjectWriteLock() {
      m_handle.writeUnlock();
    }
    // OMG THE PERF GAIN
    Object* operator->() { return m_object; }
    Object* operator*()  { return *m_object; }
  private:
    ObjectHandle m_handle;
    Object* m_object = nullptr;
  };

At first we chose this

We Can't Have Nice Things


  • Run this with TSAN
  • Get a ton of race warnings
  • Investigate
  • std::shared_ptr::use_count uses a relaxed memory order

What did TSAN see?

  • Thread A is reading from an object
  • Thread B makes a write lock
  • What would if (m_object.use_count() > 1) do?
    • If the read finishes around that time, use_count will be 1
    • But a reorder might happen and we can get 1 there before the reader has finished reading
    • In such case we won't make a CoW and will instead write to the same object
    • But ~shared_ptr() uses release on the use count, so this can't happen

The sad Truth


  • After mucho mucho investigation
  • This sadly is a false positive
  • TSAN is trying to be smart. It reads C++ code and not just assembly.
  • It "knows" of the release-acquire relatioship and assumes relaxed loads are not part of it
  • There are no actual races!

:(

What can we do?

Options


  • Live with it? Bad idea™. TSAN is too awesome to abandon
  • Rewrite std::shared_ptr with a method use_count_acquire
    • Not as bad as it sounds. There are benefits
  • Reimplement ref counting for objects

  class Object {
  public:
      void Object::incReadLockCounter() const {
          m_numActiveReadLocks.fetch_add(1, std::memory_order_relaxed);
      }
      void Object::decReadLockCounter() const {
          m_numActiveReadLocks.fetch_sub(1, std::memory_order_release);
      }
      bool Object::hasReadLocks() const {
          return m_numActiveReadLocks.load(std::memory_order_acquire) > 0;
      }
  private:
      mutable std::atomic_int32_t m_numActiveReadLocks = {};
  };
        

      std::shared_ptr<Object> ObjectWrapper::writeLock() {
          m_accessMutex.lock();
          if (m_object->hasReadLocks()) {
              ...

Options


  • Live with it? Bad idea™. TSAN is too awesome to abandon
  • Rewrite std::shared_ptr with a method use_count_acquire
    • Not as bad as it sounds. There are benefits
  • Reimplement ref counting for objects
  • Or... hack around it

Our Optimized Write Lock


  class ObjectWriteLock {
  public:
    ObjectWriteLock(const ObjectHandle& handle) : m_handle(handle) {
      m_object = m_handle.writeLock().get();
    }
    ~ObjectWriteLock() {
      m_handle.writeUnlock();
    }
    // OMG THE PERF GAIN
    Object* operator->() { return m_object; }
    Object* operator*()  { return *m_object; }
  private:
    ObjectHandle m_handle;
    Object* m_object = nullptr;
  };

Our Deoptimized Write Lock


  class ObjectWriteLock {
  public:
    ObjectWriteLock(const ObjectHandle& handle) : m_handle(handle) {
      m_object = m_handle.writeLock();
    }
    ~ObjectWriteLock() {
      m_object.reset();
      m_handle.writeUnlock();
    }
    // OMG THE PERF LOSS :(
    Object* operator->() { return m_object.get(); }
    Object* operator*()  { return *m_object; }
  private:
    ObjectHandle m_handle;
    std::shared_ptr<Object> m_object;
  };

Why does this work?


  • We're not sure
  • Possibly accessing the use count within a mutex lock helps
  • ... or some such

"Cool" Objects


  • Optional CoW only if we have active readers
  • Readers wait on active writers by locking a mutex
  • Synchronised writes from any thread
  • We actually do use these in some places

Improving Terminology


  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
      std::shared_ptr<Object> m_writeObject;
      std::mutex m_accessMutex;
      std::shared_ptr<const Object> read() const {
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      std::shared_ptr<Object> writeLock() {
          m_accessMutex.lock();
          m_writeObject = std::make_shared<Object>(*m_object);
          return m_writeObject;
      }
      void writeUnlock() {
          std::atomic_store_explicit(&m_object, m_writeObject,
              std::memory_order_relaxed);
          m_accessMutex.unlock();
      }
  };

Improving Terminology


  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
      std::shared_ptr<Object> m_writeObject;
      std::mutex m_accessMutex;
      std::shared_ptr<const Object> detach() const {
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      std::shared_ptr<Object> writeLock() {
          m_accessMutex.lock();
          m_writeObject = std::make_shared<Object>(*m_object);
          return m_writeObject;
      }
      void writeUnlock() {
          std::atomic_store_explicit(&m_object, m_writeObject,
              std::memory_order_relaxed);
          m_accessMutex.unlock();
      }
  };

Improving Terminology


  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
      std::shared_ptr<Object> m_writeObject;
      std::mutex m_accessMutex;
      std::shared_ptr<const Object> detach() const {
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      std::shared_ptr<Object> beginTransaction() {
          m_accessMutex.lock();
          m_writeObject = std::make_shared<Object>(*m_object);
          return m_writeObject;
      }
      void endTransaction() {
          std::atomic_store_explicit(&m_object, m_writeObject,
              std::memory_order_relaxed);
          m_accessMutex.unlock();
      }
  };

Improving Terminology


  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
      std::shared_ptr<Object> m_writeObject;
      std::mutex m_transactionMutex;
      std::shared_ptr<const Object> detach() const {
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      std::shared_ptr<Object> beginTransaction() {
          m_transactionMutex.lock();
          m_writeObject = std::make_shared<Object>(*m_object);
          return m_writeObject;
      }
      void endTransaction() {
          std::atomic_store_explicit(&m_object, m_writeObject,
              std::memory_order_relaxed);
          m_transactionMutex.unlock();
      }
  };

Improving Terminology


  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
      std::shared_ptr<Object> m_writeObject;
      std::mutex m_transactionMutex;
      std::shared_ptr<const Object> detach() const {
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      std::shared_ptr<Object> beginTransaction() {
          m_transactionMutex.lock();
          m_writeObject = std::make_shared<Object>(*m_object);
          return m_writeObject;
      }
      void endTransaction(bool store) {
          if (store) {
            std::atomic_store_explicit(&m_object, m_writeObject,
                std::memory_order_relaxed);
          }
          m_transactionMutex.unlock();
      }
  };

Our Immutable Objects So Far


  • Atomic transactions: synchronised writes from any thread
  • Always CoW on transaction
  • Fastest possible lockless reads by detaching
  • A detached object is possibly outdated
  • Every reference to the object is safe and valid forever
  • Why, yes, this can be called a glorified shared_ptr wrapper
  • It leads to a different way of thinking

Indeed, at first we didn't think much of it

Hmm... smells like React.js

React.js


  • It's a GUI library for single-page applications
  • Take a state
  • Create the DOM - the elements on the page
  • That's it
  • Let's see an example...

Imaging Session State

...in JavaScript


  imagingState = {
    patient: {
      orientation: null,
      weight: null,
    },
    image: {
      name: '',
      notes: '',
      size: {x: 0, y: 0, z: 0},
      buffer: null,
      progress: 0,
    },
    table: {
      pos: {x: 0, y: 0, z: 0},
      progress: 0,
    },
  };

Build Some GUI


  buildGUI({
    patient: {
      orientation: HeadFirstSuppine,
      weight: 80000,
    },
    image: {
      name: 'My Image',
      notes: 'Notes on my image',
      size: {x: 200, y: 200, z: 200},
      buffer: Loader.loadImage('test.img'),
      progress: 1,
    },
    table: {
      pos: {x: 2, y: 3, z: 4},
      progress: 0.5,
    },
  });

Change the State



  function setImageName() {
    return { image: { name: "Cool image" }}};
  }
        

  function shiftTable(state) {
    return { table: { pos: { y: state.table.pos.y + 20 }}}};
  }

Thanks to JS reflection. These will be spliced onto the state

Splicing onto the State

  function setImageName() {
    return { image: { name: "Cool image" }}};
  }
  state:
    patient:
      orientation: HeadFirstSuppine
      weight: 80000
    image:
      name: "My image"
      notes: "Notes on my image"
      size:
        x:200 y:200 z:200
      buffer: [0,3,132,34,12...
      progress: 1
    table:
      pos:
        x:2 y:3 z:4
      progress: 0.5

Splicing onto the State

  function setImageName() {
    return { image: { name: "Cool image" }}};
  }

  let oldState = state;

  state = reactSplice(state, setImageName);

  console.assert(state !== oldState, "Uh-oh"); // Uh-oh

Only the names have changed - Jon Bon Jovi

Splicing onto the State

  function setImageName() {
    return { image: { name: "Cool image" }}};
  }
  state:
    patient:
      orientation: HeadFirstSuppine
      weight: 80000
    image:
      name: "My image"
      notes: "Notes on my image"
      size:
        x:200 y:200 z:200
      buffer: [0,3,132,34,12...
      progress: 1
    table:
      pos:
        x:2 y:3 z:4
      progress: 0.5

Splicing onto the State

  function setImageName() {
    return { image: { name: "Cool image" }}};
  }

  let oldState = state;

  state = reactSplice(state, setImageName);

  console.assert(state !== oldState, "Uh-oh"); // Everything is fine

Building GUI



    if (state != oldState) return null;
        

    if (state.image !== oldState.image) return null;
    return <img src="...

React.js-style state in C++?

That would be pretty cool!

Build GUI



    auto state = getState();
    buildGUI(state);

Run Workers



    auto state = getState();
    findBladder(state->image);
    findFemurs(state->image);
    calculateElectronDensity(state->ctImage, state->structures["ptv"]);

Undo & Redo



    undoAction->old = getState()->structures["bladder"];
    applyManualUserEditsTo("bladder");
    undoAction->cur = getState()->structures["bladder"];

But most importantly...

Integration Testing by Unit Testing

Here's a thought


    auto state = getState();
    buildGUI(state);

What if...


    auto state = somePredefinedState();
    buildGUI(state);
    assert(currentGUI == expectedGUI);

Then what if...


    auto state = somePredefinedState();
    treatment(state, receivedNewImageFromMRI, loader.loadImage("test.img"));
    assert(deepCompare(getState(), expectedState));

Big Bang Integration Testing


    auto state = somePredefinedState();
    imaging(state, receivedNewImageFromMRI, loader.loadImage("test.img"));
    assert(deepCompare(getState(), expectedState));

Bottom-Up Integration Testing


    auto state = somePredefinedState();
    // Mock
    auto imaging = [](State& s){ if (!s.image) s.image=loader.loadImage("test.img");};
    treatment(state);
    assert(deepCompare(getState(), expectedState));

Top-Down Integration Testing

Integration Testing by Unit Testing


  • When we have the app state in a single object...
  • ...everything the application does is a pure function
  • State doSomething(const State&)
  • ...which can be unit tested

Moreover...


  • Since all modules are functions...
  • ...mocks are trivial
  • Since the entire state is an object...
  • ...fuzzing is easy
  • Since the an object can be saved to and loaded from disk...
  • ...resuming after a crash is trivial
  • ...jump in time debugging is possible

That got us intrigued

So... back to our objects...

shared_ptr Wrapper and React.js


  • Shallow compare: a == b compares addresses
    • Not string_view anymore
  • CoW on every change is like React splicing
  • Detached references are safe and valid forever

Let's Build the State in C++



But first...

The Object


  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
      std::shared_ptr<Object> m_writeObject;
      std::mutex m_transactionMutex;
      std::shared_ptr<const Object> detach() const {
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      std::shared_ptr<Object> beginTransaction() {
          m_transactionMutex.lock();
          m_writeObject = std::make_shared<Object>(*m_object);
          return m_writeObject;
      }
      void endTransaction(bool store) {
          if (store) {
              std::atomic_store_explicit(&m_object, m_writeObject,
                  std::memory_order_relaxed);
          }
          m_transactionMutex.unlock();
      }
  };

More changes

  template <typename T>
  class ObjectWrapper {
      std::shared_ptr<Object> m_object;
      std::shared_ptr<Object> m_writeObject;
      std::mutex m_transactionMutex;
      std::shared_ptr<const Object> detach() const {
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      std::shared_ptr<Object> beginTransaction() {
          m_transactionMutex.lock();
          m_writeObject = std::make_shared<Object>(*m_object);
          return m_writeObject;
      }
      void endTransaction(bool store) {
          if (store) {
              std::atomic_store_explicit(&m_object, m_writeObject,
                  std::memory_order_relaxed);
          }
          m_transactionMutex.unlock();
      }
  };

More changes

  template <typename T>
  class ObjectWrapper {
      std::shared_ptr<T> m_object;
      std::shared_ptr<T> m_writeObject;
      std::mutex m_transactionMutex;
      std::shared_ptr<const T> detach() const {
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      std::shared_ptr<T> beginTransaction() {
          m_transactionMutex.lock();
          m_writeObject = std::make_shared<T>(*m_object);
          return m_writeObject;
      }
      void endTransaction(bool store) {
          if (store) {
              std::atomic_store_explicit(&m_object, m_writeObject,
                  std::memory_order_relaxed);
          }
          m_transactionMutex.unlock();
      }
  };

More changes

  template <typename T>
  class Object {
      std::shared_ptr<T> m_object;
      std::shared_ptr<T> m_writeObject;
      std::mutex m_transactionMutex;
      std::shared_ptr<const T> detach() const {
          return std::atomic_load_explicit(&m_object, std::memory_order_relaxed);
      }
      std::shared_ptr<T> beginTransaction() {
          m_transactionMutex.lock();
          m_writeObject = std::make_shared<T>(*m_object);
          return m_writeObject;
      }
      void endTransaction(bool store) {
          if (store) {
              std::atomic_store_explicit(&m_object, m_writeObject,
                  std::memory_order_relaxed);
          }
          m_transactionMutex.unlock();
      }
  };

More changes

  template <typename T>
  class Object {
      std::shared_ptr<T> m_data;
      std::shared_ptr<T> m_transactionData;
      std::mutex m_transactionMutex;
      std::shared_ptr<const T> detach() const {
          return std::atomic_load_explicit(&m_data, std::memory_order_relaxed);
      }
      std::shared_ptr<T> beginTransaction() {
          m_transactionMutex.lock();
          m_transactionData = std::make_shared<T>(*m_data);
          return m_transactionData;
      }
      void endTransaction(bool store) {
          if (store) {
              std::atomic_store_explicit(&m_data, m_transactionData,
                  std::memory_order_relaxed);
          }
          m_transactionMutex.unlock();
      }
  };

More Changes

  template <typename T>
  class Transaction { // used to be WriteLock
  public:
      Transaction(Object<T>& obj) : m_object(obj) {
          m_object.beginTransaction();
      }
      ~Transaction() {
          m_object.endTransaction(std::uncaught_exceptions() == 0);
      }

      Object* operator->() { return m_object.m_transactionData.get(); }
      Object* operator*()  { return *m_object.m_transactionData; }
  private:
      Object<T>& m_object;
  };

So, Let's Build the State in C++

  struct ImagingState {
      struct PatientData {
          Orientation orientation;
          grams weight;
      };
      PatientData patient;
      struct ImageData {
          string name;
          string notes;
          point3 size;
          vector<byte> buffer;
          float progress = 0;
      };
      ImageData image;
      struct TableData {
          point3 pos;
          float progress = 0;
      };
      TableData table;
  };

  using ImagingStateObject = Object<ImagingState>;

Obviously that's not enough

We copy everything

More Objects?

struct ImagingState {
      struct PatientData {
          Orientation orientation;
          grams weight;
      };
      Object<PatientData> patient;
      struct ImageData {
          string name;
          string notes;
          point3 size;
          vector<byte> buffer;
          float progress = 0;
      };
      Object<ImageData> image;
      struct TableData {
          point3 pos;
          float progress = 0;
      };
      Object<TableData> table;
  };

  using ImagingStateObject = Object<ImagingState>;

All of the Objects?

struct ImagingState {
      struct PatientData {
          Object<Orientation> orientation;
          Object<grams> weight;
      };
      Object<PatientData> patient;
      struct ImageData {
          Object<string> name;
          Object<string> notes;
          Object<point3> size;
          Object<vector<byte>> buffer;
          Object<float> progress = 0;
      };
      Object<ImageData> image;
      struct TableData {
          Object<point3> pos;
          Object<float> progress = 0;
      };
      Object<TableData> table;
  };

  using ImagingStateObject = Object<ImagingState>;

Some Objects (It's hard)

struct ImagingState {
      struct PatientData {
          Orientation orientation;
          grams weight;
      };
      Object<PatientData> patient;
      struct ImageData {
          Object<string> name;
          Object<string> notes;
          Object<point3> size;
          Object<vector<byte>> buffer;
          float progress = 0;
      };
      Object<ImageData> image;
      struct TableData {
          Object<point3> pos;
          float progress = 0;
      };
      Object<TableData> table;
  };

  using ImagingStateObject = Object<ImagingState>;

Ok. Let's try this...

Set Image Name



  function setImageName() {
    return { image: { name: "Cool image" }}};
  }
        

  *Transaction(Transaction(Transaction(state)->image)->name)) = "Cool image";
  • That's a lot of transactions, Batman
  • That's a lot of recursive mutex locks, Batman
  • And that's not the worst part

The Worst Part



  auto oldImage = state->detach()->image->detach();// That's a lot of detach(), Batman
  *Transaction(oldImage->name) = "something different";
  auto curImage = state->detach()->image->detach();
  assert(*oldImage->name->detach() != *curImage->name->detach());
  // Uh-oh, they both are "something different"
  • We broke the detach promise
  • This is not the way of React.js

Split the Object

  template <typename T>
  class RootObject {
      std::shared_ptr<T> m_data;
      std::shared_ptr<T> m_transactionData;
      std::mutex m_transactionMutex;
      std::shared_ptr<const T> detach() const {
          return std::atomic_load_explicit(&m_data, std::memory_order_relaxed);
      }
      std::shared_ptr<T> beginTransaction() {
          m_transactionMutex.lock();
          m_transactionData = std::make_shared<T>(*m_data);
          return m_transactionData;
      }
      void endTransaction(bool store) {
          if (store) {
              std::atomic_store_explicit(m_data, m_transactionData,
                  std::memory_order_relaxed);
          }
          m_transactionMutex.unlock();
      }
  };

Split the Object

  template <typename T>
  class Node {
      std::shared_ptr<T> m_data;
      const T* operator->() const { return m_data.get(); }
      const T& operator*() const { return *m_data; }
      T* operator->() {
          cow();
          return m_data.get();
      }
      T& operator*() {
          cow();
          return *m_data;
      }
      void cow() { // moo
          m_data = std::make_shared<T>(*m_data); // no need for atomic
      }
      std::shared_ptr<const T> payload() const { return m_data; }
  };

Imaging State

struct ImagingState {
      struct PatientData {
          Orientation orientation;
          grams weight;
      };
      Node<PatientData> patient;
      struct ImageData {
          Node<string> name;
          Node<string> notes;
          Node<point3> size;
          Node<vector<byte>> buffer;
          float progress = 0;
      };
      Node<ImageData> image;
      struct TableData {
          Node<point3> pos;
          float progress = 0;
      };
      Node<TableData> table;
  };

  using ImagingStateObject = RootObject<ImagingState>;

Set Image Name



  function setImageName() {
    return { image: { name: "Cool image" }}};
  }
        

  *Transaction(state)->image->name = "Cool image";

Shallow copy-on-write on state-image-name

Test


  auto oldState = state.detach();
  auto name = oldState->image->name.payload();
  *Transaction(state)->image->name = "something different";
  auto curState = state.detach();
  assert(oldState != curState); // shallow compare
  assert(oldState->image != curState->image); // shallow compare
  assert(oldState->image->name != curState->image->name); // shallow compare
  assert(*oldState->image->name != *curState->image->name); // string compare

This is the React.js way

Problems


  *Transaction(state)->image->name = "Cool name";
  // we copied the old name, only to replace it with "Cool name"
        

  Transaction t(state);
  t->image->name = "foo";
  t->image->notes = "bar";
  // image gets CoW'd twice
        

  Transaction t(state);
  if (t->image->buffer->empty()) {
      t->image->name = "<empty>";
  }
  // we copy-on-write even if we change nothing
kuzco

Kuzco

gh/iboB/kuzco

TBD

Kuzco Solutions


  *Transaction(state)->image->name = "Cool name";
  // no copies of name
        

  Transaction t(state);
  t->image->name = "foo";
  t->image->notes = "bar";
  // image gets CoW'd once
        

  Transaction t(state);
  if (t.r()->image->buffer->empty()) {
      t->image->name = "<empty>";
  }
  // no copies if we don't change

More Problems

  struct MRIStudy {
      std::vector<Image> images;
      // ...
  };
  // copy vector on every change?
  struct MRIStudy {
      Node<std::vector<Image>> images;
      // ...
  };
  // copy all images on every change?
  struct MRIStudy {
      Node<std::vector<Node<Image>>> images;
      // ...
  };

More Problems


  Transaction(state)->images->emplace_back();

What happens here?

  1. Copy state. Fine
  2. Copy images. Er... fine
  3. emplace_back needs to reallocate. Ew... fine
  4. Copy images. This is were I draw the line!

Custom Container Wrappers


  template <typename T>
  class NodeVector {
      std::shared_ptr<std::vector<T>> m_data;
      auto& emplace_back() {
          auto old = m_data;
          m_data = std::make_shared<std::vector<T>>();
          m_data.reserve(old.size());
          m_data = old;
          return m_data.emplace_back();
      }
      // ...
  };

The same for other containers

That's a Lot of Allocations, Batman

  Transaction(state)->imaging->image[0]->progress->value = 0.4f;
  // 4 allocs here multiple times per second

  • So far we haven't done anything about it
  • Better state structure?
  • Custom allocators?
  • Reimplementing std::shared_ptr?
  • Do we even need weak pointers?
  • Still gathering information

That's a Lot of Copying

... Batman

  • Imagine setImageVoxel(point3, value)
  • Copy tens of megabytes of an image?
  • This is a real limitation
  • We just don't do that
  • A mutable placeholder with conventional locks?
  • Manual contouring works like this
  • If this is everything to do, perhaps that's not the right pattern

Reuse


  bool shouldTakeScan(const State& state) {
      return state.image->empty() || *state.image->retake;
  }
        

  struct Imaging { Node<Image> image; };
  struct Treatment { Node<Imaging> imaging; };
  struct Diagnosis { Node<Imaging> phase1; }

How can we reuse shouldTakeScan?

Queries


  bool shouldTakeScan(const State& state) {
      auto image = query<GetImaging>(state)->image;
      return image->empty() || *image->retake;
  }
  // Chaining
  bool shouldTakeScan(const State& state) {
      auto image = query<GetImaging>(state).q<GetImage>();
      return image->empty() || *image->retake;
  }
  // Mutable
  void calculateBladder(Transaction<State>& state) {
      auto& b = query<GetOrgans>(state).q<GetOrgan>("bladder");
      b = calcBladder(query<GetImaging>(state.r()).q<GetImage>());
  }

React.js-Style Objects in C++


  • Immutable objects based on ref-counted pointers
  • Shallow copies
  • Shallow compares
  • State composed of nodes
  • Special nodes for containers
  • Queries
  • Not always the way to go :(
  • Mucho potential

End of Part 1

Part 2

How do We Use Them?

Actions


  • Since we're implementing React, why not implement Redux?
  • An action changes the state
  • "Set name of scan N in the study": N and name
  • "Receive new delivery frame": Image, dose, confidence...
  • "Set the entire state to this"

Actions


  class SetNameOfScan {
    int n = 0;
    std::string name;

    template <typename State>
    void operator()(State& state) {
        auto imaging = query<GetImaging>(state); // may throw "No imaging"
        if (canSetNameOfScan(imaging, n)) {
            imaging->images[n]->name = name;
        }
        else {
            throw BadAction(action);
        }
    }
  };

Applying Actions


  template <typename Action, typename State>
  void applyAction(Action& action, RootObject<State>& state) {
      try {
          auto t = Transaction(state);
          action(*t);
      }
      catch (Exception& e) {
          // most likely notify user that their action is invalid
          // or add fatal error to state (long story)
      }
  }

Can a valid action lead to an invalid state invariant?

What if we want to enforce unique names?

Actions

class SetNameOfScan {
    int n = 0;
    std::string name;

    template <typename State>
    void operator()(State& state) {
        auto imaging = query<GetImaging>(state); // may throw "No imaging"
        if (canSetNameOfScan(imaging, n, name)) {
            imaging->images[n]->name = name;
        }
        else {
            throw BadAction(action);
        }
    }
  };

No way to check validity of state unless we set the name

No way to validate SetEntireState

State Guards


  void checkValidImageNames(const Imaging& img) {
      if (!allNamesUnique(img.images)) {
          throw BadState();
      }
  }
  template <typename State>
  void checkValidImaging(const State& state) {
      auto imaging = query<GetImaging>(state);
      checkValidImageNames(imaging);
      checkAllImagesOfSameSize(imaging);
      checkNoSimultaneousTableMoveAndScan(imaging);
      // ...
  }

App

  template <typename State>
  class App {
      RootObject<State> state;
      std::vector<std::function<void(const State&)>> guards;
      void runGuards(const State&);
  };

Or...

  class TreatmentApp {
      RootObject<TreatmentState> state;
      void runGuards(const State& state) {
          checkPatient(state);
          checkImaging(state);
          checkDelivery(state);
      }
  };

Applying Actions


  template <typename Action, typename App>
  void applyAction(Action& action, App& app) {
      try {
          auto t = Transaction(app.state);
          action(*t);
          app.runGuards(*t);
      }
      catch (Exception& e) {
          // most likely notify user that their action is invalid
          // or add fatal error to state (long story)
      }
  }
Batman and Robin

That's a lot of guard calls

Optimizing Guard Calls


  struct CheckImaging {
    std::shared_ptr<const Imaging> lastValidatedImaging;
    template <typename State>
    void operator()(const State& state) {
        auto imaging = query<GetImaging>(state);
        if (lastValidatedImaging == imaging) return;
        checkValidImageNames(imaging);
        checkAllImagesOfSameSize(imaging);
        checkNoSimultaneousTableMoveAndScan(imaging);
        // ...
        lastValidatedImaging = imaging;
    }
  };

Guards are not pure anymore :(

Promising results on memoizing guards and queries on the state

PubSub


    void endTransaction(bool store) {
        std::shared_ptr<const T> newData;
        if (store) {
            std::atomic_store_explicit(m_data, m_transactionData,
                std::memory_order_relaxed);
            newData = std::move(m_transactionData);
        }
        m_transactionMutex.unlock();
        if (newData) {
            notifySubscribers(newData);
        }
    }

Notify on each state change, but not while locked

UI Example


  treatmentState.subscribe([uiThread]() {
      uiThread->wakeUp();
  });
  // ...
  void UIThread::run() {
      waitUntilWokenUp();
      buildGUI(treatmentState.detach()); // ok if we skip states
  }
  // ...
  void UIThread::onSetImageName(UserPtr user, int i, std::string name) {
      treatmentSession.pushAction<SetImageName>(user, i, name);
  }

  void UIThread::onCalculateBladder(UserPtr user) {
      // ???
  }

Multi-Threaded Stuff

The User's Perspective


  void UserThread::run() {
      waitUntilWokenUp();
      std::future<std::optional<Action>> f
          = makeDecision(myBrainState, observedAppState);
      f.wait();
      auto action = f.get();
      if (action) app.pushAction(*action);
  }

We translate declarative to imperative code

State Observers


  void bladderObserver() {
      if (bladderCalculation.running()) {
          if (query<GetImage>(appState) != query<GetImage>(myState)) {
              bladderCalculation.abort();
          }
          else {
              return;
          }
      }
      if (!query<GetBladder>(appState)) {
          bladderCalculation.start();
          return;
      }
      if (query<GetBladder>(appState)->manualCalcRequested) {
          bladderCalculation.start();
          return;
      }
  }

So This Means...


  • Managed workers. One does not simply std::thread t(func);
  • Workers can named, found, started, aborted
  • This means they can be single-threaded
  • What to do with their result?
  • Don't just post an action and abort, or risk rerun
  • Post an action and wait until the result is collected!

Applying Async Results


  class SetBladder {
      void operator(State& s) {
          auto worker = workers("Bladder");
          if (!worker->hasResult()) throw BadAction("no bladder");
          auto result = worker->collectResult();
          // only now is the bladder worker complete
          if (query<GetImage>(state.r()) != result.image {
              throw BadAction("outdated bladder");
          }
          query<GetBladder>(state) = result.bladder;
      }
  };

Imperative to declarative code

State Observers


  • Run after every state change
  • Potentially in many threads
  • Manage workers based on their internal state
  • Can also decide to synchronously push actions
  • That's how Services communicate

Examples of Tests

GUI


  auto state = load<TreatmentState>("treatment-delivery-beam-on.state");
  auto gui = generateGui(state);
  auto expectedGUI = load<GUI>("treatment-delivery-beam-on.gui");
  assert(gui == expectedGUI);

Treatment


  auto patient = load<Patient>("john-doe.patient");
  auto app = newTreatment(patient);

  WorkerManager::setThreads(0);
  WorkerManager::overrideWorker("MRI.takeImage", []() {
      return load<Image>("test.img"); // mock
  });

  WorkerManager::exaustWorkers(); // synchronous

  assert(hasAllImages(app.state)); // auto imaging worked
  assert(hasAllOrgans(app.state)); // auto contouring worked

Programming with Immutable Objects


  • Not a solution for every problem
  • Programming and design is hard
  • It can be overly verbose
  • The performance is not great, not terrible
  • Awesome testing and debugging power
  • And most of all...

Unprecedented Robustness

End

Questions?

Borislav Stanimirov / ibob.github.io / @stanimirovb

These slides: ibob.github.io/slides/immutable-obj/
Slides license Creative Commons By 4.0
Creative Commons License