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

From: Johan Herland <johan@herland.net>
Date: Dec 8, 2009, 01:44 UTC
Message-ID: <200912080244.30390.johan@herland.net>
In-Reply-To: <20091207164130.GD17173@spearce.org>

On Monday 07 December 2009, Shawn O. Pearce wrote:

Show 14 quoted lines

> Johan Herland <johan@herland.net> wrote:
> > +static uintmax_t do_change_note_fanout(
> > +		struct tree_entry *orig_root, struct tree_entry *root,
> > +		char *hex_sha1, unsigned int hex_sha1_len,
> > +		char *fullpath, unsigned int fullpath_len,
> > +		unsigned char fanout)
> 
> I think this function winds up processing all notes twice.  Yuck.
> 
> tree_content_set() adds a new tree entry to the end of the current
> tree.  So when converting "1a9029b006484e8b9aca06ff261beb2324bb9916"
> into "1a" (to go from fanout 0 to fanout 1) we'll place 1a at the
> end of orig_root, and this function will walk 1a/ recursively,
> examining 1a9029b006484e8b9aca06ff261beb2324bb9916 all over again.

Yep, you're right. Still, we only do the tree_content_remove()/set() once per note, so although performance is probably not abysmal, we are still clearly suboptimal.

Also, keep in mind that change_note_fanout() is only called when the number of notes crosses a power of 256. Thus for typical notes trees (which are assumed to mostly accumulate notes over their lifetime), change_note_fanout() will be called zero, one or two times (depending on the final number of notes).

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

Show 7 quoted lines

> As we empty out a tree the object will be recycled into a pool of
> trees which can be reused at a later point.  It might actually make
> sense to build the new tree under a different root.  We won't scan
> entries we've moved, and the memory difference should be fairly
> small as tree_content_remove() will make a subtree available for
> reuse as soon as its empty.  So we're only dealing with a handful
> of additional tree objects as we do the conversion.

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?

Thanks for the review!

...Johan

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