promisor-remote.c: use oidset for deduplication
PATCH 1/1 promisor-remote.c: use oidset for deduplication
From: John Cai <[email protected]>
swap out oid_array for oidset in promisor-remote.c since we get a deduplicated set of oids to operate on.
swap our calls for oid_array for oidset in callers of promisor_remote_get_direct().
---
promisor-remote.c: use oidset for deduplication
swap out oid_array for oidset in promisor-remote.c since we get a deduplicated set of oids to operate on. Any direct fetch we can save will be well worth it.
oidset does use a slightly larger memory footprint than oid_array, so this change is a tradeoff between memory footprint and network calls.
What I'm not sure about is if it's worth swapping out all the calls of oid_array for oidset in callers of promisor_remote_get_direct().
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1187%2Fjohn-cai%2Fjc-dedupe-promisor-fetch-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1187/john-cai/jc-dedupe-promisor-fetch-v1
Pull-Request: https://github.com/git/git/pull/1187
builtin/index-pack.c | 9 +++--- builtin/pack-objects.c | 9 +++--- diff.c | 13 +++----- diffcore-rename.c | 12 +++---- diffcore.h | 3 +- merge-ort.c | 8 ++--- object-file.c | 4 ++- promisor-remote.c | 72 ++++++++++++++---------------------------- promisor-remote.h | 6 ++-- read-cache.c | 9 +++--- 10 files changed, 57 insertions(+), 88 deletions(-)
builtin/index-pack.c +4 -5
@@ -1387,18 +1387,17 @@ static void fix_unresolved_deltas(struct hashfile *f)/* * Prefetch the delta bases. */ -struct oid_array to_fetch =OID_ARRAY_INIT ; +struct oidset to_fetch =OIDSET_INIT ;for (i =0 ; i < nr_ref_deltas; i++) {struct ref_delta_entry *d = sorted_by_pos[i];if (!oid_object_info_extended (the_repository, &d->oid,NULL ,OBJECT_INFO_FOR_PREFETCH ))continue ; -oid_array_append (&to_fetch, &d->oid); +oidset_insert (&to_fetch, &d->oid); } -promisor_remote_get_direct (the_repository, - to_fetch.oid, to_fetch.nr); -oid_array_clear (&to_fetch); +promisor_remote_get_direct (the_repository, &to_fetch); +oidset_clear (&to_fetch); }for (i =0 ; i < nr_ref_deltas; i++) {
builtin/pack-objects.c +4 -5
@@ -1894,7 +1894,7 @@ static int can_reuse_delta(const struct object_id *base_oid, }static void prefetch_to_pack (uint32_t object_index_start) { -struct oid_array to_fetch =OID_ARRAY_INIT ; +struct oidset to_fetch =OIDSET_INIT ;uint32_t i;for (i = object_index_start; i < to_pack.nr_objects; i++) {
@@ -1905,11 +1905,10 @@ static void prefetch_to_pack(uint32_t object_index_start) {NULL , OBJECT_INFO_FOR_PREFETCH)) continue; -oid_array_append (&to_fetch, &entry->idx.oid); +oidset_insert (&to_fetch, &entry->idx.oid); } -promisor_remote_get_direct (the_repository, - to_fetch.oid, to_fetch.nr); -oid_array_clear (&to_fetch); +promisor_remote_get_direct (the_repository, &to_fetch); +oidset_clear (&to_fetch); }static void check_object (struct object_entry *entry,uint32_t object_index)
diff.c +5 -8
@@ -6609,14 +6609,14 @@ void diffcore_fix_diff_index(void) }void diff_add_if_missing (struct repository *r, -struct oid_array *to_fetch, +struct oidset *to_fetch,const struct diff_filespec *filespec) {if (filespec && filespec->oid_valid && !S_ISGITLINK (filespec->mode) &&oid_object_info_extended (r, &filespec->oid,NULL ,OBJECT_INFO_FOR_PREFETCH )) -oid_array_append (to_fetch, &filespec->oid); +oidset_insert (to_fetch, &filespec->oid); }void diff_queued_diff_prefetch (void *repository)
@@ -6624,7 +6624,7 @@ void diff_queued_diff_prefetch(void *repository)struct repository *repo = repository;int i;struct diff_queue_struct *q = &diff_queued_diff; -struct oid_array to_fetch =OID_ARRAY_INIT ; +struct oidset to_fetch =OIDSET_INIT ;for (i =0 ; i < q->nr; i++) {struct diff_filepair *p = q->queue[i];
@@ -6632,12 +6632,9 @@ void diff_queued_diff_prefetch(void *repository)diff_add_if_missing (repo, &to_fetch, p->two); } -/* -* NEEDSWORK: Consider deduplicating the OIDs sent. -*/ -promisor_remote_get_direct (repo, to_fetch.oid, to_fetch.nr); +promisor_remote_get_direct (repo, &to_fetch); -oid_array_clear (&to_fetch); +oidset_clear (&to_fetch); }void diffcore_std (struct diff_options *options)
diffcore-rename.c +6 -6
@@ -95,7 +95,7 @@ static void inexact_prefetch(void *prefetch_options) {struct inexact_prefetch_options *options = prefetch_options;int i; -struct oid_array to_fetch =OID_ARRAY_INIT ; +struct oidset to_fetch =OIDSET_INIT ;for (i =0 ; i < rename_dst_nr; i++) {if (rename_dst[i].p->renamed_pair)
@@ -118,8 +118,8 @@ static void inexact_prefetch(void *prefetch_options)diff_add_if_missing (options->repo, &to_fetch, rename_src[i].p->one); } -promisor_remote_get_direct (options->repo, to_fetch.oid, to_fetch.nr); -oid_array_clear (&to_fetch); +promisor_remote_get_direct (options->repo, &to_fetch); +oidset_clear (&to_fetch); } static int estimate_similarity(struct repository *r,
@@ -837,7 +837,7 @@ static void basename_prefetch(void *prefetch_options)struct strintmap *dests = options->dests;struct dir_rename_info *info = options->info;int i; -struct oid_array to_fetch =OID_ARRAY_INIT ; +struct oidset to_fetch =OIDSET_INIT ;/* * TODO: The following loops mirror the code/logic from
@@ -890,8 +890,8 @@ static void basename_prefetch(void *prefetch_options) } } -promisor_remote_get_direct (options->repo, to_fetch.oid, to_fetch.nr); -oid_array_clear (&to_fetch); +promisor_remote_get_direct (options->repo, &to_fetch); +oidset_clear (&to_fetch); } static int find_basename_matches(struct diff_options *options,
diffcore.h +2 -1
@@ -11,6 +11,7 @@ struct repository;struct strintmap ;struct strmap ;struct userdiff_driver ; +struct oidset ;/* This header file is internal between diff.c and its diff transformers * (e.g. diffcore-rename, diffcore-pickaxe). Never include this header
@@ -229,7 +230,7 @@ int diffcore_count_changes(struct repository *r,* repository, add that OID to to_fetch. */ void diff_add_if_missing (struct repository *r, -struct oid_array *to_fetch, +struct oidset *to_fetch,const struct diff_filespec *filespec);#endif
merge-ort.c +4 -4
@@ -3903,7 +3903,7 @@ static void prefetch_for_content_merges(struct merge_options *opt, struct string_list *plist) {struct string_list_item *e; -struct oid_array to_fetch =OID_ARRAY_INIT ; +struct oidset to_fetch =OIDSET_INIT ;if (opt->repo != the_repository || !has_promisor_remote ())return ;
@@ -3939,12 +3939,12 @@ static void prefetch_for_content_merges(struct merge_options *opt, S_ISREG(vi->mode) && oid_object_info_extended(opt->repo, &vi->oid, NULL, OBJECT_INFO_FOR_PREFETCH)) -oid_array_append (&to_fetch, &vi->oid); +oidset_insert (&to_fetch, &vi->oid); } } -promisor_remote_get_direct (opt->repo, to_fetch.oid, to_fetch.nr); -oid_array_clear (&to_fetch); +promisor_remote_get_direct (opt->repo, &to_fetch); +oidset_clear (&to_fetch); } static void process_entries(struct merge_options *opt,
object-file.c +3 -1
@@ -1519,6 +1519,7 @@ static int do_oid_object_info_extended(struct repository *r,struct cached_object *co;struct pack_entry e;int rtype; +struct oidset to_fetch =OIDSET_INIT ;const struct object_id *real = oid;int already_retried =0 ;
@@ -1587,7 +1588,8 @@ static int do_oid_object_info_extended(struct repository *r,* TODO Investigate checking promisor_remote_get_direct() * TODO return value and stopping on error here. */ -promisor_remote_get_direct (r, real,1 ); +oidset_insert (&to_fetch, real); +promisor_remote_get_direct (r, &to_fetch); already_retried =1 ;continue ; }
promisor-remote.c +23 -49
115 lines not on this page · raw message
promisor-remote.h +2 -4
@@ -3,8 +3,7 @@#include "repository.h" -struct object_id ; - +struct oidset ;/* * Promisor remote linked list *
@@ -45,7 +44,6 @@ static inline int has_promisor_remote(void)* If oid_nr is 0, this function returns 0 (success) immediately. */ int promisor_remote_get_direct (struct repository *repo, -const struct object_id *oids, -int oid_nr); +struct oidset *oids);#endif /* PROMISOR_REMOTE_H */
read-cache.c +4 -5
@@ -3732,7 +3732,7 @@ void prefetch_cache_entries(const struct index_state *istate, must_prefetch_predicate must_prefetch) {int i; -struct oid_array to_fetch =OID_ARRAY_INIT ; +struct oidset to_fetch =OIDSET_INIT ;for (i =0 ; i < istate->cache_nr; i++) {struct cache_entry *ce = istate->cache[i];
@@ -3743,9 +3743,8 @@ void prefetch_cache_entries(const struct index_state *istate,NULL , OBJECT_INFO_FOR_PREFETCH)) continue; -oid_array_append (&to_fetch, &ce->oid); +oidset_insert (&to_fetch, &ce->oid); } -promisor_remote_get_direct (the_repository, - to_fetch.oid, to_fetch.nr); -oid_array_clear (&to_fetch); +promisor_remote_get_direct (the_repository, &to_fetch); +oidset_clear (&to_fetch); }
base-commit: 1ffcbaa1a5f10c9f706314d77f88de20a4a498c2
Signature · 1 line
gitgitgadget
Quoted 13 lines · John Cai via GitGitGadget
object-file.c +1
-0@@ -1519,6 +1519,7 @@ static int do_oid_object_info_extended(struct repository *r,struct cached_object *co;struct pack_entry e;int rtype; +struct oidset to_fetch =OIDSET_INIT ;const struct object_id *real = oid;int already_retried =0 ;
object-file.c static int do_oid_object_info_extended(struct repository *r, · line 1595
Quoted 9 lines
object-file.c +2
-1@@ -1587,7 +1588,8 @@ static int do_oid_object_info_extended(struct repository *r,* TODO Investigate checking promisor_remote_get_direct() * TODO return value and stopping on error here. */ -promisor_remote_get_direct (r, real,1 ); +oidset_insert (&to_fetch, real); +promisor_remote_get_direct (r, &to_fetch); already_retried =1 ;continue ; }
Everything that migrated from oid_array to oidset should be OK because it is likely that existing oid_array_clear() would not compile until it is replaced with oidset_clear(), at which point the oidset will be cleared when we are done with it.
However, this one did not use an oid_array and did not have to clear to release the resources. So it is very likely that nobody clears to_fetch that is introduced by this patch, no?
I suspect that this introduces a new leak.
Quoted 9 lines · John Cai via GitGitGadget
From: John Cai <[email protected]>
swap out
oid_arrayfor oidset inpromisor-remote.csince we get a deduplicated set of oids to operate on.swap our calls for
oid_arrayfor oidset in callers ofpromisor_remote_get_direct().
FWIW we had an off-list discussion about oidset v.s. a custom hashmap to do the same off-list, not about s/oid_array/oidset/ in this area.
Quoted 5 lines
Signed-off-by John Cai <[email protected]>---
promisor-remote.c: use oidset for deduplication
Extra \n between $subject and $body.
Quoted 1 line
swap out
oid_arrayfor oidset inpromisor-remote.csince we get a
Nit: s/swap/Swap/, i.e. start the sentence with a capital letter...
Quoted 8 lines
deduplicated set of oids to operate on. Any direct fetch we can save will be well worth it.
oidset does use a slightly larger memory footprint than
oid_array, so this change is a tradeoff between memory footprint and network calls.What I'm not sure about is if it's worth swapping out all the calls of
oid_arrayfor oidset in callers ofpromisor_remote_get_direct().
From what I understand of GGG I think you updated only the summary on the PR but not the commit itself, the latter is what would go into git.git. Here the commit should be updated so we get this message.
The part after the "---" is usually just used in this project for ad-hoc list-only comment.
Quoted 11 lines
builtin/index-pack.c | 9 +++--- builtin/pack-objects.c | 9 +++--- diff.c | 13 +++----- diffcore-rename.c | 12 +++---- diffcore.h | 3 +- merge-ort.c | 8 ++--- object-file.c | 4 ++- promisor-remote.c | 72 ++++++++++++++---------------------------- promisor-remote.h | 6 ++-- read-cache.c | 9 +++--- 10 files changed, 57 insertions(+), 88 deletions(-)
Rather than inline comments, a comment that applies to all of these:
The difference between these two APIs is thaht oidset is hash-backed, and you'd insert into it and we de-duplicate any duplicate OIDs on-the-fly.
The oid_array is just an realloc()'d "struct object_id *oid". On insertion you can insert duplicates, but it has the ability to track "I've sorted these", and "let's iterate over this sorted, and de-dup any duplicates".
We have the two APIs for a reason, but I don't know in any of these cases whether this change is safe.
Does e.g. index-pack.c always receive de-duplicated OIDs and we were wasting CPU cycles using an oidset?
Do some of these like pack-objects.c receive de-duplicated OIDs from e.g. "git repack" *now*, but we just lack test coverage to see that they're happy to get duplicate OIDs on stdin (e.g. manually from a user), and this would introduce a bug?
But most importantly is it worth it? What's the rationale for the change? Less CPU/memory use? Getting e.g. "hyperfine" or "/usr/bin/time -v" output for those (if so) would be valuable.
Quoted 3 lines · Ævar Arnfjörð Bjarmason
From what I understand of GGG I think you updated only the summary on the PR but not the commit itself, the latter is what would go into git.git. Here the commit should be updated so we get this message.
Ah, I have long learned to ignore the blurb after the three-dash line when a patch comes via GGG (because the PR text is often useless and most often people seem to use text identical to the commit log message). I didn't realize that the proposed commit log message was useless in this particular patch. I was wondering why you were talking about an extra blank line after the title there ;-)
Quoted 2 lines
The part after the "---" is usually just used in this project for ad-hoc list-only comment.
True. "What I'm not sure about is ..." however does belong to the list-only comment, though. If it is not
Quoted 11 lines
The difference between these two APIs is thaht oidset is hash-backed, and you'd insert into it and we de-duplicate any duplicate OIDs on-the-fly.
The
oid_arrayis just an realloc()'d "structobject_id*oid". On insertion you can insert duplicates, but it has the ability to track "I've sorted these", and "let's iterate over this sorted, and de-dup any duplicates".We have the two APIs for a reason, but I don't know in any of these cases whether this change is safe.
Quoted 7 lines
Does e.g.
index-pack.calways receive de-duplicated OIDs and we were wasting CPU cycles using an oidset?Do some of these like
pack-objects.creceive de-duplicated OIDs from e.g. "git repack" *now*, but we just lack test coverage to see that they're happy to get duplicate OIDs on stdin (e.g. manually from a user), and this would introduce a bug?
Also, if oid_array is used to produce a de-duplicated list of object names in the current code, it is very likely that oid_array is sorted (perhaps the objects are fed in sorted order), and the callers depend on the order of the objects they find in the array. Throwing sorted list of object names at oidset and then iterating over what is in the oidset would likely to destroy the original ordering. I do not offhand know if the callers are broken by such a change (either correctness-wise or performance-wise).
Quoted 3 lines
But most importantly is it worth it? What's the rationale for the change? Less CPU/memory use? Getting e.g. "hyperfine" or "
/usr/bin/time-v" output for those (if so) would be valuable.
Thanks.
Quoted 8 lines · Junio C Hamano
Also, if
oid_arrayis used to produce a de-duplicated list of object names in the current code, it is very likely thatoid_arrayis sorted (perhaps the objects are fed in sorted order), and the callers depend on the order of the objects they find in the array. Throwing sorted list of object names at oidset and then iterating over what is in the oidset would likely to destroy the original ordering. I do not offhand know if the callers are broken by such a change (either correctness-wise or performance-wise).
Since I had a bit of downtime waiting for CI, I took a look.
It seems that the list of objects collected in the oidset/oid_array is fed to "git fetch --stdin" for lazy fetching, so I would be surprised if the order of objects matter. So I would stop worrying about correctness or performance due to ordering change.
Quoted 3 lines
Quoted 3 lines
But most importantly is it worth it? What's the rationale for the change? Less CPU/memory use? Getting e.g. "hyperfine" or "
/usr/bin/time-v" output for those (if so) would be valuable.
But I still agree with this. How much duplication would a typical request for a lazy fetch involve? Would it cause duplicate "want" to make the protocol exchange noticeably larger?
Having said all that, the change makes the code smaller, and possibly easier to follow.
The primary reason why promisor-remote.c::remove_fetched_oids() shrinks so much is because we used to scan the array and copied the surviving ones into a new array, while the new code just iterates over the oidset and removes the ones that were fetched. I am assuming that mucking with the oidset's contents while you are iterating over it is safe, but if that is not the case, then the advantage of the smaller code disappears.
Quoted 60 lines · Ævar Arnfjörð Bjarmason
Quoted 9 lines · John Cai via GitGitGadget
From: John Cai <[email protected]>
swap out
oid_arrayfor oidset inpromisor-remote.csince we get a deduplicated set of oids to operate on.swap our calls for
oid_arrayfor oidset in callers ofpromisor_remote_get_direct().FWIW we had an off-list discussion about oidset v.s. a custom hashmap to do the same off-list, not about s/oid_array/oidset/ in this area.
Quoted 5 lines
Signed-off-by John Cai <[email protected]>---
promisor-remote.c: use oidset for deduplicationExtra \n between $subject and $body.
Quoted 1 line
swap out
oid_arrayfor oidset inpromisor-remote.csince we get aNit: s/swap/Swap/, i.e. start the sentence with a capital letter...
Quoted 8 lines
deduplicated set of oids to operate on. Any direct fetch we can save will be well worth it.
oidset does use a slightly larger memory footprint than
oid_array, so this change is a tradeoff between memory footprint and network calls.What I'm not sure about is if it's worth swapping out all the calls of
oid_arrayfor oidset in callers ofpromisor_remote_get_direct().From what I understand of GGG I think you updated only the summary on the PR but not the commit itself, the latter is what would go into git.git. Here the commit should be updated so we get this message.
The part after the "---" is usually just used in this project for ad-hoc list-only comment.
Quoted 11 lines
builtin/index-pack.c | 9 +++--- builtin/pack-objects.c | 9 +++--- diff.c | 13 +++----- diffcore-rename.c | 12 +++---- diffcore.h | 3 +- merge-ort.c | 8 ++--- object-file.c | 4 ++- promisor-remote.c | 72 ++++++++++++++---------------------------- promisor-remote.h | 6 ++-- read-cache.c | 9 +++--- 10 files changed, 57 insertions(+), 88 deletions(-)Rather than inline comments, a comment that applies to all of these:
The difference between these two APIs is thaht oidset is hash-backed, and you'd insert into it and we de-duplicate any duplicate OIDs on-the-fly.
Quoted 7 lines
The
oid_arrayis just an realloc()'d "structobject_id*oid". On insertion you can insert duplicates, but it has the ability to track "I've sorted these", and "let's iterate over this sorted, and de-dup any duplicates".We have the two APIs for a reason, but I don't know in any of these cases whether this change is safe.
To reduce the footprint of this change, maybe we can just keep oid_array and sort it in diff.c before passing it off to promisor_remote_get_direct(), in which we then iterate over unique entries.
Quoted 3 lines
Does e.g.
index-pack.calways receive de-duplicated OIDs and we were wasting CPU cycles using an oidset?
Good question. In fact a more immediate question is how often does diff.c receive dupe oids, which was the original motivation for the change. cc’ing Jonathan as he was involved with 95acf11a that added the NEEDSWORK block.
Jonathan, how often do we expect diff to pass duplicate oids to promisor_remote_get_direct()?
Quoted 9 lines
Do some of these like
pack-objects.creceive de-duplicated OIDs from e.g. "git repack" *now*, but we just lack test coverage to see that they're happy to get duplicate OIDs on stdin (e.g. manually from a user), and this would introduce a bug?But most importantly is it worth it? What's the rationale for the change? Less CPU/memory use? Getting e.g. "hyperfine" or "
/usr/bin/time-v" output for those (if so) would be valuable.
I agree this would be very valuable, but I’m thinking more so once I get a better idea of what kind of situations would lead to duplicate oids in diff.c
Quoted 2 lines · John Cai
Jonathan, how often do we expect diff to pass duplicate oids to
promisor_remote_get_direct()?
I don't recall all the details, but not often, I believe. In a partial clone, I envision that you would typically diff one tree that you have all blobs for and one tree that you don't (or two trees that you have all blobs for). If a user is in a sparse checkout and/or they're diffing two trees that they have never checked out, I would recommend disabling inexact copy detection to reduce the number of blobs that Git would need to fetch. In these cases, I think that diff would only pass duplicate OIDs if one of the trees references the same object more than once (directly or indirectly).