From: Johan Herland <johan@herland•net>
To: "Shawn O. Pearce" <spearce@spearce•org>
Cc: git@vger•kernel.org, gitster@pobox•com
Subject: Re: [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation
Date: Tue, 08 Dec 2009 03:45:37 +0100 [thread overview]
Message-ID: <200912080345.37429.johan@herland.net> (raw)
In-Reply-To: <20091208020134.GC17588@spearce.org>
On Tuesday 08 December 2009, Shawn O. Pearce wrote:
> Johan Herland <johan@herland•net> 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@herland•net>
www.herland.net
next prev parent reply other threads:[~2009-12-08 2:45 UTC|newest]
Thread overview: 28+ messages / expand[flat|nested] mbox.gz Atom feed top
2009-12-07 11:27 [RFC/PATCHv10 00/11] git notes Johan Herland
2009-12-07 11:27 ` [RFC/PATCHv10 01/11] fast-import: Proper notes tree manipulation Johan Herland
2009-12-07 16:41 ` Shawn O. Pearce
2009-12-08 1:44 ` Johan Herland
2009-12-08 2:01 ` Shawn O. Pearce
2009-12-08 2:45 ` Johan Herland [this message]
2009-12-10 9:39 ` Johan Herland
2009-12-10 14:03 ` Shawn O. Pearce
2009-12-10 14:40 ` Johan Herland
2009-12-11 3:00 ` Junio C Hamano
2009-12-07 16:43 ` Shawn O. Pearce
2009-12-08 1:55 ` Johan Herland
2009-12-08 1:59 ` Shawn O. Pearce
2009-12-07 20:42 ` Junio C Hamano
2009-12-08 2:34 ` Johan Herland
2009-12-07 11:27 ` [RFC/PATCHv10 02/11] Rename t9301 to t9350, to make room for more fast-import tests Johan Herland
2009-12-07 11:27 ` [RFC/PATCHv10 03/11] Add more testcases to test fast-import of notes Johan Herland
2009-12-07 11:27 ` [RFC/PATCHv10 04/11] Minor style fixes to notes.c Johan Herland
2009-12-07 11:27 ` [RFC/PATCHv10 05/11] Notes API: get_commit_notes() -> format_note() + remove the commit restriction Johan Herland
2009-12-07 11:27 ` [RFC/PATCHv10 06/11] Notes API: init_notes(): Initialize the notes tree from the given notes ref Johan Herland
2009-12-07 11:27 ` [RFC/PATCHv10 07/11] Notes API: add_note(): Add note objects to the internal notes tree structure Johan Herland
2009-12-07 11:27 ` [RFC/PATCHv10 08/11] Notes API: get_note(): Return the note annotating the given object Johan Herland
2009-12-07 20:52 ` Junio C Hamano
2009-12-08 3:18 ` Johan Herland
2009-12-07 11:27 ` [RFC/PATCHv10 09/11] Notes API: for_each_note(): Traverse the entire notes tree with a callback Johan Herland
2009-12-07 11:27 ` [RFC/PATCHv10 10/11] Notes API: Allow multiple concurrent notes trees with new struct notes_tree Johan Herland
2009-12-07 11:27 ` [RFC/PATCHv10 11/11] Refactor notes concatenation into a flexible interface for combining notes Johan Herland
2009-12-08 9:25 ` [RFC/PATCHv10 00/11] git notes Junio C Hamano
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=200912080345.37429.johan@herland.net \
--to=johan@herland$(echo .)net \
--cc=git@vger$(echo .)kernel.org \
--cc=gitster@pobox$(echo .)com \
--cc=spearce@spearce$(echo .)org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox