Interleaved Deltas
The article discusses the concept of weaves, a data structure used for version control systems. It highlights the simplicity and sophistication of Git while contrasting it with the more complex interleaved deltas used in earlier systems like SCCS. The author shares insights on the algorithms behind weaves and their role in managing file revisions.
- ▪Weaves are sequences of instructions for reconstructing file revisions.
- ▪The Source Code Control System (SCCS) utilized interleaved deltas to manage revisions one file at a time.
- ▪Weave blocks can overlap, allowing for complex relationships between different versions.
Opening excerpt (first ~120 words) tap to expand
Interleaved deltas✑2026-05-22dsa Weave structureActive revision setReconstructing revisionsComputing deltasExtending weavesReconstructing deltasConclusionExercises A weave has a reputation of one of the most reinvented data structures in history.Victor Grishchenko, Mikhail Patrakeev, Chronofold: a data structure for versioned text Progress is often viewed as a transition from simple to complex. Although individual systems do become more complex over time, long-term progress happens when new ideas and advances in hardware make simple designs feasible. Think of the simplest version control system you can imagine. It probably stores project snapshots in a backup directory. Maybe it compresses files for efficiency. Add hashing for content addressing, and the sketch starts to resemble Git.
…
Excerpt limited to ~120 words for fair-use compliance. The full article is at Mmapped.
Discussion
0 commentsMore from Mmapped
