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

From: Shawn O. Pearce <spearce@spearce.org>
Date: Dec 8, 2009, 02:01 UTC
Message-ID: <20091208020134.GC17588@spearce.org>
In-Reply-To: <200912080244.30390.johan@herland.net>

Johan Herland <johan@herland.net> wrote:

Show 13 quoted lines

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

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.

> I'm not sure I get the details here. How can we avoid doing the 
> _remove()/_set() from/to the old/new tree for every tree_entry? In other 
> words, how do we avoid removing and re-setting the 2,000,000 notes in the 
> above example?

You can't. But I realize now what you are saying... for the vast majority of the notes we only need to validate they are in the correct path.

-- 
Shawn.