1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
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)
3. **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
|