Re: [PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes

From: Johan Herland <johan@herland.net>
Date: Aug 28, 2009, 14:15 UTC
Message-ID: <200908281615.49465.johan@herland.net>
In-Reply-To: <alpine.DEB.1.00.0908281349270.7434@intel-tinevez-2-302>

On Friday 28 August 2009, Johannes Schindelin wrote:

Show 24 quoted lines

> On Fri, 28 Aug 2009, Johan Herland wrote:
> > On Friday 28 August 2009, Johannes Schindelin wrote:
> > > And I can easily imagine a repository that has a daily note
> > > generated by an automatic build, and no other notes.  The
> > > date-based fan-out just wastes our time here, and even hurts
> > > performance.
> >
> > What about a month-based fanout?
>
> Well, I hoped to convince you that the date-based approach is too
> rigid. You basically cannot adapt the optimal data layout to the
> available data.
>
> (I like to think of this issue as related to storing deltas: we let
> Git choose relatively freely what to delta against, and do not force
> a delta against the parent commit like others do; I think it is
> pretty obvious that our approach is more powerful.)
>
> So the simplest (yet powerful-enough) way I could imagine is to teach
> the reading part to accept any fan-out (but that fan-out is really
> only based on the object name, nothing else), and to adjust the
> writing/merging part such that it has a maximum bin size (i.e. it
> starts a new fan-out whenever a tree object contains more than a
> config-specifyable limit).

I agree with your points on flexibility and not nailing down a structure that might prove too rigid in the future.

But it seems the date-based approach might offer wins that an object-name-based approach (flexible or not) simply cannot hope to match...

Also a rigid organization (with unique note locations) makes the implementation simpler and faster: If you allow notes for a given commit at several places in the notes tree (and require the result to be the concatenation of those notes, which seems to be the saner choice), the lookup procedure must keep looking even after it has found the first match. This affects both runtime and memory consumption negatively (more subtrees must be unpacked, etc.)

I guess I'll code up both alternatives so that we can get some actual numbers...

...Johan

-- 
Johan Herland, <johan@herland.net>
www.herland.net