Weave Insert Time
martinpool at gmail.com
Thu Oct 6 02:42:36 BST 2005
On 06/10/05, Gustavo Niemeyer <gustavo at niemeyer.net> wrote:
> > You can see the resultant graph here:
> > http://bzr.arbash-meinel.com/other/RevisionInsertTime.png
> Nice graph!
> > Basically, it looks like the time to insert one revision is very close
> > to O(N) where N is the number of revisions already in the weave. I think
> > that makes it O(N^2) when you are creating the weave for the first time.
> One thing I'm wondering is: would it be O(N), where N is the number of
> revisions, or O(N), where N is the number of lines in the weave?
> In other words, I'm curious about what would happen with that graph if
> you changed the size of the log messages in the revision, for instance.
It is O(weave_lines), because inserting a new version starts by
finding the location in the weave of the parent version(s), which
requires walk through the entire weave.
More information about the bazaar