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