Mementos That Fill the Memory

A full snapshot on every keystroke keeps two thousand copies of the document.

Each memento holds a copy of the originator's state, so a history of mementos holds as many copies as it has entries. For a small state that costs nothing; for a large document saved on every keystroke it can take more memory than everything else in the program. This card measures three ways of keeping a history, and gives the two fixes.

An editor holds a 50,000-character document and saves a full snapshot before every keystroke. The user types 2,000 characters.

Roughly how much memory does the history hold? Estimate, then look.

import sys
import tracemalloc
from collections import deque

DOCUMENT_LENGTH = 50_000
KEYSTROKES = 2_000


def type_document(keep) -> int:
    tracemalloc.start()
    text = "x" * DOCUMENT_LENGTH
    for i in range(KEYSTROKES):
        keep(text, i)
        text = text + "y"
    current, _ = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    return current


full: list[str] = []
capped: deque[str] = deque(maxlen=100)
changes: list[tuple[int, str]] = []

results = {
    "a full snapshot per keystroke": type_document(lambda text, i: full.append(text)),
    "full snapshots, last 100 only": type_document(lambda text, i: capped.append(text)),
    "only the change per keystroke": type_document(lambda text, i: changes.append((DOCUMENT_LENGTH + i, "y"))),
}

print("Python", sys.version.split()[0])
print(f"{DOCUMENT_LENGTH:,} characters, {KEYSTROKES:,} keystrokes")
for name, used in results.items():
    print(f"  {name:32} {used / 1_000_000:7.1f} MB")

OutputRan with python:3.12-slim (Python 3.12.13)

Python 3.12.13
50,000 characters, 2,000 keystrokes
  a full snapshot per keystroke      102.1 MB
  full snapshots, last 100 only        5.3 MB
  only the change per keystroke        0.2 MB

Measured with `tracemalloc` in this run; other versions and runtimes give different figures.

About 100 MB, for 2,000 copies of a document of about 50 KB. The document itself is a fraction of one megabyte.

The cost grows with the size of the state multiplied by the number of snapshots, and both grow as the user works. The program slows and may run out of memory, long after the code that saves a snapshot was tested on a short document.

Three ways of keeping the history, from the run above
Strategy	Memory measured	What it gives up
A full snapshot per keystroke	About 102 MB	Nothing; every state can be restored
Full snapshots, last 100 only	About 5.3 MB	Undo beyond the last 100 changes
Only the change per keystroke	About 0.2 MB	Restoring is no longer a copy back; each change must be reversed in order

The first fix is to cap the history, which collections.deque(maxlen=100) does by dropping the oldest snapshot when a new one arrives. The second is to store only what changed, which is no longer a pure memento: each entry must be applied in reverse, which is how a command with an undo method works. Many editors combine the two, keeping a full snapshot every so often and the changes between them.

Snapshotting less often helps too: one snapshot per word, or per pause in typing, rather than per keystroke.

← → move through sections and cards