Re: Pack v4 again..

From: Junio C Hamano <gitster@pobox.com>
Date: Feb 16, 2015, 07:12 UTC
Message-ID: <xmqqlhjy72jr.fsf@gitster.dls.corp.google.com>
In-Reply-To: <20150216064537.GF32381@peff.net>

Jeff King <peff@peff.net> writes:

Show 5 quoted lines

>   2. Calculating reachability for packing[1] spends a lot of time in
>      lookup_object, as we have to go through each tree saying "have we
>      seen object 1234abcd yet?". If we could instead just view the
>      differences, we would not have to make those hash lookups for
>      entries whose objects we know we have seen.

Hmm, that is an interesting idea.

Show 5 quoted lines

> So in short, we may end up anywhere within a tree object and need to
> walk backwards to the start of the entry. But we cannot walk backwards
> looking for a NUL, because it may also be part of a sha1. You can only
> reliably parse a git tree by starting at the beginning of the stream and
> going forwards[3].

That in general is true for non deltified tree object (you cannot take advantage of the fact that entries are sorted by pathname to bisect to directly jump to an entry).

> If we knew that our deltas were always produced on entry-boundaries (a
> "character" in your description above), this would be much simpler.

;-)

Show 5 quoted lines

> [2] One option, of course, is to generate byte-wise deltas, but with a
>     promise to always align them on entry boundaries. I'm tempted by
>     this, because the result would be readable by existing packv2
>     readers. We'd have to set a flag somewhere that indicates the pack
>     was written with this property, though.

Yes, that may work.