{"thread":{"id":"55842","subject":"[PATCH 1/5] promisor-remote: output trace2 statistics for number of objects fetched","startedAt":"2021-06-05T01:28:24Z","lastAt":"2021-06-23T17:31:30Z","messageCount":30,"participants":["Elijah Newren via GitGitGadget","Derrick Stolee","Junio C Hamano","Elijah Newren"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"426452","messageId":"ad9b451d6823f7158a2b58a82682e0c862a1ef6b.1622856485.git.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.git.1622856485.gitgitgadget@gmail.com","subject":"[PATCH 1/5] promisor-remote: output trace2 statistics for number of objects fetched","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-05T01:28:00Z","receivedAt":"2021-06-05T01:28:24Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nSigned-off-by: Elijah Newren \n---\n promisor-remote.c | 7 +++++--\n 1 file changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/promisor-remote.c b/promisor-remote.c\nindex da3f2ca2615e..d465377d7d32 100644\n--- a/promisor-remote.c\n+++ b/promisor-remote.c\n@@ -12,7 +12,8 @@ void set_repository_format_partial_clone(char *partial_clone)\n \trepository_format_partial_clone = xstrdup_or_null(partial_clone);\n }\n \n-static int fetch_objects(const char *remote_name,\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 {\n@@ -30,6 +31,8 @@ static int fetch_objects(const char *remote_name,\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+\n \tfor (i = 0; i < oid_nr; i++) {\n \t\tif (fputs(oid_to_hex(&oids[i]), child_in) < 0)\n \t\t\tdie_errno(_(\"promisor-remote: could not write to fetch subprocess\"));\n@@ -238,7 +241,7 @@ int promisor_remote_get_direct(struct repository *repo,\n \tpromisor_remote_init();\n \n \tfor (r = promisors; r; r = r->next) {\n-\t\tif (fetch_objects(r->name, remaining_oids, remaining_nr) < 0) {\n+\t\tif (fetch_objects(repo, r->name, remaining_oids, remaining_nr) < 0) {\n \t\t\tif (remaining_nr == 1)\n \t\t\t\tcontinue;\n \t\t\tremaining_nr = remove_fetched_oids(repo, &remaining_oids,\n-- \ngitgitgadget\n\n"},{"id":"426453","messageId":"ca3b2a743b8e865e9e105620744f7a5aa16b24a4.1622856485.git.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.git.1622856485.gitgitgadget@gmail.com","subject":"[PATCH 5/5] merge-ort: add prefetching for content merges","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-05T01:28:04Z","receivedAt":"2021-06-05T01:28:24Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nCommit 7fbbcb21b1 (\"diff: batch fetching of missing blobs\", 2019-04-05)\nintroduced batching of fetching missing blobs, so that the diff\nmachinery would have one fetch subprocess grab N blobs instead of N\nprocesses each grabbing 1.\n\nHowever, the diff machinery is not the only thing in a merge that needs\nto work on blobs. The 3-way content merges need them as well. Rather\nthan download all the blobs 1 at a time, prefetch all the blobs needed\nfor regular content merges.\n\nThis does not cover all possible paths in merge-ort that might need to\ndownload blobs. Others include:\n - The blob_unchanged() calls to avoid modify/delete conflicts (when\n blob renormalization results in an \"unchanged\" file)\n - Preliminary content merges needed for rename/add and\n rename/rename(2to1) style conflicts. (Both of these types of\n conflicts can result in nested conflict markers from the need to do\n two levels of content merging; the first happens before our new\n prefetch_for_content_merges() function.)\n\nThe first of these wouldn't be an extreme amount of work to support, and\neven the second could be theoretically supported in batching, but all of\nthese cases seem unusual to me, and this is a minor performance\noptimization anyway; in the worst case we only get some of the fetches\nbatched and have a few additional one-off fetches. So for now, just\nhandle the regular 3-way content merges in our prefetching.\n\nFor the testcase from the previous commit, the number of downloaded\nobjects remains at 63, but this drops the number of fetches needed from\n32 down to 20, a sizeable reduction.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 50 ++++++++++++++++++++++++++++++++++\n t/t6421-merge-partial-clone.sh | 2 +-\n 2 files changed, 51 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex cfa751053b01..e3a5dfc7b312 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -29,6 +29,7 @@\n #include \"entry.h\"\n #include \"ll-merge.h\"\n #include \"object-store.h\"\n+#include \"promisor-remote.h\"\n #include \"revision.h\"\n #include \"strmap.h\"\n #include \"submodule.h\"\n@@ -3485,6 +3486,54 @@ static void process_entry(struct merge_options *opt,\n \trecord_entry_for_tree(dir_metadata, path, &ci->merged);\n }\n \n+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+\n+\tif (opt->repo != the_repository || !has_promisor_remote())\n+\t\treturn;\n+\n+\tfor (e = &plist->items[plist->nr-1]; e >= plist->items; --e) {\n+\t\t/* char *path = e->string; */\n+\t\tstruct conflict_info *ci = e->util;\n+\t\tint i;\n+\n+\t\t/* Ignore clean entries */\n+\t\tif (ci->merged.clean)\n+\t\t\tcontinue;\n+\n+\t\t/* Ignore entries that don't need a content merge */\n+\t\tif (ci->match_mask || ci->filemask < 6 ||\n+\t\t !S_ISREG(ci->stages[1].mode) ||\n+\t\t !S_ISREG(ci->stages[2].mode) ||\n+\t\t oideq(&ci->stages[1].oid, &ci->stages[2].oid))\n+\t\t\tcontinue;\n+\n+\t\t/* Also don't need content merge if base matches either side */\n+\t\tif (ci->filemask == 7 &&\n+\t\t S_ISREG(ci->stages[0].mode) &&\n+\t\t (oideq(&ci->stages[0].oid, &ci->stages[1].oid) ||\n+\t\t oideq(&ci->stages[0].oid, &ci->stages[2].oid)))\n+\t\t\tcontinue;\n+\n+\t\tfor (i = 0; i < 3; i++) {\n+\t\t\tunsigned side_mask = (1 << i);\n+\t\t\tstruct version_info *vi = &ci->stages[i];\n+\n+\t\t\tif ((ci->filemask & side_mask) &&\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}\n+\t}\n+\n+\tpromisor_remote_get_direct(opt->repo, to_fetch.oid, to_fetch.nr);\n+\toid_array_clear(&to_fetch);\n+}\n+\n static void process_entries(struct merge_options *opt,\n \t\t\t struct object_id *result_oid)\n {\n@@ -3531,6 +3580,7 @@ static void process_entries(struct merge_options *opt,\n \t * the way when it is time to process the file at the same path).\n \t */\n \ttrace2_region_enter(\"merge\", \"processing\", opt->repo);\n+\tprefetch_for_content_merges(opt, &plist);\n \tfor (entry = &plist.items[plist.nr-1]; entry >= plist.items; --entry) {\n \t\tchar *path = entry->string;\n \t\t/*\ndiff --git a/t/t6421-merge-partial-clone.sh b/t/t6421-merge-partial-clone.sh\nindex fb7eb18cc80c..84642cb3831c 100755\n--- a/t/t6421-merge-partial-clone.sh\n+++ b/t/t6421-merge-partial-clone.sh\n@@ -392,7 +392,7 @@ test_expect_merge_algorithm failure success 'Objects downloaded when a directory\n #\n # Summary: 4 fetches (1 for 6 objects, 1 for 8, 1 for 3, 1 for 2)\n #\n-test_expect_merge_algorithm failure failure 'Objects downloaded with lots of renames and modifications' '\n+test_expect_merge_algorithm failure success 'Objects downloaded with lots of renames and modifications' '\n \ttest_setup_repo &&\n \tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-many &&\n \t(\n-- \ngitgitgadget\n"},{"id":"426454","messageId":"pull.969.git.1622856485.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":null,"subject":"[PATCH 0/5] Optimization batch 13: partial clone optimizations for merge-ort","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-05T01:27:59Z","receivedAt":"2021-06-05T01:29:26Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series optimizes blob downloading in merges for partial clones. It can\napply on master.\n\n=== Conflict heads up ===\n\nThis series has two minor textual conflicts with\nhttps://lore.kernel.org/git/cover.1622580781.git.jonathantanmy@google.com/,\nbecause we both add a repo parameter to fetch_objects() but Jonathan makes\nadditional other nearby changes. If it'd help, I can rebase my series on his\nif he resolves the GIT_TEST_DEFAULT_HASH=sha256 issue, but I thought I'd\nsend this out while the topic is fresh on Jonathan's mind.\n\n(This topic is semantically and textually independent of my other in-flight\nand not-yet-submitted ort-perf-batch-* topics, so this series need not\ninclude those.)\n\n=== Basic Optimization idea ===\n\nmerge-ort was designed to minimize the computation needed to complete a\nmerge, and much of that (particularly the \"irrelevant rename\"\ndeterminations) also dramatically reduced the amount of data needed for the\nmerge. Reducing the amount of data needed to do computations ought to\nbenefit partial clones as well by enabling them to download less\ninformation. However, my previous series didn't modify the prefetch()\ncommand in diffcore-rename to take advantage of these reduced data\nrequirements. This series changes that.\n\nFurther, although diffcore-rename batched downloads of objects for rename\ndetection, the merge machinery did not do the same for three-way content\nmerges of files. This series adds batch downloading of objects within\nmerge-ort to correct that.\n\n=== Modified performance measurement method ===\n\nThe testcases I've been using so far to measure performance were not run in\na partial clone, so they aren't directly usable for comparison. Further,\npartial clone performance depends on network speed which can be highly\nvariable. So I want to modify one of the existing testcases slightly and\nfocus on two different but more stable metrics:\n\n 1. Number of git fetch operations during rebase\n 2. Number of objects fetched during rebase\n\nThe first of these should already be decent due to Jonathan Tan's work to\nbatch fetching of missing blobs during rename detection (see commit\n7fbbcb21b1 (\"diff: batch fetching of missing blobs\", 2019-04-05)), so we are\nmostly looking to optimize the second but would like to also decrease the\nfirst if possible.\n\nThe testcase we will look at will be a modification of the mega-renames\ntestcase from commit 557ac0350d (\"merge-ort: begin performance work;\ninstrument with trace2_region_* calls\", 2020-10-28). In particular, we\nchange\n\n$ git clone \\\n git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git\n\n\nto\n\n$ git clone --sparse --filter=blob:none \\\n https://github.com/github/linux\n\n\n(The change in clone URL is just to get a server that supports the filter\npredicate.)\n\nWe otherwise keep the test the same (in particular, we do not add any calls\nto \"git-sparse checkout {set,add}\" which means that the resulting repository\nwill only have 7 total blobs from files in the toplevel directory before\nstarting the rebase).\n\n=== Results ===\n\nFor the mega-renames testcase noted above (which rebases 35 commits across\nan upstream with ~26K renames in a partial clone), I found the following\nresults for our metrics of interest:\n\n Number of `git fetch` ops during rebase\n\n Before Series After Series\nmerge-recursive: 62 63\nmerge-ort: 30 20\n\n\n Number of objects fetched during rebase\n\n Before Series After Series\nmerge-recursive: 11423 11423\nmerge-ort: 11391 63\n\n\nSo, we have a significant reduction (factor of ~3 relative to\nmerge-recursive) in the number of git fetch operations that have to be\nperformed in a partial clone to complete the rebase, and a dramatic\nreduction (factor of ~180) in the number of objects that need to be fetched.\n\n=== Summary ===\n\nIt's worth pointing out that merge-ort after the series needs only ~1.8\nblobs per commit being transplanted to complete this particular rebase.\nEssentially, this reinforces the fact the optimization work so far has taken\nrename detection from often being an overwhelmingly costly portion of a\nmerge (leading many to just capitulate on it), to what I have observed in my\nexperience so far as being just a minor cost for merges.\n\nElijah Newren (5):\n promisor-remote: output trace2 statistics for number of objects\n fetched\n t6421: add tests checking for excessive object downloads during merge\n diffcore-rename: allow different missing_object_cb functions\n diffcore-rename: use a different prefetch for basename comparisons\n merge-ort: add prefetching for content merges\n\n diffcore-rename.c | 149 +++++++++---\n merge-ort.c | 50 ++++\n promisor-remote.c | 7 +-\n t/t6421-merge-partial-clone.sh | 433 +++++++++++++++++++++++++++++++++\n 4 files changed, 605 insertions(+), 34 deletions(-)\n create mode 100755 t/t6421-merge-partial-clone.sh\n\n\nbase-commit: 01352fcdf3a96480ffa4e25a103a83a9e5d7f67a\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-969%2Fnewren%2Fort-perf-batch-13-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-969/newren/ort-perf-batch-13-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/969\n-- \ngitgitgadget\n"},{"id":"426455","messageId":"c4b3109c3b08d549b5ac698edd331639ed6280e2.1622856485.git.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.git.1622856485.gitgitgadget@gmail.com","subject":"[PATCH 3/5] diffcore-rename: allow different missing_object_cb functions","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-05T01:28:02Z","receivedAt":"2021-06-05T01:29:26Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nestimate_similarity() was setting up a diff_populate_filespec_options\nevery time it was called, requiring the caller of estimate_similarity()\nto pass in some data needed to set up this option. Currently the needed\ndata consisted of a single variable (skip_unmodified), but we want to\nalso have the different estimate_similarity() callsites start using\ndifferent missing_object_cb functions as well. Rather than also passing\nthat data in, just have the caller pass in the whole\ndiff_populate_filespec_options, and reduce the number of times we need to\nset it up.\n\nAs a side note, this also drops the number of calls to\nhas_promisor_remote() dramatically. If L is the number of basename\npaths to compare, M is the number of inexact sources, and N is the\nnumber of inexact destinations, then the number of calls to\nhas_promisor_remote() drops from L+M*N down to at most 2 -- one for each\nof the sites that calls estimate_similarity(). has_promisor_remote() is\na very fast function so this almost certainly has no measurable\nperformance impact, but it seems cleaner to avoid calling that function\nso many times.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 58 +++++++++++++++++++++++++++++++----------------\n 1 file changed, 39 insertions(+), 19 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 35378d84e8f1..e13e52046026 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -126,7 +126,7 @@ static int estimate_similarity(struct repository *r,\n \t\t\t struct diff_filespec *src,\n \t\t\t struct diff_filespec *dst,\n \t\t\t int minimum_score,\n-\t\t\t int skip_unmodified)\n+\t\t\t struct diff_populate_filespec_options *dpf_opt)\n {\n \t/* src points at a file that existed in the original tree (or\n \t * optionally a file in the destination tree) and dst points\n@@ -143,15 +143,6 @@ static int estimate_similarity(struct repository *r,\n \t */\n \tunsigned long max_size, delta_size, base_size, src_copied, literal_added;\n \tint score;\n-\tstruct diff_populate_filespec_options dpf_options = {\n-\t\t.check_size_only = 1\n-\t};\n-\tstruct prefetch_options prefetch_options = {r, skip_unmodified};\n-\n-\tif (r == the_repository && has_promisor_remote()) {\n-\t\tdpf_options.missing_object_cb = prefetch;\n-\t\tdpf_options.missing_object_data = &prefetch_options;\n-\t}\n \n \t/* We deal only with regular files. Symlink renames are handled\n \t * only when they are exact matches --- in other words, no edits\n@@ -169,11 +160,13 @@ static int estimate_similarity(struct repository *r,\n \t * is a possible size - we really should have a flag to\n \t * say whether the size is valid or not!)\n \t */\n+\tdpf_opt->check_size_only = 1;\n+\n \tif (!src->cnt_data &&\n-\t diff_populate_filespec(r, src, &dpf_options))\n+\t diff_populate_filespec(r, src, dpf_opt))\n \t\treturn 0;\n \tif (!dst->cnt_data &&\n-\t diff_populate_filespec(r, dst, &dpf_options))\n+\t diff_populate_filespec(r, dst, dpf_opt))\n \t\treturn 0;\n \n \tmax_size = ((src->size > dst->size) ? src->size : dst->size);\n@@ -191,11 +184,11 @@ static int estimate_similarity(struct repository *r,\n \tif (max_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)\n \t\treturn 0;\n \n-\tdpf_options.check_size_only = 0;\n+\tdpf_opt->check_size_only = 0;\n \n-\tif (!src->cnt_data && diff_populate_filespec(r, src, &dpf_options))\n+\tif (!src->cnt_data && diff_populate_filespec(r, src, dpf_opt))\n \t\treturn 0;\n-\tif (!dst->cnt_data && diff_populate_filespec(r, dst, &dpf_options))\n+\tif (!dst->cnt_data && diff_populate_filespec(r, dst, dpf_opt))\n \t\treturn 0;\n \n \tif (diffcore_count_changes(r, src, dst,\n@@ -862,7 +855,11 @@ static int find_basename_matches(struct diff_options *options,\n \tint i, renames = 0;\n \tstruct strintmap sources;\n \tstruct strintmap dests;\n-\n+\tstruct diff_populate_filespec_options dpf_options = {\n+\t\t.check_binary = 0,\n+\t\t.missing_object_cb = NULL,\n+\t\t.missing_object_data = NULL\n+\t};\n \t/*\n \t * The prefeteching stuff wants to know if it can skip prefetching\n \t * blobs that are unmodified...and will then do a little extra work\n@@ -873,7 +870,10 @@ static int find_basename_matches(struct diff_options *options,\n \t * the extra work necessary to check if rename_src entries are\n \t * unmodified would be a small waste.\n \t */\n-\tint skip_unmodified = 0;\n+\tstruct prefetch_options prefetch_options = {\n+\t\t.repo = options->repo,\n+\t\t.skip_unmodified = 0\n+\t};\n \n \t/*\n \t * Create maps of basename -> fullname(s) for remaining sources and\n@@ -910,6 +910,11 @@ static int find_basename_matches(struct diff_options *options,\n \t\t\tstrintmap_set(&dests, base, i);\n \t}\n \n+\tif (options->repo == the_repository && has_promisor_remote()) {\n+\t\tdpf_options.missing_object_cb = prefetch;\n+\t\tdpf_options.missing_object_data = &prefetch_options;\n+\t}\n+\n \t/* Now look for basename matchups and do similarity estimation */\n \tfor (i = 0; i < rename_src_nr; ++i) {\n \t\tchar *filename = rename_src[i].p->one->path;\n@@ -953,7 +958,7 @@ static int find_basename_matches(struct diff_options *options,\n \t\t\tone = rename_src[src_index].p->one;\n \t\t\ttwo = rename_dst[dst_index].p->two;\n \t\t\tscore = estimate_similarity(options->repo, one, two,\n-\t\t\t\t\t\t minimum_score, skip_unmodified);\n+\t\t\t\t\t\t minimum_score, &dpf_options);\n \n \t\t\t/* If sufficiently similar, record as rename pair */\n \t\t\tif (score < minimum_score)\n@@ -1272,6 +1277,14 @@ void diffcore_rename_extended(struct diff_options *options,\n \tint num_sources, want_copies;\n \tstruct progress *progress = NULL;\n \tstruct dir_rename_info info;\n+\tstruct diff_populate_filespec_options dpf_options = {\n+\t\t.check_binary = 0,\n+\t\t.missing_object_cb = NULL,\n+\t\t.missing_object_data = NULL\n+\t};\n+\tstruct prefetch_options prefetch_options = {\n+\t\t.repo = options->repo\n+\t};\n \n \ttrace2_region_enter(\"diff\", \"setup\", options->repo);\n \tinfo.setup = 0;\n@@ -1433,6 +1446,13 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t\t\t(uint64_t)num_destinations * (uint64_t)num_sources);\n \t}\n \n+\t/* Finish setting up dpf_options */\n+\tprefetch_options.skip_unmodified = skip_unmodified;\n+\tif (options->repo == the_repository && has_promisor_remote()) {\n+\t\tdpf_options.missing_object_cb = prefetch;\n+\t\tdpf_options.missing_object_data = &prefetch_options;\n+\t}\n+\n \tCALLOC_ARRAY(mx, st_mult(NUM_CANDIDATE_PER_DST, num_destinations));\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n \t\tstruct diff_filespec *two = rename_dst[i].p->two;\n@@ -1458,7 +1478,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t\tthis_src.score = estimate_similarity(options->repo,\n \t\t\t\t\t\t\t one, two,\n \t\t\t\t\t\t\t minimum_score,\n-\t\t\t\t\t\t\t skip_unmodified);\n+\t\t\t\t\t\t\t &dpf_options);\n \t\t\tthis_src.name_score = basename_same(one, two);\n \t\t\tthis_src.dst = i;\n \t\t\tthis_src.src = j;\n-- \ngitgitgadget\n\n"},{"id":"426456","messageId":"6462bb63310dbc889a3442951ef261bc7fd7e0dc.1622856485.git.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.git.1622856485.gitgitgadget@gmail.com","subject":"[PATCH 2/5] t6421: add tests checking for excessive object downloads during merge","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-05T01:28:01Z","receivedAt":"2021-06-05T01:29:26Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nSigned-off-by: Elijah Newren \n---\n t/t6421-merge-partial-clone.sh | 433 +++++++++++++++++++++++++++++++++\n 1 file changed, 433 insertions(+)\n create mode 100755 t/t6421-merge-partial-clone.sh\n\ndiff --git a/t/t6421-merge-partial-clone.sh b/t/t6421-merge-partial-clone.sh\nnew file mode 100755\nindex 000000000000..028d876be2c8\n--- /dev/null\n+++ b/t/t6421-merge-partial-clone.sh\n@@ -0,0 +1,433 @@\n+#!/bin/sh\n+\n+test_description=\"limiting blob downloads when merging with partial clones\"\n+# Uses a methodology similar to\n+# t6042: corner cases with renames but not criss-cross merges\n+# t6036: corner cases with both renames and criss-cross merges\n+# t6423: directory rename detection\n+#\n+# The setup for all of them, pictorially, is:\n+#\n+# A\n+# o\n+# / \\\n+# O o ?\n+# \\ /\n+# o\n+# B\n+#\n+# To help make it easier to follow the flow of tests, they have been\n+# divided into sections and each test will start with a quick explanation\n+# of what commits O, A, and B contain.\n+#\n+# Notation:\n+# z/{b,c} means files z/b and z/c both exist\n+# x/d_1 means file x/d exists with content d1. (Purpose of the\n+# underscore notation is to differentiate different\n+# files that might be renamed into each other's paths.)\n+\n+. ./test-lib.sh\n+. \"$TEST_DIRECTORY\"/lib-merge.sh\n+\n+test_setup_repo () {\n+\ttest -d server && return\n+\ttest_create_repo server &&\n+\t(\n+\t\tcd server &&\n+\n+\t\tgit config uploadpack.allowfilter 1 &&\n+\t\tgit config uploadpack.allowanysha1inwant 1 &&\n+\n+\t\tmkdir -p general &&\n+\t\ttest_seq 2 9 >general/leap1 &&\n+\t\tcp general/leap1 general/leap2 &&\n+\t\techo leap2 >>general/leap2 &&\n+\n+\t\tmkdir -p basename &&\n+\t\tcp general/leap1 basename/numbers &&\n+\t\tcp general/leap1 basename/sequence &&\n+\t\tcp general/leap1 basename/values &&\n+\t\techo numbers >>basename/numbers &&\n+\t\techo sequence >>basename/sequence &&\n+\t\techo values >>basename/values &&\n+\n+\t\tmkdir -p dir/unchanged &&\n+\t\tmkdir -p dir/subdir/tweaked &&\n+\t\techo a >dir/subdir/a &&\n+\t\techo b >dir/subdir/b &&\n+\t\techo c >dir/subdir/c &&\n+\t\techo d >dir/subdir/d &&\n+\t\techo e >dir/subdir/e &&\n+\t\tcp general/leap1 dir/subdir/Makefile &&\n+\t\techo toplevel makefile >>dir/subdir/Makefile &&\n+\t\techo f >dir/subdir/tweaked/f &&\n+\t\techo g >dir/subdir/tweaked/g &&\n+\t\techo h >dir/subdir/tweaked/h &&\n+\t\techo subdirectory makefile >dir/subdir/tweaked/Makefile &&\n+\t\tfor i in `test_seq 1 88`; do\n+\t\t\techo content $i >dir/unchanged/file_$i\n+\t\tdone &&\n+\t\tgit add . &&\n+\t\tgit commit -m \"O\" &&\n+\n+\t\tgit branch O &&\n+\t\tgit branch A &&\n+\t\tgit branch B-single &&\n+\t\tgit branch B-dir &&\n+\t\tgit branch B-many &&\n+\n+\t\tgit switch A &&\n+\n+\t\tgit rm general/leap* &&\n+\t\tmkdir general/ &&\n+\t\ttest_seq 1 9 >general/jump1 &&\n+\t\tcp general/jump1 general/jump2 &&\n+\t\techo leap2 >>general/jump2 &&\n+\n+\t\trm basename/numbers basename/sequence basename/values &&\n+\t\tmkdir -p basename/subdir/\n+\t\tcp general/jump1 basename/subdir/numbers &&\n+\t\tcp general/jump1 basename/subdir/sequence &&\n+\t\tcp general/jump1 basename/subdir/values &&\n+\t\techo numbers >>basename/subdir/numbers &&\n+\t\techo sequence >>basename/subdir/sequence &&\n+\t\techo values >>basename/subdir/values &&\n+\n+\t\tgit rm dir/subdir/tweaked/f &&\n+\t\techo more >>dir/subdir/e &&\n+\t\techo more >>dir/subdir/Makefile &&\n+\t\techo more >>dir/subdir/tweaked/Makefile &&\n+\t\tmkdir dir/subdir/newsubdir &&\n+\t\techo rust code >dir/subdir/newsubdir/newfile.rs &&\n+\t\tgit mv dir/subdir/e dir/subdir/newsubdir/ &&\n+\t\tgit mv dir folder &&\n+\t\tgit add . &&\n+\t\tgit commit -m \"A\" &&\n+\n+\t\tgit switch B-single &&\n+\t\techo new first line >dir/subdir/Makefile &&\n+\t\tcat general/leap1 >>dir/subdir/Makefile &&\n+\t\techo toplevel makefile >>dir/subdir/Makefile &&\n+\t\techo perl code >general/newfile.pl &&\n+\t\tgit add . &&\n+\t\tgit commit -m \"B-single\" &&\n+\n+\t\tgit switch B-dir &&\n+\t\techo java code >dir/subdir/newfile.java &&\n+\t\techo scala code >dir/subdir/newfile.scala &&\n+\t\techo groovy code >dir/subdir/newfile.groovy &&\n+\t\tgit add . &&\n+\t\tgit commit -m \"B-dir\" &&\n+\n+\t\tgit switch B-many &&\n+\t\ttest_seq 2 10 >general/leap1 &&\n+\t\trm general/leap2 &&\n+\t\tcp general/leap1 general/leap2 &&\n+\t\techo leap2 >>general/leap2 &&\n+\n+\t\trm basename/numbers basename/sequence basename/values &&\n+\t\tmkdir -p basename/subdir/\n+\t\tcp general/leap1 basename/subdir/numbers &&\n+\t\tcp general/leap1 basename/subdir/sequence &&\n+\t\tcp general/leap1 basename/subdir/values &&\n+\t\techo numbers >>basename/subdir/numbers &&\n+\t\techo sequence >>basename/subdir/sequence &&\n+\t\techo values >>basename/subdir/values &&\n+\n+\t\tmkdir dir/subdir/newsubdir/ &&\n+\t\techo c code >dir/subdir/newfile.c &&\n+\t\techo python code >dir/subdir/newsubdir/newfile.py &&\n+\t\tgit add . &&\n+\t\tgit commit -m \"B-many\" &&\n+\n+\t\tgit switch A\n+\t)\n+}\n+\n+# Testcase: Objects downloaded for single relevant rename\n+# Commit O:\n+# general/{leap1_O, leap2_O}\n+# basename/{numbers_O, sequence_O, values_O}\n+# dir/subdir/{a,b,c,d,e_O,Makefile_TOP_O}\n+# dir/subdir/tweaked/{f,g,h,Makefile_SUB_O}\n+# dir/unchanged/\n+# Commit A:\n+# (Rename leap->jump, rename basename/ -> basename/subdir/, rename dir/\n+# -> folder/, move e into newsubdir, add newfile.rs, remove f, modify\n+# both both Makefiles and jumps)\n+# general/{jump1_A, jump2_A}\n+# basename/subdir/{numbers_A, sequence_A, values_A}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_A}\n+# folder/subdir/newsubdir/{e_A,newfile.rs}\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A}\n+# folder/unchanged/\n+# Commit B(-single):\n+# (add newfile.pl, tweak Makefile_TOP)\n+# general/{leap1_O, leap2_O,newfile.pl}\n+# basename/{numbers_O, sequence_O, values_O}\n+# dir/{a,b,c,d,e_O,Makefile_TOP_B}\n+# dir/tweaked/{f,g,h,Makefile_SUB_O}\n+# dir/unchanged/\n+# Expected:\n+# general/{jump1_A, jump2_A,newfile.pl}\n+# basename/subdir/{numbers_A, sequence_A, values_A}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_Merged}\n+# folder/subdir/newsubdir/{e_A,newfile.rs}\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A}\n+# folder/unchanged/\n+#\n+# Objects that need to be fetched:\n+# Rename detection:\n+# Side1 (O->A):\n+# Basename-matches rename detection only needs to fetch these objects:\n+# Makefile_TOP_O, Makefile_TOP_A\n+# (Despite many renames, all others are content irrelevant. They\n+# are also location irrelevant because newfile.rs was added on\n+# the side doing the directory rename, and newfile.pl was added to\n+# a directory that was not renamed on either side.)\n+# General rename detection only needs to fetch these objects:\n+# \n+# (Even though newfile.rs, jump[12], basename/subdir/*, and e\n+# could all be used as destinations in rename detection, the\n+# basename detection for Makefile matches up all relevant\n+# sources, so these other files never end up needing to be\n+# used)\n+# Side2 (O->B):\n+# Basename-matches rename detection only needs to fetch these objects:\n+# \n+# (there are no deleted files, so no possible sources)\n+# General rename detection only needs to fetch these objects:\n+# \n+# (there are no deleted files, so no possible sources)\n+# Merge:\n+# 3-way content merge needs to grab these objects:\n+# Makefile_TOP_B\n+# Nothing else needs to fetch objects\n+#\n+# Summary: 2 fetches (1 for 2 objects, 1 for 1 object)\n+#\n+test_expect_merge_algorithm failure failure 'Objects downloaded for single relevant rename' '\n+\ttest_setup_repo &&\n+\tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-single &&\n+\t(\n+\t\tcd objects-single &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep '\\?' >missing-objects-before &&\n+\n+\t\tgit checkout -q origin/A &&\n+\n+\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git -c merge.directoryRenames=true merge --no-stat --no-progress origin/B-single &&\n+\n+\t\t# Check the number of objects we reported we would fetch\n+\t\tcat >expect <<-EOF &&\n+\t\t ..........fetch_count:2\n+\t\t ......fetch_count:1\n+\t\tEOF\n+\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 >actual &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\t# Check the number of fetch commands exec-ed\n+\t\tgrep d0.*fetch.negotiationAlgorithm trace.output >fetches &&\n+\t\ttest_line_count = 2 fetches &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep ^? >missing-objects-after &&\n+\t\ttest_cmp missing-objects-before missing-objects-after |\n+\t\t\tgrep \"^[-+]?\" >found-and-new-objects &&\n+\t\t# We should not have any NEW missing objects\n+\t\t! grep ^+ found-and-new-objects &&\n+\t\t# Fetched 2+1=3 objects, so should have 3 fewer missing objects\n+\t\ttest_line_count = 3 found-and-new-objects\n+\t)\n+'\n+\n+# Testcase: Objects downloaded for directory rename\n+# Commit O:\n+# general/{leap1_O, leap2_O}\n+# basename/{numbers_O, sequence_O, values_O}\n+# dir/subdir/{a,b,c,d,e_O,Makefile_TOP_O}\n+# dir/subdir/tweaked/{f,g,h,Makefile_SUB_O}\n+# dir/unchanged/\n+# Commit A:\n+# (Rename leap->jump, rename basename/ -> basename/subdir/, rename dir/ ->\n+# folder/, move e into newsubdir, add newfile.rs, remove f, modify\n+# both Makefiles and jumps)\n+# general/{jump1_A, jump2_A}\n+# basename/subdir/{numbers_A, sequence_A, values_A}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_A}\n+# folder/subdir/newsubdir/{e_A,newfile.rs}\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A}\n+# folder/unchanged/\n+# Commit B(-dir):\n+# (add dir/subdir/newfile.{java,scala,groovy}\n+# general/{leap1_O, leap2_O}\n+# basename/{numbers_O, sequence_O, values_O}\n+# dir/subdir/{a,b,c,d,e_O,Makefile_TOP_O,\n+# newfile.java,newfile.scala,newfile.groovy}\n+# dir/subdir/tweaked/{f,g,h,Makefile_SUB_O}\n+# dir/unchanged/\n+# Expected:\n+# general/{jump1_A, jump2_A}\n+# basename/subdir/{numbers_A, sequence_A, values_A}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_A,\n+# newfile.java,newfile.scala,newfile.groovy}\n+# folder/subdir/newsubdir/{e_A,newfile.rs}\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A}\n+# folder/unchanged/\n+#\n+# Objects that need to be fetched:\n+# Makefile_TOP_O, Makefile_TOP_A\n+# Makefile_SUB_O, Makefile_SUB_A\n+# e_O, e_A\n+# * Despite A's rename of jump->leap, those renames are irrelevant.\n+# * Despite A's rename of basename/ -> basename/subdir/, those renames are\n+# irrelevant.\n+# * Because of A's rename of dir/ -> folder/ and B-dir's addition of\n+# newfile.* into dir/subdir/, we need to determine directory renames.\n+# (Technically, there are enough exact renames to determine directory\n+# rename detection, but the current implementation always does\n+# basename searching before directory rename detection. Running it\n+# also before basename searching would mean doing directory rename\n+# detection twice, but it's a bit expensive to do that and cases like\n+# this are not all that common.)\n+# Summary: 1 fetches for 6 objects\n+#\n+test_expect_merge_algorithm failure failure 'Objects downloaded when a directory rename triggered' '\n+\ttest_setup_repo &&\n+\tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-dir &&\n+\t(\n+\t\tcd objects-dir &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep '\\?' >missing-objects-before &&\n+\n+\t\tgit checkout -q origin/A &&\n+\n+\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git -c merge.directoryRenames=true merge --no-stat --no-progress origin/B-dir &&\n+\n+\t\t# Check the number of objects we reported we would fetch\n+\t\tcat >expect <<-EOF &&\n+\t\t ..........fetch_count:6\n+\t\tEOF\n+\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 >actual &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\t# Check the number of fetch commands exec-ed\n+\t\tgrep d0.*fetch.negotiationAlgorithm trace.output >fetches &&\n+\t\ttest_line_count = 1 fetches &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep ^? >missing-objects-after &&\n+\t\ttest_cmp missing-objects-before missing-objects-after |\n+\t\t\tgrep \"^[-+]?\" >found-and-new-objects &&\n+\t\t# We should not have any NEW missing objects\n+\t\t! grep ^+ found-and-new-objects &&\n+\t\t# Fetched 6 objects, so should have 6 fewer missing objects\n+\t\ttest_line_count = 6 found-and-new-objects\n+\t)\n+'\n+\n+# Testcase: Objects downloaded with lots of renames and modifications\n+# Commit O:\n+# general/{leap1_O, leap2_O}\n+# basename/{numbers_O, sequence_O, values_O}\n+# dir/subdir/{a,b,c,d,e_O,Makefile_TOP_O}\n+# dir/subdir/tweaked/{f,g,h,Makefile_SUB_O}\n+# dir/unchanged/\n+# Commit A:\n+# (Rename leap->jump, rename basename/ -> basename/subdir/, rename dir/\n+# -> folder/, move e into newsubdir, add newfile.rs, remove f, modify\n+# both both Makefiles and jumps)\n+# general/{jump1_A, jump2_A}\n+# basename/subdir/{numbers_A, sequence_A, values_A}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_A}\n+# folder/subdir/newsubdir/{e_A,newfile.rs}\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A}\n+# folder/unchanged/\n+# Commit B(-minimal):\n+# (modify both leaps, rename basename/ -> basename/subdir/, add\n+# newfile.{c,py})\n+# general/{leap1_B, leap2_B}\n+# basename/subdir/{numbers_B, sequence_B, values_B}\n+# dir/{a,b,c,d,e_O,Makefile_TOP_O,newfile.c}\n+# dir/tweaked/{f,g,h,Makefile_SUB_O,newfile.py}\n+# dir/unchanged/\n+# Expected:\n+# general/{jump1_Merged, jump2_Merged}\n+# basename/subdir/{numbers_Merged, sequence_Merged, values_Merged}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_A,newfile.c}\n+# folder/subdir/newsubdir/e_A\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A,newfile.py}\n+# folder/unchanged/\n+#\n+# Objects that need to be fetched:\n+# Rename detection:\n+# Side1 (O->A):\n+# Basename-matches rename detection only needs to fetch these objects:\n+# numbers_O, numbers_A\n+# sequence_O, sequence_A\n+# values_O, values_A\n+# Makefile_TOP_O, Makefile_TOP_A\n+# Makefile_SUB_O, Makefile_SUB_A\n+# e_O, e_A\n+# General rename detection only needs to fetch these objects:\n+# leap1_O, leap2_O\n+# jump1_A, jump2_A, newfile.rs\n+# (only need remaining relevant sources, but any relevant sources need\n+# to be matched against all possible unpaired destinations)\n+# Side2 (O->B):\n+# Basename-matches rename detection only needs to fetch these objects:\n+# numbers_B\n+# sequence_B\n+# values_B\n+# (because numbers_O, sequence_O, and values_O already fetched above)\n+# General rename detection only needs to fetch these objects:\n+# \n+# Merge:\n+# 3-way content merge needs to grab these objects:\n+# leap1_B\n+# leap2_B\n+# Nothing else needs to fetch objects\n+#\n+# Summary: 4 fetches (1 for 6 objects, 1 for 8, 1 for 3, 1 for 2)\n+#\n+test_expect_merge_algorithm failure failure 'Objects downloaded with lots of renames and modifications' '\n+\ttest_setup_repo &&\n+\tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-many &&\n+\t(\n+\t\tcd objects-many &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep '\\?' >missing-objects-before &&\n+\n+\t\tgit checkout -q origin/A &&\n+\n+\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git -c merge.directoryRenames=true merge --no-stat --no-progress origin/B-many &&\n+\n+\t\t# Check the number of objects we reported we would fetch\n+\t\tcat >expect <<-EOF &&\n+\t\t ..........fetch_count:12\n+\t\t ..........fetch_count:5\n+\t\t ..........fetch_count:3\n+\t\t ......fetch_count:2\n+\t\tEOF\n+\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 >actual &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\t# Check the number of fetch commands exec-ed\n+\t\tgrep d0.*fetch.negotiationAlgorithm trace.output >fetches &&\n+\t\ttest_line_count = 4 fetches &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep ^? >missing-objects-after &&\n+\t\ttest_cmp missing-objects-before missing-objects-after |\n+\t\t\tgrep \"^[-+]?\" >found-and-new-objects &&\n+\t\t# We should not have any NEW missing objects\n+\t\t! grep ^+ found-and-new-objects &&\n+\t\t# Fetched 12 + 5 + 3 + 2 == 22 objects\n+\t\ttest_line_count = 22 found-and-new-objects\n+\t)\n+'\n+\n+test_done\n-- \ngitgitgadget\n\n"},{"id":"426457","messageId":"f4ade3996d3f2ee5d0ce52469062a1b3290f5b11.1622856485.git.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.git.1622856485.gitgitgadget@gmail.com","subject":"[PATCH 4/5] diffcore-rename: use a different prefetch for basename comparisons","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-05T01:28:03Z","receivedAt":"2021-06-05T01:29:28Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nmerge-ort was designed to minimize the amount of data needed and used,\nand several changes were made to diffcore-rename to take advantage of\nextra metadata to enable this data minimization (particularly the\nrelevant_sources variable for skipping \"irrelevant\" renames). This\neffort obviously succeeded in drastically reducing computation times,\nbut should also theoretically allow partial clones to download much less\ninformation. Previously, though, the \"prefetch\" command used in\ndiffcore-rename had never been modified and downloaded many blobs that\nwere unnecessary for merge-ort. This commit corrects that.\n\nWhen doing basename comparisons, we want to fetch only the objects that\nwill be used for basename comparisons. If after basename fetching this\nleaves us with no more relevant sources (or no more destinations), then\nwe won't need to do the full inexact rename detection and can skip\ndownloading additional source and destination files. Even if we have to\ndo that later full inexact rename detection, irrelevant sources are\nculled after basename matching and before the full inexact rename\ndetection, so we can still avoid downloading the blobs for irrelevant\nsources. Rename prefetch() to inexact_prefetch(), and introduce a\nnew basename_prefetch() to take advantage of this.\n\nIf we modify the testcase from commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2021-01-23)\nto pass\n --sparse --filter=blob:none\nto the clone command, and use the new trace2 \"fetch_count\" output from\na few commits ago to track both the number of fetch subcommands invoked\nand the number of objects fetched across all those fetches, then for\nthe mega-renames testcase we observe the following:\n\nBEFORE this commit, rebasing 35 patches:\n strategy # of fetches total # of objects fetched\n --------- ------------ --------------------------\n recursive 62 11423\n ort 30 11391\n\nAFTER this commit, rebasing the same 35 patches:\n ort 32 63\n\nThis means that the new code only needs to download less than 2 blobs\nper patch being rebased. That is especially interesting given that the\nrepository at the start only had approximately half a dozen TOTAL blobs\ndownloaded to start with (because the default sparse-checkout of just\nthe toplevel directory was in use).\n\nSo, for this particular linux kernel testcase that involved ~26,000\nrenames on the upstream side (drivers/ -> pilots/) across which 35\npatches were being rebased, this change reduces the number of blobs that\nneed to be downloaded by a factor of ~180.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 101 +++++++++++++++++++++++++++------\n t/t6421-merge-partial-clone.sh | 4 +-\n 2 files changed, 85 insertions(+), 20 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex e13e52046026..4ef0459cfb50 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -87,13 +87,13 @@ struct diff_score {\n \tshort name_score;\n };\n \n-struct prefetch_options {\n+struct inexact_prefetch_options {\n \tstruct repository *repo;\n \tint skip_unmodified;\n };\n-static void prefetch(void *prefetch_options)\n+static void inexact_prefetch(void *prefetch_options)\n {\n-\tstruct prefetch_options *options = prefetch_options;\n+\tstruct inexact_prefetch_options *options = prefetch_options;\n \tint i;\n \tstruct oid_array to_fetch = OID_ARRAY_INIT;\n \n@@ -816,6 +816,78 @@ static int idx_possible_rename(char *filename, struct dir_rename_info *info)\n \treturn idx;\n }\n \n+struct basename_prefetch_options {\n+\tstruct repository *repo;\n+\tstruct strintmap *relevant_sources;\n+\tstruct strintmap *sources;\n+\tstruct strintmap *dests;\n+\tstruct dir_rename_info *info;\n+};\n+static void basename_prefetch(void *prefetch_options)\n+{\n+\tstruct basename_prefetch_options *options = prefetch_options;\n+\tstruct strintmap *relevant_sources = options->relevant_sources;\n+\tstruct strintmap *sources = options->sources;\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+\n+\t/*\n+\t * TODO: The following loops mirror the code/logic from\n+\t * find_basename_matches(), though not quite exactly. Maybe\n+\t * abstract the iteration logic out somehow?\n+\t */\n+\tfor (i = 0; i < rename_src_nr; ++i) {\n+\t\tchar *filename = rename_src[i].p->one->path;\n+\t\tconst char *base = NULL;\n+\t\tintptr_t src_index;\n+\t\tintptr_t dst_index;\n+\n+\t\t/* Skip irrelevant sources */\n+\t\tif (relevant_sources &&\n+\t\t !strintmap_contains(relevant_sources, filename))\n+\t\t\tcontinue;\n+\n+\t\t/*\n+\t\t * If the basename is unique among remaining sources, then\n+\t\t * src_index will equal 'i' and we can attempt to match it\n+\t\t * to a unique basename in the destinations. Otherwise,\n+\t\t * use directory rename heuristics, if possible.\n+\t\t */\n+\t\tbase = get_basename(filename);\n+\t\tsrc_index = strintmap_get(sources, base);\n+\t\tassert(src_index == -1 || src_index == i);\n+\n+\t\tif (strintmap_contains(dests, base)) {\n+\t\t\tstruct diff_filespec *one, *two;\n+\n+\t\t\t/* Find a matching destination, if possible */\n+\t\t\tdst_index = strintmap_get(dests, base);\n+\t\t\tif (src_index == -1 || dst_index == -1) {\n+\t\t\t\tsrc_index = i;\n+\t\t\t\tdst_index = idx_possible_rename(filename, info);\n+\t\t\t}\n+\t\t\tif (dst_index == -1)\n+\t\t\t\tcontinue;\n+\n+\t\t\t/* Ignore this dest if already used in a rename */\n+\t\t\tif (rename_dst[dst_index].is_rename)\n+\t\t\t\tcontinue; /* already used previously */\n+\n+\t\t\tone = rename_src[src_index].p->one;\n+\t\t\ttwo = rename_dst[dst_index].p->two;\n+\n+\t\t\t/* Add the pairs */\n+\t\t\tdiff_add_if_missing(options->repo, &to_fetch, two);\n+\t\t\tdiff_add_if_missing(options->repo, &to_fetch, one);\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+}\n+\n static int find_basename_matches(struct diff_options *options,\n \t\t\t\t int minimum_score,\n \t\t\t\t struct dir_rename_info *info,\n@@ -860,19 +932,12 @@ static int find_basename_matches(struct diff_options *options,\n \t\t.missing_object_cb = NULL,\n \t\t.missing_object_data = NULL\n \t};\n-\t/*\n-\t * The prefeteching stuff wants to know if it can skip prefetching\n-\t * blobs that are unmodified...and will then do a little extra work\n-\t * to verify that the oids are indeed different before prefetching.\n-\t * Unmodified blobs are only relevant when doing copy detection;\n-\t * when limiting to rename detection, diffcore_rename[_extended]()\n-\t * will never be called with unmodified source paths fed to us, so\n-\t * the extra work necessary to check if rename_src entries are\n-\t * unmodified would be a small waste.\n-\t */\n-\tstruct prefetch_options prefetch_options = {\n+\tstruct basename_prefetch_options prefetch_options = {\n \t\t.repo = options->repo,\n-\t\t.skip_unmodified = 0\n+\t\t.relevant_sources = relevant_sources,\n+\t\t.sources = &sources,\n+\t\t.dests = &dests,\n+\t\t.info = info\n \t};\n \n \t/*\n@@ -911,7 +976,7 @@ static int find_basename_matches(struct diff_options *options,\n \t}\n \n \tif (options->repo == the_repository && has_promisor_remote()) {\n-\t\tdpf_options.missing_object_cb = prefetch;\n+\t\tdpf_options.missing_object_cb = basename_prefetch;\n \t\tdpf_options.missing_object_data = &prefetch_options;\n \t}\n \n@@ -1282,7 +1347,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t.missing_object_cb = NULL,\n \t\t.missing_object_data = NULL\n \t};\n-\tstruct prefetch_options prefetch_options = {\n+\tstruct inexact_prefetch_options prefetch_options = {\n \t\t.repo = options->repo\n \t};\n \n@@ -1449,7 +1514,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t/* Finish setting up dpf_options */\n \tprefetch_options.skip_unmodified = skip_unmodified;\n \tif (options->repo == the_repository && has_promisor_remote()) {\n-\t\tdpf_options.missing_object_cb = prefetch;\n+\t\tdpf_options.missing_object_cb = inexact_prefetch;\n \t\tdpf_options.missing_object_data = &prefetch_options;\n \t}\n \ndiff --git a/t/t6421-merge-partial-clone.sh b/t/t6421-merge-partial-clone.sh\nindex 028d876be2c8..fb7eb18cc80c 100755\n--- a/t/t6421-merge-partial-clone.sh\n+++ b/t/t6421-merge-partial-clone.sh\n@@ -206,7 +206,7 @@ test_setup_repo () {\n #\n # Summary: 2 fetches (1 for 2 objects, 1 for 1 object)\n #\n-test_expect_merge_algorithm failure failure 'Objects downloaded for single relevant rename' '\n+test_expect_merge_algorithm failure success 'Objects downloaded for single relevant rename' '\n \ttest_setup_repo &&\n \tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-single &&\n \t(\n@@ -293,7 +293,7 @@ test_expect_merge_algorithm failure failure 'Objects downloaded for single relev\n # this are not all that common.)\n # Summary: 1 fetches for 6 objects\n #\n-test_expect_merge_algorithm failure failure 'Objects downloaded when a directory rename triggered' '\n+test_expect_merge_algorithm failure success 'Objects downloaded when a directory rename triggered' '\n \ttest_setup_repo &&\n \tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-dir &&\n \t(\n-- \ngitgitgadget\n\n"},{"id":"426936","messageId":"858bc5e9-17b5-f9a8-2c67-6cffb9e2f968@gmail.com","threadId":"55842","inReplyTo":"ad9b451d6823f7158a2b58a82682e0c862a1ef6b.1622856485.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/5] promisor-remote: output trace2 statistics for number of objects fetched","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-06-09T21:12:11Z","receivedAt":"2021-06-09T21:13:30Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/4/2021 9:28 PM, Elijah Newren via GitGitGadget wrote:\n> +\ttrace2_data_intmax(\"promisor\", repo, \"fetch_count\", oid_nr);\n\nThis seems like a helpful value for lots of reasons.\n\nThanks,\n-Stolee\n"},{"id":"426937","messageId":"7fb76c82-bc54-01c1-451f-7dc05177d58f@gmail.com","threadId":"55842","inReplyTo":"6462bb63310dbc889a3442951ef261bc7fd7e0dc.1622856485.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/5] t6421: add tests checking for excessive object downloads during merge","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-06-09T21:16:31Z","receivedAt":"2021-06-09T21:16:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/4/2021 9:28 PM, Elijah Newren via GitGitGadget wrote:\n> From: Elijah Newren \n...\n> +test_expect_merge_algorithm failure failure 'Objects downloaded for single relevant rename' '\n> +\ttest_setup_repo &&\n> +\tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-single &&\n> +\t(\n> +\t\tcd objects-single &&\n> +\n> +\t\tgit rev-list --objects --all --missing=print |\n> +\t\t\tgrep '\\?' >missing-objects-before &&\n> +\n> +\t\tgit checkout -q origin/A &&\n> +\n> +\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git -c merge.directoryRenames=true merge --no-stat --no-progress origin/B-single &&\n\nnit: this long line could be split up with \\ marks.\n\n> +\n> +\t\t# Check the number of objects we reported we would fetch\n> +\t\tcat >expect <<-EOF &&\n> +\t\t ..........fetch_count:2\n> +\t\t ......fetch_count:1\n\nI'm concerned that the number of dots here could change for various\nreasons (e.g. adding regions). Could the 'cut' below cut everything\nafter the dots, so we only care about \"fetch_count:X\"?\n\n> +\t\tEOF\n> +\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 >actual &&\n> +\t\ttest_cmp expect actual &&\n> +\n> +\t\t# Check the number of fetch commands exec-ed\n> +\t\tgrep d0.*fetch.negotiationAlgorithm trace.output >fetches &&\n> +\t\ttest_line_count = 2 fetches &&\n> +\n> +\t\tgit rev-list --objects --all --missing=print |\n> +\t\t\tgrep ^? >missing-objects-after &&\n> +\t\ttest_cmp missing-objects-before missing-objects-after |\n> +\t\t\tgrep \"^[-+]?\" >found-and-new-objects &&\n> +\t\t# We should not have any NEW missing objects\n> +\t\t! grep ^+ found-and-new-objects &&\n> +\t\t# Fetched 2+1=3 objects, so should have 3 fewer missing objects\n> +\t\ttest_line_count = 3 found-and-new-objects\n> +\t)\n> +'\n\nGenerally, this idea of using trace2 to determine internal activity\nthat affects performance is a good one. The balance to strike is to\nensure that future changes don't suffer too much due to the how\nrigid the tests are. The dots are the only example of a way to relax\nthese tests a bit more.\n\nThanks,\n-Stolee\n"},{"id":"427538","messageId":"04f5ebdabe147b6652c5487ad2a440ba7b7389d5.1623796907.git.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.v2.git.1623796907.gitgitgadget@gmail.com","subject":"[PATCH v2 1/5] promisor-remote: output trace2 statistics for number of objects fetched","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-15T22:41:42Z","receivedAt":"2021-06-15T22:41:53Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nSigned-off-by: Elijah Newren \n---\n promisor-remote.c | 7 +++++--\n 1 file changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/promisor-remote.c b/promisor-remote.c\nindex da3f2ca2615e..d465377d7d32 100644\n--- a/promisor-remote.c\n+++ b/promisor-remote.c\n@@ -12,7 +12,8 @@ void set_repository_format_partial_clone(char *partial_clone)\n \trepository_format_partial_clone = xstrdup_or_null(partial_clone);\n }\n \n-static int fetch_objects(const char *remote_name,\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 {\n@@ -30,6 +31,8 @@ static int fetch_objects(const char *remote_name,\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+\n \tfor (i = 0; i < oid_nr; i++) {\n \t\tif (fputs(oid_to_hex(&oids[i]), child_in) < 0)\n \t\t\tdie_errno(_(\"promisor-remote: could not write to fetch subprocess\"));\n@@ -238,7 +241,7 @@ int promisor_remote_get_direct(struct repository *repo,\n \tpromisor_remote_init();\n \n \tfor (r = promisors; r; r = r->next) {\n-\t\tif (fetch_objects(r->name, remaining_oids, remaining_nr) < 0) {\n+\t\tif (fetch_objects(repo, r->name, remaining_oids, remaining_nr) < 0) {\n \t\t\tif (remaining_nr == 1)\n \t\t\t\tcontinue;\n \t\t\tremaining_nr = remove_fetched_oids(repo, &remaining_oids,\n-- \ngitgitgadget\n\n"},{"id":"427539","messageId":"pull.969.v2.git.1623796907.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.git.1622856485.gitgitgadget@gmail.com","subject":"[PATCH v2 0/5] Optimization batch 13: partial clone optimizations for merge-ort","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-15T22:41:41Z","receivedAt":"2021-06-15T22:41:54Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series optimizes blob downloading in merges for partial clones. It can\napply on master. It's independent of ort-perf-batch-12.\n\nChanges since v1:\n\n * Incorporated the suggestions from Stolee on patch 2.\n\nThis series has a minor conflict with jt/partial-clone-submodule-1. I asked\nabout this previously and it was decided to just submit these topics\nindependently[1]. The conflict is that both topics add a \"repo\" argument to\nfetch_objects(), but jt/partial-clone-submodule-1 also makes additional\nnearby changes.\n\n[1]\nhttps://lore.kernel.org/git/20210609045804.2329079-1-jonathantanmy@google.com/\n\n=== Basic Optimization idea ===\n\nmerge-ort was designed to minimize the computation needed to complete a\nmerge, and much of that (particularly the \"irrelevant rename\"\ndeterminations) also dramatically reduced the amount of data needed for the\nmerge. Reducing the amount of data needed to do computations ought to\nbenefit partial clones as well by enabling them to download less\ninformation. However, my previous series didn't modify the prefetch()\ncommand in diffcore-rename to take advantage of these reduced data\nrequirements. This series changes that.\n\nFurther, although diffcore-rename batched downloads of objects for rename\ndetection, the merge machinery did not do the same for three-way content\nmerges of files. This series adds batch downloading of objects within\nmerge-ort to correct that.\n\n=== Modified performance measurement method ===\n\nThe testcases I've been using so far to measure performance were not run in\na partial clone, so they aren't directly usable for comparison. Further,\npartial clone performance depends on network speed which can be highly\nvariable. So I want to modify one of the existing testcases slightly and\nfocus on two different but more stable metrics:\n\n 1. Number of git fetch operations during rebase\n 2. Number of objects fetched during rebase\n\nThe first of these should already be decent due to Jonathan Tan's work to\nbatch fetching of missing blobs during rename detection (see commit\n7fbbcb21b1 (\"diff: batch fetching of missing blobs\", 2019-04-05)), so we are\nmostly looking to optimize the second but would like to also decrease the\nfirst if possible.\n\nThe testcase we will look at will be a modification of the mega-renames\ntestcase from commit 557ac0350d (\"merge-ort: begin performance work;\ninstrument with trace2_region_* calls\", 2020-10-28). In particular, we\nchange\n\n$ git clone \\\n git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git\n\n\nto\n\n$ git clone --sparse --filter=blob:none \\\n https://github.com/github/linux\n\n\n(The change in clone URL is just to get a server that supports the filter\npredicate.)\n\nWe otherwise keep the test the same (in particular, we do not add any calls\nto \"git-sparse checkout {set,add}\" which means that the resulting repository\nwill only have 7 total blobs from files in the toplevel directory before\nstarting the rebase).\n\n=== Results ===\n\nFor the mega-renames testcase noted above (which rebases 35 commits across\nan upstream with ~26K renames in a partial clone), I found the following\nresults for our metrics of interest:\n\n Number of `git fetch` ops during rebase\n\n Before Series After Series\nmerge-recursive: 62 63\nmerge-ort: 30 20\n\n\n Number of objects fetched during rebase\n\n Before Series After Series\nmerge-recursive: 11423 11423\nmerge-ort: 11391 63\n\n\nSo, we have a significant reduction (factor of ~3 relative to\nmerge-recursive) in the number of git fetch operations that have to be\nperformed in a partial clone to complete the rebase, and a dramatic\nreduction (factor of ~180) in the number of objects that need to be fetched.\n\n=== Summary ===\n\nIt's worth pointing out that merge-ort after the series needs only ~1.8\nblobs per commit being transplanted to complete this particular rebase.\nEssentially, this reinforces the fact the optimization work so far has taken\nrename detection from often being an overwhelmingly costly portion of a\nmerge (leading many to just capitulate on it), to what I have observed in my\nexperience so far as being just a minor cost for merges.\n\nElijah Newren (5):\n promisor-remote: output trace2 statistics for number of objects\n fetched\n t6421: add tests checking for excessive object downloads during merge\n diffcore-rename: allow different missing_object_cb functions\n diffcore-rename: use a different prefetch for basename comparisons\n merge-ort: add prefetching for content merges\n\n diffcore-rename.c | 149 ++++++++---\n merge-ort.c | 50 ++++\n promisor-remote.c | 7 +-\n t/t6421-merge-partial-clone.sh | 439 +++++++++++++++++++++++++++++++++\n 4 files changed, 611 insertions(+), 34 deletions(-)\n create mode 100755 t/t6421-merge-partial-clone.sh\n\n\nbase-commit: 6de569e6ac492213e81321ca35f1f1b365ba31e3\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-969%2Fnewren%2Fort-perf-batch-13-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-969/newren/ort-perf-batch-13-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/969\n\nRange-diff vs v1:\n\n 1: ad9b451d6823 = 1: 04f5ebdabe14 promisor-remote: output trace2 statistics for number of objects fetched\n 2: 6462bb63310d ! 2: 0f786cfb4c95 t6421: add tests checking for excessive object downloads during merge\n @@ t/t6421-merge-partial-clone.sh (new)\n +\n +\t\tgit checkout -q origin/A &&\n +\n -+\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git -c merge.directoryRenames=true merge --no-stat --no-progress origin/B-single &&\n ++\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git \\\n ++\t\t\t-c merge.directoryRenames=true merge --no-stat \\\n ++\t\t\t--no-progress origin/B-single &&\n +\n +\t\t# Check the number of objects we reported we would fetch\n +\t\tcat >expect <<-EOF &&\n -+\t\t ..........fetch_count:2\n -+\t\t ......fetch_count:1\n ++\t\tfetch_count:2\n ++\t\tfetch_count:1\n +\t\tEOF\n -+\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 >actual &&\n ++\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 | tr -d \" .\" >actual &&\n +\t\ttest_cmp expect actual &&\n +\n +\t\t# Check the number of fetch commands exec-ed\n @@ t/t6421-merge-partial-clone.sh (new)\n +\n +\t\tgit checkout -q origin/A &&\n +\n -+\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git -c merge.directoryRenames=true merge --no-stat --no-progress origin/B-dir &&\n ++\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git \\\n ++\t\t\t-c merge.directoryRenames=true merge --no-stat \\\n ++\t\t\t--no-progress origin/B-dir &&\n +\n +\t\t# Check the number of objects we reported we would fetch\n +\t\tcat >expect <<-EOF &&\n -+\t\t ..........fetch_count:6\n ++\t\tfetch_count:6\n +\t\tEOF\n -+\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 >actual &&\n ++\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 | tr -d \" .\" >actual &&\n +\t\ttest_cmp expect actual &&\n +\n +\t\t# Check the number of fetch commands exec-ed\n @@ t/t6421-merge-partial-clone.sh (new)\n +\n +\t\tgit checkout -q origin/A &&\n +\n -+\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git -c merge.directoryRenames=true merge --no-stat --no-progress origin/B-many &&\n ++\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git \\\n ++\t\t\t-c merge.directoryRenames=true merge --no-stat \\\n ++\t\t\t--no-progress origin/B-many &&\n +\n +\t\t# Check the number of objects we reported we would fetch\n +\t\tcat >expect <<-EOF &&\n -+\t\t ..........fetch_count:12\n -+\t\t ..........fetch_count:5\n -+\t\t ..........fetch_count:3\n -+\t\t ......fetch_count:2\n ++\t\tfetch_count:12\n ++\t\tfetch_count:5\n ++\t\tfetch_count:3\n ++\t\tfetch_count:2\n +\t\tEOF\n -+\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 >actual &&\n ++\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 | tr -d \" .\" >actual &&\n +\t\ttest_cmp expect actual &&\n +\n +\t\t# Check the number of fetch commands exec-ed\n 3: c4b3109c3b08 = 3: 9f2a8ed8d61f diffcore-rename: allow different missing_object_cb functions\n 4: f4ade3996d3f = 4: f753f8035564 diffcore-rename: use a different prefetch for basename comparisons\n 5: ca3b2a743b8e = 5: 317bcc7f56cb merge-ort: add prefetching for content merges\n\n-- \ngitgitgadget\n"},{"id":"427540","messageId":"0f786cfb4c9507a224b1dc3ee6eca9f5ac5c2ae8.1623796907.git.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.v2.git.1623796907.gitgitgadget@gmail.com","subject":"[PATCH v2 2/5] t6421: add tests checking for excessive object downloads during merge","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-15T22:41:43Z","receivedAt":"2021-06-15T22:41:55Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nSigned-off-by: Elijah Newren \n---\n t/t6421-merge-partial-clone.sh | 439 +++++++++++++++++++++++++++++++++\n 1 file changed, 439 insertions(+)\n create mode 100755 t/t6421-merge-partial-clone.sh\n\ndiff --git a/t/t6421-merge-partial-clone.sh b/t/t6421-merge-partial-clone.sh\nnew file mode 100755\nindex 000000000000..c9d6860de9c9\n--- /dev/null\n+++ b/t/t6421-merge-partial-clone.sh\n@@ -0,0 +1,439 @@\n+#!/bin/sh\n+\n+test_description=\"limiting blob downloads when merging with partial clones\"\n+# Uses a methodology similar to\n+# t6042: corner cases with renames but not criss-cross merges\n+# t6036: corner cases with both renames and criss-cross merges\n+# t6423: directory rename detection\n+#\n+# The setup for all of them, pictorially, is:\n+#\n+# A\n+# o\n+# / \\\n+# O o ?\n+# \\ /\n+# o\n+# B\n+#\n+# To help make it easier to follow the flow of tests, they have been\n+# divided into sections and each test will start with a quick explanation\n+# of what commits O, A, and B contain.\n+#\n+# Notation:\n+# z/{b,c} means files z/b and z/c both exist\n+# x/d_1 means file x/d exists with content d1. (Purpose of the\n+# underscore notation is to differentiate different\n+# files that might be renamed into each other's paths.)\n+\n+. ./test-lib.sh\n+. \"$TEST_DIRECTORY\"/lib-merge.sh\n+\n+test_setup_repo () {\n+\ttest -d server && return\n+\ttest_create_repo server &&\n+\t(\n+\t\tcd server &&\n+\n+\t\tgit config uploadpack.allowfilter 1 &&\n+\t\tgit config uploadpack.allowanysha1inwant 1 &&\n+\n+\t\tmkdir -p general &&\n+\t\ttest_seq 2 9 >general/leap1 &&\n+\t\tcp general/leap1 general/leap2 &&\n+\t\techo leap2 >>general/leap2 &&\n+\n+\t\tmkdir -p basename &&\n+\t\tcp general/leap1 basename/numbers &&\n+\t\tcp general/leap1 basename/sequence &&\n+\t\tcp general/leap1 basename/values &&\n+\t\techo numbers >>basename/numbers &&\n+\t\techo sequence >>basename/sequence &&\n+\t\techo values >>basename/values &&\n+\n+\t\tmkdir -p dir/unchanged &&\n+\t\tmkdir -p dir/subdir/tweaked &&\n+\t\techo a >dir/subdir/a &&\n+\t\techo b >dir/subdir/b &&\n+\t\techo c >dir/subdir/c &&\n+\t\techo d >dir/subdir/d &&\n+\t\techo e >dir/subdir/e &&\n+\t\tcp general/leap1 dir/subdir/Makefile &&\n+\t\techo toplevel makefile >>dir/subdir/Makefile &&\n+\t\techo f >dir/subdir/tweaked/f &&\n+\t\techo g >dir/subdir/tweaked/g &&\n+\t\techo h >dir/subdir/tweaked/h &&\n+\t\techo subdirectory makefile >dir/subdir/tweaked/Makefile &&\n+\t\tfor i in `test_seq 1 88`; do\n+\t\t\techo content $i >dir/unchanged/file_$i\n+\t\tdone &&\n+\t\tgit add . &&\n+\t\tgit commit -m \"O\" &&\n+\n+\t\tgit branch O &&\n+\t\tgit branch A &&\n+\t\tgit branch B-single &&\n+\t\tgit branch B-dir &&\n+\t\tgit branch B-many &&\n+\n+\t\tgit switch A &&\n+\n+\t\tgit rm general/leap* &&\n+\t\tmkdir general/ &&\n+\t\ttest_seq 1 9 >general/jump1 &&\n+\t\tcp general/jump1 general/jump2 &&\n+\t\techo leap2 >>general/jump2 &&\n+\n+\t\trm basename/numbers basename/sequence basename/values &&\n+\t\tmkdir -p basename/subdir/\n+\t\tcp general/jump1 basename/subdir/numbers &&\n+\t\tcp general/jump1 basename/subdir/sequence &&\n+\t\tcp general/jump1 basename/subdir/values &&\n+\t\techo numbers >>basename/subdir/numbers &&\n+\t\techo sequence >>basename/subdir/sequence &&\n+\t\techo values >>basename/subdir/values &&\n+\n+\t\tgit rm dir/subdir/tweaked/f &&\n+\t\techo more >>dir/subdir/e &&\n+\t\techo more >>dir/subdir/Makefile &&\n+\t\techo more >>dir/subdir/tweaked/Makefile &&\n+\t\tmkdir dir/subdir/newsubdir &&\n+\t\techo rust code >dir/subdir/newsubdir/newfile.rs &&\n+\t\tgit mv dir/subdir/e dir/subdir/newsubdir/ &&\n+\t\tgit mv dir folder &&\n+\t\tgit add . &&\n+\t\tgit commit -m \"A\" &&\n+\n+\t\tgit switch B-single &&\n+\t\techo new first line >dir/subdir/Makefile &&\n+\t\tcat general/leap1 >>dir/subdir/Makefile &&\n+\t\techo toplevel makefile >>dir/subdir/Makefile &&\n+\t\techo perl code >general/newfile.pl &&\n+\t\tgit add . &&\n+\t\tgit commit -m \"B-single\" &&\n+\n+\t\tgit switch B-dir &&\n+\t\techo java code >dir/subdir/newfile.java &&\n+\t\techo scala code >dir/subdir/newfile.scala &&\n+\t\techo groovy code >dir/subdir/newfile.groovy &&\n+\t\tgit add . &&\n+\t\tgit commit -m \"B-dir\" &&\n+\n+\t\tgit switch B-many &&\n+\t\ttest_seq 2 10 >general/leap1 &&\n+\t\trm general/leap2 &&\n+\t\tcp general/leap1 general/leap2 &&\n+\t\techo leap2 >>general/leap2 &&\n+\n+\t\trm basename/numbers basename/sequence basename/values &&\n+\t\tmkdir -p basename/subdir/\n+\t\tcp general/leap1 basename/subdir/numbers &&\n+\t\tcp general/leap1 basename/subdir/sequence &&\n+\t\tcp general/leap1 basename/subdir/values &&\n+\t\techo numbers >>basename/subdir/numbers &&\n+\t\techo sequence >>basename/subdir/sequence &&\n+\t\techo values >>basename/subdir/values &&\n+\n+\t\tmkdir dir/subdir/newsubdir/ &&\n+\t\techo c code >dir/subdir/newfile.c &&\n+\t\techo python code >dir/subdir/newsubdir/newfile.py &&\n+\t\tgit add . &&\n+\t\tgit commit -m \"B-many\" &&\n+\n+\t\tgit switch A\n+\t)\n+}\n+\n+# Testcase: Objects downloaded for single relevant rename\n+# Commit O:\n+# general/{leap1_O, leap2_O}\n+# basename/{numbers_O, sequence_O, values_O}\n+# dir/subdir/{a,b,c,d,e_O,Makefile_TOP_O}\n+# dir/subdir/tweaked/{f,g,h,Makefile_SUB_O}\n+# dir/unchanged/\n+# Commit A:\n+# (Rename leap->jump, rename basename/ -> basename/subdir/, rename dir/\n+# -> folder/, move e into newsubdir, add newfile.rs, remove f, modify\n+# both both Makefiles and jumps)\n+# general/{jump1_A, jump2_A}\n+# basename/subdir/{numbers_A, sequence_A, values_A}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_A}\n+# folder/subdir/newsubdir/{e_A,newfile.rs}\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A}\n+# folder/unchanged/\n+# Commit B(-single):\n+# (add newfile.pl, tweak Makefile_TOP)\n+# general/{leap1_O, leap2_O,newfile.pl}\n+# basename/{numbers_O, sequence_O, values_O}\n+# dir/{a,b,c,d,e_O,Makefile_TOP_B}\n+# dir/tweaked/{f,g,h,Makefile_SUB_O}\n+# dir/unchanged/\n+# Expected:\n+# general/{jump1_A, jump2_A,newfile.pl}\n+# basename/subdir/{numbers_A, sequence_A, values_A}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_Merged}\n+# folder/subdir/newsubdir/{e_A,newfile.rs}\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A}\n+# folder/unchanged/\n+#\n+# Objects that need to be fetched:\n+# Rename detection:\n+# Side1 (O->A):\n+# Basename-matches rename detection only needs to fetch these objects:\n+# Makefile_TOP_O, Makefile_TOP_A\n+# (Despite many renames, all others are content irrelevant. They\n+# are also location irrelevant because newfile.rs was added on\n+# the side doing the directory rename, and newfile.pl was added to\n+# a directory that was not renamed on either side.)\n+# General rename detection only needs to fetch these objects:\n+# \n+# (Even though newfile.rs, jump[12], basename/subdir/*, and e\n+# could all be used as destinations in rename detection, the\n+# basename detection for Makefile matches up all relevant\n+# sources, so these other files never end up needing to be\n+# used)\n+# Side2 (O->B):\n+# Basename-matches rename detection only needs to fetch these objects:\n+# \n+# (there are no deleted files, so no possible sources)\n+# General rename detection only needs to fetch these objects:\n+# \n+# (there are no deleted files, so no possible sources)\n+# Merge:\n+# 3-way content merge needs to grab these objects:\n+# Makefile_TOP_B\n+# Nothing else needs to fetch objects\n+#\n+# Summary: 2 fetches (1 for 2 objects, 1 for 1 object)\n+#\n+test_expect_merge_algorithm failure failure 'Objects downloaded for single relevant rename' '\n+\ttest_setup_repo &&\n+\tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-single &&\n+\t(\n+\t\tcd objects-single &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep '\\?' >missing-objects-before &&\n+\n+\t\tgit checkout -q origin/A &&\n+\n+\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git \\\n+\t\t\t-c merge.directoryRenames=true merge --no-stat \\\n+\t\t\t--no-progress origin/B-single &&\n+\n+\t\t# Check the number of objects we reported we would fetch\n+\t\tcat >expect <<-EOF &&\n+\t\tfetch_count:2\n+\t\tfetch_count:1\n+\t\tEOF\n+\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 | tr -d \" .\" >actual &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\t# Check the number of fetch commands exec-ed\n+\t\tgrep d0.*fetch.negotiationAlgorithm trace.output >fetches &&\n+\t\ttest_line_count = 2 fetches &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep ^? >missing-objects-after &&\n+\t\ttest_cmp missing-objects-before missing-objects-after |\n+\t\t\tgrep \"^[-+]?\" >found-and-new-objects &&\n+\t\t# We should not have any NEW missing objects\n+\t\t! grep ^+ found-and-new-objects &&\n+\t\t# Fetched 2+1=3 objects, so should have 3 fewer missing objects\n+\t\ttest_line_count = 3 found-and-new-objects\n+\t)\n+'\n+\n+# Testcase: Objects downloaded for directory rename\n+# Commit O:\n+# general/{leap1_O, leap2_O}\n+# basename/{numbers_O, sequence_O, values_O}\n+# dir/subdir/{a,b,c,d,e_O,Makefile_TOP_O}\n+# dir/subdir/tweaked/{f,g,h,Makefile_SUB_O}\n+# dir/unchanged/\n+# Commit A:\n+# (Rename leap->jump, rename basename/ -> basename/subdir/, rename dir/ ->\n+# folder/, move e into newsubdir, add newfile.rs, remove f, modify\n+# both Makefiles and jumps)\n+# general/{jump1_A, jump2_A}\n+# basename/subdir/{numbers_A, sequence_A, values_A}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_A}\n+# folder/subdir/newsubdir/{e_A,newfile.rs}\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A}\n+# folder/unchanged/\n+# Commit B(-dir):\n+# (add dir/subdir/newfile.{java,scala,groovy}\n+# general/{leap1_O, leap2_O}\n+# basename/{numbers_O, sequence_O, values_O}\n+# dir/subdir/{a,b,c,d,e_O,Makefile_TOP_O,\n+# newfile.java,newfile.scala,newfile.groovy}\n+# dir/subdir/tweaked/{f,g,h,Makefile_SUB_O}\n+# dir/unchanged/\n+# Expected:\n+# general/{jump1_A, jump2_A}\n+# basename/subdir/{numbers_A, sequence_A, values_A}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_A,\n+# newfile.java,newfile.scala,newfile.groovy}\n+# folder/subdir/newsubdir/{e_A,newfile.rs}\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A}\n+# folder/unchanged/\n+#\n+# Objects that need to be fetched:\n+# Makefile_TOP_O, Makefile_TOP_A\n+# Makefile_SUB_O, Makefile_SUB_A\n+# e_O, e_A\n+# * Despite A's rename of jump->leap, those renames are irrelevant.\n+# * Despite A's rename of basename/ -> basename/subdir/, those renames are\n+# irrelevant.\n+# * Because of A's rename of dir/ -> folder/ and B-dir's addition of\n+# newfile.* into dir/subdir/, we need to determine directory renames.\n+# (Technically, there are enough exact renames to determine directory\n+# rename detection, but the current implementation always does\n+# basename searching before directory rename detection. Running it\n+# also before basename searching would mean doing directory rename\n+# detection twice, but it's a bit expensive to do that and cases like\n+# this are not all that common.)\n+# Summary: 1 fetches for 6 objects\n+#\n+test_expect_merge_algorithm failure failure 'Objects downloaded when a directory rename triggered' '\n+\ttest_setup_repo &&\n+\tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-dir &&\n+\t(\n+\t\tcd objects-dir &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep '\\?' >missing-objects-before &&\n+\n+\t\tgit checkout -q origin/A &&\n+\n+\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git \\\n+\t\t\t-c merge.directoryRenames=true merge --no-stat \\\n+\t\t\t--no-progress origin/B-dir &&\n+\n+\t\t# Check the number of objects we reported we would fetch\n+\t\tcat >expect <<-EOF &&\n+\t\tfetch_count:6\n+\t\tEOF\n+\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 | tr -d \" .\" >actual &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\t# Check the number of fetch commands exec-ed\n+\t\tgrep d0.*fetch.negotiationAlgorithm trace.output >fetches &&\n+\t\ttest_line_count = 1 fetches &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep ^? >missing-objects-after &&\n+\t\ttest_cmp missing-objects-before missing-objects-after |\n+\t\t\tgrep \"^[-+]?\" >found-and-new-objects &&\n+\t\t# We should not have any NEW missing objects\n+\t\t! grep ^+ found-and-new-objects &&\n+\t\t# Fetched 6 objects, so should have 6 fewer missing objects\n+\t\ttest_line_count = 6 found-and-new-objects\n+\t)\n+'\n+\n+# Testcase: Objects downloaded with lots of renames and modifications\n+# Commit O:\n+# general/{leap1_O, leap2_O}\n+# basename/{numbers_O, sequence_O, values_O}\n+# dir/subdir/{a,b,c,d,e_O,Makefile_TOP_O}\n+# dir/subdir/tweaked/{f,g,h,Makefile_SUB_O}\n+# dir/unchanged/\n+# Commit A:\n+# (Rename leap->jump, rename basename/ -> basename/subdir/, rename dir/\n+# -> folder/, move e into newsubdir, add newfile.rs, remove f, modify\n+# both both Makefiles and jumps)\n+# general/{jump1_A, jump2_A}\n+# basename/subdir/{numbers_A, sequence_A, values_A}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_A}\n+# folder/subdir/newsubdir/{e_A,newfile.rs}\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A}\n+# folder/unchanged/\n+# Commit B(-minimal):\n+# (modify both leaps, rename basename/ -> basename/subdir/, add\n+# newfile.{c,py})\n+# general/{leap1_B, leap2_B}\n+# basename/subdir/{numbers_B, sequence_B, values_B}\n+# dir/{a,b,c,d,e_O,Makefile_TOP_O,newfile.c}\n+# dir/tweaked/{f,g,h,Makefile_SUB_O,newfile.py}\n+# dir/unchanged/\n+# Expected:\n+# general/{jump1_Merged, jump2_Merged}\n+# basename/subdir/{numbers_Merged, sequence_Merged, values_Merged}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_A,newfile.c}\n+# folder/subdir/newsubdir/e_A\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A,newfile.py}\n+# folder/unchanged/\n+#\n+# Objects that need to be fetched:\n+# Rename detection:\n+# Side1 (O->A):\n+# Basename-matches rename detection only needs to fetch these objects:\n+# numbers_O, numbers_A\n+# sequence_O, sequence_A\n+# values_O, values_A\n+# Makefile_TOP_O, Makefile_TOP_A\n+# Makefile_SUB_O, Makefile_SUB_A\n+# e_O, e_A\n+# General rename detection only needs to fetch these objects:\n+# leap1_O, leap2_O\n+# jump1_A, jump2_A, newfile.rs\n+# (only need remaining relevant sources, but any relevant sources need\n+# to be matched against all possible unpaired destinations)\n+# Side2 (O->B):\n+# Basename-matches rename detection only needs to fetch these objects:\n+# numbers_B\n+# sequence_B\n+# values_B\n+# (because numbers_O, sequence_O, and values_O already fetched above)\n+# General rename detection only needs to fetch these objects:\n+# \n+# Merge:\n+# 3-way content merge needs to grab these objects:\n+# leap1_B\n+# leap2_B\n+# Nothing else needs to fetch objects\n+#\n+# Summary: 4 fetches (1 for 6 objects, 1 for 8, 1 for 3, 1 for 2)\n+#\n+test_expect_merge_algorithm failure failure 'Objects downloaded with lots of renames and modifications' '\n+\ttest_setup_repo &&\n+\tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-many &&\n+\t(\n+\t\tcd objects-many &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep '\\?' >missing-objects-before &&\n+\n+\t\tgit checkout -q origin/A &&\n+\n+\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git \\\n+\t\t\t-c merge.directoryRenames=true merge --no-stat \\\n+\t\t\t--no-progress origin/B-many &&\n+\n+\t\t# Check the number of objects we reported we would fetch\n+\t\tcat >expect <<-EOF &&\n+\t\tfetch_count:12\n+\t\tfetch_count:5\n+\t\tfetch_count:3\n+\t\tfetch_count:2\n+\t\tEOF\n+\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 | tr -d \" .\" >actual &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\t# Check the number of fetch commands exec-ed\n+\t\tgrep d0.*fetch.negotiationAlgorithm trace.output >fetches &&\n+\t\ttest_line_count = 4 fetches &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep ^? >missing-objects-after &&\n+\t\ttest_cmp missing-objects-before missing-objects-after |\n+\t\t\tgrep \"^[-+]?\" >found-and-new-objects &&\n+\t\t# We should not have any NEW missing objects\n+\t\t! grep ^+ found-and-new-objects &&\n+\t\t# Fetched 12 + 5 + 3 + 2 == 22 objects\n+\t\ttest_line_count = 22 found-and-new-objects\n+\t)\n+'\n+\n+test_done\n-- \ngitgitgadget\n\n"},{"id":"427541","messageId":"f753f8035564734de01bbcbe28327da6db9f1a0b.1623796907.git.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.v2.git.1623796907.gitgitgadget@gmail.com","subject":"[PATCH v2 4/5] diffcore-rename: use a different prefetch for basename comparisons","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-15T22:41:45Z","receivedAt":"2021-06-15T22:41:59Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nmerge-ort was designed to minimize the amount of data needed and used,\nand several changes were made to diffcore-rename to take advantage of\nextra metadata to enable this data minimization (particularly the\nrelevant_sources variable for skipping \"irrelevant\" renames). This\neffort obviously succeeded in drastically reducing computation times,\nbut should also theoretically allow partial clones to download much less\ninformation. Previously, though, the \"prefetch\" command used in\ndiffcore-rename had never been modified and downloaded many blobs that\nwere unnecessary for merge-ort. This commit corrects that.\n\nWhen doing basename comparisons, we want to fetch only the objects that\nwill be used for basename comparisons. If after basename fetching this\nleaves us with no more relevant sources (or no more destinations), then\nwe won't need to do the full inexact rename detection and can skip\ndownloading additional source and destination files. Even if we have to\ndo that later full inexact rename detection, irrelevant sources are\nculled after basename matching and before the full inexact rename\ndetection, so we can still avoid downloading the blobs for irrelevant\nsources. Rename prefetch() to inexact_prefetch(), and introduce a\nnew basename_prefetch() to take advantage of this.\n\nIf we modify the testcase from commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2021-01-23)\nto pass\n --sparse --filter=blob:none\nto the clone command, and use the new trace2 \"fetch_count\" output from\na few commits ago to track both the number of fetch subcommands invoked\nand the number of objects fetched across all those fetches, then for\nthe mega-renames testcase we observe the following:\n\nBEFORE this commit, rebasing 35 patches:\n strategy # of fetches total # of objects fetched\n --------- ------------ --------------------------\n recursive 62 11423\n ort 30 11391\n\nAFTER this commit, rebasing the same 35 patches:\n ort 32 63\n\nThis means that the new code only needs to download less than 2 blobs\nper patch being rebased. That is especially interesting given that the\nrepository at the start only had approximately half a dozen TOTAL blobs\ndownloaded to start with (because the default sparse-checkout of just\nthe toplevel directory was in use).\n\nSo, for this particular linux kernel testcase that involved ~26,000\nrenames on the upstream side (drivers/ -> pilots/) across which 35\npatches were being rebased, this change reduces the number of blobs that\nneed to be downloaded by a factor of ~180.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 101 +++++++++++++++++++++++++++------\n t/t6421-merge-partial-clone.sh | 4 +-\n 2 files changed, 85 insertions(+), 20 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex e13e52046026..4ef0459cfb50 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -87,13 +87,13 @@ struct diff_score {\n \tshort name_score;\n };\n \n-struct prefetch_options {\n+struct inexact_prefetch_options {\n \tstruct repository *repo;\n \tint skip_unmodified;\n };\n-static void prefetch(void *prefetch_options)\n+static void inexact_prefetch(void *prefetch_options)\n {\n-\tstruct prefetch_options *options = prefetch_options;\n+\tstruct inexact_prefetch_options *options = prefetch_options;\n \tint i;\n \tstruct oid_array to_fetch = OID_ARRAY_INIT;\n \n@@ -816,6 +816,78 @@ static int idx_possible_rename(char *filename, struct dir_rename_info *info)\n \treturn idx;\n }\n \n+struct basename_prefetch_options {\n+\tstruct repository *repo;\n+\tstruct strintmap *relevant_sources;\n+\tstruct strintmap *sources;\n+\tstruct strintmap *dests;\n+\tstruct dir_rename_info *info;\n+};\n+static void basename_prefetch(void *prefetch_options)\n+{\n+\tstruct basename_prefetch_options *options = prefetch_options;\n+\tstruct strintmap *relevant_sources = options->relevant_sources;\n+\tstruct strintmap *sources = options->sources;\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+\n+\t/*\n+\t * TODO: The following loops mirror the code/logic from\n+\t * find_basename_matches(), though not quite exactly. Maybe\n+\t * abstract the iteration logic out somehow?\n+\t */\n+\tfor (i = 0; i < rename_src_nr; ++i) {\n+\t\tchar *filename = rename_src[i].p->one->path;\n+\t\tconst char *base = NULL;\n+\t\tintptr_t src_index;\n+\t\tintptr_t dst_index;\n+\n+\t\t/* Skip irrelevant sources */\n+\t\tif (relevant_sources &&\n+\t\t !strintmap_contains(relevant_sources, filename))\n+\t\t\tcontinue;\n+\n+\t\t/*\n+\t\t * If the basename is unique among remaining sources, then\n+\t\t * src_index will equal 'i' and we can attempt to match it\n+\t\t * to a unique basename in the destinations. Otherwise,\n+\t\t * use directory rename heuristics, if possible.\n+\t\t */\n+\t\tbase = get_basename(filename);\n+\t\tsrc_index = strintmap_get(sources, base);\n+\t\tassert(src_index == -1 || src_index == i);\n+\n+\t\tif (strintmap_contains(dests, base)) {\n+\t\t\tstruct diff_filespec *one, *two;\n+\n+\t\t\t/* Find a matching destination, if possible */\n+\t\t\tdst_index = strintmap_get(dests, base);\n+\t\t\tif (src_index == -1 || dst_index == -1) {\n+\t\t\t\tsrc_index = i;\n+\t\t\t\tdst_index = idx_possible_rename(filename, info);\n+\t\t\t}\n+\t\t\tif (dst_index == -1)\n+\t\t\t\tcontinue;\n+\n+\t\t\t/* Ignore this dest if already used in a rename */\n+\t\t\tif (rename_dst[dst_index].is_rename)\n+\t\t\t\tcontinue; /* already used previously */\n+\n+\t\t\tone = rename_src[src_index].p->one;\n+\t\t\ttwo = rename_dst[dst_index].p->two;\n+\n+\t\t\t/* Add the pairs */\n+\t\t\tdiff_add_if_missing(options->repo, &to_fetch, two);\n+\t\t\tdiff_add_if_missing(options->repo, &to_fetch, one);\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+}\n+\n static int find_basename_matches(struct diff_options *options,\n \t\t\t\t int minimum_score,\n \t\t\t\t struct dir_rename_info *info,\n@@ -860,19 +932,12 @@ static int find_basename_matches(struct diff_options *options,\n \t\t.missing_object_cb = NULL,\n \t\t.missing_object_data = NULL\n \t};\n-\t/*\n-\t * The prefeteching stuff wants to know if it can skip prefetching\n-\t * blobs that are unmodified...and will then do a little extra work\n-\t * to verify that the oids are indeed different before prefetching.\n-\t * Unmodified blobs are only relevant when doing copy detection;\n-\t * when limiting to rename detection, diffcore_rename[_extended]()\n-\t * will never be called with unmodified source paths fed to us, so\n-\t * the extra work necessary to check if rename_src entries are\n-\t * unmodified would be a small waste.\n-\t */\n-\tstruct prefetch_options prefetch_options = {\n+\tstruct basename_prefetch_options prefetch_options = {\n \t\t.repo = options->repo,\n-\t\t.skip_unmodified = 0\n+\t\t.relevant_sources = relevant_sources,\n+\t\t.sources = &sources,\n+\t\t.dests = &dests,\n+\t\t.info = info\n \t};\n \n \t/*\n@@ -911,7 +976,7 @@ static int find_basename_matches(struct diff_options *options,\n \t}\n \n \tif (options->repo == the_repository && has_promisor_remote()) {\n-\t\tdpf_options.missing_object_cb = prefetch;\n+\t\tdpf_options.missing_object_cb = basename_prefetch;\n \t\tdpf_options.missing_object_data = &prefetch_options;\n \t}\n \n@@ -1282,7 +1347,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t.missing_object_cb = NULL,\n \t\t.missing_object_data = NULL\n \t};\n-\tstruct prefetch_options prefetch_options = {\n+\tstruct inexact_prefetch_options prefetch_options = {\n \t\t.repo = options->repo\n \t};\n \n@@ -1449,7 +1514,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t/* Finish setting up dpf_options */\n \tprefetch_options.skip_unmodified = skip_unmodified;\n \tif (options->repo == the_repository && has_promisor_remote()) {\n-\t\tdpf_options.missing_object_cb = prefetch;\n+\t\tdpf_options.missing_object_cb = inexact_prefetch;\n \t\tdpf_options.missing_object_data = &prefetch_options;\n \t}\n \ndiff --git a/t/t6421-merge-partial-clone.sh b/t/t6421-merge-partial-clone.sh\nindex c9d6860de9c9..a011f8d27867 100755\n--- a/t/t6421-merge-partial-clone.sh\n+++ b/t/t6421-merge-partial-clone.sh\n@@ -206,7 +206,7 @@ test_setup_repo () {\n #\n # Summary: 2 fetches (1 for 2 objects, 1 for 1 object)\n #\n-test_expect_merge_algorithm failure failure 'Objects downloaded for single relevant rename' '\n+test_expect_merge_algorithm failure success 'Objects downloaded for single relevant rename' '\n \ttest_setup_repo &&\n \tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-single &&\n \t(\n@@ -295,7 +295,7 @@ test_expect_merge_algorithm failure failure 'Objects downloaded for single relev\n # this are not all that common.)\n # Summary: 1 fetches for 6 objects\n #\n-test_expect_merge_algorithm failure failure 'Objects downloaded when a directory rename triggered' '\n+test_expect_merge_algorithm failure success 'Objects downloaded when a directory rename triggered' '\n \ttest_setup_repo &&\n \tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-dir &&\n \t(\n-- \ngitgitgadget\n\n"},{"id":"427542","messageId":"9f2a8ed8d61f7eef014ec14d93733e2267e1939f.1623796907.git.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.v2.git.1623796907.gitgitgadget@gmail.com","subject":"[PATCH v2 3/5] diffcore-rename: allow different missing_object_cb functions","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-15T22:41:44Z","receivedAt":"2021-06-15T22:42:00Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nestimate_similarity() was setting up a diff_populate_filespec_options\nevery time it was called, requiring the caller of estimate_similarity()\nto pass in some data needed to set up this option. Currently the needed\ndata consisted of a single variable (skip_unmodified), but we want to\nalso have the different estimate_similarity() callsites start using\ndifferent missing_object_cb functions as well. Rather than also passing\nthat data in, just have the caller pass in the whole\ndiff_populate_filespec_options, and reduce the number of times we need to\nset it up.\n\nAs a side note, this also drops the number of calls to\nhas_promisor_remote() dramatically. If L is the number of basename\npaths to compare, M is the number of inexact sources, and N is the\nnumber of inexact destinations, then the number of calls to\nhas_promisor_remote() drops from L+M*N down to at most 2 -- one for each\nof the sites that calls estimate_similarity(). has_promisor_remote() is\na very fast function so this almost certainly has no measurable\nperformance impact, but it seems cleaner to avoid calling that function\nso many times.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 58 +++++++++++++++++++++++++++++++----------------\n 1 file changed, 39 insertions(+), 19 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 35378d84e8f1..e13e52046026 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -126,7 +126,7 @@ static int estimate_similarity(struct repository *r,\n \t\t\t struct diff_filespec *src,\n \t\t\t struct diff_filespec *dst,\n \t\t\t int minimum_score,\n-\t\t\t int skip_unmodified)\n+\t\t\t struct diff_populate_filespec_options *dpf_opt)\n {\n \t/* src points at a file that existed in the original tree (or\n \t * optionally a file in the destination tree) and dst points\n@@ -143,15 +143,6 @@ static int estimate_similarity(struct repository *r,\n \t */\n \tunsigned long max_size, delta_size, base_size, src_copied, literal_added;\n \tint score;\n-\tstruct diff_populate_filespec_options dpf_options = {\n-\t\t.check_size_only = 1\n-\t};\n-\tstruct prefetch_options prefetch_options = {r, skip_unmodified};\n-\n-\tif (r == the_repository && has_promisor_remote()) {\n-\t\tdpf_options.missing_object_cb = prefetch;\n-\t\tdpf_options.missing_object_data = &prefetch_options;\n-\t}\n \n \t/* We deal only with regular files. Symlink renames are handled\n \t * only when they are exact matches --- in other words, no edits\n@@ -169,11 +160,13 @@ static int estimate_similarity(struct repository *r,\n \t * is a possible size - we really should have a flag to\n \t * say whether the size is valid or not!)\n \t */\n+\tdpf_opt->check_size_only = 1;\n+\n \tif (!src->cnt_data &&\n-\t diff_populate_filespec(r, src, &dpf_options))\n+\t diff_populate_filespec(r, src, dpf_opt))\n \t\treturn 0;\n \tif (!dst->cnt_data &&\n-\t diff_populate_filespec(r, dst, &dpf_options))\n+\t diff_populate_filespec(r, dst, dpf_opt))\n \t\treturn 0;\n \n \tmax_size = ((src->size > dst->size) ? src->size : dst->size);\n@@ -191,11 +184,11 @@ static int estimate_similarity(struct repository *r,\n \tif (max_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)\n \t\treturn 0;\n \n-\tdpf_options.check_size_only = 0;\n+\tdpf_opt->check_size_only = 0;\n \n-\tif (!src->cnt_data && diff_populate_filespec(r, src, &dpf_options))\n+\tif (!src->cnt_data && diff_populate_filespec(r, src, dpf_opt))\n \t\treturn 0;\n-\tif (!dst->cnt_data && diff_populate_filespec(r, dst, &dpf_options))\n+\tif (!dst->cnt_data && diff_populate_filespec(r, dst, dpf_opt))\n \t\treturn 0;\n \n \tif (diffcore_count_changes(r, src, dst,\n@@ -862,7 +855,11 @@ static int find_basename_matches(struct diff_options *options,\n \tint i, renames = 0;\n \tstruct strintmap sources;\n \tstruct strintmap dests;\n-\n+\tstruct diff_populate_filespec_options dpf_options = {\n+\t\t.check_binary = 0,\n+\t\t.missing_object_cb = NULL,\n+\t\t.missing_object_data = NULL\n+\t};\n \t/*\n \t * The prefeteching stuff wants to know if it can skip prefetching\n \t * blobs that are unmodified...and will then do a little extra work\n@@ -873,7 +870,10 @@ static int find_basename_matches(struct diff_options *options,\n \t * the extra work necessary to check if rename_src entries are\n \t * unmodified would be a small waste.\n \t */\n-\tint skip_unmodified = 0;\n+\tstruct prefetch_options prefetch_options = {\n+\t\t.repo = options->repo,\n+\t\t.skip_unmodified = 0\n+\t};\n \n \t/*\n \t * Create maps of basename -> fullname(s) for remaining sources and\n@@ -910,6 +910,11 @@ static int find_basename_matches(struct diff_options *options,\n \t\t\tstrintmap_set(&dests, base, i);\n \t}\n \n+\tif (options->repo == the_repository && has_promisor_remote()) {\n+\t\tdpf_options.missing_object_cb = prefetch;\n+\t\tdpf_options.missing_object_data = &prefetch_options;\n+\t}\n+\n \t/* Now look for basename matchups and do similarity estimation */\n \tfor (i = 0; i < rename_src_nr; ++i) {\n \t\tchar *filename = rename_src[i].p->one->path;\n@@ -953,7 +958,7 @@ static int find_basename_matches(struct diff_options *options,\n \t\t\tone = rename_src[src_index].p->one;\n \t\t\ttwo = rename_dst[dst_index].p->two;\n \t\t\tscore = estimate_similarity(options->repo, one, two,\n-\t\t\t\t\t\t minimum_score, skip_unmodified);\n+\t\t\t\t\t\t minimum_score, &dpf_options);\n \n \t\t\t/* If sufficiently similar, record as rename pair */\n \t\t\tif (score < minimum_score)\n@@ -1272,6 +1277,14 @@ void diffcore_rename_extended(struct diff_options *options,\n \tint num_sources, want_copies;\n \tstruct progress *progress = NULL;\n \tstruct dir_rename_info info;\n+\tstruct diff_populate_filespec_options dpf_options = {\n+\t\t.check_binary = 0,\n+\t\t.missing_object_cb = NULL,\n+\t\t.missing_object_data = NULL\n+\t};\n+\tstruct prefetch_options prefetch_options = {\n+\t\t.repo = options->repo\n+\t};\n \n \ttrace2_region_enter(\"diff\", \"setup\", options->repo);\n \tinfo.setup = 0;\n@@ -1433,6 +1446,13 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t\t\t(uint64_t)num_destinations * (uint64_t)num_sources);\n \t}\n \n+\t/* Finish setting up dpf_options */\n+\tprefetch_options.skip_unmodified = skip_unmodified;\n+\tif (options->repo == the_repository && has_promisor_remote()) {\n+\t\tdpf_options.missing_object_cb = prefetch;\n+\t\tdpf_options.missing_object_data = &prefetch_options;\n+\t}\n+\n \tCALLOC_ARRAY(mx, st_mult(NUM_CANDIDATE_PER_DST, num_destinations));\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n \t\tstruct diff_filespec *two = rename_dst[i].p->two;\n@@ -1458,7 +1478,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t\tthis_src.score = estimate_similarity(options->repo,\n \t\t\t\t\t\t\t one, two,\n \t\t\t\t\t\t\t minimum_score,\n-\t\t\t\t\t\t\t skip_unmodified);\n+\t\t\t\t\t\t\t &dpf_options);\n \t\t\tthis_src.name_score = basename_same(one, two);\n \t\t\tthis_src.dst = i;\n \t\t\tthis_src.src = j;\n-- \ngitgitgadget\n\n"},{"id":"427543","messageId":"317bcc7f56cb718a8be625838576f33ce788c3ef.1623796907.git.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.v2.git.1623796907.gitgitgadget@gmail.com","subject":"[PATCH v2 5/5] merge-ort: add prefetching for content merges","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-15T22:41:46Z","receivedAt":"2021-06-15T22:42:02Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nCommit 7fbbcb21b1 (\"diff: batch fetching of missing blobs\", 2019-04-05)\nintroduced batching of fetching missing blobs, so that the diff\nmachinery would have one fetch subprocess grab N blobs instead of N\nprocesses each grabbing 1.\n\nHowever, the diff machinery is not the only thing in a merge that needs\nto work on blobs. The 3-way content merges need them as well. Rather\nthan download all the blobs 1 at a time, prefetch all the blobs needed\nfor regular content merges.\n\nThis does not cover all possible paths in merge-ort that might need to\ndownload blobs. Others include:\n - The blob_unchanged() calls to avoid modify/delete conflicts (when\n blob renormalization results in an \"unchanged\" file)\n - Preliminary content merges needed for rename/add and\n rename/rename(2to1) style conflicts. (Both of these types of\n conflicts can result in nested conflict markers from the need to do\n two levels of content merging; the first happens before our new\n prefetch_for_content_merges() function.)\n\nThe first of these wouldn't be an extreme amount of work to support, and\neven the second could be theoretically supported in batching, but all of\nthese cases seem unusual to me, and this is a minor performance\noptimization anyway; in the worst case we only get some of the fetches\nbatched and have a few additional one-off fetches. So for now, just\nhandle the regular 3-way content merges in our prefetching.\n\nFor the testcase from the previous commit, the number of downloaded\nobjects remains at 63, but this drops the number of fetches needed from\n32 down to 20, a sizeable reduction.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 50 ++++++++++++++++++++++++++++++++++\n t/t6421-merge-partial-clone.sh | 2 +-\n 2 files changed, 51 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex cfa751053b01..e3a5dfc7b312 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -29,6 +29,7 @@\n #include \"entry.h\"\n #include \"ll-merge.h\"\n #include \"object-store.h\"\n+#include \"promisor-remote.h\"\n #include \"revision.h\"\n #include \"strmap.h\"\n #include \"submodule.h\"\n@@ -3485,6 +3486,54 @@ static void process_entry(struct merge_options *opt,\n \trecord_entry_for_tree(dir_metadata, path, &ci->merged);\n }\n \n+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+\n+\tif (opt->repo != the_repository || !has_promisor_remote())\n+\t\treturn;\n+\n+\tfor (e = &plist->items[plist->nr-1]; e >= plist->items; --e) {\n+\t\t/* char *path = e->string; */\n+\t\tstruct conflict_info *ci = e->util;\n+\t\tint i;\n+\n+\t\t/* Ignore clean entries */\n+\t\tif (ci->merged.clean)\n+\t\t\tcontinue;\n+\n+\t\t/* Ignore entries that don't need a content merge */\n+\t\tif (ci->match_mask || ci->filemask < 6 ||\n+\t\t !S_ISREG(ci->stages[1].mode) ||\n+\t\t !S_ISREG(ci->stages[2].mode) ||\n+\t\t oideq(&ci->stages[1].oid, &ci->stages[2].oid))\n+\t\t\tcontinue;\n+\n+\t\t/* Also don't need content merge if base matches either side */\n+\t\tif (ci->filemask == 7 &&\n+\t\t S_ISREG(ci->stages[0].mode) &&\n+\t\t (oideq(&ci->stages[0].oid, &ci->stages[1].oid) ||\n+\t\t oideq(&ci->stages[0].oid, &ci->stages[2].oid)))\n+\t\t\tcontinue;\n+\n+\t\tfor (i = 0; i < 3; i++) {\n+\t\t\tunsigned side_mask = (1 << i);\n+\t\t\tstruct version_info *vi = &ci->stages[i];\n+\n+\t\t\tif ((ci->filemask & side_mask) &&\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}\n+\t}\n+\n+\tpromisor_remote_get_direct(opt->repo, to_fetch.oid, to_fetch.nr);\n+\toid_array_clear(&to_fetch);\n+}\n+\n static void process_entries(struct merge_options *opt,\n \t\t\t struct object_id *result_oid)\n {\n@@ -3531,6 +3580,7 @@ static void process_entries(struct merge_options *opt,\n \t * the way when it is time to process the file at the same path).\n \t */\n \ttrace2_region_enter(\"merge\", \"processing\", opt->repo);\n+\tprefetch_for_content_merges(opt, &plist);\n \tfor (entry = &plist.items[plist.nr-1]; entry >= plist.items; --entry) {\n \t\tchar *path = entry->string;\n \t\t/*\ndiff --git a/t/t6421-merge-partial-clone.sh b/t/t6421-merge-partial-clone.sh\nindex a011f8d27867..26964aa56256 100755\n--- a/t/t6421-merge-partial-clone.sh\n+++ b/t/t6421-merge-partial-clone.sh\n@@ -396,7 +396,7 @@ test_expect_merge_algorithm failure success 'Objects downloaded when a directory\n #\n # Summary: 4 fetches (1 for 6 objects, 1 for 8, 1 for 3, 1 for 2)\n #\n-test_expect_merge_algorithm failure failure 'Objects downloaded with lots of renames and modifications' '\n+test_expect_merge_algorithm failure success 'Objects downloaded with lots of renames and modifications' '\n \ttest_setup_repo &&\n \tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-many &&\n \t(\n-- \ngitgitgadget\n"},{"id":"427626","messageId":"ad73c3f7-46a9-1000-e490-e5f55e283ff1@gmail.com","threadId":"55842","inReplyTo":"pull.969.v2.git.1623796907.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/5] Optimization batch 13: partial clone optimizations for merge-ort","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-06-16T17:54:34Z","receivedAt":"2021-06-16T17:54:40Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/15/2021 6:41 PM, Elijah Newren via GitGitGadget wrote:\n> This series optimizes blob downloading in merges for partial clones. It can\n> apply on master. It's independent of ort-perf-batch-12.\n> \n> Changes since v1:\n> \n> * Incorporated the suggestions from Stolee on patch 2.\n\nThank you for these.\n\n> -+\t\t ..........fetch_count:12\n> -+\t\t ..........fetch_count:5\n> -+\t\t ..........fetch_count:3\n> -+\t\t ......fetch_count:2\n> ++\t\tfetch_count:12\n> ++\t\tfetch_count:5\n> ++\t\tfetch_count:3\n> ++\t\tfetch_count:2\n\nIn particular, I think this simplification will pay dividends in the\nfuture.\n\nAlso, I am in full support of the goals of this series. With such\nchanges, we could potentially re-enable merge.renames in Scalar and\nVFS for Git. Currently, we avoid this so we don't download a huge\nlist of missing blobs whenever pulling the latest changes in these\nenormous repos.\n\nI am still late in doing more meaningful testing which would allow me\nto give this a full stamp of approval. Specifically, I want to merge\nthis code and the rest of merge-ort into the vfs-2.32.0 branch of\nmicrosoft/git and run some sample merges on some private monorepos\nand see how it behaves. I'm very eager to include merge-ort as a\nrecommended config in Scalar, but I haven't had the time to devote\nto testing like this.\n\nI just created a calendar event for Tuesday, June 22nd to hopefully\ndevote the entire day to such an effort. Thank you for your\npatience.\n\nThanks,\n-Stolee\n"},{"id":"427660","messageId":"xmqqk0mtm6yr.fsf@gitster.g","threadId":"55842","inReplyTo":"0f786cfb4c9507a224b1dc3ee6eca9f5ac5c2ae8.1623796907.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 2/5] t6421: add tests checking for excessive object downloads during merge","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-06-17T04:49:00Z","receivedAt":"2021-06-17T04:49:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> +\t\tfor i in `test_seq 1 88`; do\n> +\t\t\techo content $i >dir/unchanged/file_$i\n> +\t\tdone &&\n\n for i in $(...)\n do\n ... || return 1\n done &&\n\n> +test_expect_merge_algorithm failure failure 'Objects downloaded for single relevant rename' '\n> +\ttest_setup_repo &&\n> +\tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-single &&\n> +\t(\n> +\t\tcd objects-single &&\n> +\n> +\t\tgit rev-list --objects --all --missing=print |\n> +\t\t\tgrep '\\?' >missing-objects-before &&\n\nThe closing and reopening of single quote here is somewhat\nmisleading. Wouldn't\n\n\t\tgrep \"?\" >... &&\n\nwork just as well?\n\n> +\t\tgit rev-list --objects --all --missing=print |\n> +\t\t\tgrep ^? >missing-objects-after &&\n> +\t\ttest_cmp missing-objects-before missing-objects-after |\n> +\t\t\tgrep \"^[-+]?\" >found-and-new-objects &&\n\nI do not think we specify what test_cmp's output looks like; we only\nguarantee that it is the right tool to use for expecting two paths\nhave the same contents, and it may give some human readable output.\n\nDo not assume you can grep in the output; use \"diff -u\" if you mean\nyou expect things that exist on the left side and missing from the\nright hand side are prefixed with '-' and vice versa for '+'.\n\nOr sort \"missing-objects-after\" and \"missing-objects-before\" and run \n\"comm\" on them, which might be more stable. Depending on the order\ntwo invocations of rev-list spews out the \"missing\" objects, you may\neven see the same object mentioned with \"-\" and \"+\" in the diff output\nif lines appear to be moved around.\n\n> +\t\t# We should not have any NEW missing objects\n> +\t\t! grep ^+ found-and-new-objects &&\n> +\t\t# Fetched 2+1=3 objects, so should have 3 fewer missing objects\n> +\t\ttest_line_count = 3 found-and-new-objects\n> +\t)\n> +'\n\nI think similar comments apply to the tests in the remainder of the\npatch.\n\nThanks.\n"},{"id":"427663","messageId":"xmqqfsxhm69b.fsf@gitster.g","threadId":"55842","inReplyTo":"317bcc7f56cb718a8be625838576f33ce788c3ef.1623796907.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 5/5] merge-ort: add prefetching for content merges","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-06-17T05:04:16Z","receivedAt":"2021-06-17T05:04:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> +\t\t/* Ignore clean entries */\n> +\t\tif (ci->merged.clean)\n> +\t\t\tcontinue;\n> +\n> +\t\t/* Ignore entries that don't need a content merge */\n> +\t\tif (ci->match_mask || ci->filemask < 6 ||\n> +\t\t !S_ISREG(ci->stages[1].mode) ||\n> +\t\t !S_ISREG(ci->stages[2].mode) ||\n> +\t\t oideq(&ci->stages[1].oid, &ci->stages[2].oid))\n> +\t\t\tcontinue;\n> +\n> +\t\t/* Also don't need content merge if base matches either side */\n> +\t\tif (ci->filemask == 7 &&\n> +\t\t S_ISREG(ci->stages[0].mode) &&\n> +\t\t (oideq(&ci->stages[0].oid, &ci->stages[1].oid) ||\n> +\t\t oideq(&ci->stages[0].oid, &ci->stages[2].oid)))\n> +\t\t\tcontinue;\n\nEven though this is unlikely to change, it is unsatisfactory that we\nreproduce the knowledge on the situations when a merge will\ntrivially resolve and when it will need to go content level.\n\nOne obvious way to solve it would be to fold this logic into the\nmain code that actually merges a list of \"ci\"s by making it a two\npass process (the first pass does essentially the same as this new\nfunction, the second pass does the tree-level merge where the above\nsays \"continue\", fills mmfiles with the loop below, and calls into\nll_merge() after the loop to merge), but the logic duplication is\nnot too big and it may not be worth such a code churn.\n\n> +\t\tfor (i = 0; i < 3; i++) {\n> +\t\t\tunsigned side_mask = (1 << i);\n> +\t\t\tstruct version_info *vi = &ci->stages[i];\n> +\n> +\t\t\tif ((ci->filemask & side_mask) &&\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}\n> +\t}\n> +\n> +\tpromisor_remote_get_direct(opt->repo, to_fetch.oid, to_fetch.nr);\n> +\toid_array_clear(&to_fetch);\n> +}\n> +\n"},{"id":"427664","messageId":"xmqqbl85m67t.fsf@gitster.g","threadId":"55842","inReplyTo":"pull.969.v2.git.1623796907.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/5] Optimization batch 13: partial clone optimizations for merge-ort","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-06-17T05:05:10Z","receivedAt":"2021-06-17T05:05:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> This series optimizes blob downloading in merges for partial clones. It can\n> apply on master. It's independent of ort-perf-batch-12.\n\nOverall this has a good feel of going in the right direction.\nI left comments on a few of the patches, though.\n\nThanks.\n"},{"id":"428179","messageId":"CABPp-BEEUD6UUuL4RmFfgukE=bm4CQjZ2Jy0ZmMaQVaA-Es+zQ@mail.gmail.com","threadId":"55842","inReplyTo":"xmqqfsxhm69b.fsf@gitster.g","subject":"Re: [PATCH v2 5/5] merge-ort: add prefetching for content merges","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-06-22T08:02:38Z","receivedAt":"2021-06-22T08:02:52Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Jun 16, 2021 at 10:04 PM Junio C Hamano wrote:\n>\n> \"Elijah Newren via GitGitGadget\" writes:\n>\n> > + /* Ignore clean entries */\n> > + if (ci->merged.clean)\n> > + continue;\n> > +\n> > + /* Ignore entries that don't need a content merge */\n> > + if (ci->match_mask || ci->filemask < 6 ||\n> > + !S_ISREG(ci->stages[1].mode) ||\n> > + !S_ISREG(ci->stages[2].mode) ||\n> > + oideq(&ci->stages[1].oid, &ci->stages[2].oid))\n> > + continue;\n> > +\n> > + /* Also don't need content merge if base matches either side */\n> > + if (ci->filemask == 7 &&\n> > + S_ISREG(ci->stages[0].mode) &&\n> > + (oideq(&ci->stages[0].oid, &ci->stages[1].oid) ||\n> > + oideq(&ci->stages[0].oid, &ci->stages[2].oid)))\n> > + continue;\n>\n> Even though this is unlikely to change, it is unsatisfactory that we\n> reproduce the knowledge on the situations when a merge will\n> trivially resolve and when it will need to go content level.\n\nI agree, it's not the nicest.\n\n> One obvious way to solve it would be to fold this logic into the\n> main code that actually merges a list of \"ci\"s by making it a two\n> pass process (the first pass does essentially the same as this new\n> function, the second pass does the tree-level merge where the above\n> says \"continue\", fills mmfiles with the loop below, and calls into\n> ll_merge() after the loop to merge), but the logic duplication is\n> not too big and it may not be worth such a code churn.\n\nI'm worried even more about the resulting complexity than the code\nchurn. The two-pass model, which I considered, would require special\ncasing so many of the branches of process_entry() that it feels like\nit'd be increasing code complexity more than introducing a function\nwith a few duplicated checks. process_entry() was already a function\nthat Stolee reported as coming across as pretty complex to him in\nearlier rounds of review, but that seems to just be intrinsic based on\nthe number of special cases: handling anything from entries with D/F\nconflicts, to different file types, to match_mask being precomputed,\nto recursive vs. normal cases, to modify/delete, to normalization, to\nadded on one side, to deleted on both side, to three-way content\nmerges. The three-way content merges are just one of 9-ish different\nbranches, and are the only one that we're prefetching for. It just\nseems easier and cleaner overall to add these three checks to pick off\nthe cases that will end up going through the three-way content merges.\nI've looked at it again a couple times over the past few days based on\nyour comment, but I still can't see a way to restructure it that feels\ncleaner than what I've currently got.\n\nAlso, it may be worth noting here that if these checks fell out of\ndate with process_entry() in some manner, it still would not affect\nthe correctness of the code. At worst, it'd only affect whether\nenough or too many objects are prefetched. If too many, then some\nextra objects would be downloaded, and if too few, then we'd end up\nlater fetching additional objects 1-by-1 on demand later.\n\nSo I'm going to agree with the not-worth-it portion of your final\nsentence and leave this out of the next roll.\n"},{"id":"428180","messageId":"pull.969.v3.git.1624349082.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.v2.git.1623796907.gitgitgadget@gmail.com","subject":"[PATCH v3 0/5] Optimization batch 13: partial clone optimizations for merge-ort","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-22T08:04:36Z","receivedAt":"2021-06-22T08:04:51Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series optimizes blob downloading in merges for partial clones. It can\napply on master. It's independent of ort-perf-batch-12.\n\nChanges since v2:\n\n * Incorporated the suggestions from Junio on patch 2.\n\nChanges since v1:\n\n * Incorporated the suggestions from Stolee on patch 2.\n\n=== High level summary ===\n\n 1. diffcore-rename.c has had a prefetch() to get data needed for inexact\n renames for a while.\n 2. find_basename_matches() only requires a small subset of what prefetch()\n provides.\n 3. I added a basename_prefetch() for find_basename_matches()\n\nIn the worst case, the above means:\n\n * We download the same number of objects, in 2 steps instead of 1.\n\nHowever, in practice, since rename detection can usually quit after\nfind_basename_matches() (usually due to the irrelevant check that cannot be\nperformed until after find_basename_matches()):\n\n * We download far fewer objects, and use barely more download steps than\n before.\n\nAdding some prefetching to merge-ort.c allows us to also drop the number of\ndownloads overall.\n\n=== Modified performance measurement method ===\n\nThe testcases I've been using so far to measure performance were not run in\na partial clone, so they aren't directly usable for comparison. Further,\npartial clone performance depends on network speed which can be highly\nvariable. So I want to modify one of the existing testcases slightly and\nfocus on two different but more stable metrics:\n\n 1. Number of git fetch operations during rebase\n 2. Number of objects fetched during rebase\n\nThe first of these should already be decent due to Jonathan Tan's work to\nbatch fetching of missing blobs during rename detection (see commit\n7fbbcb21b1 (\"diff: batch fetching of missing blobs\", 2019-04-05)), so we are\nmostly looking to optimize the second but would like to also decrease the\nfirst if possible.\n\nThe testcase we will look at will be a modification of the mega-renames\ntestcase from commit 557ac0350d (\"merge-ort: begin performance work;\ninstrument with trace2_region_* calls\", 2020-10-28). In particular, we\nchange\n\n$ git clone \\\n git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git\n\n\nto\n\n$ git clone --sparse --filter=blob:none \\\n https://github.com/github/linux\n\n\n(The change in clone URL is just to get a server that supports the filter\npredicate.)\n\nWe otherwise keep the test the same (in particular, we do not add any calls\nto \"git-sparse checkout {set,add}\" which means that the resulting repository\nwill only have 7 total blobs from files in the toplevel directory before\nstarting the rebase).\n\n=== Results ===\n\nFor the mega-renames testcase noted above (which rebases 35 commits across\nan upstream with ~26K renames in a partial clone), I found the following\nresults for our metrics of interest:\n\n Number of `git fetch` ops during rebase\n\n Before Series After Series\nmerge-recursive: 62 63\nmerge-ort: 30 20\n\n\n Number of objects fetched during rebase\n\n Before Series After Series\nmerge-recursive: 11423 11423\nmerge-ort: 11391 63\n\n\nSo, we have a significant reduction (factor of ~3 relative to\nmerge-recursive) in the number of git fetch operations that have to be\nperformed in a partial clone to complete the rebase, and a dramatic\nreduction (factor of ~180) in the number of objects that need to be fetched.\n\n=== Summary ===\n\nIt's worth pointing out that merge-ort after the series needs only ~1.8\nblobs per commit being transplanted to complete this particular rebase.\nEssentially, this reinforces the fact the optimization work so far has taken\nrename detection from often being an overwhelmingly costly portion of a\nmerge (leading many to just capitulate on it), to what I have observed in my\nexperience so far as being just a minor cost for merges.\n\nElijah Newren (5):\n promisor-remote: output trace2 statistics for number of objects\n fetched\n t6421: add tests checking for excessive object downloads during merge\n diffcore-rename: allow different missing_object_cb functions\n diffcore-rename: use a different prefetch for basename comparisons\n merge-ort: add prefetching for content merges\n\n diffcore-rename.c | 149 ++++++++---\n merge-ort.c | 50 ++++\n promisor-remote.c | 7 +-\n t/t6421-merge-partial-clone.sh | 440 +++++++++++++++++++++++++++++++++\n 4 files changed, 612 insertions(+), 34 deletions(-)\n create mode 100755 t/t6421-merge-partial-clone.sh\n\n\nbase-commit: 6de569e6ac492213e81321ca35f1f1b365ba31e3\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-969%2Fnewren%2Fort-perf-batch-13-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-969/newren/ort-perf-batch-13-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/969\n\nRange-diff vs v2:\n\n 1: 04f5ebdabe14 = 1: 04f5ebdabe14 promisor-remote: output trace2 statistics for number of objects fetched\n 2: 0f786cfb4c95 ! 2: 4796e096fdb4 t6421: add tests checking for excessive object downloads during merge\n @@ t/t6421-merge-partial-clone.sh (new)\n +\t\techo g >dir/subdir/tweaked/g &&\n +\t\techo h >dir/subdir/tweaked/h &&\n +\t\techo subdirectory makefile >dir/subdir/tweaked/Makefile &&\n -+\t\tfor i in `test_seq 1 88`; do\n ++\t\tfor i in $(test_seq 1 88)\n ++\t\tdo\n +\t\t\techo content $i >dir/unchanged/file_$i\n +\t\tdone &&\n +\t\tgit add . &&\n @@ t/t6421-merge-partial-clone.sh (new)\n +\t\tcd objects-single &&\n +\n +\t\tgit rev-list --objects --all --missing=print |\n -+\t\t\tgrep '\\?' >missing-objects-before &&\n ++\t\t\tgrep \"^?\" | sort >missing-objects-before &&\n +\n +\t\tgit checkout -q origin/A &&\n +\n @@ t/t6421-merge-partial-clone.sh (new)\n +\t\ttest_line_count = 2 fetches &&\n +\n +\t\tgit rev-list --objects --all --missing=print |\n -+\t\t\tgrep ^? >missing-objects-after &&\n -+\t\ttest_cmp missing-objects-before missing-objects-after |\n -+\t\t\tgrep \"^[-+]?\" >found-and-new-objects &&\n -+\t\t# We should not have any NEW missing objects\n -+\t\t! grep ^+ found-and-new-objects &&\n -+\t\t# Fetched 2+1=3 objects, so should have 3 fewer missing objects\n -+\t\ttest_line_count = 3 found-and-new-objects\n ++\t\t\tgrep \"^?\" | sort >missing-objects-after &&\n ++\t\tcomm -2 -3 missing-objects-before missing-objects-after >old &&\n ++\t\tcomm -1 -3 missing-objects-before missing-objects-after >new &&\n ++\t\t# No new missing objects\n ++\t\ttest_must_be_empty new &&\n ++\t\t# Fetched 2 + 1 = 3 objects\n ++\t\ttest_line_count = 3 old\n +\t)\n +'\n +\n @@ t/t6421-merge-partial-clone.sh (new)\n +\t\tcd objects-dir &&\n +\n +\t\tgit rev-list --objects --all --missing=print |\n -+\t\t\tgrep '\\?' >missing-objects-before &&\n ++\t\t\tgrep \"^?\" | sort >missing-objects-before &&\n +\n +\t\tgit checkout -q origin/A &&\n +\n @@ t/t6421-merge-partial-clone.sh (new)\n +\t\ttest_line_count = 1 fetches &&\n +\n +\t\tgit rev-list --objects --all --missing=print |\n -+\t\t\tgrep ^? >missing-objects-after &&\n -+\t\ttest_cmp missing-objects-before missing-objects-after |\n -+\t\t\tgrep \"^[-+]?\" >found-and-new-objects &&\n -+\t\t# We should not have any NEW missing objects\n -+\t\t! grep ^+ found-and-new-objects &&\n -+\t\t# Fetched 6 objects, so should have 6 fewer missing objects\n -+\t\ttest_line_count = 6 found-and-new-objects\n ++\t\t\tgrep \"^?\" | sort >missing-objects-after &&\n ++\t\tcomm -2 -3 missing-objects-before missing-objects-after >old &&\n ++\t\tcomm -1 -3 missing-objects-before missing-objects-after >new &&\n ++\t\t# No new missing objects\n ++\t\ttest_must_be_empty new &&\n ++\t\t# Fetched 6 objects\n ++\t\ttest_line_count = 6 old\n +\t)\n +'\n +\n @@ t/t6421-merge-partial-clone.sh (new)\n +\t\tcd objects-many &&\n +\n +\t\tgit rev-list --objects --all --missing=print |\n -+\t\t\tgrep '\\?' >missing-objects-before &&\n ++\t\t\tgrep \"^?\" | sort >missing-objects-before &&\n +\n +\t\tgit checkout -q origin/A &&\n +\n @@ t/t6421-merge-partial-clone.sh (new)\n +\t\ttest_line_count = 4 fetches &&\n +\n +\t\tgit rev-list --objects --all --missing=print |\n -+\t\t\tgrep ^? >missing-objects-after &&\n -+\t\ttest_cmp missing-objects-before missing-objects-after |\n -+\t\t\tgrep \"^[-+]?\" >found-and-new-objects &&\n -+\t\t# We should not have any NEW missing objects\n -+\t\t! grep ^+ found-and-new-objects &&\n -+\t\t# Fetched 12 + 5 + 3 + 2 == 22 objects\n -+\t\ttest_line_count = 22 found-and-new-objects\n ++\t\t\tgrep \"^?\" | sort >missing-objects-after &&\n ++\t\tcomm -2 -3 missing-objects-before missing-objects-after >old &&\n ++\t\tcomm -1 -3 missing-objects-before missing-objects-after >new &&\n ++\t\t# No new missing objects\n ++\t\ttest_must_be_empty new &&\n ++\t\t# Fetched 12 + 5 + 3 + 2 = 22 objects\n ++\t\ttest_line_count = 22 old\n +\t)\n +'\n +\n 3: 9f2a8ed8d61f = 3: 7ed0162cdb4e diffcore-rename: allow different missing_object_cb functions\n 4: f753f8035564 = 4: c9b55241d831 diffcore-rename: use a different prefetch for basename comparisons\n 5: 317bcc7f56cb = 5: 69011cfe9fae merge-ort: add prefetching for content merges\n\n-- \ngitgitgadget\n"},{"id":"428181","messageId":"04f5ebdabe147b6652c5487ad2a440ba7b7389d5.1624349082.git.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.v3.git.1624349082.gitgitgadget@gmail.com","subject":"[PATCH v3 1/5] promisor-remote: output trace2 statistics for number of objects fetched","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-22T08:04:37Z","receivedAt":"2021-06-22T08:04:52Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nSigned-off-by: Elijah Newren \n---\n promisor-remote.c | 7 +++++--\n 1 file changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/promisor-remote.c b/promisor-remote.c\nindex da3f2ca2615e..d465377d7d32 100644\n--- a/promisor-remote.c\n+++ b/promisor-remote.c\n@@ -12,7 +12,8 @@ void set_repository_format_partial_clone(char *partial_clone)\n \trepository_format_partial_clone = xstrdup_or_null(partial_clone);\n }\n \n-static int fetch_objects(const char *remote_name,\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 {\n@@ -30,6 +31,8 @@ static int fetch_objects(const char *remote_name,\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+\n \tfor (i = 0; i < oid_nr; i++) {\n \t\tif (fputs(oid_to_hex(&oids[i]), child_in) < 0)\n \t\t\tdie_errno(_(\"promisor-remote: could not write to fetch subprocess\"));\n@@ -238,7 +241,7 @@ int promisor_remote_get_direct(struct repository *repo,\n \tpromisor_remote_init();\n \n \tfor (r = promisors; r; r = r->next) {\n-\t\tif (fetch_objects(r->name, remaining_oids, remaining_nr) < 0) {\n+\t\tif (fetch_objects(repo, r->name, remaining_oids, remaining_nr) < 0) {\n \t\t\tif (remaining_nr == 1)\n \t\t\t\tcontinue;\n \t\t\tremaining_nr = remove_fetched_oids(repo, &remaining_oids,\n-- \ngitgitgadget\n\n"},{"id":"428182","messageId":"7ed0162cdb4e3fe20c122bffa093d366c30df9c7.1624349082.git.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.v3.git.1624349082.gitgitgadget@gmail.com","subject":"[PATCH v3 3/5] diffcore-rename: allow different missing_object_cb functions","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-22T08:04:39Z","receivedAt":"2021-06-22T08:04:53Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nestimate_similarity() was setting up a diff_populate_filespec_options\nevery time it was called, requiring the caller of estimate_similarity()\nto pass in some data needed to set up this option. Currently the needed\ndata consisted of a single variable (skip_unmodified), but we want to\nalso have the different estimate_similarity() callsites start using\ndifferent missing_object_cb functions as well. Rather than also passing\nthat data in, just have the caller pass in the whole\ndiff_populate_filespec_options, and reduce the number of times we need to\nset it up.\n\nAs a side note, this also drops the number of calls to\nhas_promisor_remote() dramatically. If L is the number of basename\npaths to compare, M is the number of inexact sources, and N is the\nnumber of inexact destinations, then the number of calls to\nhas_promisor_remote() drops from L+M*N down to at most 2 -- one for each\nof the sites that calls estimate_similarity(). has_promisor_remote() is\na very fast function so this almost certainly has no measurable\nperformance impact, but it seems cleaner to avoid calling that function\nso many times.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 58 +++++++++++++++++++++++++++++++----------------\n 1 file changed, 39 insertions(+), 19 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 35378d84e8f1..e13e52046026 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -126,7 +126,7 @@ static int estimate_similarity(struct repository *r,\n \t\t\t struct diff_filespec *src,\n \t\t\t struct diff_filespec *dst,\n \t\t\t int minimum_score,\n-\t\t\t int skip_unmodified)\n+\t\t\t struct diff_populate_filespec_options *dpf_opt)\n {\n \t/* src points at a file that existed in the original tree (or\n \t * optionally a file in the destination tree) and dst points\n@@ -143,15 +143,6 @@ static int estimate_similarity(struct repository *r,\n \t */\n \tunsigned long max_size, delta_size, base_size, src_copied, literal_added;\n \tint score;\n-\tstruct diff_populate_filespec_options dpf_options = {\n-\t\t.check_size_only = 1\n-\t};\n-\tstruct prefetch_options prefetch_options = {r, skip_unmodified};\n-\n-\tif (r == the_repository && has_promisor_remote()) {\n-\t\tdpf_options.missing_object_cb = prefetch;\n-\t\tdpf_options.missing_object_data = &prefetch_options;\n-\t}\n \n \t/* We deal only with regular files. Symlink renames are handled\n \t * only when they are exact matches --- in other words, no edits\n@@ -169,11 +160,13 @@ static int estimate_similarity(struct repository *r,\n \t * is a possible size - we really should have a flag to\n \t * say whether the size is valid or not!)\n \t */\n+\tdpf_opt->check_size_only = 1;\n+\n \tif (!src->cnt_data &&\n-\t diff_populate_filespec(r, src, &dpf_options))\n+\t diff_populate_filespec(r, src, dpf_opt))\n \t\treturn 0;\n \tif (!dst->cnt_data &&\n-\t diff_populate_filespec(r, dst, &dpf_options))\n+\t diff_populate_filespec(r, dst, dpf_opt))\n \t\treturn 0;\n \n \tmax_size = ((src->size > dst->size) ? src->size : dst->size);\n@@ -191,11 +184,11 @@ static int estimate_similarity(struct repository *r,\n \tif (max_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)\n \t\treturn 0;\n \n-\tdpf_options.check_size_only = 0;\n+\tdpf_opt->check_size_only = 0;\n \n-\tif (!src->cnt_data && diff_populate_filespec(r, src, &dpf_options))\n+\tif (!src->cnt_data && diff_populate_filespec(r, src, dpf_opt))\n \t\treturn 0;\n-\tif (!dst->cnt_data && diff_populate_filespec(r, dst, &dpf_options))\n+\tif (!dst->cnt_data && diff_populate_filespec(r, dst, dpf_opt))\n \t\treturn 0;\n \n \tif (diffcore_count_changes(r, src, dst,\n@@ -862,7 +855,11 @@ static int find_basename_matches(struct diff_options *options,\n \tint i, renames = 0;\n \tstruct strintmap sources;\n \tstruct strintmap dests;\n-\n+\tstruct diff_populate_filespec_options dpf_options = {\n+\t\t.check_binary = 0,\n+\t\t.missing_object_cb = NULL,\n+\t\t.missing_object_data = NULL\n+\t};\n \t/*\n \t * The prefeteching stuff wants to know if it can skip prefetching\n \t * blobs that are unmodified...and will then do a little extra work\n@@ -873,7 +870,10 @@ static int find_basename_matches(struct diff_options *options,\n \t * the extra work necessary to check if rename_src entries are\n \t * unmodified would be a small waste.\n \t */\n-\tint skip_unmodified = 0;\n+\tstruct prefetch_options prefetch_options = {\n+\t\t.repo = options->repo,\n+\t\t.skip_unmodified = 0\n+\t};\n \n \t/*\n \t * Create maps of basename -> fullname(s) for remaining sources and\n@@ -910,6 +910,11 @@ static int find_basename_matches(struct diff_options *options,\n \t\t\tstrintmap_set(&dests, base, i);\n \t}\n \n+\tif (options->repo == the_repository && has_promisor_remote()) {\n+\t\tdpf_options.missing_object_cb = prefetch;\n+\t\tdpf_options.missing_object_data = &prefetch_options;\n+\t}\n+\n \t/* Now look for basename matchups and do similarity estimation */\n \tfor (i = 0; i < rename_src_nr; ++i) {\n \t\tchar *filename = rename_src[i].p->one->path;\n@@ -953,7 +958,7 @@ static int find_basename_matches(struct diff_options *options,\n \t\t\tone = rename_src[src_index].p->one;\n \t\t\ttwo = rename_dst[dst_index].p->two;\n \t\t\tscore = estimate_similarity(options->repo, one, two,\n-\t\t\t\t\t\t minimum_score, skip_unmodified);\n+\t\t\t\t\t\t minimum_score, &dpf_options);\n \n \t\t\t/* If sufficiently similar, record as rename pair */\n \t\t\tif (score < minimum_score)\n@@ -1272,6 +1277,14 @@ void diffcore_rename_extended(struct diff_options *options,\n \tint num_sources, want_copies;\n \tstruct progress *progress = NULL;\n \tstruct dir_rename_info info;\n+\tstruct diff_populate_filespec_options dpf_options = {\n+\t\t.check_binary = 0,\n+\t\t.missing_object_cb = NULL,\n+\t\t.missing_object_data = NULL\n+\t};\n+\tstruct prefetch_options prefetch_options = {\n+\t\t.repo = options->repo\n+\t};\n \n \ttrace2_region_enter(\"diff\", \"setup\", options->repo);\n \tinfo.setup = 0;\n@@ -1433,6 +1446,13 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t\t\t(uint64_t)num_destinations * (uint64_t)num_sources);\n \t}\n \n+\t/* Finish setting up dpf_options */\n+\tprefetch_options.skip_unmodified = skip_unmodified;\n+\tif (options->repo == the_repository && has_promisor_remote()) {\n+\t\tdpf_options.missing_object_cb = prefetch;\n+\t\tdpf_options.missing_object_data = &prefetch_options;\n+\t}\n+\n \tCALLOC_ARRAY(mx, st_mult(NUM_CANDIDATE_PER_DST, num_destinations));\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n \t\tstruct diff_filespec *two = rename_dst[i].p->two;\n@@ -1458,7 +1478,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t\tthis_src.score = estimate_similarity(options->repo,\n \t\t\t\t\t\t\t one, two,\n \t\t\t\t\t\t\t minimum_score,\n-\t\t\t\t\t\t\t skip_unmodified);\n+\t\t\t\t\t\t\t &dpf_options);\n \t\t\tthis_src.name_score = basename_same(one, two);\n \t\t\tthis_src.dst = i;\n \t\t\tthis_src.src = j;\n-- \ngitgitgadget\n\n"},{"id":"428183","messageId":"4796e096fdb4f4ef8513c0e9214754d41b4db5d7.1624349082.git.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.v3.git.1624349082.gitgitgadget@gmail.com","subject":"[PATCH v3 2/5] t6421: add tests checking for excessive object downloads during merge","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-22T08:04:38Z","receivedAt":"2021-06-22T08:04:56Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nSigned-off-by: Elijah Newren \n---\n t/t6421-merge-partial-clone.sh | 440 +++++++++++++++++++++++++++++++++\n 1 file changed, 440 insertions(+)\n create mode 100755 t/t6421-merge-partial-clone.sh\n\ndiff --git a/t/t6421-merge-partial-clone.sh b/t/t6421-merge-partial-clone.sh\nnew file mode 100755\nindex 000000000000..3dcffc15f801\n--- /dev/null\n+++ b/t/t6421-merge-partial-clone.sh\n@@ -0,0 +1,440 @@\n+#!/bin/sh\n+\n+test_description=\"limiting blob downloads when merging with partial clones\"\n+# Uses a methodology similar to\n+# t6042: corner cases with renames but not criss-cross merges\n+# t6036: corner cases with both renames and criss-cross merges\n+# t6423: directory rename detection\n+#\n+# The setup for all of them, pictorially, is:\n+#\n+# A\n+# o\n+# / \\\n+# O o ?\n+# \\ /\n+# o\n+# B\n+#\n+# To help make it easier to follow the flow of tests, they have been\n+# divided into sections and each test will start with a quick explanation\n+# of what commits O, A, and B contain.\n+#\n+# Notation:\n+# z/{b,c} means files z/b and z/c both exist\n+# x/d_1 means file x/d exists with content d1. (Purpose of the\n+# underscore notation is to differentiate different\n+# files that might be renamed into each other's paths.)\n+\n+. ./test-lib.sh\n+. \"$TEST_DIRECTORY\"/lib-merge.sh\n+\n+test_setup_repo () {\n+\ttest -d server && return\n+\ttest_create_repo server &&\n+\t(\n+\t\tcd server &&\n+\n+\t\tgit config uploadpack.allowfilter 1 &&\n+\t\tgit config uploadpack.allowanysha1inwant 1 &&\n+\n+\t\tmkdir -p general &&\n+\t\ttest_seq 2 9 >general/leap1 &&\n+\t\tcp general/leap1 general/leap2 &&\n+\t\techo leap2 >>general/leap2 &&\n+\n+\t\tmkdir -p basename &&\n+\t\tcp general/leap1 basename/numbers &&\n+\t\tcp general/leap1 basename/sequence &&\n+\t\tcp general/leap1 basename/values &&\n+\t\techo numbers >>basename/numbers &&\n+\t\techo sequence >>basename/sequence &&\n+\t\techo values >>basename/values &&\n+\n+\t\tmkdir -p dir/unchanged &&\n+\t\tmkdir -p dir/subdir/tweaked &&\n+\t\techo a >dir/subdir/a &&\n+\t\techo b >dir/subdir/b &&\n+\t\techo c >dir/subdir/c &&\n+\t\techo d >dir/subdir/d &&\n+\t\techo e >dir/subdir/e &&\n+\t\tcp general/leap1 dir/subdir/Makefile &&\n+\t\techo toplevel makefile >>dir/subdir/Makefile &&\n+\t\techo f >dir/subdir/tweaked/f &&\n+\t\techo g >dir/subdir/tweaked/g &&\n+\t\techo h >dir/subdir/tweaked/h &&\n+\t\techo subdirectory makefile >dir/subdir/tweaked/Makefile &&\n+\t\tfor i in $(test_seq 1 88)\n+\t\tdo\n+\t\t\techo content $i >dir/unchanged/file_$i\n+\t\tdone &&\n+\t\tgit add . &&\n+\t\tgit commit -m \"O\" &&\n+\n+\t\tgit branch O &&\n+\t\tgit branch A &&\n+\t\tgit branch B-single &&\n+\t\tgit branch B-dir &&\n+\t\tgit branch B-many &&\n+\n+\t\tgit switch A &&\n+\n+\t\tgit rm general/leap* &&\n+\t\tmkdir general/ &&\n+\t\ttest_seq 1 9 >general/jump1 &&\n+\t\tcp general/jump1 general/jump2 &&\n+\t\techo leap2 >>general/jump2 &&\n+\n+\t\trm basename/numbers basename/sequence basename/values &&\n+\t\tmkdir -p basename/subdir/\n+\t\tcp general/jump1 basename/subdir/numbers &&\n+\t\tcp general/jump1 basename/subdir/sequence &&\n+\t\tcp general/jump1 basename/subdir/values &&\n+\t\techo numbers >>basename/subdir/numbers &&\n+\t\techo sequence >>basename/subdir/sequence &&\n+\t\techo values >>basename/subdir/values &&\n+\n+\t\tgit rm dir/subdir/tweaked/f &&\n+\t\techo more >>dir/subdir/e &&\n+\t\techo more >>dir/subdir/Makefile &&\n+\t\techo more >>dir/subdir/tweaked/Makefile &&\n+\t\tmkdir dir/subdir/newsubdir &&\n+\t\techo rust code >dir/subdir/newsubdir/newfile.rs &&\n+\t\tgit mv dir/subdir/e dir/subdir/newsubdir/ &&\n+\t\tgit mv dir folder &&\n+\t\tgit add . &&\n+\t\tgit commit -m \"A\" &&\n+\n+\t\tgit switch B-single &&\n+\t\techo new first line >dir/subdir/Makefile &&\n+\t\tcat general/leap1 >>dir/subdir/Makefile &&\n+\t\techo toplevel makefile >>dir/subdir/Makefile &&\n+\t\techo perl code >general/newfile.pl &&\n+\t\tgit add . &&\n+\t\tgit commit -m \"B-single\" &&\n+\n+\t\tgit switch B-dir &&\n+\t\techo java code >dir/subdir/newfile.java &&\n+\t\techo scala code >dir/subdir/newfile.scala &&\n+\t\techo groovy code >dir/subdir/newfile.groovy &&\n+\t\tgit add . &&\n+\t\tgit commit -m \"B-dir\" &&\n+\n+\t\tgit switch B-many &&\n+\t\ttest_seq 2 10 >general/leap1 &&\n+\t\trm general/leap2 &&\n+\t\tcp general/leap1 general/leap2 &&\n+\t\techo leap2 >>general/leap2 &&\n+\n+\t\trm basename/numbers basename/sequence basename/values &&\n+\t\tmkdir -p basename/subdir/\n+\t\tcp general/leap1 basename/subdir/numbers &&\n+\t\tcp general/leap1 basename/subdir/sequence &&\n+\t\tcp general/leap1 basename/subdir/values &&\n+\t\techo numbers >>basename/subdir/numbers &&\n+\t\techo sequence >>basename/subdir/sequence &&\n+\t\techo values >>basename/subdir/values &&\n+\n+\t\tmkdir dir/subdir/newsubdir/ &&\n+\t\techo c code >dir/subdir/newfile.c &&\n+\t\techo python code >dir/subdir/newsubdir/newfile.py &&\n+\t\tgit add . &&\n+\t\tgit commit -m \"B-many\" &&\n+\n+\t\tgit switch A\n+\t)\n+}\n+\n+# Testcase: Objects downloaded for single relevant rename\n+# Commit O:\n+# general/{leap1_O, leap2_O}\n+# basename/{numbers_O, sequence_O, values_O}\n+# dir/subdir/{a,b,c,d,e_O,Makefile_TOP_O}\n+# dir/subdir/tweaked/{f,g,h,Makefile_SUB_O}\n+# dir/unchanged/\n+# Commit A:\n+# (Rename leap->jump, rename basename/ -> basename/subdir/, rename dir/\n+# -> folder/, move e into newsubdir, add newfile.rs, remove f, modify\n+# both both Makefiles and jumps)\n+# general/{jump1_A, jump2_A}\n+# basename/subdir/{numbers_A, sequence_A, values_A}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_A}\n+# folder/subdir/newsubdir/{e_A,newfile.rs}\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A}\n+# folder/unchanged/\n+# Commit B(-single):\n+# (add newfile.pl, tweak Makefile_TOP)\n+# general/{leap1_O, leap2_O,newfile.pl}\n+# basename/{numbers_O, sequence_O, values_O}\n+# dir/{a,b,c,d,e_O,Makefile_TOP_B}\n+# dir/tweaked/{f,g,h,Makefile_SUB_O}\n+# dir/unchanged/\n+# Expected:\n+# general/{jump1_A, jump2_A,newfile.pl}\n+# basename/subdir/{numbers_A, sequence_A, values_A}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_Merged}\n+# folder/subdir/newsubdir/{e_A,newfile.rs}\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A}\n+# folder/unchanged/\n+#\n+# Objects that need to be fetched:\n+# Rename detection:\n+# Side1 (O->A):\n+# Basename-matches rename detection only needs to fetch these objects:\n+# Makefile_TOP_O, Makefile_TOP_A\n+# (Despite many renames, all others are content irrelevant. They\n+# are also location irrelevant because newfile.rs was added on\n+# the side doing the directory rename, and newfile.pl was added to\n+# a directory that was not renamed on either side.)\n+# General rename detection only needs to fetch these objects:\n+# \n+# (Even though newfile.rs, jump[12], basename/subdir/*, and e\n+# could all be used as destinations in rename detection, the\n+# basename detection for Makefile matches up all relevant\n+# sources, so these other files never end up needing to be\n+# used)\n+# Side2 (O->B):\n+# Basename-matches rename detection only needs to fetch these objects:\n+# \n+# (there are no deleted files, so no possible sources)\n+# General rename detection only needs to fetch these objects:\n+# \n+# (there are no deleted files, so no possible sources)\n+# Merge:\n+# 3-way content merge needs to grab these objects:\n+# Makefile_TOP_B\n+# Nothing else needs to fetch objects\n+#\n+# Summary: 2 fetches (1 for 2 objects, 1 for 1 object)\n+#\n+test_expect_merge_algorithm failure failure 'Objects downloaded for single relevant rename' '\n+\ttest_setup_repo &&\n+\tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-single &&\n+\t(\n+\t\tcd objects-single &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep \"^?\" | sort >missing-objects-before &&\n+\n+\t\tgit checkout -q origin/A &&\n+\n+\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git \\\n+\t\t\t-c merge.directoryRenames=true merge --no-stat \\\n+\t\t\t--no-progress origin/B-single &&\n+\n+\t\t# Check the number of objects we reported we would fetch\n+\t\tcat >expect <<-EOF &&\n+\t\tfetch_count:2\n+\t\tfetch_count:1\n+\t\tEOF\n+\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 | tr -d \" .\" >actual &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\t# Check the number of fetch commands exec-ed\n+\t\tgrep d0.*fetch.negotiationAlgorithm trace.output >fetches &&\n+\t\ttest_line_count = 2 fetches &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep \"^?\" | sort >missing-objects-after &&\n+\t\tcomm -2 -3 missing-objects-before missing-objects-after >old &&\n+\t\tcomm -1 -3 missing-objects-before missing-objects-after >new &&\n+\t\t# No new missing objects\n+\t\ttest_must_be_empty new &&\n+\t\t# Fetched 2 + 1 = 3 objects\n+\t\ttest_line_count = 3 old\n+\t)\n+'\n+\n+# Testcase: Objects downloaded for directory rename\n+# Commit O:\n+# general/{leap1_O, leap2_O}\n+# basename/{numbers_O, sequence_O, values_O}\n+# dir/subdir/{a,b,c,d,e_O,Makefile_TOP_O}\n+# dir/subdir/tweaked/{f,g,h,Makefile_SUB_O}\n+# dir/unchanged/\n+# Commit A:\n+# (Rename leap->jump, rename basename/ -> basename/subdir/, rename dir/ ->\n+# folder/, move e into newsubdir, add newfile.rs, remove f, modify\n+# both Makefiles and jumps)\n+# general/{jump1_A, jump2_A}\n+# basename/subdir/{numbers_A, sequence_A, values_A}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_A}\n+# folder/subdir/newsubdir/{e_A,newfile.rs}\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A}\n+# folder/unchanged/\n+# Commit B(-dir):\n+# (add dir/subdir/newfile.{java,scala,groovy}\n+# general/{leap1_O, leap2_O}\n+# basename/{numbers_O, sequence_O, values_O}\n+# dir/subdir/{a,b,c,d,e_O,Makefile_TOP_O,\n+# newfile.java,newfile.scala,newfile.groovy}\n+# dir/subdir/tweaked/{f,g,h,Makefile_SUB_O}\n+# dir/unchanged/\n+# Expected:\n+# general/{jump1_A, jump2_A}\n+# basename/subdir/{numbers_A, sequence_A, values_A}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_A,\n+# newfile.java,newfile.scala,newfile.groovy}\n+# folder/subdir/newsubdir/{e_A,newfile.rs}\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A}\n+# folder/unchanged/\n+#\n+# Objects that need to be fetched:\n+# Makefile_TOP_O, Makefile_TOP_A\n+# Makefile_SUB_O, Makefile_SUB_A\n+# e_O, e_A\n+# * Despite A's rename of jump->leap, those renames are irrelevant.\n+# * Despite A's rename of basename/ -> basename/subdir/, those renames are\n+# irrelevant.\n+# * Because of A's rename of dir/ -> folder/ and B-dir's addition of\n+# newfile.* into dir/subdir/, we need to determine directory renames.\n+# (Technically, there are enough exact renames to determine directory\n+# rename detection, but the current implementation always does\n+# basename searching before directory rename detection. Running it\n+# also before basename searching would mean doing directory rename\n+# detection twice, but it's a bit expensive to do that and cases like\n+# this are not all that common.)\n+# Summary: 1 fetches for 6 objects\n+#\n+test_expect_merge_algorithm failure failure 'Objects downloaded when a directory rename triggered' '\n+\ttest_setup_repo &&\n+\tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-dir &&\n+\t(\n+\t\tcd objects-dir &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep \"^?\" | sort >missing-objects-before &&\n+\n+\t\tgit checkout -q origin/A &&\n+\n+\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git \\\n+\t\t\t-c merge.directoryRenames=true merge --no-stat \\\n+\t\t\t--no-progress origin/B-dir &&\n+\n+\t\t# Check the number of objects we reported we would fetch\n+\t\tcat >expect <<-EOF &&\n+\t\tfetch_count:6\n+\t\tEOF\n+\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 | tr -d \" .\" >actual &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\t# Check the number of fetch commands exec-ed\n+\t\tgrep d0.*fetch.negotiationAlgorithm trace.output >fetches &&\n+\t\ttest_line_count = 1 fetches &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep \"^?\" | sort >missing-objects-after &&\n+\t\tcomm -2 -3 missing-objects-before missing-objects-after >old &&\n+\t\tcomm -1 -3 missing-objects-before missing-objects-after >new &&\n+\t\t# No new missing objects\n+\t\ttest_must_be_empty new &&\n+\t\t# Fetched 6 objects\n+\t\ttest_line_count = 6 old\n+\t)\n+'\n+\n+# Testcase: Objects downloaded with lots of renames and modifications\n+# Commit O:\n+# general/{leap1_O, leap2_O}\n+# basename/{numbers_O, sequence_O, values_O}\n+# dir/subdir/{a,b,c,d,e_O,Makefile_TOP_O}\n+# dir/subdir/tweaked/{f,g,h,Makefile_SUB_O}\n+# dir/unchanged/\n+# Commit A:\n+# (Rename leap->jump, rename basename/ -> basename/subdir/, rename dir/\n+# -> folder/, move e into newsubdir, add newfile.rs, remove f, modify\n+# both both Makefiles and jumps)\n+# general/{jump1_A, jump2_A}\n+# basename/subdir/{numbers_A, sequence_A, values_A}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_A}\n+# folder/subdir/newsubdir/{e_A,newfile.rs}\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A}\n+# folder/unchanged/\n+# Commit B(-minimal):\n+# (modify both leaps, rename basename/ -> basename/subdir/, add\n+# newfile.{c,py})\n+# general/{leap1_B, leap2_B}\n+# basename/subdir/{numbers_B, sequence_B, values_B}\n+# dir/{a,b,c,d,e_O,Makefile_TOP_O,newfile.c}\n+# dir/tweaked/{f,g,h,Makefile_SUB_O,newfile.py}\n+# dir/unchanged/\n+# Expected:\n+# general/{jump1_Merged, jump2_Merged}\n+# basename/subdir/{numbers_Merged, sequence_Merged, values_Merged}\n+# folder/subdir/{a,b,c,d,Makefile_TOP_A,newfile.c}\n+# folder/subdir/newsubdir/e_A\n+# folder/subdir/tweaked/{g,h,Makefile_SUB_A,newfile.py}\n+# folder/unchanged/\n+#\n+# Objects that need to be fetched:\n+# Rename detection:\n+# Side1 (O->A):\n+# Basename-matches rename detection only needs to fetch these objects:\n+# numbers_O, numbers_A\n+# sequence_O, sequence_A\n+# values_O, values_A\n+# Makefile_TOP_O, Makefile_TOP_A\n+# Makefile_SUB_O, Makefile_SUB_A\n+# e_O, e_A\n+# General rename detection only needs to fetch these objects:\n+# leap1_O, leap2_O\n+# jump1_A, jump2_A, newfile.rs\n+# (only need remaining relevant sources, but any relevant sources need\n+# to be matched against all possible unpaired destinations)\n+# Side2 (O->B):\n+# Basename-matches rename detection only needs to fetch these objects:\n+# numbers_B\n+# sequence_B\n+# values_B\n+# (because numbers_O, sequence_O, and values_O already fetched above)\n+# General rename detection only needs to fetch these objects:\n+# \n+# Merge:\n+# 3-way content merge needs to grab these objects:\n+# leap1_B\n+# leap2_B\n+# Nothing else needs to fetch objects\n+#\n+# Summary: 4 fetches (1 for 6 objects, 1 for 8, 1 for 3, 1 for 2)\n+#\n+test_expect_merge_algorithm failure failure 'Objects downloaded with lots of renames and modifications' '\n+\ttest_setup_repo &&\n+\tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-many &&\n+\t(\n+\t\tcd objects-many &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep \"^?\" | sort >missing-objects-before &&\n+\n+\t\tgit checkout -q origin/A &&\n+\n+\t\tGIT_TRACE2_PERF=\"$(pwd)/trace.output\" git \\\n+\t\t\t-c merge.directoryRenames=true merge --no-stat \\\n+\t\t\t--no-progress origin/B-many &&\n+\n+\t\t# Check the number of objects we reported we would fetch\n+\t\tcat >expect <<-EOF &&\n+\t\tfetch_count:12\n+\t\tfetch_count:5\n+\t\tfetch_count:3\n+\t\tfetch_count:2\n+\t\tEOF\n+\t\tgrep fetch_count trace.output | cut -d \"|\" -f 9 | tr -d \" .\" >actual &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\t# Check the number of fetch commands exec-ed\n+\t\tgrep d0.*fetch.negotiationAlgorithm trace.output >fetches &&\n+\t\ttest_line_count = 4 fetches &&\n+\n+\t\tgit rev-list --objects --all --missing=print |\n+\t\t\tgrep \"^?\" | sort >missing-objects-after &&\n+\t\tcomm -2 -3 missing-objects-before missing-objects-after >old &&\n+\t\tcomm -1 -3 missing-objects-before missing-objects-after >new &&\n+\t\t# No new missing objects\n+\t\ttest_must_be_empty new &&\n+\t\t# Fetched 12 + 5 + 3 + 2 = 22 objects\n+\t\ttest_line_count = 22 old\n+\t)\n+'\n+\n+test_done\n-- \ngitgitgadget\n\n"},{"id":"428184","messageId":"c9b55241d83144df0ddc479f67fbf3aabca43bd8.1624349082.git.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.v3.git.1624349082.gitgitgadget@gmail.com","subject":"[PATCH v3 4/5] diffcore-rename: use a different prefetch for basename comparisons","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-22T08:04:40Z","receivedAt":"2021-06-22T08:04:58Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nmerge-ort was designed to minimize the amount of data needed and used,\nand several changes were made to diffcore-rename to take advantage of\nextra metadata to enable this data minimization (particularly the\nrelevant_sources variable for skipping \"irrelevant\" renames). This\neffort obviously succeeded in drastically reducing computation times,\nbut should also theoretically allow partial clones to download much less\ninformation. Previously, though, the \"prefetch\" command used in\ndiffcore-rename had never been modified and downloaded many blobs that\nwere unnecessary for merge-ort. This commit corrects that.\n\nWhen doing basename comparisons, we want to fetch only the objects that\nwill be used for basename comparisons. If after basename fetching this\nleaves us with no more relevant sources (or no more destinations), then\nwe won't need to do the full inexact rename detection and can skip\ndownloading additional source and destination files. Even if we have to\ndo that later full inexact rename detection, irrelevant sources are\nculled after basename matching and before the full inexact rename\ndetection, so we can still avoid downloading the blobs for irrelevant\nsources. Rename prefetch() to inexact_prefetch(), and introduce a\nnew basename_prefetch() to take advantage of this.\n\nIf we modify the testcase from commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2021-01-23)\nto pass\n --sparse --filter=blob:none\nto the clone command, and use the new trace2 \"fetch_count\" output from\na few commits ago to track both the number of fetch subcommands invoked\nand the number of objects fetched across all those fetches, then for\nthe mega-renames testcase we observe the following:\n\nBEFORE this commit, rebasing 35 patches:\n strategy # of fetches total # of objects fetched\n --------- ------------ --------------------------\n recursive 62 11423\n ort 30 11391\n\nAFTER this commit, rebasing the same 35 patches:\n ort 32 63\n\nThis means that the new code only needs to download less than 2 blobs\nper patch being rebased. That is especially interesting given that the\nrepository at the start only had approximately half a dozen TOTAL blobs\ndownloaded to start with (because the default sparse-checkout of just\nthe toplevel directory was in use).\n\nSo, for this particular linux kernel testcase that involved ~26,000\nrenames on the upstream side (drivers/ -> pilots/) across which 35\npatches were being rebased, this change reduces the number of blobs that\nneed to be downloaded by a factor of ~180.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 101 +++++++++++++++++++++++++++------\n t/t6421-merge-partial-clone.sh | 4 +-\n 2 files changed, 85 insertions(+), 20 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex e13e52046026..4ef0459cfb50 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -87,13 +87,13 @@ struct diff_score {\n \tshort name_score;\n };\n \n-struct prefetch_options {\n+struct inexact_prefetch_options {\n \tstruct repository *repo;\n \tint skip_unmodified;\n };\n-static void prefetch(void *prefetch_options)\n+static void inexact_prefetch(void *prefetch_options)\n {\n-\tstruct prefetch_options *options = prefetch_options;\n+\tstruct inexact_prefetch_options *options = prefetch_options;\n \tint i;\n \tstruct oid_array to_fetch = OID_ARRAY_INIT;\n \n@@ -816,6 +816,78 @@ static int idx_possible_rename(char *filename, struct dir_rename_info *info)\n \treturn idx;\n }\n \n+struct basename_prefetch_options {\n+\tstruct repository *repo;\n+\tstruct strintmap *relevant_sources;\n+\tstruct strintmap *sources;\n+\tstruct strintmap *dests;\n+\tstruct dir_rename_info *info;\n+};\n+static void basename_prefetch(void *prefetch_options)\n+{\n+\tstruct basename_prefetch_options *options = prefetch_options;\n+\tstruct strintmap *relevant_sources = options->relevant_sources;\n+\tstruct strintmap *sources = options->sources;\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+\n+\t/*\n+\t * TODO: The following loops mirror the code/logic from\n+\t * find_basename_matches(), though not quite exactly. Maybe\n+\t * abstract the iteration logic out somehow?\n+\t */\n+\tfor (i = 0; i < rename_src_nr; ++i) {\n+\t\tchar *filename = rename_src[i].p->one->path;\n+\t\tconst char *base = NULL;\n+\t\tintptr_t src_index;\n+\t\tintptr_t dst_index;\n+\n+\t\t/* Skip irrelevant sources */\n+\t\tif (relevant_sources &&\n+\t\t !strintmap_contains(relevant_sources, filename))\n+\t\t\tcontinue;\n+\n+\t\t/*\n+\t\t * If the basename is unique among remaining sources, then\n+\t\t * src_index will equal 'i' and we can attempt to match it\n+\t\t * to a unique basename in the destinations. Otherwise,\n+\t\t * use directory rename heuristics, if possible.\n+\t\t */\n+\t\tbase = get_basename(filename);\n+\t\tsrc_index = strintmap_get(sources, base);\n+\t\tassert(src_index == -1 || src_index == i);\n+\n+\t\tif (strintmap_contains(dests, base)) {\n+\t\t\tstruct diff_filespec *one, *two;\n+\n+\t\t\t/* Find a matching destination, if possible */\n+\t\t\tdst_index = strintmap_get(dests, base);\n+\t\t\tif (src_index == -1 || dst_index == -1) {\n+\t\t\t\tsrc_index = i;\n+\t\t\t\tdst_index = idx_possible_rename(filename, info);\n+\t\t\t}\n+\t\t\tif (dst_index == -1)\n+\t\t\t\tcontinue;\n+\n+\t\t\t/* Ignore this dest if already used in a rename */\n+\t\t\tif (rename_dst[dst_index].is_rename)\n+\t\t\t\tcontinue; /* already used previously */\n+\n+\t\t\tone = rename_src[src_index].p->one;\n+\t\t\ttwo = rename_dst[dst_index].p->two;\n+\n+\t\t\t/* Add the pairs */\n+\t\t\tdiff_add_if_missing(options->repo, &to_fetch, two);\n+\t\t\tdiff_add_if_missing(options->repo, &to_fetch, one);\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+}\n+\n static int find_basename_matches(struct diff_options *options,\n \t\t\t\t int minimum_score,\n \t\t\t\t struct dir_rename_info *info,\n@@ -860,19 +932,12 @@ static int find_basename_matches(struct diff_options *options,\n \t\t.missing_object_cb = NULL,\n \t\t.missing_object_data = NULL\n \t};\n-\t/*\n-\t * The prefeteching stuff wants to know if it can skip prefetching\n-\t * blobs that are unmodified...and will then do a little extra work\n-\t * to verify that the oids are indeed different before prefetching.\n-\t * Unmodified blobs are only relevant when doing copy detection;\n-\t * when limiting to rename detection, diffcore_rename[_extended]()\n-\t * will never be called with unmodified source paths fed to us, so\n-\t * the extra work necessary to check if rename_src entries are\n-\t * unmodified would be a small waste.\n-\t */\n-\tstruct prefetch_options prefetch_options = {\n+\tstruct basename_prefetch_options prefetch_options = {\n \t\t.repo = options->repo,\n-\t\t.skip_unmodified = 0\n+\t\t.relevant_sources = relevant_sources,\n+\t\t.sources = &sources,\n+\t\t.dests = &dests,\n+\t\t.info = info\n \t};\n \n \t/*\n@@ -911,7 +976,7 @@ static int find_basename_matches(struct diff_options *options,\n \t}\n \n \tif (options->repo == the_repository && has_promisor_remote()) {\n-\t\tdpf_options.missing_object_cb = prefetch;\n+\t\tdpf_options.missing_object_cb = basename_prefetch;\n \t\tdpf_options.missing_object_data = &prefetch_options;\n \t}\n \n@@ -1282,7 +1347,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t.missing_object_cb = NULL,\n \t\t.missing_object_data = NULL\n \t};\n-\tstruct prefetch_options prefetch_options = {\n+\tstruct inexact_prefetch_options prefetch_options = {\n \t\t.repo = options->repo\n \t};\n \n@@ -1449,7 +1514,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t/* Finish setting up dpf_options */\n \tprefetch_options.skip_unmodified = skip_unmodified;\n \tif (options->repo == the_repository && has_promisor_remote()) {\n-\t\tdpf_options.missing_object_cb = prefetch;\n+\t\tdpf_options.missing_object_cb = inexact_prefetch;\n \t\tdpf_options.missing_object_data = &prefetch_options;\n \t}\n \ndiff --git a/t/t6421-merge-partial-clone.sh b/t/t6421-merge-partial-clone.sh\nindex 3dcffc15f801..aad975d24ddb 100755\n--- a/t/t6421-merge-partial-clone.sh\n+++ b/t/t6421-merge-partial-clone.sh\n@@ -207,7 +207,7 @@ test_setup_repo () {\n #\n # Summary: 2 fetches (1 for 2 objects, 1 for 1 object)\n #\n-test_expect_merge_algorithm failure failure 'Objects downloaded for single relevant rename' '\n+test_expect_merge_algorithm failure success 'Objects downloaded for single relevant rename' '\n \ttest_setup_repo &&\n \tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-single &&\n \t(\n@@ -296,7 +296,7 @@ test_expect_merge_algorithm failure failure 'Objects downloaded for single relev\n # this are not all that common.)\n # Summary: 1 fetches for 6 objects\n #\n-test_expect_merge_algorithm failure failure 'Objects downloaded when a directory rename triggered' '\n+test_expect_merge_algorithm failure success 'Objects downloaded when a directory rename triggered' '\n \ttest_setup_repo &&\n \tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-dir &&\n \t(\n-- \ngitgitgadget\n\n"},{"id":"428185","messageId":"69011cfe9fae1410213aae7a5599a3cd3c4207ce.1624349082.git.gitgitgadget@gmail.com","threadId":"55842","inReplyTo":"pull.969.v3.git.1624349082.gitgitgadget@gmail.com","subject":"[PATCH v3 5/5] merge-ort: add prefetching for content merges","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-22T08:04:41Z","receivedAt":"2021-06-22T08:05:06Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nCommit 7fbbcb21b1 (\"diff: batch fetching of missing blobs\", 2019-04-05)\nintroduced batching of fetching missing blobs, so that the diff\nmachinery would have one fetch subprocess grab N blobs instead of N\nprocesses each grabbing 1.\n\nHowever, the diff machinery is not the only thing in a merge that needs\nto work on blobs. The 3-way content merges need them as well. Rather\nthan download all the blobs 1 at a time, prefetch all the blobs needed\nfor regular content merges.\n\nThis does not cover all possible paths in merge-ort that might need to\ndownload blobs. Others include:\n - The blob_unchanged() calls to avoid modify/delete conflicts (when\n blob renormalization results in an \"unchanged\" file)\n - Preliminary content merges needed for rename/add and\n rename/rename(2to1) style conflicts. (Both of these types of\n conflicts can result in nested conflict markers from the need to do\n two levels of content merging; the first happens before our new\n prefetch_for_content_merges() function.)\n\nThe first of these wouldn't be an extreme amount of work to support, and\neven the second could be theoretically supported in batching, but all of\nthese cases seem unusual to me, and this is a minor performance\noptimization anyway; in the worst case we only get some of the fetches\nbatched and have a few additional one-off fetches. So for now, just\nhandle the regular 3-way content merges in our prefetching.\n\nFor the testcase from the previous commit, the number of downloaded\nobjects remains at 63, but this drops the number of fetches needed from\n32 down to 20, a sizeable reduction.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 50 ++++++++++++++++++++++++++++++++++\n t/t6421-merge-partial-clone.sh | 2 +-\n 2 files changed, 51 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex cfa751053b01..e3a5dfc7b312 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -29,6 +29,7 @@\n #include \"entry.h\"\n #include \"ll-merge.h\"\n #include \"object-store.h\"\n+#include \"promisor-remote.h\"\n #include \"revision.h\"\n #include \"strmap.h\"\n #include \"submodule.h\"\n@@ -3485,6 +3486,54 @@ static void process_entry(struct merge_options *opt,\n \trecord_entry_for_tree(dir_metadata, path, &ci->merged);\n }\n \n+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+\n+\tif (opt->repo != the_repository || !has_promisor_remote())\n+\t\treturn;\n+\n+\tfor (e = &plist->items[plist->nr-1]; e >= plist->items; --e) {\n+\t\t/* char *path = e->string; */\n+\t\tstruct conflict_info *ci = e->util;\n+\t\tint i;\n+\n+\t\t/* Ignore clean entries */\n+\t\tif (ci->merged.clean)\n+\t\t\tcontinue;\n+\n+\t\t/* Ignore entries that don't need a content merge */\n+\t\tif (ci->match_mask || ci->filemask < 6 ||\n+\t\t !S_ISREG(ci->stages[1].mode) ||\n+\t\t !S_ISREG(ci->stages[2].mode) ||\n+\t\t oideq(&ci->stages[1].oid, &ci->stages[2].oid))\n+\t\t\tcontinue;\n+\n+\t\t/* Also don't need content merge if base matches either side */\n+\t\tif (ci->filemask == 7 &&\n+\t\t S_ISREG(ci->stages[0].mode) &&\n+\t\t (oideq(&ci->stages[0].oid, &ci->stages[1].oid) ||\n+\t\t oideq(&ci->stages[0].oid, &ci->stages[2].oid)))\n+\t\t\tcontinue;\n+\n+\t\tfor (i = 0; i < 3; i++) {\n+\t\t\tunsigned side_mask = (1 << i);\n+\t\t\tstruct version_info *vi = &ci->stages[i];\n+\n+\t\t\tif ((ci->filemask & side_mask) &&\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}\n+\t}\n+\n+\tpromisor_remote_get_direct(opt->repo, to_fetch.oid, to_fetch.nr);\n+\toid_array_clear(&to_fetch);\n+}\n+\n static void process_entries(struct merge_options *opt,\n \t\t\t struct object_id *result_oid)\n {\n@@ -3531,6 +3580,7 @@ static void process_entries(struct merge_options *opt,\n \t * the way when it is time to process the file at the same path).\n \t */\n \ttrace2_region_enter(\"merge\", \"processing\", opt->repo);\n+\tprefetch_for_content_merges(opt, &plist);\n \tfor (entry = &plist.items[plist.nr-1]; entry >= plist.items; --entry) {\n \t\tchar *path = entry->string;\n \t\t/*\ndiff --git a/t/t6421-merge-partial-clone.sh b/t/t6421-merge-partial-clone.sh\nindex aad975d24ddb..36bcd7c32801 100755\n--- a/t/t6421-merge-partial-clone.sh\n+++ b/t/t6421-merge-partial-clone.sh\n@@ -397,7 +397,7 @@ test_expect_merge_algorithm failure success 'Objects downloaded when a directory\n #\n # Summary: 4 fetches (1 for 6 objects, 1 for 8, 1 for 3, 1 for 2)\n #\n-test_expect_merge_algorithm failure failure 'Objects downloaded with lots of renames and modifications' '\n+test_expect_merge_algorithm failure success 'Objects downloaded with lots of renames and modifications' '\n \ttest_setup_repo &&\n \tgit clone --sparse --filter=blob:none \"file://$(pwd)/server\" objects-many &&\n \t(\n-- \ngitgitgadget\n"},{"id":"428213","messageId":"3a397e04-88a1-1205-a465-75dc2fd7e93d@gmail.com","threadId":"55842","inReplyTo":"pull.969.v3.git.1624349082.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 0/5] Optimization batch 13: partial clone optimizations for merge-ort","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-06-22T16:10:34Z","receivedAt":"2021-06-22T16:10:42Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/22/2021 4:04 AM, Elijah Newren via GitGitGadget wrote:\n> This series optimizes blob downloading in merges for partial clones. It can\n> apply on master. It's independent of ort-perf-batch-12.\n\nAs promised, I completed a performance evaluation of this series as well\nas ort-perf-batch-12 (and all earlier batches) against our microsoft/git\nfork and running in one of our large monorepos that has over 2 million\nfiles at HEAD. Here are my findings.\n\nIn my comparisons, I compare the recursive merge strategy with renames\ndisabled against the ORT strategy (which always has renames enabled). When\nI enabled renames for the recursive merge I saw the partial clone logic\nkick in and start downloading many files in every case, so I dropped that\nfrom consideration.\n\n\nExperiment #1: Large RI/FI merges\n---------------------------------\n\nMost of the merge commits in this repo's history are merges of several\nlong-lived branches as code is merged across organizational boundaries. I\nfocused on the merge commits in the first-parent history, which mean these\nare the merges that brought the latest changes from several areas into the\ncanonical version of the software.\n\nThese merges are all automated merges created by libgit2's implementation\nof the recursive merge strategy. Since they are created on the server,\nthese will not have any merge conflicts.\n\nThey are still interesting because the sheer number of files that change\ncan be large. This is a pain point for the recursive merge because many\nindex entries need to update with the merge. For ORT, some of the updates\nare simple because only one side changed a certain subtree (the\norganizational boundaries also correspond to the directory structure in\nmany cases).\n\nAcross these merges I tested, ORT was _always_ faster and was consistent\nwith the recursive strategy. Even more interesting was the fact that the\nrecursive strategy had very slow outliers while the ORT strategy was much\nmore consistent:\n\n Recursive ORT\n-----------------------\nMAX 34.97s 4.74s\nP90 30.04s 4.50s\nP75 15.35s 3.74s\nP50 7.22s 3.39s\nP10 3.61s 3.08s\n\n(I'm not testing ORT with the sparse-index yet. A significant portion of\nthis 3 second lower bound is due to reading and writing the index file\nwith 2 million entries. I _am_ using sparse-checkout with only the files\nat root, which minimizes the time required to update the working directory\nwith any changed files.)\n\nFor these merges, ORT is a clear win.\n\n\nExperiment #2: User-created merges\n----------------------------------\n\nTo find merges that might be created by actual user cases, I ran\n'git rev-list --grep=\"^Merge branch\"' to get merges that had default\nmessages from 'git merge' runs. (The merges from Experiment #1 had other\nautomated names that did not appear in this search.)\n\nHere, the differences are less striking, but still valuable:\n\n Recursive ORT\n-----------------------\nMAX 10.61s 6.27s\nP75 8.81s 3.92s\nP50 4.32s 3.21s\nP10 3.53s 2.95s\n\nThe ORT strategy had more variance in these examples, though still not as\nmuch as the recursive strategy. Here the variance is due to conflicting\nfiles needing content merges, which usually were automatically resolved.\n\nThis version of the experiment provided interesting observations in a few\ncases:\n\n1. One case had the recursive merge strategy result in a root tree that\n disagreed with what the user committed, but the ORT strategy _did_ the\n correct resolution. Likely, this is due to the rename detection and\n resolution. The user probably had to manually resolve the merge to\n match their expected renames since we turn off merge.renames in their\n config.\n\n2. I watched for the partial clone logic to kick in and download blobs.\n Some of these were inevitable: we need the blobs to resolve edit/edit\n conflicts. Most cases none were downloaded at all, so this series is\n working as advertised. There _was_ a case where the inexact rename\n detection requested a large list of files (~2900 in three batches) but\n _then_ said \"inexact rename detection was skipped due to too many\n files\". This is a case that would be nice to resolve in this series. I\n will try to find exactly where in the code this is being triggered and\n report back.\n\n3. As I mentioned, I was using sparse-checkout to limit the size of the\n working directory. In one case of a conflict that could not be\n automatically resolved, the ORT strategy output this error:\n\n error: could not open '': No such file or directory\n\n It seems we are looking for a file on disk without considering if it\n might have the SKIP_WORKTREE bit on in the index. I don't think this is\n an issue for this series, but might require a follow-up on top of the\n other ORT work.\n\n\nConclusions\n-----------\n\nI continue to be excited about the ORT strategy and will likely be\nfocusing on it in a month or so to integrate it with the sparse-index. I\nthink we would be interested in making the ORT strategy a new default for\nScalar, but we might really want it to respect merge.renames=false if only\nso we can deploy the settings in stages (first, change the strategy, then\nenable renames as an independent step) so we can isolate concerns.\n\n\nThanks!\n-Stolee\n"},{"id":"428224","messageId":"CABPp-BH9vy3otHvAxR2T6JmVKtH2+EKj-A7NxGsuoqnZA_Bykg@mail.gmail.com","threadId":"55842","inReplyTo":"3a397e04-88a1-1205-a465-75dc2fd7e93d@gmail.com","subject":"Re: [PATCH v3 0/5] Optimization batch 13: partial clone optimizations for merge-ort","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-06-22T18:45:04Z","receivedAt":"2021-06-22T18:45:18Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Jun 22, 2021 at 9:10 AM Derrick Stolee wrote:\n>\n> On 6/22/2021 4:04 AM, Elijah Newren via GitGitGadget wrote:\n> > This series optimizes blob downloading in merges for partial clones. It can\n> > apply on master. It's independent of ort-perf-batch-12.\n>\n> As promised, I completed a performance evaluation of this series as well\n> as ort-perf-batch-12 (and all earlier batches) against our microsoft/git\n> fork and running in one of our large monorepos that has over 2 million\n> files at HEAD. Here are my findings.\n\nNice, thanks for the investigation and the detailed report!\n\n> In my comparisons, I compare the recursive merge strategy with renames\n> disabled against the ORT strategy (which always has renames enabled). When\n> I enabled renames for the recursive merge I saw the partial clone logic\n> kick in and start downloading many files in every case, so I dropped that\n> from consideration.\n\nI understand it'd take way too long to do an exhaustive testing, but\njust doing a couple example comparisons against recursive with rename\ndetection turned on (and merge.renameLimit set to e.g. 0, or to some\nhigh number if needed) would still be interesting.\n\n> Experiment #1: Large RI/FI merges\n> ---------------------------------\n>\n...\n> Recursive ORT\n> -----------------------\n> MAX 34.97s 4.74s\n> P90 30.04s 4.50s\n> P75 15.35s 3.74s\n> P50 7.22s 3.39s\n> P10 3.61s 3.08s\n>\n> (I'm not testing ORT with the sparse-index yet. A significant portion of\n> this 3 second lower bound is due to reading and writing the index file\n> with 2 million entries. I _am_ using sparse-checkout with only the files\n> at root, which minimizes the time required to update the working directory\n> with any changed files.)\n>\n> For these merges, ORT is a clear win.\n\nWahoo!\n\nI suspect I know what you're seeing from recursive as well; recursive\nhad some quadratic behaviors found within it, separate from the calls\ninto diffcore-rename. It was much less likely to be triggered with\nrename detection turned off, but could still be triggered. I suspect\nyou just had enough testcases that some of them were affected. (I\nparticularly suspect the item described at (5a) of\nhttps://lore.kernel.org/git/pull.842.git.1612331345.gitgitgadget@gmail.com/)\n\nGiven the 2 million entries, I'm curious if ort-perf-batch-14 (not yet\nsubmitted; I've been waiting a few weeks for ort-perf-batch-12 to hit\nnext) will provide further significant benefits. If it really does\ntake 3s or so to do index reading and writing, then it'd only be able\nto help with the slower cases, but I'm still curious. It helped\nrather dramatically on my linux kernel testcase with lots of renames.\n\n\n> Experiment #2: User-created merges\n> ----------------------------------\n>\n> To find merges that might be created by actual user cases, I ran\n> 'git rev-list --grep=\"^Merge branch\"' to get merges that had default\n> messages from 'git merge' runs. (The merges from Experiment #1 had other\n> automated names that did not appear in this search.)\n>\n> Here, the differences are less striking, but still valuable:\n>\n> Recursive ORT\n> -----------------------\n> MAX 10.61s 6.27s\n> P75 8.81s 3.92s\n> P50 4.32s 3.21s\n> P10 3.53s 2.95s\n>\n> The ORT strategy had more variance in these examples, though still not as\n> much as the recursive strategy. Here the variance is due to conflicting\n> files needing content merges, which usually were automatically resolved.\n\nIs the max case on the ort side related to item #2 below, where\nperhaps there was a case where there was no automatic resolution of\nsome file?\n\n> This version of the experiment provided interesting observations in a few\n> cases:\n>\n> 1. One case had the recursive merge strategy result in a root tree that\n> disagreed with what the user committed, but the ORT strategy _did_ the\n> correct resolution. Likely, this is due to the rename detection and\n> resolution. The user probably had to manually resolve the merge to\n> match their expected renames since we turn off merge.renames in their\n> config.\n\nI agree that seems like the likely explanation.\n\n> 2. I watched for the partial clone logic to kick in and download blobs.\n> Some of these were inevitable: we need the blobs to resolve edit/edit\n> conflicts. Most cases none were downloaded at all, so this series is\n> working as advertised. There _was_ a case where the inexact rename\n> detection requested a large list of files (~2900 in three batches) but\n> _then_ said \"inexact rename detection was skipped due to too many\n> files\". This is a case that would be nice to resolve in this series. I\n> will try to find exactly where in the code this is being triggered and\n> report back.\n\nThis suggests perhaps that EITHER there was a real modify/delete\nconflict (because you have to do full rename detection to rule out\nthat the modify/delete was part of some rename), OR that there was a\nrenamed file modified on both sides that did not keep its original\nbasename (because that combination is needed to bypass the various\noptimizations and make it fall back to full inexact rename detection).\nFurther, in either case, there were enough adds/deletes that full\ninexact detection is still a bit expensive. It'd be interesting to\nknow which case it was. What happens if you set merge.renameLimit to\nsomething higher (the default is surprisingly small)?\n\n> 3. As I mentioned, I was using sparse-checkout to limit the size of the\n> working directory. In one case of a conflict that could not be\n> automatically resolved, the ORT strategy output this error:\n>\n> error: could not open '': No such file or directory\n>\n> It seems we are looking for a file on disk without considering if it\n> might have the SKIP_WORKTREE bit on in the index. I don't think this is\n> an issue for this series, but might require a follow-up on top of the\n> other ORT work.\n\nI suspect either checkout() or record_conflicted_index_entries() are\nto blame, and yeah, it'd be an issue from a previous series. If you\nhave any further details or even hints about reproducing (doesn't have\nto be a complete set of steps or minimal testcase), I would love to\nhear it. (Incidentally, of all the reviews on merge-ort, those two\nfunctions were left out; look for \"17\" and \"19\" in\nhttps://lore.kernel.org/git/pull.923.git.git.1606635803.gitgitgadget@gmail.com/\n)\n\n\n> Conclusions\n> -----------\n>\n> I continue to be excited about the ORT strategy and will likely be\n> focusing on it in a month or so to integrate it with the sparse-index. I\n> think we would be interested in making the ORT strategy a new default for\n> Scalar, but we might really want it to respect merge.renames=false if only\n> so we can deploy the settings in stages (first, change the strategy, then\n> enable renames as an independent step) so we can isolate concerns.\n\nGiven that my ort performance work concentrated on rename detection,\nit's encouraging to see that ort-WITH-renames is generally faster for\nyou than recursive-WITHOUT-renames. That means not only that rename\ndetection can be done in reasonable time now, but that the\nimprovements outside of rename detection show some real benefits as\nwell. It'll be interesting to see how the final two performance\nseries for merge-ort, which will concentrate on performance on areas\nother than rename detection, will affect these above results.\n\n\nAnd by the way, thanks for the herculean review effort you've put in.\nYou've reviewed nearly every merge-ort and diffcore-rename patch\n(which included many big, tricky patches)...and a quick search says\nthere's been at least 128 patches so far in the last 8 months. And\nthe code is better (cleaner, clearer, and faster) for all your\nreviews.\n"},{"id":"428246","messageId":"8f1edc60-f754-541b-1d66-7f5ec49eff55@gmail.com","threadId":"55842","inReplyTo":"CABPp-BH9vy3otHvAxR2T6JmVKtH2+EKj-A7NxGsuoqnZA_Bykg@mail.gmail.com","subject":"Re: [PATCH v3 0/5] Optimization batch 13: partial clone optimizations for merge-ort","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-06-23T02:14:03Z","receivedAt":"2021-06-23T02:14:07Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/22/2021 2:45 PM, Elijah Newren wrote:\n> On Tue, Jun 22, 2021 at 9:10 AM Derrick Stolee wrote:\n\nI want to focus on this item:\n\n>> 2. I watched for the partial clone logic to kick in and download blobs.\n>> Some of these were inevitable: we need the blobs to resolve edit/edit\n>> conflicts. Most cases none were downloaded at all, so this series is\n>> working as advertised. There _was_ a case where the inexact rename\n>> detection requested a large list of files (~2900 in three batches) but\n>> _then_ said \"inexact rename detection was skipped due to too many\n>> files\". This is a case that would be nice to resolve in this series. I\n>> will try to find exactly where in the code this is being triggered and\n>> report back.\n> \n> This suggests perhaps that EITHER there was a real modify/delete\n> conflict (because you have to do full rename detection to rule out\n> that the modify/delete was part of some rename), OR that there was a\n> renamed file modified on both sides that did not keep its original\n> basename (because that combination is needed to bypass the various\n> optimizations and make it fall back to full inexact rename detection).\n> Further, in either case, there were enough adds/deletes that full\n> inexact detection is still a bit expensive. It'd be interesting to\n> know which case it was. What happens if you set merge.renameLimit to\n> something higher (the default is surprisingly small)?\n\nThe behavior I'd like to see is that the partial clone logic is not\nrun if we are going to download more than merge.renameLimit files.\nWhatever is getting these missing blobs is earlier than the limit\ncheck, but it should be after instead.\n\nIt's particularly problematic that Git does all the work to get the\nblobs, but then gives up and doesn't even use them for rename\ndetection.\n\nI'm happy that we download necessary blobs when there are a few\ndozen files that need inexact renames. When it gets into the\nthousands, then we jump into a different category of user experience.\n\nHaving a stop-gap of rename detection limits is an important way to\navoid huge amounts of file downloads in these huge repo cases. Users\ncan always opt into a larger limit if they really do want that rename\ndetection to work at such a large scale, but we still need protections\nfor the vast majority of cases where a user isn't willing to pay the\ncost of downloading these blobs.\n\nThanks,\n-Stolee\n"},{"id":"428260","messageId":"CABPp-BEuHbFbTWXKhW0MYkcW9ScJfUungwL6y9g=W=bZ=cmCbg@mail.gmail.com","threadId":"55842","inReplyTo":"8f1edc60-f754-541b-1d66-7f5ec49eff55@gmail.com","subject":"Re: [PATCH v3 0/5] Optimization batch 13: partial clone optimizations for merge-ort","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-06-23T08:11:19Z","receivedAt":"2021-06-23T08:11:34Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Jun 22, 2021 at 7:14 PM Derrick Stolee wrote:\n>\n> On 6/22/2021 2:45 PM, Elijah Newren wrote:\n> > On Tue, Jun 22, 2021 at 9:10 AM Derrick Stolee wrote:\n>\n> I want to focus on this item:\n>\n> >> 2. I watched for the partial clone logic to kick in and download blobs.\n> >> Some of these were inevitable: we need the blobs to resolve edit/edit\n> >> conflicts. Most cases none were downloaded at all, so this series is\n> >> working as advertised. There _was_ a case where the inexact rename\n> >> detection requested a large list of files (~2900 in three batches) but\n> >> _then_ said \"inexact rename detection was skipped due to too many\n> >> files\". This is a case that would be nice to resolve in this series. I\n> >> will try to find exactly where in the code this is being triggered and\n> >> report back.\n> >\n> > This suggests perhaps that EITHER there was a real modify/delete\n> > conflict (because you have to do full rename detection to rule out\n> > that the modify/delete was part of some rename), OR that there was a\n> > renamed file modified on both sides that did not keep its original\n> > basename (because that combination is needed to bypass the various\n> > optimizations and make it fall back to full inexact rename detection).\n> > Further, in either case, there were enough adds/deletes that full\n> > inexact detection is still a bit expensive. It'd be interesting to\n> > know which case it was. What happens if you set merge.renameLimit to\n> > something higher (the default is surprisingly small)?\n>\n> The behavior I'd like to see is that the partial clone logic is not\n> run if we are going to download more than merge.renameLimit files.\n> Whatever is getting these missing blobs is earlier than the limit\n> check, but it should be after instead.\n>\n> It's particularly problematic that Git does all the work to get the\n> blobs, but then gives up and doesn't even use them for rename\n> detection.\n\nI agree with what should happen, but I'm surprised it's not already\nhappening. The give up check comes from too_many_rename_candidates(),\nwhich is called before dpf_options.missing_object_cb is even set to\ninexact_prefetch. So I'm not sure how the fetching comes first. Is\nthere a microsoft specific patch that changes the order somehow? Is\nthere something I'm mis-reading in the code?\n\n> I'm happy that we download necessary blobs when there are a few\n> dozen files that need inexact renames. When it gets into the\n> thousands, then we jump into a different category of user experience.\n>\n> Having a stop-gap of rename detection limits is an important way to\n> avoid huge amounts of file downloads in these huge repo cases. Users\n> can always opt into a larger limit if they really do want that rename\n> detection to work at such a large scale, but we still need protections\n> for the vast majority of cases where a user isn't willing to pay the\n> cost of downloading these blobs.\n\nSure, that's fair.\n\nBut I'm still curious what the particular shape is for the data in\nquestion. What does the error say merge.renameLimit would be need to\nset to? If it's set higher, do some of the files resolve nicely (i.e.\nthey really were renames modified on both sides with a different\nbasename), or are they modify/delete conflicts and we're paying the\ncost of rename detection to verify they were deleted and we really do\nhave a conflict? I'm curious if there's more to learn and more\noptimization potential, basically. Your repository is bigger, so\nthere may be more to learn from it than from the testcases I've tried\nso far. :-)\n"},{"id":"428280","messageId":"CABPp-BE3W0yfM3aB0hM+EG15zV=krSMv3kGRTjfVNV2rQtiDrA@mail.gmail.com","threadId":"55842","inReplyTo":"CABPp-BEuHbFbTWXKhW0MYkcW9ScJfUungwL6y9g=W=bZ=cmCbg@mail.gmail.com","subject":"Re: [PATCH v3 0/5] Optimization batch 13: partial clone optimizations for merge-ort","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-06-23T17:31:15Z","receivedAt":"2021-06-23T17:31:30Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Jun 23, 2021 at 1:11 AM Elijah Newren wrote:\n>\n> On Tue, Jun 22, 2021 at 7:14 PM Derrick Stolee wrote:\n> >\n> > On 6/22/2021 2:45 PM, Elijah Newren wrote:\n> > > On Tue, Jun 22, 2021 at 9:10 AM Derrick Stolee wrote:\n> >\n> > I want to focus on this item:\n> >\n> > >> 2. I watched for the partial clone logic to kick in and download blobs.\n> > >> Some of these were inevitable: we need the blobs to resolve edit/edit\n> > >> conflicts. Most cases none were downloaded at all, so this series is\n> > >> working as advertised. There _was_ a case where the inexact rename\n> > >> detection requested a large list of files (~2900 in three batches) but\n> > >> _then_ said \"inexact rename detection was skipped due to too many\n> > >> files\". This is a case that would be nice to resolve in this series. I\n> > >> will try to find exactly where in the code this is being triggered and\n> > >> report back.\n> > >\n> > > This suggests perhaps that EITHER there was a real modify/delete\n> > > conflict (because you have to do full rename detection to rule out\n> > > that the modify/delete was part of some rename), OR that there was a\n> > > renamed file modified on both sides that did not keep its original\n> > > basename (because that combination is needed to bypass the various\n> > > optimizations and make it fall back to full inexact rename detection).\n> > > Further, in either case, there were enough adds/deletes that full\n> > > inexact detection is still a bit expensive. It'd be interesting to\n> > > know which case it was. What happens if you set merge.renameLimit to\n> > > something higher (the default is surprisingly small)?\n> >\n> > The behavior I'd like to see is that the partial clone logic is not\n> > run if we are going to download more than merge.renameLimit files.\n> > Whatever is getting these missing blobs is earlier than the limit\n> > check, but it should be after instead.\n> >\n> > It's particularly problematic that Git does all the work to get the\n> > blobs, but then gives up and doesn't even use them for rename\n> > detection.\n>\n> I agree with what should happen, but I'm surprised it's not already\n> happening. The give up check comes from too_many_rename_candidates(),\n> which is called before dpf_options.missing_object_cb is even set to\n> inexact_prefetch. So I'm not sure how the fetching comes first. Is\n> there a microsoft specific patch that changes the order somehow? Is\n> there something I'm mis-reading in the code?\n\nAfter thinking about it more, I wonder if the following is what is happening:\n\n* Some directory was renamed (and likely not a leaf), resulting in a\nlarge pile of renames (or some other change that gives lots of renames\nwithout changing basename)\n* basename_prefetch() kicks in to download files whose basenames have\nchanged (even for \"irrelevant\" renames)\n* Basename matching is performed (which is linear in the number of\nrenames, and not subject to the merge.renameLimit)\n* After basename matching, there are still unmatched destinations and\nrelevant sources; which would need to be handled by the quadratic\ninexact matching algorithm.\n* Since there are enough renames left to trigger the renameLimit, you\nget the \"inexact rename detection was skipped due to too many files\"\nwarning.\n\nand then you assumed the prefetching was for the quadratic inexact\nrename detection when in reality it was just for the linear basename\nmatching.\n\nIf so, there's a couple things we could do here:\n\n* The easy change: modify the warning, perhaps to something like\n\"quadratic inexact rename detection was skipped...\", to make it better\nreflect its meaning (basename matching is also an inexact match)\n* The more complicated change: be more aggressive about not detecting\nrenames via basename match for \"irrelevant\" sources...perhaps avoiding\nit when it involves prefetching, or maybe just when we can somehow\ndetermine that we'd bail on the quadratic inexact rename detection\nanyway.\n\nThe second point perhaps deserves a bit more explanation. Basename\nmatching has an advantage of removing both sources and destinations\nfrom the later quadratic (O(N*M)) inexact rename detection, so it was\ngenerally beneficial to just always do the basename matching even if\nthe path wasn't relevant for either content or location reasons. But\nthat was presuming later quadratic inexact rename detection was going\nto run and not be skipped. It was one of those tradeoffs in\noptimization. But if the file hasn't been prefetched and we're likely\nto skip the quadratic inexact rename detection, then trying to do\nbasename matching for an irrelevant rename is wasted work, as is\nprefetching the blobs in order to be able to detect that irrelevant\nrename. But how do we know if we'll skip the quadratic rename\ndetection if we don't match the basenames that we can, since every\nmatched basename removes both a source and a destination from the\nunmatched pairs?\n\nMaybe we should reorder the basename matching as a two-pass algorithm,\nwhere we first detect basename-matching renames for all relevant\nsources, and then repeat for non-relevant sources.\n\nThat would also allow us to insert a check before the second pass,\nwhere if the first pass removed all relevant sources (meaning both\nthat no relevant sources were left out of basename matching and we\nfound a match for every relevant source included in basename\nmatching), then we can exit without doing the second pass. That might\neven improve the performance in cases without prefetching. But it\nwould mean adding another prefetch step.\n\nAfter doing the above splitting, then we could add extra conditions\nbefore the second step, such as bailing on it if we think we'd bail on\nquadratic inexact rename detection (which may still be hard to guess).\nOr maybe even just bailing on the second step if prefetching would be\ninvolved, because we'd rather lump those all into the quadratic\ninexact rename detection anyway.\n\n> But I'm still curious what the particular shape is for the data in\n> question. What does the error say merge.renameLimit would be need to\n> set to? If it's set higher, do some of the files resolve nicely (i.e.\n> they really were renames modified on both sides with a different\n> basename), or are they modify/delete conflicts and we're paying the\n> cost of rename detection to verify they were deleted and we really do\n> have a conflict? I'm curious if there's more to learn and more\n> optimization potential, basically. Your repository is bigger, so\n> there may be more to learn from it than from the testcases I've tried\n> so far. :-)\n\nWe might have just identified multiple additional optimization\nopportunities above, neither of which is included in my pending\noptimization series. It would be helpful to get more details about\nhow frequently these kind of cases occur, the particular renameLimit\nin use, the number of paths involved (number of unmatched source and\ndestinations), how many of the sources are relevant (perhaps even\nbroken down into content relevant and location relevant), etc., as\nthese all may help inform the implementation and whatever tests we\nwant to add to the testsuite.\n\nHowever, some of that info is currently hard to gather. I could\nprobably start by adding some trace2 statistics to diffcore-rename to\nprint out the original number of sources and destinations, the number\nmatched via exact matching, the number matched via basename matching,\nthe number of sources removed due to being irrelevant, and anything\nelse I might be overlooking at the moment to help gather relevant\ndata.\n"}]}