Weave Insert Time

[Martin Pool]

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.

--
Martin