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

From: Johan Herland <johan@herland.net>
Date: Dec 8, 2009, 02:45 UTC
Message-ID: <200912080345.37429.johan@herland.net>
In-Reply-To: <20091208020134.GC17588@spearce.org>

On Tuesday 08 December 2009, Shawn O. Pearce wrote:

Show 18 quoted lines

> 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.

Have fun! :)

...Johan

-- 
Johan Herland, <johan@herland.net>
www.herland.net