/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to doc/developers/bundle-creation.txt

  • Committer: John Arbash Meinel
  • Date: 2009-06-02 21:11:18 UTC
  • mto: This revision was merged to the branch mainline in revision 4412.
  • Revision ID: john@arbash-meinel.com-20090602211118-fjsx4dxokahrqkrr
Change groupcompress.DeltaIndex to be lazy about indexing the first source.

This changes the performance characteristics of 'commit', especially of large files.
The main benefit is that during commit, we won't be doing any deltas as we add
all new content to a new group anyway.
Thus we know that we won't ever use the delta index we were creating, so
we can save both time and memory by never creating the index until it is
needed.

Show diffs side-by-side

added added

removed removed

Lines of Context:
doc/developers/bundle-creation.txt
 
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
 
29
-----
 
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