Re: [PATCH 03/10] builtin/pack-objects.c: learn '--assume-kept-packs-closed'

Taylor Blau [off-list ref] writes:

So, I think that teaching pack-objects a way to understand a caller that
says "include objects from packs X, Y, and Z, but not if they appear in
packs A, B, or C, and also pull in any loose objects" is the best way
forward here.

Are our goals still include that the resulting packfile has good
delta compression and object locality?  Reachability traversal
discovers which commit comes close to which other commits to help
pack-objects to arrange the resulting pack so that objects that
appear close together in history appears close together.  It also
gives each object a pathname hint to help group objects of the same
type (either blobs or trees) with like-paths together for better
deltification.

Without reachability traversal, I would imagine that it would become
quite important to keep the order in which objects appear in the
original pack, and existing delta chain, as much as possible, or
we'd be seeing a horribly inefficient pack like fast-import would
produce.

Thanks.

On Fri, Jan 29, 2021 at 03:03:08PM -0800, Junio C Hamano wrote:

Taylor Blau [off-list ref] writes:

quoted

So, I think that teaching pack-objects a way to understand a caller that
says "include objects from packs X, Y, and Z, but not if they appear in
packs A, B, or C, and also pull in any loose objects" is the best way
forward here.

Are our goals still include that the resulting packfile has good
delta compression and object locality?  Reachability traversal
discovers which commit comes close to which other commits to help
pack-objects to arrange the resulting pack so that objects that
appear close together in history appears close together.  It also
gives each object a pathname hint to help group objects of the same
type (either blobs or trees) with like-paths together for better
deltification.

I think our goals here are somewhere between having fewer packfiles
while also ensuring that the packfiles we had to create don't have
horrible delta compression and locality.

But now that you do mention it, I remember the reachability traversal's
bringing in object names was a reason that we decided to implement this
series using a reachability traversal in the first place.

Without reachability traversal, I would imagine that it would become
quite important to keep the order in which objects appear in the
original pack, and existing delta chain, as much as possible, or
we'd be seeing a horribly inefficient pack like fast-import would
produce.

Yeah; we'd definitely want to feed the objects to pack-objects in the
order that they appear in the original pack. Maybe that's not that bad a
tradeoff to make, though...

Thanks.

Thanks,
Taylor

On Fri, Jan 29, 2021 at 03:03:08PM -0800, Junio C Hamano wrote:

Taylor Blau [off-list ref] writes:

quoted

So, I think that teaching pack-objects a way to understand a caller that
says "include objects from packs X, Y, and Z, but not if they appear in
packs A, B, or C, and also pull in any loose objects" is the best way
forward here.

Are our goals still include that the resulting packfile has good
delta compression and object locality?  Reachability traversal
discovers which commit comes close to which other commits to help
pack-objects to arrange the resulting pack so that objects that
appear close together in history appears close together.  It also
gives each object a pathname hint to help group objects of the same
type (either blobs or trees) with like-paths together for better
deltification.

Without reachability traversal, I would imagine that it would become
quite important to keep the order in which objects appear in the
original pack, and existing delta chain, as much as possible, or
we'd be seeing a horribly inefficient pack like fast-import would
produce.

Thanks, that's another good point we discussed a while ago (off-list),
but hasn't come up in this discussion yet.

Another option here is not to roll up packs at all, but instead to use a
midx to cover them all[1]. That solves the issue where object lookup is
O(nr_packs), and you retain the same locality and delta characteristics.

But I think part of the goal is to actually improve the deltas, in two
ways:

  - we'd hopefully find new delta opportunities between objects in the
    various packs

  - we'll drop some objects that are duplicated in other packs.
    Definitely we have to to avoid duplicates in the roll-up pack, but I
    think we'd want to even for objects that are in the "big" kept pack.
    These are likely bases of deltas in our roll-up pack, since the
    common cause there is --fix-thin adding them to complete the pack.
    But we really prefer to serve fetches using the ones out of the main
    pack, since they may already themselves be deltas (which makes them
    way cheaper; we can send the delta straight off the disk, rather
    than looking for a new possible base).

So I would anticipate the delta-compression phase actually trying to do
some new work. I do worry that the lack of pathname hints may make the
deltas we find much more worse (or cause us to spend excessive CPU
searching for them). It's possible we could do a "best effort" traversal
where we walk new commits to find newly added pathnames, but don't
bother crossing into trees/commits that aren't in the set of objects to
be packed. It's OK to optimize for speed there, because it's just
feeding the delta heuristic, not the set of objects we'd plan to pack.

-Peff

[1] Our end-game plan is actually to _also_ use a midx to cover the
    roll-ups and the "big" pack, since we'd want to generate bitmaps for
    the new objects, too.'

On Fri, Jan 29, 2021 at 06:28:28PM -0500, Taylor Blau wrote:

On Fri, Jan 29, 2021 at 03:03:08PM -0800, Junio C Hamano wrote:

quoted

Are our goals still include that the resulting packfile has good
delta compression and object locality?  Reachability traversal
discovers which commit comes close to which other commits to help
pack-objects to arrange the resulting pack so that objects that
appear close together in history appears close together.  It also
gives each object a pathname hint to help group objects of the same
type (either blobs or trees) with like-paths together for better
deltification.

I think our goals here are somewhere between having fewer packfiles
while also ensuring that the packfiles we had to create don't have
horrible delta compression and locality.

But now that you do mention it, I remember the reachability traversal's
bringing in object names was a reason that we decided to implement this
series using a reachability traversal in the first place.

Peff shared a very clever idea with me today. Like in the naive
approach, we fill the list of "objects to pack" with everything in the
packs that are about to get rolled up, excluding anything that appears
in the large packs.

But we do a reachability traversal whose starting points are all of the
commits in the packs that are about to be rolled up, filling in the
namehash of the objects we encounter along the way.

Like in the original version of this series, we'll stop early once we
encounter an object in any of the frozen packs (which are marked as kept
in core), and so we might not traverse through everything. But that's
completely OK, since we know we have the right list of objects to pack
(at worst, we would having some zero'd namehashes and come up with
slightly worse deltas).

But, I think that this is a nice middle-ground (and it allows us to
reuse lots of work from the original version), so I'm quite happy.

It's in my fork [1] in the tb/geometric-repack.wip branch, but I'll try
and clean those patches up tomorrow and send a v2 to the list.

Thanks,
Taylor

[1]: https://github.com/ttaylorr/git