On Tuesday 08 December 2009, Johan Herland wrote: > On Tuesday 08 December 2009, Shawn O. Pearce wrote: > > Johan Herland <johan@xxxxxxxxxxx> wrote: > > > > 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. 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, <johan@xxxxxxxxxxx> www.herland.net -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html