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

On Tuesday 08 December 2009, Johan Herland wrote:

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

quoted

Johan Herland [off-list ref] wrote:

quoted

quoted

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.

quoted

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.

Do you have more comments/suggestions on this patch? Or is it ok to include 
in fast-import as-is?


Have fun! :)

...Johan


-- 
Johan Herland, [off-list ref]
www.herland.net