{"thread":{"id":"57240","subject":"[PATCH] promisor-remote.c: use oidset for deduplication","startedAt":"2022-01-13T20:32:11Z","lastAt":"2022-01-25T19:17:16Z","messageCount":7,"participants":["John Cai via GitGitGadget","Junio C Hamano","Ævar Arnfjörð Bjarmason","John Cai","Jonathan Tan"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"446182","messageId":"pull.1187.git.git.1642105926064.gitgitgadget@gmail.com","threadId":"57240","inReplyTo":null,"subject":"[PATCH] promisor-remote.c: use oidset for deduplication","fromName":"John Cai via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2022-01-13T20:32:05Z","receivedAt":"2022-01-13T20:32:11Z","isPatch":true,"sender":{"key":"johncai86@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2354211?v=4"},"body":"From: John Cai <johncai86@gmail.com>\n\nswap out oid_array for oidset in promisor-remote.c since we get\na deduplicated set of oids to operate on.\n\nswap our calls for oid_array for oidset in callers of\npromisor_remote_get_direct().\n\nHelped-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>\nSigned-off-by: John Cai <johncai86@gmail.com>\n---\n    promisor-remote.c: use oidset for deduplication\n    \n    \n    swap out oid_array for oidset in promisor-remote.c since we get a\n    deduplicated set of oids to operate on. Any direct fetch we can save\n    will be well worth it.\n    \n    oidset does use a slightly larger memory footprint than oid_array, so\n    this change is a tradeoff between memory footprint and network calls.\n    \n    What I'm not sure about is if it's worth swapping out all the calls of\n    oid_array for oidset in callers of promisor_remote_get_direct().\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1187%2Fjohn-cai%2Fjc-dedupe-promisor-fetch-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1187/john-cai/jc-dedupe-promisor-fetch-v1\nPull-Request: https://github.com/git/git/pull/1187\n\n builtin/index-pack.c   |  9 +++---\n builtin/pack-objects.c |  9 +++---\n diff.c                 | 13 +++-----\n diffcore-rename.c      | 12 +++----\n diffcore.h             |  3 +-\n merge-ort.c            |  8 ++---\n object-file.c          |  4 ++-\n promisor-remote.c      | 72 ++++++++++++++----------------------------\n promisor-remote.h      |  6 ++--\n read-cache.c           |  9 +++---\n 10 files changed, 57 insertions(+), 88 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 3c2e6aee3cc..7de2eb42794 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1387,18 +1387,17 @@ static void fix_unresolved_deltas(struct hashfile *f)\n \t\t/*\n \t\t * Prefetch the delta bases.\n \t\t */\n-\t\tstruct oid_array to_fetch = OID_ARRAY_INIT;\n+\t\tstruct oidset to_fetch = OIDSET_INIT;\n \t\tfor (i = 0; i < nr_ref_deltas; i++) {\n \t\t\tstruct ref_delta_entry *d = sorted_by_pos[i];\n \t\t\tif (!oid_object_info_extended(the_repository, &d->oid,\n \t\t\t\t\t\t      NULL,\n \t\t\t\t\t\t      OBJECT_INFO_FOR_PREFETCH))\n \t\t\t\tcontinue;\n-\t\t\toid_array_append(&to_fetch, &d->oid);\n+\t\t\toidset_insert(&to_fetch, &d->oid);\n \t\t}\n-\t\tpromisor_remote_get_direct(the_repository,\n-\t\t\t\t\t   to_fetch.oid, to_fetch.nr);\n-\t\toid_array_clear(&to_fetch);\n+\t\tpromisor_remote_get_direct(the_repository, &to_fetch);\n+\t\toidset_clear(&to_fetch);\n \t}\n \n \tfor (i = 0; i < nr_ref_deltas; i++) {\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex ba2006f2212..4cef3bd78b2 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1894,7 +1894,7 @@ static int can_reuse_delta(const struct object_id *base_oid,\n }\n \n static void prefetch_to_pack(uint32_t object_index_start) {\n-\tstruct oid_array to_fetch = OID_ARRAY_INIT;\n+\tstruct oidset to_fetch = OIDSET_INIT;\n \tuint32_t i;\n \n \tfor (i = object_index_start; i < to_pack.nr_objects; i++) {\n@@ -1905,11 +1905,10 @@ static void prefetch_to_pack(uint32_t object_index_start) {\n \t\t\t\t\t      NULL,\n \t\t\t\t\t      OBJECT_INFO_FOR_PREFETCH))\n \t\t\tcontinue;\n-\t\toid_array_append(&to_fetch, &entry->idx.oid);\n+\t\toidset_insert(&to_fetch, &entry->idx.oid);\n \t}\n-\tpromisor_remote_get_direct(the_repository,\n-\t\t\t\t   to_fetch.oid, to_fetch.nr);\n-\toid_array_clear(&to_fetch);\n+\tpromisor_remote_get_direct(the_repository, &to_fetch);\n+\toidset_clear(&to_fetch);\n }\n \n static void check_object(struct object_entry *entry, uint32_t object_index)\ndiff --git a/diff.c b/diff.c\nindex c862771a589..e48a5c7bfcc 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -6609,14 +6609,14 @@ void diffcore_fix_diff_index(void)\n }\n \n void diff_add_if_missing(struct repository *r,\n-\t\t\t struct oid_array *to_fetch,\n+\t\t\t struct oidset *to_fetch,\n \t\t\t const struct diff_filespec *filespec)\n {\n \tif (filespec && filespec->oid_valid &&\n \t    !S_ISGITLINK(filespec->mode) &&\n \t    oid_object_info_extended(r, &filespec->oid, NULL,\n \t\t\t\t     OBJECT_INFO_FOR_PREFETCH))\n-\t\toid_array_append(to_fetch, &filespec->oid);\n+\t\toidset_insert(to_fetch, &filespec->oid);\n }\n \n void diff_queued_diff_prefetch(void *repository)\n@@ -6624,7 +6624,7 @@ void diff_queued_diff_prefetch(void *repository)\n \tstruct repository *repo = repository;\n \tint i;\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n-\tstruct oid_array to_fetch = OID_ARRAY_INIT;\n+\tstruct oidset to_fetch = OIDSET_INIT;\n \n \tfor (i = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n@@ -6632,12 +6632,9 @@ void diff_queued_diff_prefetch(void *repository)\n \t\tdiff_add_if_missing(repo, &to_fetch, p->two);\n \t}\n \n-\t/*\n-\t * NEEDSWORK: Consider deduplicating the OIDs sent.\n-\t */\n-\tpromisor_remote_get_direct(repo, to_fetch.oid, to_fetch.nr);\n+\tpromisor_remote_get_direct(repo, &to_fetch);\n \n-\toid_array_clear(&to_fetch);\n+\toidset_clear(&to_fetch);\n }\n \n void diffcore_std(struct diff_options *options)\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex bebd4ed6a42..2fe89ef01b8 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -95,7 +95,7 @@ static void inexact_prefetch(void *prefetch_options)\n {\n \tstruct inexact_prefetch_options *options = prefetch_options;\n \tint i;\n-\tstruct oid_array to_fetch = OID_ARRAY_INIT;\n+\tstruct oidset to_fetch = OIDSET_INIT;\n \n \tfor (i = 0; i < rename_dst_nr; i++) {\n \t\tif (rename_dst[i].p->renamed_pair)\n@@ -118,8 +118,8 @@ static void inexact_prefetch(void *prefetch_options)\n \t\tdiff_add_if_missing(options->repo, &to_fetch,\n \t\t\t\t    rename_src[i].p->one);\n \t}\n-\tpromisor_remote_get_direct(options->repo, to_fetch.oid, to_fetch.nr);\n-\toid_array_clear(&to_fetch);\n+\tpromisor_remote_get_direct(options->repo, &to_fetch);\n+\toidset_clear(&to_fetch);\n }\n \n static int estimate_similarity(struct repository *r,\n@@ -837,7 +837,7 @@ static void basename_prefetch(void *prefetch_options)\n \tstruct strintmap *dests = options->dests;\n \tstruct dir_rename_info *info = options->info;\n \tint i;\n-\tstruct oid_array to_fetch = OID_ARRAY_INIT;\n+\tstruct oidset to_fetch = OIDSET_INIT;\n \n \t/*\n \t * TODO: The following loops mirror the code/logic from\n@@ -890,8 +890,8 @@ static void basename_prefetch(void *prefetch_options)\n \t\t}\n \t}\n \n-\tpromisor_remote_get_direct(options->repo, to_fetch.oid, to_fetch.nr);\n-\toid_array_clear(&to_fetch);\n+\tpromisor_remote_get_direct(options->repo, &to_fetch);\n+\toidset_clear(&to_fetch);\n }\n \n static int find_basename_matches(struct diff_options *options,\ndiff --git a/diffcore.h b/diffcore.h\nindex badc2261c20..9f593e01165 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -11,6 +11,7 @@ struct repository;\n struct strintmap;\n struct strmap;\n struct userdiff_driver;\n+struct oidset;\n \n /* This header file is internal between diff.c and its diff transformers\n  * (e.g. diffcore-rename, diffcore-pickaxe).  Never include this header\n@@ -229,7 +230,7 @@ int diffcore_count_changes(struct repository *r,\n  * repository, add that OID to to_fetch.\n  */\n void diff_add_if_missing(struct repository *r,\n-\t\t\t struct oid_array *to_fetch,\n+\t\t\t struct oidset *to_fetch,\n \t\t\t const struct diff_filespec *filespec);\n \n #endif\ndiff --git a/merge-ort.c b/merge-ort.c\nindex c3197970219..107c086bb6a 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -3903,7 +3903,7 @@ static void prefetch_for_content_merges(struct merge_options *opt,\n \t\t\t\t\tstruct string_list *plist)\n {\n \tstruct string_list_item *e;\n-\tstruct oid_array to_fetch = OID_ARRAY_INIT;\n+\tstruct oidset to_fetch = OIDSET_INIT;\n \n \tif (opt->repo != the_repository || !has_promisor_remote())\n \t\treturn;\n@@ -3939,12 +3939,12 @@ static void prefetch_for_content_merges(struct merge_options *opt,\n \t\t\t    S_ISREG(vi->mode) &&\n \t\t\t    oid_object_info_extended(opt->repo, &vi->oid, NULL,\n \t\t\t\t\t\t     OBJECT_INFO_FOR_PREFETCH))\n-\t\t\t\toid_array_append(&to_fetch, &vi->oid);\n+\t\t\t\toidset_insert(&to_fetch, &vi->oid);\n \t\t}\n \t}\n \n-\tpromisor_remote_get_direct(opt->repo, to_fetch.oid, to_fetch.nr);\n-\toid_array_clear(&to_fetch);\n+\tpromisor_remote_get_direct(opt->repo, &to_fetch);\n+\toidset_clear(&to_fetch);\n }\n \n static void process_entries(struct merge_options *opt,\ndiff --git a/object-file.c b/object-file.c\nindex 8be57f48de7..baec8f099de 100644\n--- a/object-file.c\n+++ b/object-file.c\n@@ -1519,6 +1519,7 @@ static int do_oid_object_info_extended(struct repository *r,\n \tstruct cached_object *co;\n \tstruct pack_entry e;\n \tint rtype;\n+\tstruct oidset to_fetch = OIDSET_INIT;\n \tconst struct object_id *real = oid;\n \tint already_retried = 0;\n \n@@ -1587,7 +1588,8 @@ static int do_oid_object_info_extended(struct repository *r,\n \t\t\t * TODO Investigate checking promisor_remote_get_direct()\n \t\t\t * TODO return value and stopping on error here.\n \t\t\t */\n-\t\t\tpromisor_remote_get_direct(r, real, 1);\n+\t\t\toidset_insert(&to_fetch, real);\n+\t\t\tpromisor_remote_get_direct(r, &to_fetch);\n \t\t\talready_retried = 1;\n \t\t\tcontinue;\n \t\t}\ndiff --git a/promisor-remote.c b/promisor-remote.c\nindex db2ebdc66ef..00166269f60 100644\n--- a/promisor-remote.c\n+++ b/promisor-remote.c\n@@ -12,12 +12,13 @@ struct promisor_remote_config {\n \n static int fetch_objects(struct repository *repo,\n \t\t\t const char *remote_name,\n-\t\t\t const struct object_id *oids,\n-\t\t\t int oid_nr)\n+\t\t\t struct oidset *oids)\n {\n \tstruct child_process child = CHILD_PROCESS_INIT;\n-\tint i;\n \tFILE *child_in;\n+\tstruct oidset_iter iter;\n+\tconst struct object_id *oid;\n+\toidset_iter_init(oids, &iter);\n \n \tchild.git_cmd = 1;\n \tchild.in = -1;\n@@ -31,10 +32,10 @@ static int fetch_objects(struct repository *repo,\n \t\tdie(_(\"promisor-remote: unable to fork off fetch subprocess\"));\n \tchild_in = xfdopen(child.in, \"w\");\n \n-\ttrace2_data_intmax(\"promisor\", repo, \"fetch_count\", oid_nr);\n+\ttrace2_data_intmax(\"promisor\", repo, \"fetch_count\", oidset_size(oids));\n \n-\tfor (i = 0; i < oid_nr; i++) {\n-\t\tif (fputs(oid_to_hex(&oids[i]), child_in) < 0)\n+\twhile((oid = oidset_iter_next(&iter))) {\n+\t\tif (fputs(oid_to_hex(oid), child_in) < 0)\n \t\t\tdie_errno(_(\"promisor-remote: could not write to fetch subprocess\"));\n \t\tif (fputc('\\n', child_in) < 0)\n \t\t\tdie_errno(_(\"promisor-remote: could not write to fetch subprocess\"));\n@@ -198,70 +199,43 @@ int repo_has_promisor_remote(struct repository *r)\n \treturn !!repo_promisor_remote_find(r, NULL);\n }\n \n-static int remove_fetched_oids(struct repository *repo,\n-\t\t\t       struct object_id **oids,\n-\t\t\t       int oid_nr, int to_free)\n+static void remove_fetched_oids(struct repository *repo,\n+\t\t\t       struct oidset *oids)\n {\n-\tint i, remaining_nr = 0;\n-\tint *remaining = xcalloc(oid_nr, sizeof(*remaining));\n-\tstruct object_id *old_oids = *oids;\n-\tstruct object_id *new_oids;\n-\n-\tfor (i = 0; i < oid_nr; i++)\n-\t\tif (oid_object_info_extended(repo, &old_oids[i], NULL,\n-\t\t\t\t\t     OBJECT_INFO_SKIP_FETCH_OBJECT)) {\n-\t\t\tremaining[i] = 1;\n-\t\t\tremaining_nr++;\n-\t\t}\n-\n-\tif (remaining_nr) {\n-\t\tint j = 0;\n-\t\tCALLOC_ARRAY(new_oids, remaining_nr);\n-\t\tfor (i = 0; i < oid_nr; i++)\n-\t\t\tif (remaining[i])\n-\t\t\t\toidcpy(&new_oids[j++], &old_oids[i]);\n-\t\t*oids = new_oids;\n-\t\tif (to_free)\n-\t\t\tfree(old_oids);\n-\t}\n+\tstruct oidset_iter iter;\n+\tconst struct object_id *oid;\n \n-\tfree(remaining);\n+\toidset_iter_init(oids, &iter);\n \n-\treturn remaining_nr;\n+\twhile((oid = oidset_iter_next(&iter)))\n+\t\tif (oid_object_info_extended(repo, oid, NULL,\n+\t\t\t\t\t     OBJECT_INFO_SKIP_FETCH_OBJECT)){\n+\t\t\toidset_remove(oids, oid);\n+\t\t}\n }\n \n int promisor_remote_get_direct(struct repository *repo,\n-\t\t\t       const struct object_id *oids,\n-\t\t\t       int oid_nr)\n+\t\t\t\t       struct oidset *oids)\n {\n \tstruct promisor_remote *r;\n-\tstruct object_id *remaining_oids = (struct object_id *)oids;\n-\tint remaining_nr = oid_nr;\n-\tint to_free = 0;\n \tint res = -1;\n \n-\tif (oid_nr == 0)\n+\tif (oidset_size(oids) == 0)\n \t\treturn 0;\n \n \tpromisor_remote_init(repo);\n \n \tfor (r = repo->promisor_remote_config->promisors; r; r = r->next) {\n-\t\tif (fetch_objects(repo, r->name, remaining_oids, remaining_nr) < 0) {\n-\t\t\tif (remaining_nr == 1)\n+\t\tif (fetch_objects(repo, r->name, oids) < 0) {\n+\t\t\tif (oidset_size(oids) == 1)\n \t\t\t\tcontinue;\n-\t\t\tremaining_nr = remove_fetched_oids(repo, &remaining_oids,\n-\t\t\t\t\t\t\t remaining_nr, to_free);\n-\t\t\tif (remaining_nr) {\n-\t\t\t\tto_free = 1;\n+\t\t\tremove_fetched_oids(repo, oids);\n+\t\t\tif (oidset_size(oids))\n \t\t\t\tcontinue;\n-\t\t\t}\n \t\t}\n \t\tres = 0;\n \t\tbreak;\n \t}\n \n-\tif (to_free)\n-\t\tfree(remaining_oids);\n-\n \treturn res;\n }\ndiff --git a/promisor-remote.h b/promisor-remote.h\nindex edc45ab0f5f..c90837d3592 100644\n--- a/promisor-remote.h\n+++ b/promisor-remote.h\n@@ -3,8 +3,7 @@\n \n #include \"repository.h\"\n \n-struct object_id;\n-\n+struct oidset;\n /*\n  * Promisor remote linked list\n  *\n@@ -45,7 +44,6 @@ static inline int has_promisor_remote(void)\n  * If oid_nr is 0, this function returns 0 (success) immediately.\n  */\n int promisor_remote_get_direct(struct repository *repo,\n-\t\t\t       const struct object_id *oids,\n-\t\t\t       int oid_nr);\n+\t\t\t       struct oidset *oids);\n \n #endif /* PROMISOR_REMOTE_H */\ndiff --git a/read-cache.c b/read-cache.c\nindex cbe73f14e5e..b78801b1f20 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -3732,7 +3732,7 @@ void prefetch_cache_entries(const struct index_state *istate,\n \t\t\t    must_prefetch_predicate must_prefetch)\n {\n \tint i;\n-\tstruct oid_array to_fetch = OID_ARRAY_INIT;\n+\tstruct oidset to_fetch = OIDSET_INIT;\n \n \tfor (i = 0; i < istate->cache_nr; i++) {\n \t\tstruct cache_entry *ce = istate->cache[i];\n@@ -3743,9 +3743,8 @@ void prefetch_cache_entries(const struct index_state *istate,\n \t\t\t\t\t      NULL,\n \t\t\t\t\t      OBJECT_INFO_FOR_PREFETCH))\n \t\t\tcontinue;\n-\t\toid_array_append(&to_fetch, &ce->oid);\n+\t\toidset_insert(&to_fetch, &ce->oid);\n \t}\n-\tpromisor_remote_get_direct(the_repository,\n-\t\t\t\t   to_fetch.oid, to_fetch.nr);\n-\toid_array_clear(&to_fetch);\n+\tpromisor_remote_get_direct(the_repository, &to_fetch);\n+\toidset_clear(&to_fetch);\n }\n\nbase-commit: 1ffcbaa1a5f10c9f706314d77f88de20a4a498c2\n-- \ngitgitgadget\n"},{"id":"446191","messageId":"xmqqilunfber.fsf@gitster.g","threadId":"57240","inReplyTo":"pull.1187.git.git.1642105926064.gitgitgadget@gmail.com","subject":"Re: [PATCH] promisor-remote.c: use oidset for deduplication","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-13T23:45:00Z","receivedAt":"2022-01-13T23:45:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"John Cai via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> diff --git a/object-file.c b/object-file.c\n> index 8be57f48de7..baec8f099de 100644\n> --- a/object-file.c\n> +++ b/object-file.c\n> @@ -1519,6 +1519,7 @@ static int do_oid_object_info_extended(struct repository *r,\n>  \tstruct cached_object *co;\n>  \tstruct pack_entry e;\n>  \tint rtype;\n> +\tstruct oidset to_fetch = OIDSET_INIT;\n>  \tconst struct object_id *real = oid;\n>  \tint already_retried = 0;\n>  \n> @@ -1587,7 +1588,8 @@ static int do_oid_object_info_extended(struct repository *r,\n>  \t\t\t * TODO Investigate checking promisor_remote_get_direct()\n>  \t\t\t * TODO return value and stopping on error here.\n>  \t\t\t */\n> -\t\t\tpromisor_remote_get_direct(r, real, 1);\n> +\t\t\toidset_insert(&to_fetch, real);\n> +\t\t\tpromisor_remote_get_direct(r, &to_fetch);\n>  \t\t\talready_retried = 1;\n>  \t\t\tcontinue;\n>  \t\t}\n\nEverything that migrated from oid_array to oidset should be OK\nbecause it is likely that existing oid_array_clear() would not\ncompile until it is replaced with oidset_clear(), at which point\nthe oidset will be cleared when we are done with it.\n\nHowever, this one did not use an oid_array and did not have to clear\nto release the resources.  So it is very likely that nobody clears\nto_fetch that is introduced by this patch, no?\n\nI suspect that this introduces a new leak.\n"},{"id":"446216","messageId":"220114.86wnj2se41.gmgdl@evledraar.gmail.com","threadId":"57240","inReplyTo":"pull.1187.git.git.1642105926064.gitgitgadget@gmail.com","subject":"Re: [PATCH] promisor-remote.c: use oidset for deduplication","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-01-14T12:11:57Z","receivedAt":"2022-01-14T12:20:35Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, Jan 13 2022, John Cai via GitGitGadget wrote:\n\n> From: John Cai <johncai86@gmail.com>\n>\n> swap out oid_array for oidset in promisor-remote.c since we get\n> a deduplicated set of oids to operate on.\n>\n> swap our calls for oid_array for oidset in callers of\n> promisor_remote_get_direct().\n>\n> Helped-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>\n\nFWIW we had an off-list discussion about oidset v.s. a custom hashmap to\ndo the same off-list, not about s/oid_array/oidset/ in this area.\n\n> Signed-off-by: John Cai <johncai86@gmail.com>\n> ---\n>     promisor-remote.c: use oidset for deduplication\n>     \n>     \n\nExtra \\n between $subject and $body.\n\n>     swap out oid_array for oidset in promisor-remote.c since we get a\n\nNit: s/swap/Swap/, i.e. start the sentence with a capital letter...\n\n>     deduplicated set of oids to operate on. Any direct fetch we can save\n>     will be well worth it.\n>     \n>     oidset does use a slightly larger memory footprint than oid_array, so\n>     this change is a tradeoff between memory footprint and network calls.\n>     \n>     What I'm not sure about is if it's worth swapping out all the calls of\n>     oid_array for oidset in callers of promisor_remote_get_direct().\n\nFrom what I understand of GGG I think you updated only the summary on\nthe PR but not the commit itself, the latter is what would go into\ngit.git. Here the commit should be updated so we get this message.\n\nThe part after the \"---\" is usually just used in this project for ad-hoc\nlist-only comment.\n\n>  builtin/index-pack.c   |  9 +++---\n>  builtin/pack-objects.c |  9 +++---\n>  diff.c                 | 13 +++-----\n>  diffcore-rename.c      | 12 +++----\n>  diffcore.h             |  3 +-\n>  merge-ort.c            |  8 ++---\n>  object-file.c          |  4 ++-\n>  promisor-remote.c      | 72 ++++++++++++++----------------------------\n>  promisor-remote.h      |  6 ++--\n>  read-cache.c           |  9 +++---\n>  10 files changed, 57 insertions(+), 88 deletions(-)\n\nRather than inline comments, a comment that applies to all of these:\n\nThe difference between these two APIs is thaht oidset is hash-backed,\nand you'd insert into it and we de-duplicate any duplicate OIDs on-the-fly.\n\nThe oid_array is just an realloc()'d \"struct object_id *oid\". On\ninsertion you can insert duplicates, but it has the ability to track\n\"I've sorted these\", and \"let's iterate over this sorted, and de-dup any\nduplicates\".\n\nWe have the two APIs for a reason, but I don't know in any of these\ncases whether this change is safe.\n\nDoes e.g. index-pack.c always receive de-duplicated OIDs and we were\nwasting CPU cycles using an oidset?\n\nDo some of these like pack-objects.c receive de-duplicated OIDs from\ne.g. \"git repack\" *now*, but we just lack test coverage to see that\nthey're happy to get duplicate OIDs on stdin (e.g. manually from a\nuser), and this would introduce a bug?\n\nBut most importantly is it worth it? What's the rationale for the\nchange? Less CPU/memory use? Getting e.g. \"hyperfine\" or \"/usr/bin/time\n-v\" output for those (if so) would be valuable.\n"},{"id":"446238","messageId":"xmqqzgnyb03z.fsf@gitster.g","threadId":"57240","inReplyTo":"220114.86wnj2se41.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH] promisor-remote.c: use oidset for deduplication","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-14T19:14:56Z","receivedAt":"2022-01-14T19:15:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:\n\n> From what I understand of GGG I think you updated only the summary on\n> the PR but not the commit itself, the latter is what would go into\n> git.git. Here the commit should be updated so we get this message.\n\nAh, I have long learned to ignore the blurb after the three-dash\nline when a patch comes via GGG (because the PR text is often\nuseless and most often people seem to use text identical to the\ncommit log message).  I didn't realize that the proposed commit log\nmessage was useless in this particular patch.  I was wondering why\nyou were talking about an extra blank line after the title there ;-)\n\n> The part after the \"---\" is usually just used in this project for ad-hoc\n> list-only comment.\n\nTrue.  \"What I'm not sure about is ...\" however does belong to the\nlist-only comment, though.  If it is not \n\n> The difference between these two APIs is thaht oidset is hash-backed,\n> and you'd insert into it and we de-duplicate any duplicate OIDs on-the-fly.\n> \n> The oid_array is just an realloc()'d \"struct object_id *oid\". On\n> insertion you can insert duplicates, but it has the ability to track\n> \"I've sorted these\", and \"let's iterate over this sorted, and de-dup any\n> duplicates\".\n>\n> We have the two APIs for a reason, but I don't know in any of these\n> cases whether this change is safe.\n>\n> Does e.g. index-pack.c always receive de-duplicated OIDs and we were\n> wasting CPU cycles using an oidset?\n>\n> Do some of these like pack-objects.c receive de-duplicated OIDs from\n> e.g. \"git repack\" *now*, but we just lack test coverage to see that\n> they're happy to get duplicate OIDs on stdin (e.g. manually from a\n> user), and this would introduce a bug?\n\nAlso, if oid_array is used to produce a de-duplicated list of object\nnames in the current code, it is very likely that oid_array is\nsorted (perhaps the objects are fed in sorted order), and the\ncallers depend on the order of the objects they find in the array.\nThrowing sorted list of object names at oidset and then iterating\nover what is in the oidset would likely to destroy the original\nordering.  I do not offhand know if the callers are broken by such a\nchange (either correctness-wise or performance-wise).\n\n> But most importantly is it worth it? What's the rationale for the\n> change? Less CPU/memory use? Getting e.g. \"hyperfine\" or \"/usr/bin/time\n> -v\" output for those (if so) would be valuable.\n\nThanks.\n"},{"id":"446263","messageId":"xmqqv8yl9aje.fsf@gitster.g","threadId":"57240","inReplyTo":"xmqqzgnyb03z.fsf@gitster.g","subject":"Re: [PATCH] promisor-remote.c: use oidset for deduplication","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-14T23:12:37Z","receivedAt":"2022-01-14T23:12:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Also, if oid_array is used to produce a de-duplicated list of object\n> names in the current code, it is very likely that oid_array is\n> sorted (perhaps the objects are fed in sorted order), and the\n> callers depend on the order of the objects they find in the array.\n> Throwing sorted list of object names at oidset and then iterating\n> over what is in the oidset would likely to destroy the original\n> ordering.  I do not offhand know if the callers are broken by such a\n> change (either correctness-wise or performance-wise).\n\nSince I had a bit of downtime waiting for CI, I took a look.\n\nIt seems that the list of objects collected in the oidset/oid_array\nis fed to \"git fetch --stdin\" for lazy fetching, so I would be\nsurprised if the order of objects matter.  So I would stop worrying\nabout correctness or performance due to ordering change.\n\n>> But most importantly is it worth it? What's the rationale for the\n>> change? Less CPU/memory use? Getting e.g. \"hyperfine\" or \"/usr/bin/time\n>> -v\" output for those (if so) would be valuable.\n\nBut I still agree with this.  How much duplication would a typical\nrequest for a lazy fetch involve?  Would it cause duplicate \"want\"\nto make the protocol exchange noticeably larger?\n\nHaving said all that, the change makes the code smaller, and\npossibly easier to follow.\n\nThe primary reason why promisor-remote.c::remove_fetched_oids()\nshrinks so much is because we used to scan the array and copied\nthe surviving ones into a new array, while the new code just\niterates over the oidset and removes the ones that were fetched.\nI am assuming that mucking with the oidset's contents while you\nare iterating over it is safe, but if that is not the case, then\nthe advantage of the smaller code disappears.\n\n"},{"id":"446828","messageId":"E5AD42A3-AEAC-44F8-B223-90E2ACAEFCB0@gmail.com","threadId":"57240","inReplyTo":"220114.86wnj2se41.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH] promisor-remote.c: use oidset for deduplication","fromName":"John Cai","fromEmail":"johncai86@gmail.com","sentAt":"2022-01-24T22:55:32Z","receivedAt":"2022-01-25T04:04:56Z","isPatch":true,"sender":{"key":"johncai86@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2354211?v=4"},"body":"\n\nOn 14 Jan 2022, at 7:11, Ævar Arnfjörð Bjarmason wrote:\n\n> On Thu, Jan 13 2022, John Cai via GitGitGadget wrote:\n>\n>> From: John Cai <johncai86@gmail.com>\n>>\n>> swap out oid_array for oidset in promisor-remote.c since we get\n>> a deduplicated set of oids to operate on.\n>>\n>> swap our calls for oid_array for oidset in callers of\n>> promisor_remote_get_direct().\n>>\n>> Helped-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>\n>\n> FWIW we had an off-list discussion about oidset v.s. a custom hashmap to\n> do the same off-list, not about s/oid_array/oidset/ in this area.\n>\n>> Signed-off-by: John Cai <johncai86@gmail.com>\n>> ---\n>>     promisor-remote.c: use oidset for deduplication\n>>\n>>\n>\n> Extra \\n between $subject and $body.\n>\n>>     swap out oid_array for oidset in promisor-remote.c since we get a\n>\n> Nit: s/swap/Swap/, i.e. start the sentence with a capital letter...\n>\n>>     deduplicated set of oids to operate on. Any direct fetch we can save\n>>     will be well worth it.\n>>\n>>     oidset does use a slightly larger memory footprint than oid_array, so\n>>     this change is a tradeoff between memory footprint and network calls.\n>>\n>>     What I'm not sure about is if it's worth swapping out all the calls of\n>>     oid_array for oidset in callers of promisor_remote_get_direct().\n>\n> From what I understand of GGG I think you updated only the summary on\n> the PR but not the commit itself, the latter is what would go into\n> git.git. Here the commit should be updated so we get this message.\n>\n> The part after the \"---\" is usually just used in this project for ad-hoc\n> list-only comment.\n>\n>>  builtin/index-pack.c   |  9 +++---\n>>  builtin/pack-objects.c |  9 +++---\n>>  diff.c                 | 13 +++-----\n>>  diffcore-rename.c      | 12 +++----\n>>  diffcore.h             |  3 +-\n>>  merge-ort.c            |  8 ++---\n>>  object-file.c          |  4 ++-\n>>  promisor-remote.c      | 72 ++++++++++++++----------------------------\n>>  promisor-remote.h      |  6 ++--\n>>  read-cache.c           |  9 +++---\n>>  10 files changed, 57 insertions(+), 88 deletions(-)\n>\n> Rather than inline comments, a comment that applies to all of these:\n>\n> The difference between these two APIs is thaht oidset is hash-backed,\n> and you'd insert into it and we de-duplicate any duplicate OIDs on-the-fly.\n>\n> The oid_array is just an realloc()'d \"struct object_id *oid\". On\n> insertion you can insert duplicates, but it has the ability to track\n> \"I've sorted these\", and \"let's iterate over this sorted, and de-dup any\n> duplicates\".\n>\n> We have the two APIs for a reason, but I don't know in any of these\n> cases whether this change is safe.\n\nTo reduce the footprint of this change, maybe we can just keep oid_array and sort it\nin diff.c before passing it off to promisor_remote_get_direct(), in which we then iterate\nover unique entries.\n>\n> Does e.g. index-pack.c always receive de-duplicated OIDs and we were\n> wasting CPU cycles using an oidset?\n\nGood question. In fact a more immediate question is how often does diff.c receive dupe oids,\nwhich was the original motivation for the change. cc’ing Jonathan as he was involved with\n95acf11a that added the NEEDSWORK block.\n\nJonathan, how often do we expect diff to pass duplicate oids to promisor_remote_get_direct()?\n>\n> Do some of these like pack-objects.c receive de-duplicated OIDs from\n> e.g. \"git repack\" *now*, but we just lack test coverage to see that\n> they're happy to get duplicate OIDs on stdin (e.g. manually from a\n> user), and this would introduce a bug?\n>\n> But most importantly is it worth it? What's the rationale for the\n> change? Less CPU/memory use? Getting e.g. \"hyperfine\" or \"/usr/bin/time\n> -v\" output for those (if so) would be valuable.\n\nI agree this would be very valuable, but I’m thinking more so once I get a better idea of\nwhat kind of situations would lead to duplicate oids in diff.c\n"},{"id":"446867","messageId":"20220125191701.2649292-1-jonathantanmy@google.com","threadId":"57240","inReplyTo":"E5AD42A3-AEAC-44F8-B223-90E2ACAEFCB0@gmail.com","subject":"Re: [PATCH] promisor-remote.c: use oidset for deduplication","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2022-01-25T19:17:01Z","receivedAt":"2022-01-25T19:17:16Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"John Cai <johncai86@gmail.com> writes:\n> Jonathan, how often do we expect diff to pass duplicate oids to\n> promisor_remote_get_direct()?\n\nI don't recall all the details, but not often, I believe. In a partial\nclone, I envision that you would typically diff one tree that you have\nall blobs for and one tree that you don't (or two trees that you have\nall blobs for). If a user is in a sparse checkout and/or they're diffing\ntwo trees that they have never checked out, I would recommend disabling\ninexact copy detection to reduce the number of blobs that Git would need\nto fetch. In these cases, I think that diff would only pass duplicate\nOIDs if one of the trees references the same object more than once\n(directly or indirectly).\n"}]}