Re: [PATCH v4 8/8] builtin/repack.c: add '--geometric' option

> Taylor Blau <me@ttaylorr.com> writes:
>
> > Concretely, say that a repository has 'n' packfiles, labeled P1, P2,
> > ..., up to Pn. Each packfile has an object count equal to 'objects(Pn)'.
> > With a geometric factor of 'r', it should be that:
> >
> >   objects(Pi) > r*objects(P(i-1))
> >
> > for all i in [1, n], where the packs are sorted by
> >
> >   objects(P1) <= objects(P2) <= ... <= objects(Pn).
> >
> > Since finding a true optimal repacking is NP-hard, we approximate it
> > along two directions:
> >
> >   1. We assume that there is a cutoff of packs _before starting the
> >      repack_ where everything to the right of that cut-off already forms
> >      a geometric progression (or no cutoff exists and everything must be
> >      repacked).
>
> When you order existing packs like how you explained the next
> "direction" below, do we assume loose ones would sit before
> (i.e. "newer and smaller" than) all of the packs?

> >   2. We assume that everything smaller than the cutoff count must be
> >      repacked. This forms our base assumption, but it can also cause
> >      even the "heavy" packs to get repacked, for e.g., if we have 6
> >      packs containing the following number of objects:
> >
> >        1, 1, 1, 2, 4, 32
> >
> >      then we would place the cutoff between '1, 1' and '1, 2, 4, 32',
> >      rolling up the first two packs into a pack with 2 objects. That
> >      breaks our progression and leaves us:
> >
> >        2, 1, 2, 4, 32
> >          ^
> >
> >      (where the '^' indicates the position of our split). To restore a
> >      progression, we move the split forward (towards larger packs)
> >      joining each pack into our new pack until a geometric progression
> >      is restored. Here, that looks like:
> >
> >        2, 1, 2, 4, 32  ~>  3, 2, 4, 32  ~>  5, 4, 32  ~> ... ~> 9, 32
> >          ^                   ^                ^                   ^
>
> This explanation is very intuitive and easy to understand (I assume
> we aren't actually repacking 1+1 into 2 and then 2+1 into 3 and then
> choosing to repack 3+2 to create 5, but we scan before doing any
> repacking and decide to repack 2+1+2+4 into a single 9).

