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