|
2495.2.1
by Aaron Bentley
Add bundle creation and merge scaling analysis |
1 |
Bundle Creation |
2 |
=============== |
|
3 |
1. Find common ancestor [O(a)] **O(b)** |
|
4 |
2. Emit bundle [O(a)] **O(b) O(h)** |
|
5 |
||
6 |
Per revision |
|
7 |
||
8 |
1. emit metadata O(1) |
|
9 |
2. emit changes for files |
|
10 |
||
11 |
1. find changed files [O(c)] **O(f)** |
|
12 |
2. emit file metadata O(d) |
|
13 |
3. emit diff [O(e * e) * O(f) + O(h)] **O(i)** |
|
14 |
4. base64 encode O(g) |
|
15 |
||
16 |
3. **emit overal diff (or maybe do interdiff) O(e * e) * O(f)** |
|
17 |
||
18 |
:a: nodes in revision graph |
|
19 |
:b: number of descendants of common ancestor |
|
20 |
:c: number of files in the tree |
|
21 |
:d: length of metadata |
|
22 |
:e: number of lines |
|
23 |
:f: number of modified files |
|
24 |
:g: length of diff |
|
25 |
:h: nodes in knit graph of modified files |
|
26 |
:i: length of stored diff |
|
27 |
||
28 |
Needs |
|
|
2506.1.1
by Alexander Belchenko
sanitize developers docs |
29 |
----- |
|
2495.2.1
by Aaron Bentley
Add bundle creation and merge scaling analysis |
30 |
- Improved common ancestor algorithm |
31 |
- Access to partial revision graph proportional to relevant revisions |
|
32 |
- Access to changed files proportional to number of change files and |
|
33 |
intervening revisions |
|
34 |
- Use knit deltas without recomputing |
|
35 |
- Access to knit deltas in O(1) time |
|
36 |
- Access to snapshots in O(1) amortized time |
|
37 |
- All snapshots must have knit deltas |