patch, 3 partspack-objects: simplify add_objects_in_unpacked_packs()

This short series is extracted from mine and Peff's work on cruft packs. These three patches focus on cleaning up add_objects_in_unpacked_packs(), which is used to implement `git repack -k`.

The pay-off for this clean-up is significant, though: we net -50 lines of code, and the result is much more readable, at least in my opinion.

The changes are described in detail in the patch messages, but essentially we are replacing a loop over get_all_packs() with for_each_packed_object() after adding a couple of new flags necessary to make the switch. And once we are done with that, the third patch removes a bit from the object flag allocation table.

Thanks in advance for your review.

Taylor Blau (3):
  object-store.h: teach for_each_packed_object to ignore kept packs
  builtin/pack-objects.c: simplify add_objects_in_unpacked_packs()
  builtin/pack-objects.c: remove duplicate hash lookup

 builtin/pack-objects.c | 85 ++++++------------------------------------
 object-store.h         |  6 +++
 object.h               |  1 -
 packfile.c             |  6 +++
 4 files changed, 24 insertions(+), 74 deletions(-)

The next patch will reimplement a function that wants to iterate over packed objects while ignoring packs which are marked as kept (either in-core or on-disk).

Teach for_each_packed_object() to ignore all objects from those packs by adding a new flag for each of the "kept" states that a pack can be in.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 object-store.h | 6 ++++++
 packfile.c     | 6 ++++++
 2 files changed, 12 insertions(+)

This function is used to implement `pack-objects`'s `--keep-unreachable` option, but can be simplified in a couple of ways:

  - add_objects_in_unpacked_packs() iterates over all packs (and then
    all packed objects) itself, but could use for_each_packed_object()
    instead since the missing flags necessary were added in the previous
    commit

  - objects are added to an in_pack array which store (off_t, object)
    tuples, and then sorted in offset order when we could iterate
    objects in offset order.

    There is a slight behavior change here: before we would have added
    objects in sorted offset order among _all_ packs. Handing objects to
    create_object_entry() in pack order for each pack (instead of
    feeding objects from all packs simultaneously their offset relative
    to different packs) is much more reasonable, if different than how
    the code currently works.

  - objects in a single pack are iterated in index order and searched
    for in order to discover their offsets, which is much less efficient
    than using the on-disk reverse index

Simplify the function by addressing each of the above and moving the core of the loop into a callback function that we then pass to for_each_packed_object() instead of open-coding the latter function ourselves.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 builtin/pack-objects.c | 84 ++++++++----------------------------------
 1 file changed, 16 insertions(+), 68 deletions(-)

On Sun, Aug 29, 2021 at 10:48:54PM -0400, Taylor Blau wrote:

This is not new in your patch series, but while merging this with another topic I had, I noticed another opportunity for optimization here. We already know the pack/pos in which we found the object. But when we call add_object_entry(), it will do another lookup, via want_object_in_pack().

We could shortcut that by providing it with the extra information, the way add_object_entry_from_bitmap() does. The original code before your series could have done the same optimization, but it became much more obvious after your series, since -Wunused-parameters notices that we do not look at the "pack" or "pos" parameters at all. :)

It may not be that exciting an optimization, though. Pack lookups aren't _that_ expensive, and the pack-mru code would mean we always find it in the first pack (since by definition we're iterating through the objects in whole packs, our locality is perfect).

It would also probably involve some slight refactoring of add_object_entry() to avoid duplication (though possibly the result could reduce similar duplication with the bitmap variant). Hmm, actually looking further, we already have add_object_entry_from_pack() for --stdin-packs.

So I offer it mainly as an observation, in case somebody wants to look into it further (both for the optimization and the possibility of simplifying the code).

-Peff

On Thu, Sep 02, 2021 at 07:04:36PM -0400, Jeff King wrote:

I was trying to remember how I handled this for cruft packs (which want to take a slightly different path to add_object_entry() in order to record the object mtimes along the way). Indeed, in that case there is a special add_cruft_object_entry() which uses pack and offset directly.

Having looked at all of these functions which are layered on top of add_object_entry() recently, I tend to agree that there is some room for clean-up there.

I plan on sending the cruft pack series soon, after I untangle all of the `repack` + multi-pack bitmaps stuff, so perhaps that will be a good time to pursue this.

Anyway, just to say that I probably agree that the pack mru cache is helping us enough to make this negligible, but that it is on my mind and we'll have a chance to look at it soon.

Thanks, Taylor

In the original code from 08cdfb1337 (pack-objects --keep-unreachable, 2007-09-16), we add each object to the packing list with type `obj->type`, where `obj` comes from `lookup_unknown_object()`. Unless we had already looked up and parsed the object, this will be `OBJ_NONE`. That's fine, since oe_set_type() sets the type_valid bit to '0', and we determine the real type later on.

So the only thing we need from the object lookup is access to the `flags` field so that we can mark that we've added the object with `OBJECT_ADDED` to avoid adding it again (we can just pass `OBJ_NONE` directly instead of grabbing it from the object).

But add_object_entry() already rejects duplicates! This has been the behavior since 7a979d99ba (Thin pack - create packfile with missing delta base., 2006-02-19), but 08cdfb1337 didn't take advantage of it. Moreover, to do the OBJECT_ADDED check, we have to do a hash lookup in `obj_hash`.

So we can drop the lookup_unknown_object() call completely, *and* the OBJECT_ADDED flag, too, since the spot we're touching here is the only location that checks it.

In the end, we perform the same number of hash lookups, but with the added bonus that we don't waste memory allocating an OBJ_NONE object (if we were traversing, we'd need it eventually, but the whole point of this code path is not to traverse).

Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 builtin/pack-objects.c | 11 +----------
 object.h               |  1 -
 2 files changed, 1 insertion(+), 11 deletions(-)

Taylor Blau <me@ttaylorr.com> writes:

A quite pleasant read.  

Each step looked nicely done and well explained.

Will queue.

Thanks.

On Sun, Aug 29, 2021 at 10:48:43PM -0400, Taylor Blau wrote:

Thanks for extracting these from that other work. I gave them all an extra read-through and didn't find anything wrong.

Of course I love this diffstat, and I _really_ love dropping the one-off bit from the flag allocation table. But I wanted to also give some numbers for the lookup_unknown_object() part of the final patch.

Those unknown objects cost 72 bytes of heap each (the same size as a commit, since it's the biggest struct and the unknown object is a union). We've seen some real-world cases where there are 40M+ unreachable objects. So that's almost 3GB of wasted RAM during pack-objects just to store those "did I see it already" bits. :)

Of course, we are already spending 96 bytes per object in "struct object_entry", but at least that's doing more useful stuff. :)

(And the more obvious question is: why not delete those objects. The answer thus far has been: because git's pruning is racy, and thus we don't run it as part of our automatic maintenance).

-Peff

On Mon, Aug 30, 2021 at 04:58:34PM -0400, Jeff King wrote:

I wondered if you could see the drop-off represented in GitHub's overall "total heap allocated by Git" metrics, but they get drowned out in the noise of other processes we're running.

But not wasting memory there is obviously good, even if it isn't noticeable in the overall metrics.

Thanks, Taylor