pack-objects: simplify add_objects_in_unpacked_packs()
cover pack-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(-)
Signature · 1 line
2.33.0.96.g73915697e6
PATCH 1/3 object-store.h: teach for_each_packed_object to ignore kept packs
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.
--- object-store.h | 6 ++++++ packfile.c | 6 ++++++ 2 files changed, 12 insertions(+)
object-store.h +6 -0
@@ -455,6 +455,12 @@ enum for_each_object_flags {* Visit objects within a pack in packfile order rather than .idx order */ 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), };/*
packfile.c +6 -0
@@ -2205,6 +2205,12 @@ int for_each_packed_object(each_packed_object_fn cb, void *data,if ((flags &FOR_EACH_OBJECT_PROMISOR_ONLY ) && !p->pack_promisor)continue ; +if ((flags &FOR_EACH_OBJECT_SKIP_IN_CORE_KEPT_PACKS ) && + p->pack_keep_in_core) +continue ; +if ((flags &FOR_EACH_OBJECT_SKIP_ON_DISK_KEPT_PACKS ) && + p->pack_keep) +continue ;if (open_pack_index (p)) { pack_errors =1 ;continue ;
Signature · 1 line
2.33.0.96.g73915697e6
PATCH 2/3 builtin/pack-objects.c: simplify add_objects_in_unpacked_packs()
In reply to Taylor BlauThis 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.
--- builtin/pack-objects.c | 84 ++++++++---------------------------------- 1 file changed, 16 insertions(+), 68 deletions(-)
builtin/pack-objects.c +16 -68
@@ -3505,79 +3505,27 @@ static void show_edge(struct commit *commit)add_preferred_base (&commit->object.oid); } -struct in_pack_object { -off_t offset; -struct object *object; -}; - -struct in_pack { -unsigned int alloc; -unsigned int nr; -struct in_pack_object *array; -}; - -static void mark_in_pack_object (struct object *object,struct packed_git *p,struct in_pack *in_pack) +static int add_object_in_unpacked_pack (const struct object_id *oid, +struct packed_git *pack, +uint32_t pos, +void *_data) { - in_pack->array[in_pack->nr].offset =find_pack_entry_one (object->oid.hash, p); - in_pack->array[in_pack->nr].object = object; - in_pack->nr++; -} - -/* -* Compare the objects in the offset order, in order to emulate the -* "git rev-list --objects" output that produced the pack originally. -*/ -static int ofscmp (const void *a_,const void *b_) -{ -struct in_pack_object *a = (struct in_pack_object *)a_; -struct in_pack_object *b = (struct in_pack_object *)b_; - -if (a->offset < b->offset) -return -1 ; -else if (a->offset > b->offset) -return 1 ; -else -return oidcmp (&a->object->oid, &b->object->oid); +struct object *obj =lookup_unknown_object (the_repository, oid); +if (obj->flags &OBJECT_ADDED ) +return 0 ; +add_object_entry (oid, obj->type,"" ,0 ); + obj->flags |=OBJECT_ADDED ; +return 0 ; }static void add_objects_in_unpacked_packs (void ) { -struct packed_git *p; -struct in_pack in_pack; -uint32_t i; - -memset (&in_pack,0 ,sizeof (in_pack)); - -for (p =get_all_packs (the_repository); p; p = p->next) { -struct object_id oid; -struct object *o; - -if (!p->pack_local || p->pack_keep || p->pack_keep_in_core) -continue ; -if (open_pack_index (p)) -die (_ ("cannot open pack index" )); - -ALLOC_GROW (in_pack.array, - in_pack.nr + p->num_objects, - in_pack.alloc); - -for (i =0 ; i < p->num_objects; i++) { -nth_packed_object_id (&oid, p, i); - o =lookup_unknown_object (the_repository, &oid); -if (!(o->flags &OBJECT_ADDED )) -mark_in_pack_object (o, p, &in_pack); - o->flags |=OBJECT_ADDED ; - } - } - -if (in_pack.nr) { -QSORT (in_pack.array, in_pack.nr, ofscmp); -for (i =0 ; i < in_pack.nr; i++) { -struct object *o = in_pack.array[i].object; -add_object_entry (&o->oid, o->type,"" ,0 ); - } - } -free (in_pack.array); +if (for_each_packed_object (add_object_in_unpacked_pack,NULL , +FOR_EACH_OBJECT_PACK_ORDER | +FOR_EACH_OBJECT_LOCAL_ONLY | +FOR_EACH_OBJECT_SKIP_IN_CORE_KEPT_PACKS | +FOR_EACH_OBJECT_SKIP_ON_DISK_KEPT_PACKS )) +die (_ ("cannot open pack index" )); } static int add_loose_object(const struct object_id *oid, const char *path,
Signature · 1 line
2.33.0.96.g73915697e6
PATCH 3/3 builtin/pack-objects.c: remove duplicate hash lookup
In reply to Taylor BlauIn 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).
--- builtin/pack-objects.c | 11 +---------- object.h | 1 - 2 files changed, 1 insertion(+), 11 deletions(-)
builtin/pack-objects.c +1 -10
@@ -3405,13 +3405,9 @@ static void read_object_list_from_stdin(void) } } -/* Remember to update object flag allocation in object.h */ -#define OBJECT_ADDED (1u<<20) -static void show_commit (struct commit *commit,void *data) {add_object_entry (&commit->object.oid,OBJ_COMMIT ,NULL ,0 ); - commit->object.flags |=OBJECT_ADDED ;if (write_bitmap_index)index_commit_for_bitmap (commit);
@@ -3424,7 +3420,6 @@ static void show_object(struct object *obj, const char *name, void *data) {add_preferred_base_object (name);add_object_entry (&obj->oid, obj->type, name,0 ); - obj->flags |=OBJECT_ADDED ;if (use_delta_islands) {const char *p;
@@ -3510,11 +3505,7 @@ static int add_object_in_unpacked_pack(const struct object_id *oid,uint32_t pos, void *_data) { - struct object *obj = lookup_unknown_object(the_repository, oid); -if (obj->flags &OBJECT_ADDED ) -return 0 ; -add_object_entry (oid, obj->type,"" ,0 ); - obj->flags |=OBJECT_ADDED ; + add_object_entry(oid, OBJ_NONE, "", 0);return 0 ; }
object.h +0 -1
@@ -75,7 +75,6 @@ struct object_array {* builtin/fsck.c: 0--3 * builtin/gc.c: 0 * builtin/index-pack.c: 2021 -* builtin/pack-objects.c: 20 * builtin/reflog.c: 10--12 * builtin/show-branch.c: 0-------------------------------------------26 * builtin/unpack-objects.c: 2021
Signature · 1 line
2.33.0.96.g73915697e6
Quoted 11 lines · Taylor Blau
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 implementgit 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()withfor_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.
A quite pleasant read.
Each step looked nicely done and well explained.
Will queue.
Thanks.
Quoted 13 lines
Thanks in advance for your review.
Taylor Blau (3):
object-store.h: teachfor_each_packed_objectto ignore kept packsbuiltin/pack-objects.c: simplifyadd_objects_in_unpacked_packs()builtin/pack-objects.c: remove duplicate hash lookupbuiltin/pack-objects.c | 85 ++++++------------------------------------ object-store.h | 6 +++ object.h | 1 - packfile.c | 6 +++ 4 files changed, 24 insertions(+), 74 deletions(-)
Quoted 11 lines · Taylor Blau
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 implementgit 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()withfor_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.
Quoted 5 lines
builtin/pack-objects.c | 85 ++++++------------------------------------ object-store.h | 6 +++ object.h | 1 - packfile.c | 6 +++ 4 files changed, 24 insertions(+), 74 deletions(-)
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
Quoted 5 lines · Jeff King
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
Re: [PATCH 2/3] builtin/pack-objects.c: simplify add_objects_in_unpacked_packs()
In reply to Taylor Blaubuiltin/pack-objects.c static void show_edge(struct commit *commit) · line 3519
Quoted 13 lines · Taylor Blau
builtin/pack-objects.c +10
-0+static int add_object_in_unpacked_pack (const struct object_id *oid, +struct packed_git *pack, +uint32_t pos, +void *_data) { +struct object *obj =lookup_unknown_object (the_repository, oid); +if (obj->flags &OBJECT_ADDED ) +return 0 ; +add_object_entry (oid, obj->type,"" ,0 ); + obj->flags |=OBJECT_ADDED ; +return 0 ; }
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
Re: [PATCH 2/3] builtin/pack-objects.c: simplify add_objects_in_unpacked_packs()
Quoted 22 lines · Jeff King
builtin/pack-objects.c static void show_edge(struct commit *commit) · line 3519
Quoted 13 lines · Taylor Blau
builtin/pack-objects.c +10
-0+static int add_object_in_unpacked_pack (const struct object_id *oid, +struct packed_git *pack, +uint32_t pos, +void *_data) { +struct object *obj =lookup_unknown_object (the_repository, oid); +if (obj->flags &OBJECT_ADDED ) +return 0 ; +add_object_entry (oid, obj->type,"" ,0 ); + obj->flags |=OBJECT_ADDED ; +return 0 ; }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, viawant_object_in_pack().
Quoted 7 lines
[...]
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 haveadd_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