Re: Calculating tree nodes

From: Shawn O. Pearce <spearce@spearce.org>
Date: Sep 6, 2007, 03:20 UTC
Message-ID: <20070906032026.GO18160@spearce.org>
In-Reply-To: <7vbqcinxdb.fsf@gitster.siamese.dyndns.org>

Junio C Hamano <gitster@pobox.com> wrote:

Show 6 quoted lines

> "Shawn O. Pearce" <spearce@spearce.org> writes:
> 
> > There's nothing stopping us from creating additional indexes.
> > ...
> > But we can also store the notes alongside the commits in the
> > packfile, so that if the data for the commit has been paged in

...

Show 5 quoted lines

> 
> I would agree with your main thrust "nobody prevents you from
> building additional index", but on a tangent, I am skeptical
> about adding too much to pack v4.  Especially "clustering the
> notes" part.

...

Show 5 quoted lines

> Now, hopefully many operations do not need notes either,
> although notes themselves can store _anything_ so each of them
> could be large and/or each commit could have large number of
> them.  I suspect clustering notes along with the commit they
> annotate would break the locality of access for common case.

I'm inclined to agree.

Its something I've thought about doing. I haven't even prototyped code for it. Let alone shown numbers that say one way or the other.

One of the notes proposals was talking about having lots of different classes of notes. E.g. a "Signed-off-by" class and a "build and test log results" class.

The former would generally be very small and may even want to be shown most of the time the commit body is displayed (e.g. in gitk, git-log). These would be good candidates to cluster alongside the commit. Indeed they are clustered there today, just hung inside of the commit object itself. Nobody is bitching about the hit they cause on the common case of `pack-objects`. :)

The latter (build and test log) would generally be very large. We would *not* want to cluster them. But we might want to store next to the commit a very small pointer to the note itself. Such as the note's SHA-1. Or its offset within the packfile's index. This would make locating those notes very cheap, while not having a huge impact on the common case of commit traversal.

Likewise we might want to pack a tag's SHA-1 alongside of the commit it points at, as parsing the commit would immediately give us all annotated tags that refer to that commit. Tags are (usually) few and far between. But tools like git-describe are commonly used and would benefit from not needing to build the commit->tag hashtable. OK, well, git-describe cheats and uses the struct object hashtable, but whatever.

You get my point. I think. And I got yours about not making the common case worse than it already is today.

-- 
Shawn.