Re: A look at some alternative PACK file encodings

From: Nicolas Pitre <nico@cam.org>
Date: Sep 7, 2006, 02:30 UTC
Message-ID: <Pine.LNX.4.64.0609062221490.18635@xanadu.home>
In-Reply-To: <9e4733910609061759m2aae9e31ja146e309dc449628@mail.gmail.com>

On Wed, 6 Sep 2006, Jon Smirl wrote:

Show 17 quoted lines

> On 9/6/06, Nicolas Pitre <nico@cam.org> wrote:
> > On Wed, 6 Sep 2006, Jon Smirl wrote:
> >
> > > Shawn is doing some prototype work on true dictionary based
> > > compression. I don't know how far along he is but it has potential for
> > > taking 30% off the Mozilla pack.
> >
> > BTW I'm half-way done with support for deltas which base object is
> > referenced with an offset in the pack instead of a hash.  It is quite
> > messy though since it touches pretty core code all over the place when
> > it comes to fetching objects out of a pack.
> 
> Would it help to change all of the references in the pack from sha1 to
> encoded relative offsets? Then collect all of the object fetch code
> into a single subroutine which would change it algorithm depending on
> which type of pack it is operating on. Now the pack wouldn't mix
> reference types, they would all be encoded relative or sha1.

No. The problem is more about sha1_file.c using a mix of sha1 refs and/or pack,offset tuples to reference deltas. I converted most of them to pack,offset tuples. This also has a mnice side effect of having less stack usage when recursing down a delta chain.

When a delta with sha1 reference is encountered the code turns that reference into the appropriate offset with a binary search in the pack index. When a delta with offset reference is encountered then no search in the index is needed.

This is not really complicated but only spread all over so that the diffstat is a bit scary.

Nicolas