Description

Replace the naïve Map implementation of NodeMap with a version optimized for structural sharing when the Map is over a size threshold (>= 1000 entries currently).

GenMap has two "modes" based on the _mutable flag:

• !mutable - The nursery is considered readonly, on first mutation it will either do a Collection (create a new _old from the previous _old and _nursery) or make a Shallow Copy of _nursery before changing to mutable mode. This is the default state.
• mutable - The nursery is considered writable, it has been modified since construction or clone.

Each GenMap contains two maps (both created on demand):

• _old - A read-only snapshot of some previous state (equivalent to an old Map based NodeMap), generated by the last collection
• _nursery - The working set of nodes (or tombstones) that have changed from _old. Tombstones are used to mark deletions of nodes that are still present in _old but will be removed at the next collection. Whether or not this is safe to mutate directly is based on the _mutable flag.

A GenMap can be cloned from another GenMap. This will mark the previous GenMap as not mutable (so its nursery must be copied before use) and reference its _old and _nursery directly.

  clone(): GenMap<K, V> {
    this._mutable = false;
    const clone = new GenMap<K, V>();
    // clone is already _mutable = false
    clone._old = this._old;
    clone._nursery = this._nursery;
    clone._size = this._size;
    return clone;
  }

Terms

Collection is when the next _old is generated. Pseudocode:

this._old = new Map(this.entries());
this._nursery = new Map();
this._mutable = true;

Shallow Copy is when a copy or the nursery is made (_old is not changed). Pseudocode:

this._nursery = new Map(this._nursery);
this._mutable = true;

Notes

This is an optimization because the cost of copying a Map is linear in both memory and time. In large documents, most nodes are not updated on each update cycle, so we are only paying the cost to copy the smaller nursery. Occasionally we pay the full cost to do a collection, but this is amortized since we don't do it often.

Related:

• Feature: Add Maximum Change Limit and Optimization for Lexical History Plugin #6728
• https://emergence-engineering.com/blog/lexical-prosemirror-comparison
• discord discussion

Test plan

All existing suites pass

TODO

• Benchmarks
• More specific tests