Re: RFC: Flat directory for notes, or fan-out? Both!

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Feb 10, 2009, 16:48 UTC
Message-ID: <alpine.DEB.1.00.0902101743180.10279@pacific.mpi-cbg.de>
In-Reply-To: <7vprhqnv0c.fsf@gitster.siamese.dyndns.org>

Hi,

On Tue, 10 Feb 2009, Junio C Hamano wrote:

Show 24 quoted lines

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> >> OK. I think if you are seeing performance benefits from a 2-character
> >> fanout, then we should standardize on that (do you have new performance
> >> numbers somewhere?).
> >
> > The thing is: Shawn is correct when he says that a tree object to hold the 
> > notes of all commits (which is not an unlikely scenario if you are 
> > thinking about corporate processes) would be huge.
> >
> >> The notes implementation is now in master. If it's about to change in an 
> >> incompatible way, how do you want to handle it? I'm wary of a quick 
> >> patch to change the format this late in the release cycle. We could hold 
> >> it back from 1.6.2. Alternatively, we could let it release with a "this 
> >> is probably going to change" warning.
> >> 
> >> I think I favor holding it back, but I am not picky.
> >
> > Yes, I am also in favor of holding it back.
> 
> I could do a revert on 'master' if it is really needed, but I found that
> the above reasoning is a bit troublesome.  The thing is, if a tree to hold
> the notes would be huge to be unmanageable, then it would still be huge to
> be unmanageable if you split it into 256 pieces.

The thing is, a tree object of 17 megabyte is unmanagably large if you have to read it whenever you access even a single node. Having 256 trees instead, each of which is about 68 kilobyte is much nicer.

> I'd rather prefer to see us first try to find a way to optimze the tree 
> parser.  Maybe packv4 or Linus's binary search (which IIRC you declared 
> would not work --- I recall I once thought about it myself but I do not 
> recall what my conclusions were) play a role in it.

I declared it did not work, and showed an example here:

	http://article.gmane.org/gmane.comp.version-control.git/103297

Now, this example is so concocted that it is not even funny. For example, it falls flat down for notes, as the names never contain spaces there.

I guess that we could detect possible false positives such as my example, by searching for NULs and spaces in the vicinity, and just search on if there is a salmon of a doubt left.

But the worst part about it: we'd still have to unpack the whole tree object to start bisecting (as described in said mail).

Ciao, Dscho