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

From: "Shawn O. Pearce" <[email-masked]>
Date: Mon, 7 Dec 2009 08:41:30 -0800

Johan Herland <[email-masked]> wrote:
> As stated in the cover letter, I simply cannot store note information in
> the tree_entry mode bits. So, I chose this somewhat more simple and crude
> approach, which I still think solves the problems quite nicely.

Oh, duh.  Of course you can't.  You lose the note mode when the
tree is flushed to disk, purged from memory, and reloaded later.
Whoops, sorry I missed that during the last round of review.
 
> +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.

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?

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.

-- 
Shawn.