Bundle Creation

  1. Find common ancestor [O(a)] O(b)

  2. Emit bundle [O(a)] O(b) O(h)

Per revision

  1. emit metadata O(1)

  2. emit changes for files

  1. find changed files [O(c)] O(f)

  2. emit file metadata O(d)

  3. emit diff [O(e * e) * O(f) + O(h)] O(i)

  4. base64 encode O(g)

  1. 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