Bundle Creation¶
- Find common ancestor [O(a)] O(b)
- Emit bundle [O(a)] O(b) O(h)
Per revision
- emit metadata O(1)
- emit changes for files
- find changed files [O(c)] O(f)
- emit file metadata O(d)
- emit diff [O(e * e) * O(f) + O(h)] O(i)
- base64 encode O(g)
- emit overal diff (or maybe do interdiff) O(e * e) * O(f)
a: | nodes in revision graph |
---|---|
b: | number of descendants of common ancestor |
c: | number of files in the tree |
d: | length of metadata |
e: | number of lines |
f: | number of modified files |
g: | length of diff |
h: | nodes in knit graph of modified files |
i: | length of stored diff |
Needs¶
- Improved common ancestor algorithm
- Access to partial revision graph proportional to relevant revisions
- Access to changed files proportional to number of change files and intervening revisions
- Use knit deltas without recomputing
- Access to knit deltas in O(1) time
- Access to snapshots in O(1) amortized time
- All snapshots must have knit deltas