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

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

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.

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, [off-list ref]
www.herland.net