> > +static void split_pack_geometry(struct pack_geometry *geometry, int factor)
> > +{
> > +	uint32_t i;
> > +	uint32_t split;
> > +	off_t total_size = 0;
> > +
> > +	if (geometry->pack_nr <= 1) {
> > +		geometry->split = geometry->pack_nr;
> > +		return;
> > +	}
>
> When there is a single pack (or no pack), we place the split to 1
> (let's keep reading with the need to find out what split means in
> mind; it is not yet clear if it points at the pack that will be part
> of the kept set, or at the pack that is the last one among the
> repacked set, at this point in the code).

> > +	split = geometry->pack_nr - 1;
> > +
> > +	/*
> > +	 * First, count the number of packs (in descending order of size) which
> > +	 * already form a geometric progression.
> > +	 */
> > +	for (i = geometry->pack_nr - 1; i > 0; i--) {
> > +		struct packed_git *ours = geometry->pack[i];
> > +		struct packed_git *prev = geometry->pack[i - 1];
> > +		if (geometry_pack_weight(ours) >= factor * geometry_pack_weight(prev))
> > +			split--;
> > +		else
> > +			break;
> > +	}
>
> Instead of rolling up from smaller ones like explained in the log
> message, we scan from the larger end and see where the existing
> progression is broken.  When the loop breaks in the middle, the pack
> at position 'i-1' (prev) is too big.
>
> Why do we need to initialize 'split' before the loop and decrement
> it?  Wouldn't it be equivalent to assign 'i' after the loop breaks
> to 'split'?

> In any case, after the loop breaks, the packs starting at position
> 'i+1' (one after ours when the loop broke) thru to the end of the
> geometry->pack[] array are in good progression.  We have 'i' in
> 'split' at this point, so ...
>
> > +	if (split) {
> > +		/*
> > +		 * Move the split one to the right, since the top element in the
> > +		 * last-compared pair can't be in the progression. Only do this
> > +		 * when we split in the middle of the array (otherwise if we got
> > +		 * to the end, then the split is in the right place).
> > +		 */
> > +		split++;
> > +	}
>
> ... we increment it.  It means geometry->pack[split] is small enough
> relative to geometry->pack[split+1] and so on thru to the end of the
> array.
>
> What if split==0 when we exited the loop?  That would mean that the
> everything in the array was in good progression, which is in line
> with the "in the middle" case.  Either way, the pack at 'split' and
> later are in good progression.

> > @@ -396,9 +525,19 @@ int cmd_repack(int argc, const char **argv, const char *prefix)
> >  		strvec_pushf(&cmd.args, "--keep-pack=%s",
> >  			     keep_pack_list.items[i].string);
> >  	strvec_push(&cmd.args, "--non-empty");
> > -	strvec_push(&cmd.args, "--all");
> > -	strvec_push(&cmd.args, "--reflog");
> > -	strvec_push(&cmd.args, "--indexed-objects");
> > +	if (!geometry) {
> > +		/*
> > +		 * 'git pack-objects' will up all objects loose or packed
>
> "git pack-objects --stdin-packs" will?
> What verb is missing in "will VERB up all objects"?

> > +		 * (either rolling them up or leaving them alone), so don't pass
> > +		 * these options.
> > +		 *
> > +		 * The implementation of 'git pack-objects --stdin-packs'
> > +		 * makes them redundant (and the two are incompatible).
>
> I am not sure if that is true.
>
> More importantly, if you read this comment after you are done with
> the series and no longer feel that geometric repacking is the most
> important thing in the world, you'd realize that an important piece
> of information is missing to help readers.  It talks about what
> "geometric" code does (i.e. uses --stdin-packs hence no need to pass
> these options) in a block that is for !geometric.
>
> 	We need to grab all reachable objects, including those that
> 	are reachable from reflogs and the index.
>
> 	When repacking into a geometric progression of packs,
> 	however, we ask 'git pack-objects --stdin-packs', and it is
> 	not about packing objects based on reachability but about
> 	repacking all the objects in specified packs and loose ones
> 	(indeed, --stdin-packs is incompatible with these options).
>
> or something?  I suspect that --stdin-packs does not make --all and
> others "redundant".  The operation is about creating a new pack out
> of the objects contained in these packs, regardless of the objects'
> reachability from the usual "refs, index and reflogs" anchor points,
> no?

> > @@ -507,6 +666,25 @@ int cmd_repack(int argc, const char **argv, const char *prefix)
> >  			if (!string_list_has_string(&names, sha1))
> >  				remove_redundant_pack(packdir, item->string);
> >  		}
> > +
> > +		if (geometry) {
> > +			struct strbuf buf = STRBUF_INIT;
> > +
> > +			uint32_t i;
> > +			for (i = 0; i < geometry->split; i++) {
> > +				struct packed_git *p = geometry->pack[i];
> > +				if (string_list_has_string(&names,
> > +							   hash_to_hex(p->hash)))
> > +					continue;
> > +
> > +				strbuf_reset(&buf);
> > +				strbuf_addstr(&buf, pack_basename(p));
> > +				strbuf_strip_suffix(&buf, ".pack");
> > +
> > +				remove_redundant_pack(packdir, buf.buf);
> > +			}
> > +			strbuf_release(&buf);
> > +		}
>
> Before this new code, we seem to remove all pre-existing packfiles
> that are not in the output from the pack-objects already.  The only
> reason that code does not harm the geometry case is we assume
> get_non_kept_pack_filenames() call is never made while doing
> geometric repack (iow, ALL_INTO_ONE is not set) and the list of
> pre-existing packfiles &existing_packs is empty.  Am I reading the
> code correctly?
>
>  - It is a bit unnerving to learn (and it will be a maintenance
>    burden in the future) that a variable whose name is
>    existing_packs does not necessarily have a list of existing packs
>    depending on the mode we are operating in.
>
>  - The guard to make geometric incompatible with ALL_INTO_ONE does
>    not mention ALL_INTO_ONE, even though that bit is what would
>    corrupt the resulting repository if overlooked.  We should
>    probably need s/pack_everything/& \& ALL_INTO_ONE/ in the hunk
>     below.