From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Tue, 10 Feb 2009 21:10:43 GMT
Subject: Re: RFC: Flat directory for notes, or fan-out? Both!
Message-ID: <alpine.DEB.1.00.0902102210140.10279@pacific.mpi-cbg.de>
In-Reply-To: <7vocxam96s.fsf@gitster.siamese.dyndns.org>

Hi,

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

> "Shawn O. Pearce" <spearce@spearce.org> writes:
> 
> > Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> >> On Tue, 10 Feb 2009, Junio C Hamano wrote:
> >> > 
> >> > 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.
> >
> > See my other email on this thread; we'd probably need to unpack
> > all 256 subtrees *anyway* due to the distribution of SHA-1 names
> > for commits.
> 
> I wonder if we can solve this by introducing a local cache that is a flat
> file that looks like:
> 
>     magic number for /usr/bin/file
>     tree object SHA-1 the file caches
>     Number of entries in this file
>     256 fan-out offsets into this file
>     N entries of <SHA-1, SHA-1>, sorted
>     Checksum of the file itself
> 
> and use it when availble (otherwise optionally create it upon the first
> lookup).  The file can be used by mmaping it and then doing a newton
> raphson or binary search similar to the way patch-ids.c does.

Or we could use an on-disk hashmap.  Oh, wait...

Ciao,
Dscho