From: Taylor Blau <hidden> Date: 2021-08-30 02:48:53
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(-)
--
2.33.0.96.g73915697e6
From: Taylor Blau <hidden> Date: 2021-08-30 02:48:57
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 <redacted>
---
object-store.h | 6 ++++++
packfile.c | 6 ++++++
2 files changed, 12 insertions(+)
@@ -455,6 +455,12 @@ enum for_each_object_flags {*Visitobjectswithinapackinpackfileorderratherthan.idxorder*/FOR_EACH_OBJECT_PACK_ORDER=(1<<2),++/* Only iterate over packs that are not marked as kept in-core. */+FOR_EACH_OBJECT_SKIP_IN_CORE_KEPT_PACKS=(1<<3),++/* Only iterate over packs that do not have .keep files. */+FOR_EACH_OBJECT_SKIP_ON_DISK_KEPT_PACKS=(1<<4),};/*
From: Taylor Blau <hidden> Date: 2021-08-30 02:49:01
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 <redacted>
---
builtin/pack-objects.c | 84 ++++++++----------------------------------
1 file changed, 16 insertions(+), 68 deletions(-)
From: Taylor Blau <hidden> Date: 2021-08-30 02:49:05
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 <redacted>
---
builtin/pack-objects.c | 11 +----------
object.h | 1 -
2 files changed, 1 insertion(+), 11 deletions(-)
From: Jeff King <hidden> Date: 2021-08-30 20:58:39
On Sun, Aug 29, 2021 at 10:48:43PM -0400, Taylor Blau wrote:
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 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
From: Taylor Blau <hidden> Date: 2021-08-30 21:30:07
On Mon, Aug 30, 2021 at 04:58:34PM -0400, Jeff King wrote:
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. :)
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
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
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().
[...]
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.
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