1
Commit Performance Notes
2
========================
4
Commit: The Minimum Work Required
5
---------------------------------
7
Here is a description of the minimum work that commit must do. We
8
want to make sure that our design doesn't cost too much more than this
9
minimum. I am trying to do this without making too many assumptions
10
about the underlying storage, but am assuming that the ui and basic
11
architecture (wt, branch, repo) stays about the same.
13
The basic purpose of commit is to:
15
1. create and store a new revision based on the contents of the working tree
16
2. make this the new basis revision for the working tree
18
We can do a selected commit of only some files or subtrees.
20
The best performance we could hope for is:
21
- stat each versioned selected working file once
22
- read from the workingtree and write into the repository any new file texts
23
- in general, do work proportional to the size of the shape (eg
24
inventory) of the old and new selected trees, and to the total size of
29
1.0 - Store new file texts: if a versioned file contains a new text
30
there is no avoiding storing it. To determine which ones have changed
31
we must go over the workingtree and at least stat each file. If the
32
file is modified since it was last hashed, it must be read in.
33
Ideally we would read it only once, and either notice that it has not
34
changed, or store it at that point.
36
On the other hand we want new code to be able to handle files that are
37
larger than will fit in memory. We may then need to read each file up
38
to two times: once to determine if there is a new text and calculate
39
its hash, and again to store it.
41
1.1 - Store a tree-shape description (ie inventory or similar.) This
42
describes the non-file objects, and provides a reference from the
43
Revision to the texts within it.
45
1.2 - Generate and store a new revision object.
47
1.3 - Do delta-compression on the stored objects. (git notably does
48
not do this at commit time, deferring this entirely until later.)
49
This requires finding the appropriate basis for each modified file: in
50
the current scheme we get the file id, last-revision from the
51
dirstate, look into the knit for that text, extract that text in
52
total, generate a delta, then store that into the knit. Most delta
53
operations are O(n**2) to O(n**3) in the size of the modified files.
55
1.4 - Cache annotation information for the changes: at the moment this
56
is done as part of the delta storage. There are some flaws in that
57
approach, such as that it is not updated when ghosts are filled, and
58
the annotation can't be re-run with new diff parameters.
60
2.1 - Make the new revision the basis for the tree, and clear the list
61
of parents. Strictly this is all that's logically necessary, unless
62
the working tree format requires more work.
64
The dirstate format does require more work, because it caches the
65
parent tree data for each file within the working tree data. In
66
practice this means that every commit rewrites the entire dirstate
67
file - we could try to avoid rewriting the whole file but this may be
68
difficult because variable-length data (the last-changed revision id)
69
is inserted into many rows.
71
The current dirstate design then seems to mean that any commit of a
72
single file imposes a cost proportional to the size of the current
73
workingtree. Maybe there are other benefits that outweigh this.
74
Alternatively if it was fast enough for operations to always look at
75
the original storage of the parent trees we could do without the
78
2.2 - Record the observed file hashes into the workingtree control
79
files. For the files that we just committed, we have the information
80
to store a valid hash cache entry: we know their stat information and
81
the sha1 of the file contents. This is not strictly necessary to the
82
speed of commit, but it will be useful later in avoiding reading those
83
files, and the only cost of doing it now is writing it out.
85
In fact there are some user interface niceties that complicate this:
87
3 - Before starting the commit proper, we prompt for a commit message
88
and in that commit message editor we show a list of the files that
89
will be committed: basically the output of bzr status. This is
90
basically the same as the list of changes we detect while storing the
91
commit, but because the user will sometimes change the tree after
92
opening the commit editor and expect the final state to be committed I
93
think we do have to look for changes twice. Since it takes the user a
94
while to enter a message this is not a big problem as long as both the
95
status summary and the commit are individually fast.
97
4 - As the commit proceeds (or after?) we show another status-like
98
summary. Just printing the names of modified files as they're stored
99
would be easy. Recording deleted and renamed files or directories is
100
more work: this can only be done by reference to the primary parent
101
tree and requires it be read in. Worse, reporting renames requires
102
searching by id across the entire parent tree. Possibly full
103
reporting should be a default-off verbose option because it does
104
require more work beyond the commit itself.
106
5 - Bazaar currently allows for missing files to be automatically
107
marked as removed at the time of commit. Leaving aside the ui
108
consequences, this means that we have to update the working inventory
109
to mark these files as removed. Since as discussed above we always
110
have to rewrite the dirstate on commit this is not substantial, though
111
we should make sure we do this in one pass, not two. I have
112
previously proposed to make this behaviour a non-default option.
114
We may need to run hooks or generate signatures during commit, but
115
they don't seem to have substantial performance consequences.
117
If one wanted to optimize solely for the speed of commit I think
118
hash-addressed file-per-text storage like in git (or bzr 0.1) is very
119
good. Remarkably, it does not need to read the inventory for the
120
previous revision. For each versioned file, we just need to get its
121
hash, either by reading the file or validating its stat data. If that
122
hash is not already in the repository, the file is just copied in and
123
compressed. As directories are traversed, they're turned into texts
124
and stored as well, and then finally the revision is too. This does
125
depend on later doing some delta compression of these texts.
127
Variations on this are possible. Rather than writing a single file
128
into the repository for each text, we could fold them into a single
129
collation or pack file. That would create a smaller number of files
130
in the repository, but looking up a single text would require looking
131
into their indexes rather than just asking the filesystem.
133
Rather than using hashes we can use file-id/rev-id pairs as at
134
present, which has several consequences pro and con.
140
At first glance, commit simply stores the changes status reports. In fact,
141
this isn't technically correct: commit considers some files modified that
142
status does not. The notes below were put together by John Arbash Meinel
143
and Aaron Bentley in May 2007 to explain the finer details of commit to
144
Ian Clatworthy. They are recorded here as they are likely to be useful to
145
others new to Bazaar ...
147
1) **Unknown files have a different effect.** With --no-strict (the default)
148
they have no effect and can be completely ignored. With --strict they
149
should cause the commit to abort (so you don't forget to add the two new
150
test files that you just created).
152
2) **Multiple parents.** 'status' always compares 2 trees, typically the
153
last-committed tree and the current working tree. 'commit' will compare
154
more trees if there has been a merge.
156
a) The "last modified" property for files.
157
A file may be marked as changed since the last commit, but that
158
change may have come in from the merge, and the change could have
159
happened several commits back. There are several edge cases to be
160
handled here, like if both branches modified the same file, or if
161
just one branch modified it.
163
b) The trickier case is when a file appears unmodified since last
164
commit, but it was modified versus one of the merged branches. I
165
believe there are a few ways this can happen, like if a merged
166
branch changes a file and then reverts it back (you still update
167
the 'last modified' field).
168
In general, if both sides disagree on the 'last-modified' flag,
169
then you need to generate a new entry pointing 'last-modified' at
170
this revision (because you are resolving the differences between
173
3) **Automatic deletion of 'missing' files.** This is a point that we go
174
back and forth on. I think the basic idea is that 'bzr commit' by
175
default should abort if it finds a 'missing' file (in case that file was
176
renamed rather than deleted), but 'bzr commit --auto' can add unknown
177
files and remove missing files automatically.
179
4) **sha1 for newly added files.** status doesn't really need this: it should
180
only care that the file is not present in base, but is present now. In
181
some ways commit doesn't care either, since it needs to read and sha the
184
5) **Nested trees.** status doesn't recurse into nested trees, but commit does.
185
This is just because not all of the nested-trees work has been merged yet.
187
A tree-reference is considered modified if the subtree has been
188
committed since the last containing-tree commit. But commit needs to
189
recurse into every subtree, to ensure that a commit is done if the
190
subtree has changed since its last commit. _iter_changes only reports
191
on tree-references that are modified, so it can't be used for doing
195
Avoiding Work: Smarter Change Detection
196
---------------------------------------
198
Commit currently walks through every file building an inventory. Here is
199
Aaron's brain dump on a better way ...
201
_iter_changes won't tell us about tree references that haven't changed,
202
even if those subtrees have changed. (Unless we ask for unchanged
203
files, which we don't want to do, of course.)
205
There is an iter_references method, but using it looks just as expensive
208
I did some work on updating commit to use iter_changes, but found for
209
multi-parent trees, I had to fall back to the slow inventory comparison
212
Really, I think we need a call akin to iter_changes that handles
213
multiple parents, and knows to emit entries when InventoryEntry.revision
214
is all that's changed.
217
Avoiding Work: Better Layering
218
------------------------------
220
For each file, commit is currently doing more work than it should. Here is
221
John's take on a better way ...
223
Note that "_iter_changes" *does* have to touch every path on disk, but
224
it just can do it in a more efficient manner. (It doesn't have to create
225
an InventoryEntry for all the ones that haven't changed).
227
I agree with Aaron that we need something a little different than
228
_iter_changes. Both because of handling multiple parents, as well as we
229
don't want it to actually read the files if we have a stat-cache miss.
231
Specifically, the commit code *has* to read the files because it is
232
going to add the text to the repository, and we want it to compute the
233
sha1 at *that* time, so we are guaranteed to have the valid sha (rather
234
than just whatever the last cached one was). So we want the code to
235
return 'None' if it doesn't have an up-to-date sha1, rather than reading
236
the file and computing it, just before it returns it to the parent.
238
The commit code (0.16) should really be restructured. It's layering is
241
Specifically, calling "kind()" requires a stat of the file. But we have
242
to do a stat to get the size/whether the record is up-to-date, etc. So
243
we really need to have a "create_an_up_to_date_inventory()" function.
244
But because we are accessing every object on disk, we want to be working
245
in tuples rather than Inventory objects. And because DirState already
246
has the parent records next to the current working inventory, it can do
247
all the work to do really fast comparison and throw-away of unimportant
250
The way I made "bzr status" fast is by moving the 'ignore this record'
251
ability as deep into the stack as I could get. Status has the property
252
that you don't care about most of the records, just like commit. So the
253
sooner you can stop evaluating the 99% that you don't care about, the
257
Avoiding work: avoiding reading parent data
258
-------------------------------------------
260
We would like to avoid the work of reading any data about the parent
261
revisions. We should at least try to avoid reading anything from the
262
repository; we can also consider whether it is possible or useful to hold
263
less parent information in the working tree.
265
When a commit of selected files is requested, the committed snapshot is a
266
composite of some directories from the parent revision and some from the
267
working tree. In this case it is logically necessary to have the parent
268
inventory information.
270
If file last-change information or per-file graph information is stored
271
then it must be available from the parent trees.
273
If the Branch's storage method does delta compression at commit time it
274
may need to retrieve file or inventory texts from the repository.
276
It is desirable to avoid roundtrips to the Repository during commit,
277
particularly because it may be remote. If the WorkingTree can determine
278
by itself that a text was in the parent and therefore should be in the
279
Repository that avoids one roundtrip per file.
281
There is a possibility here that the parent revision is not stored, or not
282
correctly stored, in the repository the tree is being committed into, and
283
so the committed tree would not be reconstructable. We could check that
284
the parent revision is present in the inventory and rely on the invariant
285
that if a revision is present, everything to reconstruct it will be
288
Complications of commit
289
-----------------------
291
Bazaar (as of 0.17) does not support selective-file commit of a merge;
292
this could be done if we decide how it should be recorded - is this to be
293
stored as an overall merge revision; as a preliminary non-merge revisions;
294
or will the per-file graph diverge from the revision graph.
296
There are several checks that may cause the commit to be refused, which
297
may be activated or deactivated by options.
299
* presence of conflicts in the tree
301
* presence of unknown files
303
* the working tree basis is up to date with the branch tip
305
* the local branch is up to date with the master branch, if there
306
is one and --local is not specified
308
* an empty commit message is given,
310
* a hook flags an error
312
* a "pointless" commit, with no inventory changes
314
Most of these require walking the tree and can be easily done while
315
recording the tree shape. This does require that it be possible to abort
316
the commit after the tree changes have been recorded. It could be ok to
317
either leave the unreachable partly-committed records in the repository,
322
* when automatically adding new files or deleting missing files during
323
commit, they must be noted during commit and written into the working
326
* refuse "pointless" commits with no file changes - should be easy by
327
just refusing to do the final step of storing a new overall inventory
330
* heuristic detection of renames between add and delete (out of scope for
333
* pushing changes to a master branch if any
335
* running hooks, pre and post commit
337
* prompting for a commit message if necessary, including a list of the
338
changes that have already been observed
340
* if there are tree references and recursing into them is enabled, then
343
Updates that need to be made in the working tree, either on conclusion
344
of commit or during the scan, include
346
* Changes made to the tree shape, including automatic adds, renames or
349
* For trees (eg dirstate) that cache parent inventories, the old parent
350
information must be removed and the new one inserted
352
* The tree hashcache information should be updated to reflect the stat
353
value at which the file was the same as the committed version, and the
354
content hash it was observed to have. This needs to be done carefully to
355
prevent inconsistencies if the file is modified during or shortly after
356
the commit. Perhaps it would work to read the mtime of the file before we
357
read its text to commit.
363
The commit api is invoked by the command interface, and copies information
364
from the tree into the branch and its repository, possibly updating the
365
WorkingTree afterwards.
367
The command interface passes:
369
* a commit message (from an option, if any),
370
* or an indication that it should be read interactively from the ui object;
371
* a list of files to commit
372
* an option for a dry-run commit
373
* verbose option, or callback to indicate
374
* timestamp, timezone, committer, chosen revision id
376
* option for local-only commit on a bound branch
377
* option for strict commits (fail if there are unknown or missing files)
378
* option to allow "pointless" commits (with no tree changes)
380
(This is rather a lot of options to pass individually and just for code tidyness maybe some of them should be combine into objects.)
382
>>> Branch.commit(from_tree, message, files_to_commit, ...)
384
There will be different implementations of this for different Branch
385
classes, whether for foreign branches or Bazaar repositories using
386
different storage methods.
388
Most of the commit should occur during a single lockstep iteration across
389
the workingtree and parent trees. The WorkingTree interface needs to
390
provide methods that give commit all it needs. Some of these methods
391
(such as answering the file's last change revision) may be deprecated in
392
newer working trees and there we have a choice of either calculating the
393
value from the data that is present, or refusing to support commit to
396
For a dirstate tree the iteration of changes from the parent can easily be
397
done within its own iter_changes.
399
Dirstate inventories may be most easily updated in a single operation at
400
the end; however it may be best to accumulate data as we proceed through
401
the tree rather than revisiting it at the end.
403
Showing a progress bar for commit may not be necessary if we report files
404
as they are committed. Alternatively we could transiently show a progress
405
bar for each directory that's scanned, even if no changes are observed.
407
This needs to collect a list of added/changed/removed files, each of which
408
must have its text stored (if any) and containing directory updated. This
409
can be done by calling Tree._iter_changes on the source tree, asking for
412
In the 0.17 model the commit operation needs to know the per-file parents
413
and per-file last-changed revision.
415
(In this and other operations we must avoid having multiple layers walk
416
over the tree separately. For example, it is no good to have the Command
417
layer walk the tree to generate a list of all file ids to commit, because
418
the tree will also be walked later. The layers that do need to operate
419
per-file should probably be bound together in a per-dirblock iterator,
420
rather than each iterating independently.)
422
Branch->Tree interface
423
----------------------
425
The Branch commit code needs to ask the Tree what should be committed, in
426
terms of changes from the parent revisions. If the Tree holds all the
427
necessary parent tree information itself it can do it single handed;
428
otherwise it may need to ask the Repository for parent information.
430
This should be a streaming interface, probably like iter_changes returning
431
information per directory block.
433
The interface should not return a block for directories that are
434
recursively unchanged.
436
The tree's idea of what is possibly changed may be more conservative than that of the branch. For example the tree may report on merges of files where the text is identical to the parents: this must be recorded for Bazaar branches that record per-file ancestry but is not necessary for all branches.
437
If the tree is responsible for determining when directories have been recursively modified then it will report on all the parents of such files.
438
There are several implementation options:
440
1. Return all files and directories the branch might want to commit, even if the branch ends up taking no action on them.
441
2. When starting the iteration, the branch can specify what type of change is considered interesting.
443
Since these types of changes are probably (??) rare compared to files that are either completely unmodified or substantially modified, the first may be the best and simplest option.
446
Open question: per-file graphs
447
------------------------------
449
**XXX:** If we want to retain explicitly stored per-file graphs, it would
450
seem that we do need to record per-file parents. We have not yet finally
451
settled that we do want to remove them or treat them as a cache. This api
452
stack is still ok whether we do or not, but the internals of it may
added
removed
doc/developers/commit.txt
