Re: [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation

> On Tuesday 08 December 2009, Shawn O. Pearce wrote:
> > Johan Herland <johan@herland.net> wrote:
> > > > If we're here, isn't it likely that *all* notes are in the wrong
> > > > path in the tree, and we need to move them all to a new location?
> > > > If that's true then should we instead just build an entirely new
> > > > tree and swap the root when we are done?
> > >
> > > Hmm. Not always. In your earlier scenario where we add 2,000,000
> > > notes in a single commit, the current code would need to rewrite 255
> > > of them from fanout 0 to fanout 2, and 65,535 of them from fanout 1
> > > to fanout 2. But the vast majority (1,934,465) would not require
> > > rewriting (having been added at the correct fanout initially).
> > > However, if we build a new tree (by which I assume you mean
> > > tree_content_remove() from the old tree and
> > > tree_content_set() to the new tree for every single note (and
> > > non-note)), we end up processing all 2,000,000 entries.
> >
> > Well, by processing here you mean we wind up looking at them, only
> > to determine they are in the correct place already and skipping past.
> 
> No, (as far as I (mis?)understood your idea) by processing here I'm
>  talking about moving all 2,000,000 entries from the old tree to the new
>  tree.
> 
> Here's my understanding of your idea:
> - Create a new, empty tree
> - For each entry in the old/existing tree:
>   - If not a note, move[*] verbatim to new tree
>   - If a correctly placed note, move[*] verbatim to new tree
>   - Else, move[*] note to the _correct_ place in the new tree
> 
> [*]: By "move" I assume you mean tree_content_remove() from the old tree,
> followed by tree_content_set() into the new tree.
> 
> From this understanding, I cannot see how your idea improves on the
> adding-2M-notes scenario.
> 
> > I guess I see your point though.  We're fairly bounded on how many
> > we might need to move, probably only 65,535, and the rest will be
> > at the right position so we're mostly just iterating through to
> > confirm they don't have to be moved.
> 
> Yep.