{"thread":{"id":"54966","subject":"[PATCH 0/1] And so it begins...merge/rename performance work","startedAt":"2021-01-08T20:52:33Z","lastAt":"2021-01-24T19:13:02Z","messageCount":17,"participants":["Elijah Newren","Taylor Blau","Junio C Hamano","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"413889","messageId":"20210108205111.2197944-1-newren@gmail.com","threadId":"54966","inReplyTo":null,"subject":"[PATCH 0/1] And so it begins...merge/rename performance work","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-08T20:51:10Z","receivedAt":"2021-01-08T20:52:33Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This depends on a merge of en/ort-conflict-handling, en/diffcore-rename,\nand en/ort-directory-rename.\n\nThis series begins the performance work for merge-ort and\ndiffcore-rename. This series only has one patch and all it does is add\ntrace2_region enter/leave pairs -- but it comes with a lengthy commit\nmessage detailing my driving testcases, the current status, and my\nplans. Part of the point of the lengthy testcase description is it will\nallow me to repeatedly refer to it in subsequent series' commit messages\nwith a paragraph of the form:\n\n For the testcases mentioned in commit 9542932eee (\"merge-ort: begin\n performance work; instrument with trace2_region_* calls\", 2020-10-28),\n this change improves the performance as follows:\n \n Before After\n no-renames: 12.975 s ± 0.037 s 12.904 s ± 0.069 s\n mega-renames: 5154.338 s ± 19.139 s 1670.582 s ± 0.904 s\n just-one-mega: 146.703 s ± 0.852 s 48.149 s ± 0.306 s\n\n\nElijah Newren (1):\n merge-ort: begin performance work; instrument with trace2_region_*\n calls\n\n diffcore-rename.c | 8 +++++++\n merge-ort.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 65 insertions(+)\n\n-- \n2.29.1.107.g69489f3566\n\n"},{"id":"413890","messageId":"20210108205111.2197944-2-newren@gmail.com","threadId":"54966","inReplyTo":"20210108205111.2197944-1-newren@gmail.com","subject":"[PATCH 1/1] merge-ort: begin performance work; instrument with trace2_region_* calls","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-08T20:51:11Z","receivedAt":"2021-01-08T20:52:34Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Add some timing instrumentation for both merge-ort and diffcore-rename;\nI used these to measure and optimize performance in both, and several\nfuture patch series will build on these to reduce the timings of some\nselect testcases.\n\n=== Setup ===\n\nThe primary testcase I used involved rebasing a random topic in the\nlinux kernel (consisting of 35 patches) against an older version. I\nadded two variants, one where I rename a toplevel directory, and another\nwhere I only rebase one patch instead of the whole topic. The setup is\nas follows:\n\n $ git clone git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git\n $ git branch hwmon-updates fd8bdb23b91876ac1e624337bb88dc1dcc21d67e\n $ git branch hwmon-just-one fd8bdb23b91876ac1e624337bb88dc1dcc21d67e~34\n $ git branch base 4703d9119972bf586d2cca76ec6438f819ffa30e\n $ git switch -c 5.4-renames v5.4\n $ git mv drivers pilots # Introduce over 26,000 renames\n $ git commit -m \"Rename drivers/ to pilots/\"\n\n=== Testcases ===\n\nNow with REBASE standing for either \"git rebase [--merge]\" (using\nmerge-recursive) or \"test-tool fast-rebase\" (using merge-ort), the\ntestcases are:\n\nTestcase #1: no-renames\n\n $ git checkout v5.4^0\n $ REBASE --onto HEAD base hwmon-updates\n\n Note: technically the name is misleading; there are some renames, but\n very few. Rename detection only takes about half the overall time.\n\nTestcase #2: mega-renames\n\n $ git checkout 5.4-renames^0\n $ REBASE --onto HEAD base hwmon-updates\n\nTestcase #3: just-one-mega\n\n $ git checkout 5.4-renames^0\n $ REBASE --onto HEAD base hwmon-just-one\n\n=== Timing results ===\n\nOverall timings, using hyperfine (1 warmup run, 3 runs for mega-renames,\n10 runs for the other two cases):\n\n merge-recursive merge-ort\n no-renames: 18.912 s ± 0.174 s 12.975 s ± 0.037 s\n mega-renames: 5964.031 s ± 10.459 s 5154.338 s ± 19.139 s\n just-one-mega: 149.583 s ± 0.751 s 146.703 s ± 0.852 s\n\nA single re-run of each with some breakdowns:\n\n --- no-renames ---\n merge-recursive merge-ort\n overall runtime: 19.302 s 13.017 s\n inexact rename detection: 7.603 s 7.695 s\n everything else: 11.699 s 5.322 s\n\n --- mega-renames ---\n merge-recursive merge-ort\n overall runtime: 5950.195 s 5132.851 s\n inexact rename detection: 5746.309 s 5119.215 s\n everything else: 203.886 s 13.636 s\n\n --- just-one-mega ---\n merge-recursive merge-ort\n overall runtime: 151.001 s 146.478 s\n inexact rename detection: 143.448 s 145.901 s\n everything else: 7.553 s 0.577 s\n\n=== Timing observations ===\n\n1) no-renames\n\n1a) merge-ort is faster than merge-recursive, which is nice. However,\nthis still should not be considered good enough. Although the \"merge\"\nbackend to rebase (merge-recursive) is sometimes faster than the \"apply\"\nbackend, this is one of those cases where it is not. In fact, even\nmerge-ort is slower. The \"apply\" backend can complete this testcase in\n 6.940 s ± 0.485 s\nwhich is about 2x faster than merge-ort and 3x faster than\nmerge-recursive. One goal of the merge-ort performance work will be to\nmake it faster than git-am on this (and similar) testcases.\n\n2) mega-renames\n\n2a) Obviously rename detection is a huge cost; it's where most the time\nis spent. We need to cut that down. If we could somehow infinitely\nparallelize it and drive its time to 0, the merge-recursive time would\ndrop to about 204s, and the merge-ort time would drop to about 14s. I\nthink this particular stat shows I've subtly baked a couple performance\nimprovements into merge-ort[A] (one of them large) and into\nfast-rebase[B] already.\n\n [A] Avoid quadratic behavior with O(N) insertions or removals\n\tof entries in the index & avoid unconditional dropping and\n re-reading of the index\n [B] Avoid updating the on-disk index or the working directory\n for intermediate patches -- only update at the end\n\n2b) rename-detection is somehow ~10% cheaper for merge-ort than\nmerge-recursive. This was and is a big surprise to me. Both of them\ncall diff_tree_oid() and diffcore_std() with the EXACT same inputs. I\ndon't have an explanation, but it is very consistent even after\nre-running many times. Interestingly, the rename detection for the\nfirst patch is more expensive (just barely) for merge-ort than\nmerge-recursive, and that is also consistent. I won't investigate this\nfurther, as I'm just going to focus on 1a & 2a.\n\n3) just-one-mega\n\n3a) not much to say here, it just gives some flavor for how rebasing\nonly one patch compares to rebasing 35.\n\n=== Goals ===\n\nThis patch is obviously just the beginning. Here are some of my goals\nthat this measurement will help us achieve:\n\n* Drive the cost of rename detection down considerably for merges\n* After the above has been achieved, see if there are other slowness\n factors (which would have previously been overshadowed by rename\n detection costs) which we can then focus on and also optimize.\n* Ensure our rebase testcase that requires little rename detection\n is noticeably faster with merge-ort than with apply-based rebase.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 8 +++++++\n merge-ort.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 65 insertions(+)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 90db9ebd6d..8fe6c9384b 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -465,6 +465,7 @@ void diffcore_rename(struct diff_options *options)\n \tint num_destinations, dst_cnt;\n \tstruct progress *progress = NULL;\n \n+\ttrace2_region_enter(\"diff\", \"setup\", options->repo);\n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n \n@@ -510,14 +511,17 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tregister_rename_src(p);\n \t\t}\n \t}\n+\ttrace2_region_leave(\"diff\", \"setup\", options->repo);\n \tif (rename_dst_nr == 0 || rename_src_nr == 0)\n \t\tgoto cleanup; /* nothing to do */\n \n+\ttrace2_region_enter(\"diff\", \"exact renames\", options->repo);\n \t/*\n \t * We really want to cull the candidates list early\n \t * with cheap tests in order to avoid doing deltas.\n \t */\n \trename_count = find_exact_renames(options);\n+\ttrace2_region_leave(\"diff\", \"exact renames\", options->repo);\n \n \t/* Did we only want exact renames? */\n \tif (minimum_score == MAX_SCORE)\n@@ -545,6 +549,7 @@ void diffcore_rename(struct diff_options *options)\n \t\tbreak;\n \t}\n \n+\ttrace2_region_enter(\"diff\", \"inexact renames\", options->repo);\n \tif (options->show_rename_progress) {\n \t\tprogress = start_delayed_progress(\n \t\t\t\t_(\"Performing inexact rename detection\"),\n@@ -600,11 +605,13 @@ void diffcore_rename(struct diff_options *options)\n \tif (detect_rename == DIFF_DETECT_COPY)\n \t\trename_count += find_renames(mx, dst_cnt, minimum_score, 1);\n \tfree(mx);\n+\ttrace2_region_leave(\"diff\", \"inexact renames\", options->repo);\n \n cleanup:\n \t/* At this point, we have found some renames and copies and they\n \t * are recorded in rename_dst. The original list is still in *q.\n \t */\n+\ttrace2_region_enter(\"diff\", \"write back to queue\", options->repo);\n \tDIFF_QUEUE_CLEAR(&outq);\n \tfor (i = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n@@ -680,5 +687,6 @@ void diffcore_rename(struct diff_options *options)\n \t\tstrintmap_clear(break_idx);\n \t\tFREE_AND_NULL(break_idx);\n \t}\n+\ttrace2_region_leave(\"diff\", \"write back to queue\", options->repo);\n \treturn;\n }\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 8f4ca4fe83..0f3ad78f3c 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -752,7 +752,9 @@ static int collect_merge_info(struct merge_options *opt,\n \tinit_tree_desc(t + 1, side1->buffer, side1->size);\n \tinit_tree_desc(t + 2, side2->buffer, side2->size);\n \n+\ttrace2_region_enter(\"merge\", \"traverse_trees\", opt->repo);\n \tret = traverse_trees(NULL, 3, t, &info);\n+\ttrace2_region_leave(\"merge\", \"traverse_trees\", opt->repo);\n \n \treturn ret;\n }\n@@ -2095,9 +2097,12 @@ static void detect_regular_renames(struct merge_options *opt,\n \tdiff_opts.show_rename_progress = opt->show_rename_progress;\n \tdiff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;\n \tdiff_setup_done(&diff_opts);\n+\n+\ttrace2_region_enter(\"diff\", \"diffcore_rename\", opt->repo);\n \tdiff_tree_oid(&merge_base->object.oid, &side->object.oid, \"\",\n \t\t &diff_opts);\n \tdiffcore_std(&diff_opts);\n+\ttrace2_region_leave(\"diff\", \"diffcore_rename\", opt->repo);\n \n \tif (diff_opts.needed_rename_limit > renames->needed_limit)\n \t\trenames->needed_limit = diff_opts.needed_rename_limit;\n@@ -2196,9 +2201,12 @@ static int detect_and_process_renames(struct merge_options *opt,\n \n \tmemset(&combined, 0, sizeof(combined));\n \n+\ttrace2_region_enter(\"merge\", \"regular renames\", opt->repo);\n \tdetect_regular_renames(opt, merge_base, side1, MERGE_SIDE1);\n \tdetect_regular_renames(opt, merge_base, side2, MERGE_SIDE2);\n+\ttrace2_region_leave(\"merge\", \"regular renames\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"directory renames\", opt->repo);\n \tneed_dir_renames =\n \t !opt->priv->call_depth &&\n \t (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE ||\n@@ -2220,8 +2228,11 @@ static int detect_and_process_renames(struct merge_options *opt,\n \t\t\t\t &renames->dir_renames[1],\n \t\t\t\t &renames->dir_renames[2]);\n \tQSORT(combined.queue, combined.nr, compare_pairs);\n+\ttrace2_region_leave(\"merge\", \"directory renames\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"process renames\", opt->repo);\n \tclean &= process_renames(opt, &combined);\n+\ttrace2_region_leave(\"merge\", \"process renames\", opt->repo);\n \n \t/* Free memory for renames->pairs[] and combined */\n \tfor (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {\n@@ -2903,20 +2914,30 @@ static void process_entries(struct merge_options *opt,\n \t\t\t\t\t\t STRING_LIST_INIT_NODUP,\n \t\t\t\t\t\t NULL, 0 };\n \n+\ttrace2_region_enter(\"merge\", \"process_entries setup\", opt->repo);\n \tif (strmap_empty(&opt->priv->paths)) {\n \t\toidcpy(result_oid, opt->repo->hash_algo->empty_tree);\n \t\treturn;\n \t}\n \n \t/* Hack to pre-allocate plist to the desired size */\n+\ttrace2_region_enter(\"merge\", \"plist grow\", opt->repo);\n \tALLOC_GROW(plist.items, strmap_get_size(&opt->priv->paths), plist.alloc);\n+\ttrace2_region_leave(\"merge\", \"plist grow\", opt->repo);\n \n \t/* Put every entry from paths into plist, then sort */\n+\ttrace2_region_enter(\"merge\", \"plist copy\", opt->repo);\n \tstrmap_for_each_entry(&opt->priv->paths, &iter, e) {\n \t\tstring_list_append(&plist, e->key)->util = e->value;\n \t}\n+\ttrace2_region_leave(\"merge\", \"plist copy\", opt->repo);\n+\n+\ttrace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n \tplist.cmp = string_list_df_name_compare;\n \tstring_list_sort(&plist);\n+\ttrace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n+\n+\ttrace2_region_leave(\"merge\", \"process_entries setup\", opt->repo);\n \n \t/*\n \t * Iterate over the items in reverse order, so we can handle paths\n@@ -2927,6 +2948,7 @@ static void process_entries(struct merge_options *opt,\n \t * (because it allows us to know whether the directory is still in\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 \tfor (entry = &plist.items[plist.nr-1]; entry >= plist.items; --entry) {\n \t\tchar *path = entry->string;\n \t\t/*\n@@ -2945,7 +2967,9 @@ static void process_entries(struct merge_options *opt,\n \t\t\tprocess_entry(opt, path, ci, &dir_metadata);\n \t\t}\n \t}\n+\ttrace2_region_leave(\"merge\", \"processing\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"process_entries cleanup\", opt->repo);\n \tif (dir_metadata.offsets.nr != 1 ||\n \t (uintptr_t)dir_metadata.offsets.items[0].util != 0) {\n \t\tprintf(\"dir_metadata.offsets.nr = %d (should be 1)\\n\",\n@@ -2960,6 +2984,7 @@ static void process_entries(struct merge_options *opt,\n \tstring_list_clear(&plist, 0);\n \tstring_list_clear(&dir_metadata.versions, 0);\n \tstring_list_clear(&dir_metadata.offsets, 0);\n+\ttrace2_region_leave(\"merge\", \"process_entries cleanup\", opt->repo);\n }\n \n /*** Function Grouping: functions related to merge_switch_to_result() ***/\n@@ -3118,12 +3143,15 @@ void merge_switch_to_result(struct merge_options *opt,\n \tif (result->clean >= 0 && update_worktree_and_index) {\n \t\tstruct merge_options_internal *opti = result->priv;\n \n+\t\ttrace2_region_enter(\"merge\", \"checkout\", opt->repo);\n \t\tif (checkout(opt, head, result->tree)) {\n \t\t\t/* failure to function */\n \t\t\tresult->clean = -1;\n \t\t\treturn;\n \t\t}\n+\t\ttrace2_region_leave(\"merge\", \"checkout\", opt->repo);\n \n+\t\ttrace2_region_enter(\"merge\", \"record_conflicted\", opt->repo);\n \t\tif (record_conflicted_index_entries(opt, opt->repo->index,\n \t\t\t\t\t\t &opti->paths,\n \t\t\t\t\t\t &opti->conflicted)) {\n@@ -3131,6 +3159,7 @@ void merge_switch_to_result(struct merge_options *opt,\n \t\t\tresult->clean = -1;\n \t\t\treturn;\n \t\t}\n+\t\ttrace2_region_leave(\"merge\", \"record_conflicted\", opt->repo);\n \t}\n \n \tif (display_update_msgs) {\n@@ -3140,6 +3169,8 @@ void merge_switch_to_result(struct merge_options *opt,\n \t\tstruct string_list olist = STRING_LIST_INIT_NODUP;\n \t\tint i;\n \n+\t\ttrace2_region_enter(\"merge\", \"display messages\", opt->repo);\n+\n \t\t/* Hack to pre-allocate olist to the desired size */\n \t\tALLOC_GROW(olist.items, strmap_get_size(&opti->output),\n \t\t\t olist.alloc);\n@@ -3161,6 +3192,8 @@ void merge_switch_to_result(struct merge_options *opt,\n \t\t/* Also include needed rename limit adjustment now */\n \t\tdiff_warn_rename_limit(\"merge.renamelimit\",\n \t\t\t\t opti->renames.needed_limit, 0);\n+\n+\t\ttrace2_region_leave(\"merge\", \"display messages\", opt->repo);\n \t}\n \n \tmerge_finalize(opt, result);\n@@ -3202,6 +3235,7 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \tint i;\n \n \t/* Sanity checks on opt */\n+\ttrace2_region_enter(\"merge\", \"sanity checks\", opt->repo);\n \tassert(opt->repo);\n \n \tassert(opt->branch1 && opt->branch2);\n@@ -3228,11 +3262,13 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \tassert(opt->obuf.len == 0);\n \n \tassert(opt->priv == NULL);\n+\ttrace2_region_leave(\"merge\", \"sanity checks\", opt->repo);\n \n \t/* Default to histogram diff. Actually, just hardcode it...for now. */\n \topt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);\n \n \t/* Initialization of opt->priv, our internal merge data */\n+\ttrace2_region_enter(\"merge\", \"allocate/init\", opt->repo);\n \topt->priv = xcalloc(1, sizeof(*opt->priv));\n \n \t/* Initialization of various renames fields */\n@@ -3265,6 +3301,8 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \t * subset of the overall paths that have special output.\n \t */\n \tstrmap_init(&opt->priv->output);\n+\n+\ttrace2_region_leave(\"merge\", \"allocate/init\", opt->repo);\n }\n \n /*** Function Grouping: merge_incore_*() and their internal variants ***/\n@@ -3280,6 +3318,7 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n {\n \tstruct object_id working_tree_oid;\n \n+\ttrace2_region_enter(\"merge\", \"collect_merge_info\", opt->repo);\n \tif (collect_merge_info(opt, merge_base, side1, side2) != 0) {\n \t\t/*\n \t\t * TRANSLATORS: The %s arguments are: 1) tree hash of a merge\n@@ -3292,10 +3331,16 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n \t\tresult->clean = -1;\n \t\treturn;\n \t}\n+\ttrace2_region_leave(\"merge\", \"collect_merge_info\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"renames\", opt->repo);\n \tresult->clean = detect_and_process_renames(opt, merge_base,\n \t\t\t\t\t\t side1, side2);\n+\ttrace2_region_leave(\"merge\", \"renames\", opt->repo);\n+\n+\ttrace2_region_enter(\"merge\", \"process_entries\", opt->repo);\n \tprocess_entries(opt, &working_tree_oid);\n+\ttrace2_region_leave(\"merge\", \"process_entries\", opt->repo);\n \n \t/* Set return values */\n \tresult->tree = parse_tree_indirect(&working_tree_oid);\n@@ -3396,9 +3441,15 @@ void merge_incore_nonrecursive(struct merge_options *opt,\n \t\t\t struct tree *side2,\n \t\t\t struct merge_result *result)\n {\n+\ttrace2_region_enter(\"merge\", \"incore_nonrecursive\", opt->repo);\n+\n+\ttrace2_region_enter(\"merge\", \"merge_start\", opt->repo);\n \tassert(opt->ancestor != NULL);\n \tmerge_start(opt, result);\n+\ttrace2_region_leave(\"merge\", \"merge_start\", opt->repo);\n+\n \tmerge_ort_nonrecursive_internal(opt, merge_base, side1, side2, result);\n+\ttrace2_region_leave(\"merge\", \"incore_nonrecursive\", opt->repo);\n }\n \n void merge_incore_recursive(struct merge_options *opt,\n@@ -3407,9 +3458,15 @@ void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit *side2,\n \t\t\t struct merge_result *result)\n {\n+\ttrace2_region_enter(\"merge\", \"incore_recursive\", opt->repo);\n+\n \t/* We set the ancestor label based on the merge_bases */\n \tassert(opt->ancestor == NULL);\n \n+\ttrace2_region_enter(\"merge\", \"merge_start\", opt->repo);\n \tmerge_start(opt, result);\n+\ttrace2_region_leave(\"merge\", \"merge_start\", opt->repo);\n+\n \tmerge_ort_internal(opt, merge_bases, side1, side2, result);\n+\ttrace2_region_leave(\"merge\", \"incore_recursive\", opt->repo);\n }\n-- \n2.29.1.107.g69489f3566\n\n"},{"id":"413891","messageId":"X/jHpZlSxwAxoUyq@nand.local","threadId":"54966","inReplyTo":"20210108205111.2197944-2-newren@gmail.com","subject":"Re: [PATCH 1/1] merge-ort: begin performance work; instrument with trace2_region_* calls","fromName":"Taylor Blau","fromEmail":"ttaylorr@github.com","sentAt":"2021-01-08T20:59:36Z","receivedAt":"2021-01-08T21:00:44Z","isPatch":true,"sender":{"key":"ttaylorr@github.com","avatar":"https://gravatar.com/avatar/d5f3476f26b6f99cbb6b467e7ed7482f5762c8157bc73f569196e428bdcbea25?d=mp&s=160"},"body":"On Fri, Jan 08, 2021 at 12:51:11PM -0800, Elijah Newren wrote:\n> Overall timings, using hyperfine (1 warmup run, 3 runs for mega-renames,\n> 10 runs for the other two cases):\n\nAh, I love hyperfine. In case you don't already have this in your\narsenal, the following `--prepare` step is useful for measuring\ncold-cache performance:\n\n --prepare='sync; echo 3 | sudo tee /proc/sys/vm/drop_caches'\n\n> === Goals ===\n>\n> This patch is obviously just the beginning. Here are some of my goals\n> that this measurement will help us achieve:\n>\n> * Drive the cost of rename detection down considerably for merges\n> * After the above has been achieved, see if there are other slowness\n> factors (which would have previously been overshadowed by rename\n> detection costs) which we can then focus on and also optimize.\n> * Ensure our rebase testcase that requires little rename detection\n> is noticeably faster with merge-ort than with apply-based rebase.\n\nThese are great, and I am looking forward to your work.\n\n> Signed-off-by: Elijah Newren \n\nThanks, this patch looks good to me.\n\nThanks,\nTaylor\n"},{"id":"413893","messageId":"CABPp-BE4zyGa7=dOKifWhv-46__0YtfRZ39Q1JYT0JZ2HT0itA@mail.gmail.com","threadId":"54966","inReplyTo":"X/jHpZlSxwAxoUyq@nand.local","subject":"Re: [PATCH 1/1] merge-ort: begin performance work; instrument with trace2_region_* calls","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-08T21:50:34Z","receivedAt":"2021-01-08T21:51:45Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Jan 8, 2021 at 12:59 PM Taylor Blau wrote:\n>\n> On Fri, Jan 08, 2021 at 12:51:11PM -0800, Elijah Newren wrote:\n> > Overall timings, using hyperfine (1 warmup run, 3 runs for mega-renames,\n> > 10 runs for the other two cases):\n>\n> Ah, I love hyperfine. In case you don't already have this in your\n> arsenal, the following `--prepare` step is useful for measuring\n> cold-cache performance:\n>\n> --prepare='sync; echo 3 | sudo tee /proc/sys/vm/drop_caches'\n\n/proc/sys/vm/drop_caches is definitely useful for cold-cache\nmeasurements and I've used it in other projects for that purpose. I\nthink cold-cache testing makes sense for various I/O intensive areas\nsuch as object lookup, but I ignored it here as I felt the merge code\nis really about algorithmic performance. So, I instead went the other\ndirection and ensured warm-cache testing by using a warmup run, in\norder to ensure that I wasn't putting one of the tests at an unfair\ndisadvantage. (Side note: My script that runs the tests actually does\nmore than the warmup run to ensure a fair playing field. For example,\nthe script expires reflogs and runs a git prune before each hyperfine\ninvocation, to make sure that each hyperfine run starts with a fully\nrepacked repository with no loose objects. Without the expire &\nprune, enough perf testing of rebases in a short time period will\nresult in a mysterious and gradual slowdown of all the test runs even\nwithout code changes...).\n\n> > === Goals ===\n> >\n> > This patch is obviously just the beginning. Here are some of my goals\n> > that this measurement will help us achieve:\n> >\n> > * Drive the cost of rename detection down considerably for merges\n> > * After the above has been achieved, see if there are other slowness\n> > factors (which would have previously been overshadowed by rename\n> > detection costs) which we can then focus on and also optimize.\n> > * Ensure our rebase testcase that requires little rename detection\n> > is noticeably faster with merge-ort than with apply-based rebase.\n>\n> These are great, and I am looking forward to your work.\n>\n> > Signed-off-by: Elijah Newren \n>\n> Thanks, this patch looks good to me.\n\nAs always, thanks for taking a look.\n"},{"id":"413894","messageId":"X/jUykDe8hfPDqv4@nand.local","threadId":"54966","inReplyTo":"CABPp-BE4zyGa7=dOKifWhv-46__0YtfRZ39Q1JYT0JZ2HT0itA@mail.gmail.com","subject":"Re: [PATCH 1/1] merge-ort: begin performance work; instrument with trace2_region_* calls","fromName":"Taylor Blau","fromEmail":"ttaylorr@github.com","sentAt":"2021-01-08T21:55:49Z","receivedAt":"2021-01-08T21:56:51Z","isPatch":true,"sender":{"key":"ttaylorr@github.com","avatar":"https://gravatar.com/avatar/d5f3476f26b6f99cbb6b467e7ed7482f5762c8157bc73f569196e428bdcbea25?d=mp&s=160"},"body":"On Fri, Jan 08, 2021 at 01:50:34PM -0800, Elijah Newren wrote:\n> On Fri, Jan 8, 2021 at 12:59 PM Taylor Blau wrote:\n> >\n> > On Fri, Jan 08, 2021 at 12:51:11PM -0800, Elijah Newren wrote:\n> > > Overall timings, using hyperfine (1 warmup run, 3 runs for mega-renames,\n> > > 10 runs for the other two cases):\n> >\n> > Ah, I love hyperfine. In case you don't already have this in your\n> > arsenal, the following `--prepare` step is useful for measuring\n> > cold-cache performance:\n> >\n> > --prepare='sync; echo 3 | sudo tee /proc/sys/vm/drop_caches'\n>\n> /proc/sys/vm/drop_caches is definitely useful for cold-cache\n> measurements and I've used it in other projects for that purpose. I\n> think cold-cache testing makes sense for various I/O intensive areas\n> such as object lookup, but I ignored it here as I felt the merge code\n> is really about algorithmic performance.\n\nYes, I agree that the interesting thing here is algorithmic performance\nmoreso than I/O.\n\n> So, I instead went the other direction and ensured warm-cache testing\n> by using a warmup run, in order to ensure that I wasn't putting one of\n> the tests at an unfair disadvantage.\n\nI often use it for both. Combining that `--prepare` step with at least\none `--warmup` invocation is useful to make sure that your I/O cache is\nwarmed only with the things it might want to read during your timing\ntests. (Probably one `--warmup` without dumping the cache is fine, since\nyou will likely end up evicting things out of your cache that you don't\ncare about, but I digress..)\n\nThanks,\nTaylor\n"},{"id":"413901","messageId":"CABPp-BG0QTdbdnNp-4XDfVCS+59t8p6L7oszN1TUJ_L6LM3tpA@mail.gmail.com","threadId":"54966","inReplyTo":"X/jUykDe8hfPDqv4@nand.local","subject":"Re: [PATCH 1/1] merge-ort: begin performance work; instrument with trace2_region_* calls","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-09T00:52:37Z","receivedAt":"2021-01-09T00:53:31Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Jan 8, 2021 at 1:55 PM Taylor Blau wrote:\n>\n> On Fri, Jan 08, 2021 at 01:50:34PM -0800, Elijah Newren wrote:\n> > On Fri, Jan 8, 2021 at 12:59 PM Taylor Blau wrote:\n> > >\n> > > On Fri, Jan 08, 2021 at 12:51:11PM -0800, Elijah Newren wrote:\n> > > > Overall timings, using hyperfine (1 warmup run, 3 runs for mega-renames,\n> > > > 10 runs for the other two cases):\n> > >\n> > > Ah, I love hyperfine. In case you don't already have this in your\n> > > arsenal, the following `--prepare` step is useful for measuring\n> > > cold-cache performance:\n> > >\n> > > --prepare='sync; echo 3 | sudo tee /proc/sys/vm/drop_caches'\n> >\n> > /proc/sys/vm/drop_caches is definitely useful for cold-cache\n> > measurements and I've used it in other projects for that purpose. I\n> > think cold-cache testing makes sense for various I/O intensive areas\n> > such as object lookup, but I ignored it here as I felt the merge code\n> > is really about algorithmic performance.\n>\n> Yes, I agree that the interesting thing here is algorithmic performance\n> moreso than I/O.\n>\n> > So, I instead went the other direction and ensured warm-cache testing\n> > by using a warmup run, in order to ensure that I wasn't putting one of\n> > the tests at an unfair disadvantage.\n>\n> I often use it for both. Combining that `--prepare` step with at least\n> one `--warmup` invocation is useful to make sure that your I/O cache is\n> warmed only with the things it might want to read during your timing\n> tests. (Probably one `--warmup` without dumping the cache is fine, since\n> you will likely end up evicting things out of your cache that you don't\n> care about, but I digress..)\n\nAh, that hadn't occurred to me, but it makes sense. Thanks for the\ntip; I may give it a try at some point. I worry slightly that it\nmight increase the run-to-run noise instead of decreasing it since I'm\ncommitting sins by not running the performance tests on a quiet server\nbut on my laptop with a full GUI running -- a few year old,\nnearly-bottom-of-the-line Dell refurbished grade B laptop with spinny\ndisks. Dropping disk caches would lower the risk of needing to spend\ntime evicting other things from the warm cache, but would increase the\nrisk that some background GUI thing or system daemon needs to read\nfrom the hard disk when it wouldn't have needed to otherwise, and if\nthe timing of that disk read is unfortunately placed, then it could\nslow down I/O I care about. I guess there's only one way to find out\nif it'd help or hurt though...\n"},{"id":"414322","messageId":"20210113221158.2869128-1-newren@gmail.com","threadId":"54966","inReplyTo":"20210108205111.2197944-1-newren@gmail.com","subject":"[PATCH v2 0/1] And so it begins...merge/rename performance work","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-13T22:11:57Z","receivedAt":"2021-01-14T02:11:36Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This depends on a merge of en/ort-conflict-handling, en/diffcore-rename,\nand en/ort-directory-rename.\n\nChanges since v1:\n * Add a step I forgot in my testcase setup -- increasing\n merge.renameLimit\n * Add Acked-by from Taylor\n\nElijah Newren (1):\n merge-ort: begin performance work; instrument with trace2_region_*\n calls\n\n diffcore-rename.c | 8 +++++++\n merge-ort.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 65 insertions(+)\n\nRange-diff:\n1: 9542932eee ! 1: 8783f209ef merge-ort: begin performance work; instrument with trace2_region_* calls\n @@ Commit message\n $ git switch -c 5.4-renames v5.4\n $ git mv drivers pilots # Introduce over 26,000 renames\n $ git commit -m \"Rename drivers/ to pilots/\"\n + $ git config merge.renameLimit 30000\n \n === Testcases ===\n \n @@ Commit message\n is noticeably faster with merge-ort than with apply-based rebase.\n \n Signed-off-by: Elijah Newren \n + Acked-by: Taylor Blau \n \n ## diffcore-rename.c ##\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n-- \n2.29.2.544.gecb49aa127.dirty\n\n"},{"id":"414323","messageId":"20210113221158.2869128-2-newren@gmail.com","threadId":"54966","inReplyTo":"20210113221158.2869128-1-newren@gmail.com","subject":"[PATCH v2 1/1] merge-ort: begin performance work; instrument with trace2_region_* calls","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-13T22:11:58Z","receivedAt":"2021-01-14T02:12:17Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Add some timing instrumentation for both merge-ort and diffcore-rename;\nI used these to measure and optimize performance in both, and several\nfuture patch series will build on these to reduce the timings of some\nselect testcases.\n\n=== Setup ===\n\nThe primary testcase I used involved rebasing a random topic in the\nlinux kernel (consisting of 35 patches) against an older version. I\nadded two variants, one where I rename a toplevel directory, and another\nwhere I only rebase one patch instead of the whole topic. The setup is\nas follows:\n\n $ git clone git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git\n $ git branch hwmon-updates fd8bdb23b91876ac1e624337bb88dc1dcc21d67e\n $ git branch hwmon-just-one fd8bdb23b91876ac1e624337bb88dc1dcc21d67e~34\n $ git branch base 4703d9119972bf586d2cca76ec6438f819ffa30e\n $ git switch -c 5.4-renames v5.4\n $ git mv drivers pilots # Introduce over 26,000 renames\n $ git commit -m \"Rename drivers/ to pilots/\"\n $ git config merge.renameLimit 30000\n\n=== Testcases ===\n\nNow with REBASE standing for either \"git rebase [--merge]\" (using\nmerge-recursive) or \"test-tool fast-rebase\" (using merge-ort), the\ntestcases are:\n\nTestcase #1: no-renames\n\n $ git checkout v5.4^0\n $ REBASE --onto HEAD base hwmon-updates\n\n Note: technically the name is misleading; there are some renames, but\n very few. Rename detection only takes about half the overall time.\n\nTestcase #2: mega-renames\n\n $ git checkout 5.4-renames^0\n $ REBASE --onto HEAD base hwmon-updates\n\nTestcase #3: just-one-mega\n\n $ git checkout 5.4-renames^0\n $ REBASE --onto HEAD base hwmon-just-one\n\n=== Timing results ===\n\nOverall timings, using hyperfine (1 warmup run, 3 runs for mega-renames,\n10 runs for the other two cases):\n\n merge-recursive merge-ort\n no-renames: 18.912 s ± 0.174 s 12.975 s ± 0.037 s\n mega-renames: 5964.031 s ± 10.459 s 5154.338 s ± 19.139 s\n just-one-mega: 149.583 s ± 0.751 s 146.703 s ± 0.852 s\n\nA single re-run of each with some breakdowns:\n\n --- no-renames ---\n merge-recursive merge-ort\n overall runtime: 19.302 s 13.017 s\n inexact rename detection: 7.603 s 7.695 s\n everything else: 11.699 s 5.322 s\n\n --- mega-renames ---\n merge-recursive merge-ort\n overall runtime: 5950.195 s 5132.851 s\n inexact rename detection: 5746.309 s 5119.215 s\n everything else: 203.886 s 13.636 s\n\n --- just-one-mega ---\n merge-recursive merge-ort\n overall runtime: 151.001 s 146.478 s\n inexact rename detection: 143.448 s 145.901 s\n everything else: 7.553 s 0.577 s\n\n=== Timing observations ===\n\n1) no-renames\n\n1a) merge-ort is faster than merge-recursive, which is nice. However,\nthis still should not be considered good enough. Although the \"merge\"\nbackend to rebase (merge-recursive) is sometimes faster than the \"apply\"\nbackend, this is one of those cases where it is not. In fact, even\nmerge-ort is slower. The \"apply\" backend can complete this testcase in\n 6.940 s ± 0.485 s\nwhich is about 2x faster than merge-ort and 3x faster than\nmerge-recursive. One goal of the merge-ort performance work will be to\nmake it faster than git-am on this (and similar) testcases.\n\n2) mega-renames\n\n2a) Obviously rename detection is a huge cost; it's where most the time\nis spent. We need to cut that down. If we could somehow infinitely\nparallelize it and drive its time to 0, the merge-recursive time would\ndrop to about 204s, and the merge-ort time would drop to about 14s. I\nthink this particular stat shows I've subtly baked a couple performance\nimprovements into merge-ort[A] (one of them large) and into\nfast-rebase[B] already.\n\n [A] Avoid quadratic behavior with O(N) insertions or removals\n\tof entries in the index & avoid unconditional dropping and\n re-reading of the index\n [B] Avoid updating the on-disk index or the working directory\n for intermediate patches -- only update at the end\n\n2b) rename-detection is somehow ~10% cheaper for merge-ort than\nmerge-recursive. This was and is a big surprise to me. Both of them\ncall diff_tree_oid() and diffcore_std() with the EXACT same inputs. I\ndon't have an explanation, but it is very consistent even after\nre-running many times. Interestingly, the rename detection for the\nfirst patch is more expensive (just barely) for merge-ort than\nmerge-recursive, and that is also consistent. I won't investigate this\nfurther, as I'm just going to focus on 1a & 2a.\n\n3) just-one-mega\n\n3a) not much to say here, it just gives some flavor for how rebasing\nonly one patch compares to rebasing 35.\n\n=== Goals ===\n\nThis patch is obviously just the beginning. Here are some of my goals\nthat this measurement will help us achieve:\n\n* Drive the cost of rename detection down considerably for merges\n* After the above has been achieved, see if there are other slowness\n factors (which would have previously been overshadowed by rename\n detection costs) which we can then focus on and also optimize.\n* Ensure our rebase testcase that requires little rename detection\n is noticeably faster with merge-ort than with apply-based rebase.\n\nSigned-off-by: Elijah Newren \nAcked-by: Taylor Blau \n---\n diffcore-rename.c | 8 +++++++\n merge-ort.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 65 insertions(+)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 90db9ebd6d..8fe6c9384b 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -465,6 +465,7 @@ void diffcore_rename(struct diff_options *options)\n \tint num_destinations, dst_cnt;\n \tstruct progress *progress = NULL;\n \n+\ttrace2_region_enter(\"diff\", \"setup\", options->repo);\n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n \n@@ -510,14 +511,17 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tregister_rename_src(p);\n \t\t}\n \t}\n+\ttrace2_region_leave(\"diff\", \"setup\", options->repo);\n \tif (rename_dst_nr == 0 || rename_src_nr == 0)\n \t\tgoto cleanup; /* nothing to do */\n \n+\ttrace2_region_enter(\"diff\", \"exact renames\", options->repo);\n \t/*\n \t * We really want to cull the candidates list early\n \t * with cheap tests in order to avoid doing deltas.\n \t */\n \trename_count = find_exact_renames(options);\n+\ttrace2_region_leave(\"diff\", \"exact renames\", options->repo);\n \n \t/* Did we only want exact renames? */\n \tif (minimum_score == MAX_SCORE)\n@@ -545,6 +549,7 @@ void diffcore_rename(struct diff_options *options)\n \t\tbreak;\n \t}\n \n+\ttrace2_region_enter(\"diff\", \"inexact renames\", options->repo);\n \tif (options->show_rename_progress) {\n \t\tprogress = start_delayed_progress(\n \t\t\t\t_(\"Performing inexact rename detection\"),\n@@ -600,11 +605,13 @@ void diffcore_rename(struct diff_options *options)\n \tif (detect_rename == DIFF_DETECT_COPY)\n \t\trename_count += find_renames(mx, dst_cnt, minimum_score, 1);\n \tfree(mx);\n+\ttrace2_region_leave(\"diff\", \"inexact renames\", options->repo);\n \n cleanup:\n \t/* At this point, we have found some renames and copies and they\n \t * are recorded in rename_dst. The original list is still in *q.\n \t */\n+\ttrace2_region_enter(\"diff\", \"write back to queue\", options->repo);\n \tDIFF_QUEUE_CLEAR(&outq);\n \tfor (i = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n@@ -680,5 +687,6 @@ void diffcore_rename(struct diff_options *options)\n \t\tstrintmap_clear(break_idx);\n \t\tFREE_AND_NULL(break_idx);\n \t}\n+\ttrace2_region_leave(\"diff\", \"write back to queue\", options->repo);\n \treturn;\n }\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 8f4ca4fe83..0f3ad78f3c 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -752,7 +752,9 @@ static int collect_merge_info(struct merge_options *opt,\n \tinit_tree_desc(t + 1, side1->buffer, side1->size);\n \tinit_tree_desc(t + 2, side2->buffer, side2->size);\n \n+\ttrace2_region_enter(\"merge\", \"traverse_trees\", opt->repo);\n \tret = traverse_trees(NULL, 3, t, &info);\n+\ttrace2_region_leave(\"merge\", \"traverse_trees\", opt->repo);\n \n \treturn ret;\n }\n@@ -2095,9 +2097,12 @@ static void detect_regular_renames(struct merge_options *opt,\n \tdiff_opts.show_rename_progress = opt->show_rename_progress;\n \tdiff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;\n \tdiff_setup_done(&diff_opts);\n+\n+\ttrace2_region_enter(\"diff\", \"diffcore_rename\", opt->repo);\n \tdiff_tree_oid(&merge_base->object.oid, &side->object.oid, \"\",\n \t\t &diff_opts);\n \tdiffcore_std(&diff_opts);\n+\ttrace2_region_leave(\"diff\", \"diffcore_rename\", opt->repo);\n \n \tif (diff_opts.needed_rename_limit > renames->needed_limit)\n \t\trenames->needed_limit = diff_opts.needed_rename_limit;\n@@ -2196,9 +2201,12 @@ static int detect_and_process_renames(struct merge_options *opt,\n \n \tmemset(&combined, 0, sizeof(combined));\n \n+\ttrace2_region_enter(\"merge\", \"regular renames\", opt->repo);\n \tdetect_regular_renames(opt, merge_base, side1, MERGE_SIDE1);\n \tdetect_regular_renames(opt, merge_base, side2, MERGE_SIDE2);\n+\ttrace2_region_leave(\"merge\", \"regular renames\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"directory renames\", opt->repo);\n \tneed_dir_renames =\n \t !opt->priv->call_depth &&\n \t (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE ||\n@@ -2220,8 +2228,11 @@ static int detect_and_process_renames(struct merge_options *opt,\n \t\t\t\t &renames->dir_renames[1],\n \t\t\t\t &renames->dir_renames[2]);\n \tQSORT(combined.queue, combined.nr, compare_pairs);\n+\ttrace2_region_leave(\"merge\", \"directory renames\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"process renames\", opt->repo);\n \tclean &= process_renames(opt, &combined);\n+\ttrace2_region_leave(\"merge\", \"process renames\", opt->repo);\n \n \t/* Free memory for renames->pairs[] and combined */\n \tfor (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {\n@@ -2903,20 +2914,30 @@ static void process_entries(struct merge_options *opt,\n \t\t\t\t\t\t STRING_LIST_INIT_NODUP,\n \t\t\t\t\t\t NULL, 0 };\n \n+\ttrace2_region_enter(\"merge\", \"process_entries setup\", opt->repo);\n \tif (strmap_empty(&opt->priv->paths)) {\n \t\toidcpy(result_oid, opt->repo->hash_algo->empty_tree);\n \t\treturn;\n \t}\n \n \t/* Hack to pre-allocate plist to the desired size */\n+\ttrace2_region_enter(\"merge\", \"plist grow\", opt->repo);\n \tALLOC_GROW(plist.items, strmap_get_size(&opt->priv->paths), plist.alloc);\n+\ttrace2_region_leave(\"merge\", \"plist grow\", opt->repo);\n \n \t/* Put every entry from paths into plist, then sort */\n+\ttrace2_region_enter(\"merge\", \"plist copy\", opt->repo);\n \tstrmap_for_each_entry(&opt->priv->paths, &iter, e) {\n \t\tstring_list_append(&plist, e->key)->util = e->value;\n \t}\n+\ttrace2_region_leave(\"merge\", \"plist copy\", opt->repo);\n+\n+\ttrace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n \tplist.cmp = string_list_df_name_compare;\n \tstring_list_sort(&plist);\n+\ttrace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n+\n+\ttrace2_region_leave(\"merge\", \"process_entries setup\", opt->repo);\n \n \t/*\n \t * Iterate over the items in reverse order, so we can handle paths\n@@ -2927,6 +2948,7 @@ static void process_entries(struct merge_options *opt,\n \t * (because it allows us to know whether the directory is still in\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 \tfor (entry = &plist.items[plist.nr-1]; entry >= plist.items; --entry) {\n \t\tchar *path = entry->string;\n \t\t/*\n@@ -2945,7 +2967,9 @@ static void process_entries(struct merge_options *opt,\n \t\t\tprocess_entry(opt, path, ci, &dir_metadata);\n \t\t}\n \t}\n+\ttrace2_region_leave(\"merge\", \"processing\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"process_entries cleanup\", opt->repo);\n \tif (dir_metadata.offsets.nr != 1 ||\n \t (uintptr_t)dir_metadata.offsets.items[0].util != 0) {\n \t\tprintf(\"dir_metadata.offsets.nr = %d (should be 1)\\n\",\n@@ -2960,6 +2984,7 @@ static void process_entries(struct merge_options *opt,\n \tstring_list_clear(&plist, 0);\n \tstring_list_clear(&dir_metadata.versions, 0);\n \tstring_list_clear(&dir_metadata.offsets, 0);\n+\ttrace2_region_leave(\"merge\", \"process_entries cleanup\", opt->repo);\n }\n \n /*** Function Grouping: functions related to merge_switch_to_result() ***/\n@@ -3118,12 +3143,15 @@ void merge_switch_to_result(struct merge_options *opt,\n \tif (result->clean >= 0 && update_worktree_and_index) {\n \t\tstruct merge_options_internal *opti = result->priv;\n \n+\t\ttrace2_region_enter(\"merge\", \"checkout\", opt->repo);\n \t\tif (checkout(opt, head, result->tree)) {\n \t\t\t/* failure to function */\n \t\t\tresult->clean = -1;\n \t\t\treturn;\n \t\t}\n+\t\ttrace2_region_leave(\"merge\", \"checkout\", opt->repo);\n \n+\t\ttrace2_region_enter(\"merge\", \"record_conflicted\", opt->repo);\n \t\tif (record_conflicted_index_entries(opt, opt->repo->index,\n \t\t\t\t\t\t &opti->paths,\n \t\t\t\t\t\t &opti->conflicted)) {\n@@ -3131,6 +3159,7 @@ void merge_switch_to_result(struct merge_options *opt,\n \t\t\tresult->clean = -1;\n \t\t\treturn;\n \t\t}\n+\t\ttrace2_region_leave(\"merge\", \"record_conflicted\", opt->repo);\n \t}\n \n \tif (display_update_msgs) {\n@@ -3140,6 +3169,8 @@ void merge_switch_to_result(struct merge_options *opt,\n \t\tstruct string_list olist = STRING_LIST_INIT_NODUP;\n \t\tint i;\n \n+\t\ttrace2_region_enter(\"merge\", \"display messages\", opt->repo);\n+\n \t\t/* Hack to pre-allocate olist to the desired size */\n \t\tALLOC_GROW(olist.items, strmap_get_size(&opti->output),\n \t\t\t olist.alloc);\n@@ -3161,6 +3192,8 @@ void merge_switch_to_result(struct merge_options *opt,\n \t\t/* Also include needed rename limit adjustment now */\n \t\tdiff_warn_rename_limit(\"merge.renamelimit\",\n \t\t\t\t opti->renames.needed_limit, 0);\n+\n+\t\ttrace2_region_leave(\"merge\", \"display messages\", opt->repo);\n \t}\n \n \tmerge_finalize(opt, result);\n@@ -3202,6 +3235,7 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \tint i;\n \n \t/* Sanity checks on opt */\n+\ttrace2_region_enter(\"merge\", \"sanity checks\", opt->repo);\n \tassert(opt->repo);\n \n \tassert(opt->branch1 && opt->branch2);\n@@ -3228,11 +3262,13 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \tassert(opt->obuf.len == 0);\n \n \tassert(opt->priv == NULL);\n+\ttrace2_region_leave(\"merge\", \"sanity checks\", opt->repo);\n \n \t/* Default to histogram diff. Actually, just hardcode it...for now. */\n \topt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);\n \n \t/* Initialization of opt->priv, our internal merge data */\n+\ttrace2_region_enter(\"merge\", \"allocate/init\", opt->repo);\n \topt->priv = xcalloc(1, sizeof(*opt->priv));\n \n \t/* Initialization of various renames fields */\n@@ -3265,6 +3301,8 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \t * subset of the overall paths that have special output.\n \t */\n \tstrmap_init(&opt->priv->output);\n+\n+\ttrace2_region_leave(\"merge\", \"allocate/init\", opt->repo);\n }\n \n /*** Function Grouping: merge_incore_*() and their internal variants ***/\n@@ -3280,6 +3318,7 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n {\n \tstruct object_id working_tree_oid;\n \n+\ttrace2_region_enter(\"merge\", \"collect_merge_info\", opt->repo);\n \tif (collect_merge_info(opt, merge_base, side1, side2) != 0) {\n \t\t/*\n \t\t * TRANSLATORS: The %s arguments are: 1) tree hash of a merge\n@@ -3292,10 +3331,16 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n \t\tresult->clean = -1;\n \t\treturn;\n \t}\n+\ttrace2_region_leave(\"merge\", \"collect_merge_info\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"renames\", opt->repo);\n \tresult->clean = detect_and_process_renames(opt, merge_base,\n \t\t\t\t\t\t side1, side2);\n+\ttrace2_region_leave(\"merge\", \"renames\", opt->repo);\n+\n+\ttrace2_region_enter(\"merge\", \"process_entries\", opt->repo);\n \tprocess_entries(opt, &working_tree_oid);\n+\ttrace2_region_leave(\"merge\", \"process_entries\", opt->repo);\n \n \t/* Set return values */\n \tresult->tree = parse_tree_indirect(&working_tree_oid);\n@@ -3396,9 +3441,15 @@ void merge_incore_nonrecursive(struct merge_options *opt,\n \t\t\t struct tree *side2,\n \t\t\t struct merge_result *result)\n {\n+\ttrace2_region_enter(\"merge\", \"incore_nonrecursive\", opt->repo);\n+\n+\ttrace2_region_enter(\"merge\", \"merge_start\", opt->repo);\n \tassert(opt->ancestor != NULL);\n \tmerge_start(opt, result);\n+\ttrace2_region_leave(\"merge\", \"merge_start\", opt->repo);\n+\n \tmerge_ort_nonrecursive_internal(opt, merge_base, side1, side2, result);\n+\ttrace2_region_leave(\"merge\", \"incore_nonrecursive\", opt->repo);\n }\n \n void merge_incore_recursive(struct merge_options *opt,\n@@ -3407,9 +3458,15 @@ void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit *side2,\n \t\t\t struct merge_result *result)\n {\n+\ttrace2_region_enter(\"merge\", \"incore_recursive\", opt->repo);\n+\n \t/* We set the ancestor label based on the merge_bases */\n \tassert(opt->ancestor == NULL);\n \n+\ttrace2_region_enter(\"merge\", \"merge_start\", opt->repo);\n \tmerge_start(opt, result);\n+\ttrace2_region_leave(\"merge\", \"merge_start\", opt->repo);\n+\n \tmerge_ort_internal(opt, merge_bases, side1, side2, result);\n+\ttrace2_region_leave(\"merge\", \"incore_recursive\", opt->repo);\n }\n-- \n2.29.2.544.gecb49aa127.dirty\n\n"},{"id":"414373","messageId":"xmqqo8hrxrnh.fsf@gitster.c.googlers.com","threadId":"54966","inReplyTo":"20210113221158.2869128-1-newren@gmail.com","subject":"Re: [PATCH v2 0/1] And so it begins...merge/rename performance work","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-14T19:08:50Z","receivedAt":"2021-01-14T19:09:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n> This depends on a merge of en/ort-conflict-handling, en/diffcore-rename,\n> and en/ort-directory-rename.\n\nThanks.\n\nHow ready is the foundation to accept this change? This will depend\non all of the above three topics and I am not sure what the status\nof them is---I think that I've read through the diffcore-rename one\nand it was a pleasant read, but I do not recall the reviewer\nreactions to the other two.\n\nIt does not instill a lot of confidence in these topics that nobody\ncommented on things like [v2 17/17] of en/ort-directory-rename\n(which fixes the code introduced in [v2 06/17] instead of fixing it\nat the source before 06/17 copies it from elsewhere [*1*]). It\nlooks to me like a sign that these collection of series are moving\ntoo fast than any reviewer to catch up.\n\nThanks.\n\n\n[Footnote]\n\n*1* I do not particularly think [06/17] that copies and leaves the\n recursive backend behind is necessarily bad. What I find more\n disturbing is that nobody seems to have a chance to give any\n look to the two iterations of the series (as far as I can see,\n v2 is just in name only---it removed 18/17 in v1 that were not\n meant to be sent), and we are about to build on top of the\n foundation that nobody knows how solid it is.\n"},{"id":"414385","messageId":"CABPp-BHhXXAX7QJeD6jGckozL9DHf5UZ=UXzaogyv-F4_xdYVQ@mail.gmail.com","threadId":"54966","inReplyTo":"xmqqo8hrxrnh.fsf@gitster.c.googlers.com","subject":"Re: [PATCH v2 0/1] And so it begins...merge/rename performance work","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-14T20:18:17Z","receivedAt":"2021-01-14T20:19:11Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi Junio,\n\nOn Thu, Jan 14, 2021 at 11:08 AM Junio C Hamano wrote:\n>\n> Elijah Newren writes:\n>\n> > This depends on a merge of en/ort-conflict-handling, en/diffcore-rename,\n> > and en/ort-directory-rename.\n>\n> Thanks.\n>\n> How ready is the foundation to accept this change? This will depend\n> on all of the above three topics and I am not sure what the status\n> of them is---I think that I've read through the diffcore-rename one\n> and it was a pleasant read, but I do not recall the reviewer\n> reactions to the other two.\n\nGood questions. Let me go through the three in order:\n\nen/ort-conflict-handling: Has already been reviewed; v2 included the\nfixes to the issues Stolee noted in v1 and Stolee was happy with v2\n(https://lore.kernel.org/git/5f6d5428-36ce-3e91-4916-8968ac1b8686@gmail.com/)\nas of a week and a half ago. I am unaware of any issues; I think it's\nready as-is to merge down to next and then to master.\n\nen/diffcore-rename: Taylor and you both reviewed it; Christian skimmed\nover it and noted a typo. I fixed up the issues all three of you\nnoted by v3 at the end of December. I was assuming based on your\ncomments (at https://lore.kernel.org/git/xmqqwnwnglim.fsf@gitster.c.googlers.com/)\nthat you are happy with it now, which seems to be supported by the\nfact that you've already merged it to next. I think it's ready to\ncontinue merging on to master.\n\nen/ort-directory-rename: This one is the only question mark in my\nmind. Most of the ort patches I wanted folks to review because I'm\ndoing things significantly differently than merge-recursive.c does.\nThis series is an exception; patches 1-16 are just porting over the\nexact same algorithm from merge-recursive.c using the new data\nstructures. It's a lot of code, because directory rename detection\nhas a lot of logic to it, but there's not anything new or tricky to it\nin relation to what's in merge-recursive.c. However, even though the\nalgorithm is essentially just being copied, the differences in data\nstructures means there are lots of tiny changes all over that make a\ndirect comparison difficult (unless folks are familiar with the old\nlogic, but I think only Stefan Beller and I were). Honestly, I'm not\nso sure this series is worth reviewers' time given all those details,\nwith the exception of patch 17/17. If folks can review everything,\nthat's great, but if we have limited review resources, I'd rather\npeople review the series before this one, and the performance related\nones I'll be posting later. The testcases are pretty thorough in this\narea, in part thanks to additional suggestions from Stefan a few years\nback, and the similarity of the logic makes me less concerned about\nthis topic than any of the others in the merge-ort and diffcore-rename\nwork that I have and will be doing.\n\n\nIn summary:\n * en/ort-conflict-handling and en/diffcore-rename are ready to merge\ndown (and you already started on one of them)\n * I'm not sure if anyone will review en/ort-directory-rename (it's\nbeen a week and a half with no review so far), but I'm tempted to\nencourage people to save their review effort for other topics.\nThere's just not much different here than what's found in\nmerge-recursive.c. (With the exception of patch 17...)\n\n> It does not instill a lot of confidence in these topics that nobody\n> commented on things like [v2 17/17] of en/ort-directory-rename\n> (which fixes the code introduced in [v2 06/17] instead of fixing it\n> at the source before 06/17 copies it from elsewhere [*1*]). It\n> looks to me like a sign that these collection of series are moving\n> too fast than any reviewer to catch up.\n\nI considered just moving 17/17 earlier, and even started that way, but\nthere are a couple problems with that:\n\n1) The comparison of directory rename detection code between\nmerge-recursive.c and merge-ort.c, if folks want to compare the two,\nis much easier if I first implement the same algorithm\n\n2) 06/17 introduces the concept of counting renames from a directory\nand picking the highest count; the idea is simple but but with the\nextra complications from 17/17 the combined patch just looks too\nobtuse to follow done all in one step. Splitting 17/17 into a\nseparate later step was something that I felt would make it easier to\nreview.\n\n3) 06/17 consists of well-understood code from merge-recursive.c.\n17/17 is new. If we ever want to port the fix from merge-ort to\nmerge-recursive, having it as a separate change will help with that.\n\n\nSo, although it may look weird, I intentionally changed from a\ncombined early commit, as you seem to be suggesting here, into\nsplitting it out this way. I also considered removing 17/17 from the\nseries and then submitting it later.\n\n> Thanks.\n>\n>\n> [Footnote]\n>\n> *1* I do not particularly think [06/17] that copies and leaves the\n> recursive backend behind is necessarily bad. What I find more\n> disturbing is that nobody seems to have a chance to give any\n> look to the two iterations of the series (as far as I can see,\n> v2 is just in name only---it removed 18/17 in v1 that were not\n> meant to be sent), and we are about to build on top of the\n> foundation that nobody knows how solid it is.\n\nWhat if we dropped 17/17 from en/ort-directory-rename (the\nmerge/rename performance work doesn't depend upon it), and then merged\nthat series down? Without 17/17, the series is just a port of code\nthat exists in merge-recursive.c that has been battle tested for\nyears. I could submit the final patch separately later.\n"},{"id":"414463","messageId":"20210115192958.3336755-1-newren@gmail.com","threadId":"54966","inReplyTo":"20210113221158.2869128-1-newren@gmail.com","subject":"[PATCH v3 0/1] And so it begins...merge/rename performance work","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-15T19:29:57Z","receivedAt":"2021-01-15T19:31:30Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This depends on a merge of en/ort-conflict-handling, en/diffcore-rename,\nand en/ort-directory-rename.\n\nChanges since v2:\n * Add another step I forgot in my testcase setup -- setting\n merge.directoryRenames (noticed by Sangeeta); I've double checked\n that I didn't forget any other settings.\n\nElijah Newren (1):\n merge-ort: begin performance work; instrument with trace2_region_*\n calls\n\n diffcore-rename.c | 8 +++++++\n merge-ort.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 65 insertions(+)\n\nRange-diff:\n1: 8783f209ef ! 1: 644f458c01 merge-ort: begin performance work; instrument with trace2_region_* calls\n @@ Commit message\n $ git mv drivers pilots # Introduce over 26,000 renames\n $ git commit -m \"Rename drivers/ to pilots/\"\n $ git config merge.renameLimit 30000\n + $ git config merge.directoryRenames true\n \n === Testcases ===\n \n-- \n2.29.2.506.ga68ba46ed0.dirty\n\n"},{"id":"414464","messageId":"20210115192958.3336755-2-newren@gmail.com","threadId":"54966","inReplyTo":"20210115192958.3336755-1-newren@gmail.com","subject":"[PATCH v3 1/1] merge-ort: begin performance work; instrument with trace2_region_* calls","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-15T19:29:58Z","receivedAt":"2021-01-15T19:31:30Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Add some timing instrumentation for both merge-ort and diffcore-rename;\nI used these to measure and optimize performance in both, and several\nfuture patch series will build on these to reduce the timings of some\nselect testcases.\n\n=== Setup ===\n\nThe primary testcase I used involved rebasing a random topic in the\nlinux kernel (consisting of 35 patches) against an older version. I\nadded two variants, one where I rename a toplevel directory, and another\nwhere I only rebase one patch instead of the whole topic. The setup is\nas follows:\n\n $ git clone git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git\n $ git branch hwmon-updates fd8bdb23b91876ac1e624337bb88dc1dcc21d67e\n $ git branch hwmon-just-one fd8bdb23b91876ac1e624337bb88dc1dcc21d67e~34\n $ git branch base 4703d9119972bf586d2cca76ec6438f819ffa30e\n $ git switch -c 5.4-renames v5.4\n $ git mv drivers pilots # Introduce over 26,000 renames\n $ git commit -m \"Rename drivers/ to pilots/\"\n $ git config merge.renameLimit 30000\n $ git config merge.directoryRenames true\n\n=== Testcases ===\n\nNow with REBASE standing for either \"git rebase [--merge]\" (using\nmerge-recursive) or \"test-tool fast-rebase\" (using merge-ort), the\ntestcases are:\n\nTestcase #1: no-renames\n\n $ git checkout v5.4^0\n $ REBASE --onto HEAD base hwmon-updates\n\n Note: technically the name is misleading; there are some renames, but\n very few. Rename detection only takes about half the overall time.\n\nTestcase #2: mega-renames\n\n $ git checkout 5.4-renames^0\n $ REBASE --onto HEAD base hwmon-updates\n\nTestcase #3: just-one-mega\n\n $ git checkout 5.4-renames^0\n $ REBASE --onto HEAD base hwmon-just-one\n\n=== Timing results ===\n\nOverall timings, using hyperfine (1 warmup run, 3 runs for mega-renames,\n10 runs for the other two cases):\n\n merge-recursive merge-ort\n no-renames: 18.912 s ± 0.174 s 12.975 s ± 0.037 s\n mega-renames: 5964.031 s ± 10.459 s 5154.338 s ± 19.139 s\n just-one-mega: 149.583 s ± 0.751 s 146.703 s ± 0.852 s\n\nA single re-run of each with some breakdowns:\n\n --- no-renames ---\n merge-recursive merge-ort\n overall runtime: 19.302 s 13.017 s\n inexact rename detection: 7.603 s 7.695 s\n everything else: 11.699 s 5.322 s\n\n --- mega-renames ---\n merge-recursive merge-ort\n overall runtime: 5950.195 s 5132.851 s\n inexact rename detection: 5746.309 s 5119.215 s\n everything else: 203.886 s 13.636 s\n\n --- just-one-mega ---\n merge-recursive merge-ort\n overall runtime: 151.001 s 146.478 s\n inexact rename detection: 143.448 s 145.901 s\n everything else: 7.553 s 0.577 s\n\n=== Timing observations ===\n\n1) no-renames\n\n1a) merge-ort is faster than merge-recursive, which is nice. However,\nthis still should not be considered good enough. Although the \"merge\"\nbackend to rebase (merge-recursive) is sometimes faster than the \"apply\"\nbackend, this is one of those cases where it is not. In fact, even\nmerge-ort is slower. The \"apply\" backend can complete this testcase in\n 6.940 s ± 0.485 s\nwhich is about 2x faster than merge-ort and 3x faster than\nmerge-recursive. One goal of the merge-ort performance work will be to\nmake it faster than git-am on this (and similar) testcases.\n\n2) mega-renames\n\n2a) Obviously rename detection is a huge cost; it's where most the time\nis spent. We need to cut that down. If we could somehow infinitely\nparallelize it and drive its time to 0, the merge-recursive time would\ndrop to about 204s, and the merge-ort time would drop to about 14s. I\nthink this particular stat shows I've subtly baked a couple performance\nimprovements into merge-ort[A] (one of them large) and into\nfast-rebase[B] already.\n\n [A] Avoid quadratic behavior with O(N) insertions or removals\n\tof entries in the index & avoid unconditional dropping and\n re-reading of the index\n [B] Avoid updating the on-disk index or the working directory\n for intermediate patches -- only update at the end\n\n2b) rename-detection is somehow ~10% cheaper for merge-ort than\nmerge-recursive. This was and is a big surprise to me. Both of them\ncall diff_tree_oid() and diffcore_std() with the EXACT same inputs. I\ndon't have an explanation, but it is very consistent even after\nre-running many times. Interestingly, the rename detection for the\nfirst patch is more expensive (just barely) for merge-ort than\nmerge-recursive, and that is also consistent. I won't investigate this\nfurther, as I'm just going to focus on 1a & 2a.\n\n3) just-one-mega\n\n3a) not much to say here, it just gives some flavor for how rebasing\nonly one patch compares to rebasing 35.\n\n=== Goals ===\n\nThis patch is obviously just the beginning. Here are some of my goals\nthat this measurement will help us achieve:\n\n* Drive the cost of rename detection down considerably for merges\n* After the above has been achieved, see if there are other slowness\n factors (which would have previously been overshadowed by rename\n detection costs) which we can then focus on and also optimize.\n* Ensure our rebase testcase that requires little rename detection\n is noticeably faster with merge-ort than with apply-based rebase.\n\nSigned-off-by: Elijah Newren \nAcked-by: Taylor Blau \n---\n diffcore-rename.c | 8 +++++++\n merge-ort.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 65 insertions(+)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 90db9ebd6d..8fe6c9384b 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -465,6 +465,7 @@ void diffcore_rename(struct diff_options *options)\n \tint num_destinations, dst_cnt;\n \tstruct progress *progress = NULL;\n \n+\ttrace2_region_enter(\"diff\", \"setup\", options->repo);\n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n \n@@ -510,14 +511,17 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tregister_rename_src(p);\n \t\t}\n \t}\n+\ttrace2_region_leave(\"diff\", \"setup\", options->repo);\n \tif (rename_dst_nr == 0 || rename_src_nr == 0)\n \t\tgoto cleanup; /* nothing to do */\n \n+\ttrace2_region_enter(\"diff\", \"exact renames\", options->repo);\n \t/*\n \t * We really want to cull the candidates list early\n \t * with cheap tests in order to avoid doing deltas.\n \t */\n \trename_count = find_exact_renames(options);\n+\ttrace2_region_leave(\"diff\", \"exact renames\", options->repo);\n \n \t/* Did we only want exact renames? */\n \tif (minimum_score == MAX_SCORE)\n@@ -545,6 +549,7 @@ void diffcore_rename(struct diff_options *options)\n \t\tbreak;\n \t}\n \n+\ttrace2_region_enter(\"diff\", \"inexact renames\", options->repo);\n \tif (options->show_rename_progress) {\n \t\tprogress = start_delayed_progress(\n \t\t\t\t_(\"Performing inexact rename detection\"),\n@@ -600,11 +605,13 @@ void diffcore_rename(struct diff_options *options)\n \tif (detect_rename == DIFF_DETECT_COPY)\n \t\trename_count += find_renames(mx, dst_cnt, minimum_score, 1);\n \tfree(mx);\n+\ttrace2_region_leave(\"diff\", \"inexact renames\", options->repo);\n \n cleanup:\n \t/* At this point, we have found some renames and copies and they\n \t * are recorded in rename_dst. The original list is still in *q.\n \t */\n+\ttrace2_region_enter(\"diff\", \"write back to queue\", options->repo);\n \tDIFF_QUEUE_CLEAR(&outq);\n \tfor (i = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n@@ -680,5 +687,6 @@ void diffcore_rename(struct diff_options *options)\n \t\tstrintmap_clear(break_idx);\n \t\tFREE_AND_NULL(break_idx);\n \t}\n+\ttrace2_region_leave(\"diff\", \"write back to queue\", options->repo);\n \treturn;\n }\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 8f4ca4fe83..0f3ad78f3c 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -752,7 +752,9 @@ static int collect_merge_info(struct merge_options *opt,\n \tinit_tree_desc(t + 1, side1->buffer, side1->size);\n \tinit_tree_desc(t + 2, side2->buffer, side2->size);\n \n+\ttrace2_region_enter(\"merge\", \"traverse_trees\", opt->repo);\n \tret = traverse_trees(NULL, 3, t, &info);\n+\ttrace2_region_leave(\"merge\", \"traverse_trees\", opt->repo);\n \n \treturn ret;\n }\n@@ -2095,9 +2097,12 @@ static void detect_regular_renames(struct merge_options *opt,\n \tdiff_opts.show_rename_progress = opt->show_rename_progress;\n \tdiff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;\n \tdiff_setup_done(&diff_opts);\n+\n+\ttrace2_region_enter(\"diff\", \"diffcore_rename\", opt->repo);\n \tdiff_tree_oid(&merge_base->object.oid, &side->object.oid, \"\",\n \t\t &diff_opts);\n \tdiffcore_std(&diff_opts);\n+\ttrace2_region_leave(\"diff\", \"diffcore_rename\", opt->repo);\n \n \tif (diff_opts.needed_rename_limit > renames->needed_limit)\n \t\trenames->needed_limit = diff_opts.needed_rename_limit;\n@@ -2196,9 +2201,12 @@ static int detect_and_process_renames(struct merge_options *opt,\n \n \tmemset(&combined, 0, sizeof(combined));\n \n+\ttrace2_region_enter(\"merge\", \"regular renames\", opt->repo);\n \tdetect_regular_renames(opt, merge_base, side1, MERGE_SIDE1);\n \tdetect_regular_renames(opt, merge_base, side2, MERGE_SIDE2);\n+\ttrace2_region_leave(\"merge\", \"regular renames\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"directory renames\", opt->repo);\n \tneed_dir_renames =\n \t !opt->priv->call_depth &&\n \t (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE ||\n@@ -2220,8 +2228,11 @@ static int detect_and_process_renames(struct merge_options *opt,\n \t\t\t\t &renames->dir_renames[1],\n \t\t\t\t &renames->dir_renames[2]);\n \tQSORT(combined.queue, combined.nr, compare_pairs);\n+\ttrace2_region_leave(\"merge\", \"directory renames\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"process renames\", opt->repo);\n \tclean &= process_renames(opt, &combined);\n+\ttrace2_region_leave(\"merge\", \"process renames\", opt->repo);\n \n \t/* Free memory for renames->pairs[] and combined */\n \tfor (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {\n@@ -2903,20 +2914,30 @@ static void process_entries(struct merge_options *opt,\n \t\t\t\t\t\t STRING_LIST_INIT_NODUP,\n \t\t\t\t\t\t NULL, 0 };\n \n+\ttrace2_region_enter(\"merge\", \"process_entries setup\", opt->repo);\n \tif (strmap_empty(&opt->priv->paths)) {\n \t\toidcpy(result_oid, opt->repo->hash_algo->empty_tree);\n \t\treturn;\n \t}\n \n \t/* Hack to pre-allocate plist to the desired size */\n+\ttrace2_region_enter(\"merge\", \"plist grow\", opt->repo);\n \tALLOC_GROW(plist.items, strmap_get_size(&opt->priv->paths), plist.alloc);\n+\ttrace2_region_leave(\"merge\", \"plist grow\", opt->repo);\n \n \t/* Put every entry from paths into plist, then sort */\n+\ttrace2_region_enter(\"merge\", \"plist copy\", opt->repo);\n \tstrmap_for_each_entry(&opt->priv->paths, &iter, e) {\n \t\tstring_list_append(&plist, e->key)->util = e->value;\n \t}\n+\ttrace2_region_leave(\"merge\", \"plist copy\", opt->repo);\n+\n+\ttrace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n \tplist.cmp = string_list_df_name_compare;\n \tstring_list_sort(&plist);\n+\ttrace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n+\n+\ttrace2_region_leave(\"merge\", \"process_entries setup\", opt->repo);\n \n \t/*\n \t * Iterate over the items in reverse order, so we can handle paths\n@@ -2927,6 +2948,7 @@ static void process_entries(struct merge_options *opt,\n \t * (because it allows us to know whether the directory is still in\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 \tfor (entry = &plist.items[plist.nr-1]; entry >= plist.items; --entry) {\n \t\tchar *path = entry->string;\n \t\t/*\n@@ -2945,7 +2967,9 @@ static void process_entries(struct merge_options *opt,\n \t\t\tprocess_entry(opt, path, ci, &dir_metadata);\n \t\t}\n \t}\n+\ttrace2_region_leave(\"merge\", \"processing\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"process_entries cleanup\", opt->repo);\n \tif (dir_metadata.offsets.nr != 1 ||\n \t (uintptr_t)dir_metadata.offsets.items[0].util != 0) {\n \t\tprintf(\"dir_metadata.offsets.nr = %d (should be 1)\\n\",\n@@ -2960,6 +2984,7 @@ static void process_entries(struct merge_options *opt,\n \tstring_list_clear(&plist, 0);\n \tstring_list_clear(&dir_metadata.versions, 0);\n \tstring_list_clear(&dir_metadata.offsets, 0);\n+\ttrace2_region_leave(\"merge\", \"process_entries cleanup\", opt->repo);\n }\n \n /*** Function Grouping: functions related to merge_switch_to_result() ***/\n@@ -3118,12 +3143,15 @@ void merge_switch_to_result(struct merge_options *opt,\n \tif (result->clean >= 0 && update_worktree_and_index) {\n \t\tstruct merge_options_internal *opti = result->priv;\n \n+\t\ttrace2_region_enter(\"merge\", \"checkout\", opt->repo);\n \t\tif (checkout(opt, head, result->tree)) {\n \t\t\t/* failure to function */\n \t\t\tresult->clean = -1;\n \t\t\treturn;\n \t\t}\n+\t\ttrace2_region_leave(\"merge\", \"checkout\", opt->repo);\n \n+\t\ttrace2_region_enter(\"merge\", \"record_conflicted\", opt->repo);\n \t\tif (record_conflicted_index_entries(opt, opt->repo->index,\n \t\t\t\t\t\t &opti->paths,\n \t\t\t\t\t\t &opti->conflicted)) {\n@@ -3131,6 +3159,7 @@ void merge_switch_to_result(struct merge_options *opt,\n \t\t\tresult->clean = -1;\n \t\t\treturn;\n \t\t}\n+\t\ttrace2_region_leave(\"merge\", \"record_conflicted\", opt->repo);\n \t}\n \n \tif (display_update_msgs) {\n@@ -3140,6 +3169,8 @@ void merge_switch_to_result(struct merge_options *opt,\n \t\tstruct string_list olist = STRING_LIST_INIT_NODUP;\n \t\tint i;\n \n+\t\ttrace2_region_enter(\"merge\", \"display messages\", opt->repo);\n+\n \t\t/* Hack to pre-allocate olist to the desired size */\n \t\tALLOC_GROW(olist.items, strmap_get_size(&opti->output),\n \t\t\t olist.alloc);\n@@ -3161,6 +3192,8 @@ void merge_switch_to_result(struct merge_options *opt,\n \t\t/* Also include needed rename limit adjustment now */\n \t\tdiff_warn_rename_limit(\"merge.renamelimit\",\n \t\t\t\t opti->renames.needed_limit, 0);\n+\n+\t\ttrace2_region_leave(\"merge\", \"display messages\", opt->repo);\n \t}\n \n \tmerge_finalize(opt, result);\n@@ -3202,6 +3235,7 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \tint i;\n \n \t/* Sanity checks on opt */\n+\ttrace2_region_enter(\"merge\", \"sanity checks\", opt->repo);\n \tassert(opt->repo);\n \n \tassert(opt->branch1 && opt->branch2);\n@@ -3228,11 +3262,13 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \tassert(opt->obuf.len == 0);\n \n \tassert(opt->priv == NULL);\n+\ttrace2_region_leave(\"merge\", \"sanity checks\", opt->repo);\n \n \t/* Default to histogram diff. Actually, just hardcode it...for now. */\n \topt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);\n \n \t/* Initialization of opt->priv, our internal merge data */\n+\ttrace2_region_enter(\"merge\", \"allocate/init\", opt->repo);\n \topt->priv = xcalloc(1, sizeof(*opt->priv));\n \n \t/* Initialization of various renames fields */\n@@ -3265,6 +3301,8 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \t * subset of the overall paths that have special output.\n \t */\n \tstrmap_init(&opt->priv->output);\n+\n+\ttrace2_region_leave(\"merge\", \"allocate/init\", opt->repo);\n }\n \n /*** Function Grouping: merge_incore_*() and their internal variants ***/\n@@ -3280,6 +3318,7 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n {\n \tstruct object_id working_tree_oid;\n \n+\ttrace2_region_enter(\"merge\", \"collect_merge_info\", opt->repo);\n \tif (collect_merge_info(opt, merge_base, side1, side2) != 0) {\n \t\t/*\n \t\t * TRANSLATORS: The %s arguments are: 1) tree hash of a merge\n@@ -3292,10 +3331,16 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n \t\tresult->clean = -1;\n \t\treturn;\n \t}\n+\ttrace2_region_leave(\"merge\", \"collect_merge_info\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"renames\", opt->repo);\n \tresult->clean = detect_and_process_renames(opt, merge_base,\n \t\t\t\t\t\t side1, side2);\n+\ttrace2_region_leave(\"merge\", \"renames\", opt->repo);\n+\n+\ttrace2_region_enter(\"merge\", \"process_entries\", opt->repo);\n \tprocess_entries(opt, &working_tree_oid);\n+\ttrace2_region_leave(\"merge\", \"process_entries\", opt->repo);\n \n \t/* Set return values */\n \tresult->tree = parse_tree_indirect(&working_tree_oid);\n@@ -3396,9 +3441,15 @@ void merge_incore_nonrecursive(struct merge_options *opt,\n \t\t\t struct tree *side2,\n \t\t\t struct merge_result *result)\n {\n+\ttrace2_region_enter(\"merge\", \"incore_nonrecursive\", opt->repo);\n+\n+\ttrace2_region_enter(\"merge\", \"merge_start\", opt->repo);\n \tassert(opt->ancestor != NULL);\n \tmerge_start(opt, result);\n+\ttrace2_region_leave(\"merge\", \"merge_start\", opt->repo);\n+\n \tmerge_ort_nonrecursive_internal(opt, merge_base, side1, side2, result);\n+\ttrace2_region_leave(\"merge\", \"incore_nonrecursive\", opt->repo);\n }\n \n void merge_incore_recursive(struct merge_options *opt,\n@@ -3407,9 +3458,15 @@ void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit *side2,\n \t\t\t struct merge_result *result)\n {\n+\ttrace2_region_enter(\"merge\", \"incore_recursive\", opt->repo);\n+\n \t/* We set the ancestor label based on the merge_bases */\n \tassert(opt->ancestor == NULL);\n \n+\ttrace2_region_enter(\"merge\", \"merge_start\", opt->repo);\n \tmerge_start(opt, result);\n+\ttrace2_region_leave(\"merge\", \"merge_start\", opt->repo);\n+\n \tmerge_ort_internal(opt, merge_bases, side1, side2, result);\n+\ttrace2_region_leave(\"merge\", \"incore_recursive\", opt->repo);\n }\n-- \n2.29.2.506.ga68ba46ed0.dirty\n\n"},{"id":"415129","messageId":"20210124060112.1258291-1-newren@gmail.com","threadId":"54966","inReplyTo":"20210115192958.3336755-1-newren@gmail.com","subject":"[PATCH v4 0/3] And so it begins...merge/rename performance work","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-24T06:01:09Z","receivedAt":"2021-01-24T06:02:41Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This depends on a merge of en/ort-conflict-handling, en/diffcore-rename,\nand en/ort-directory-rename.\n\nChanges since v3:\n * Add a couple preliminary patches needed for later performance work,\n including fixing a big memory leak (in some series that has already\n been merged to master, I should have included a small additional\n section of code from my 'ort' branch, but I overlooked it).\n * Update the performance numbers in the commit message of the final\n patch based on the changes; the memory leak makes a noticeable\n difference on the overall timings since it basically represents\n a combination of all the data allocated during the merge algorithm.\n\nElijah Newren (3):\n merge-ort: fix massive leak\n merge-ort: ignore the directory rename split conflict for now\n merge-ort: begin performance work; instrument with trace2_region_*\n calls\n\n diffcore-rename.c | 8 +++++\n merge-ort.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++-\n 2 files changed, 94 insertions(+), 1 deletion(-)\n\nRange-diff:\n-: ---------- > 1: 549a63cd2a merge-ort: fix massive leak\n-: ---------- > 2: 817a197dbc merge-ort: ignore the directory rename split conflict for now\n1: 36d1f87d05 ! 3: 7f7d4a3e17 merge-ort: begin performance work; instrument with trace2_region_* calls\n @@ Commit message\n Overall timings, using hyperfine (1 warmup run, 3 runs for mega-renames,\n 10 runs for the other two cases):\n \n - merge-recursive merge-ort\n - no-renames: 18.912 s ± 0.174 s 12.975 s ± 0.037 s\n - mega-renames: 5964.031 s ± 10.459 s 5154.338 s ± 19.139 s\n - just-one-mega: 149.583 s ± 0.751 s 146.703 s ± 0.852 s\n + merge-recursive merge-ort\n + no-renames: 18.912 s ± 0.174 s 14.263 s ± 0.053 s\n + mega-renames: 5964.031 s ± 10.459 s 5504.231 s ± 5.150 s\n + just-one-mega: 149.583 s ± 0.751 s 158.534 s ± 0.498 s\n \n A single re-run of each with some breakdowns:\n \n - --- no-renames ---\n - merge-recursive merge-ort\n - overall runtime: 19.302 s 13.017 s\n - inexact rename detection: 7.603 s 7.695 s\n - everything else: 11.699 s 5.322 s\n + --- no-renames ---\n + merge-recursive merge-ort\n + overall runtime: 19.302 s 14.257 s\n + inexact rename detection: 7.603 s 7.906 s\n + everything else: 11.699 s 6.351 s\n \n - --- mega-renames ---\n - merge-recursive merge-ort\n - overall runtime: 5950.195 s 5132.851 s\n - inexact rename detection: 5746.309 s 5119.215 s\n - everything else: 203.886 s 13.636 s\n + --- mega-renames ---\n + merge-recursive merge-ort\n + overall runtime: 5950.195 s 5499.672 s\n + inexact rename detection: 5746.309 s 5487.120 s\n + everything else: 203.886 s 17.552 s\n \n - --- just-one-mega ---\n - merge-recursive merge-ort\n - overall runtime: 151.001 s 146.478 s\n - inexact rename detection: 143.448 s 145.901 s\n - everything else: 7.553 s 0.577 s\n + --- just-one-mega ---\n + merge-recursive merge-ort\n + overall runtime: 151.001 s 158.582 s\n + inexact rename detection: 143.448 s 157.835 s\n + everything else: 7.553 s 0.747 s\n \n === Timing observations ===\n \n + 0) Maximum speedup\n +\n + The \"everything else\" row represents the maximum speedup we could\n + achieve if we were to somehow infinitely parallelize inexact rename\n + detection, but leave everything else alone. The fact that this is so\n + much smaller than the real runtime (even in the case with virtually no\n + renames) makes it clear just how overwhelmingly large the time spent on\n + rename detection can be.\n +\n 1) no-renames\n \n 1a) merge-ort is faster than merge-recursive, which is nice. However,\n @@ Commit message\n 2a) Obviously rename detection is a huge cost; it's where most the time\n is spent. We need to cut that down. If we could somehow infinitely\n parallelize it and drive its time to 0, the merge-recursive time would\n - drop to about 204s, and the merge-ort time would drop to about 14s. I\n + drop to about 204s, and the merge-ort time would drop to about 17s. I\n think this particular stat shows I've subtly baked a couple performance\n - improvements into merge-ort[A] (one of them large) and into\n - fast-rebase[B] already.\n -\n - [A] Avoid quadratic behavior with O(N) insertions or removals\n - of entries in the index & avoid unconditional dropping and\n - re-reading of the index\n - [B] Avoid updating the on-disk index or the working directory\n - for intermediate patches -- only update at the end\n -\n - 2b) rename-detection is somehow ~10% cheaper for merge-ort than\n - merge-recursive. This was and is a big surprise to me. Both of them\n - call diff_tree_oid() and diffcore_std() with the EXACT same inputs. I\n - don't have an explanation, but it is very consistent even after\n - re-running many times. Interestingly, the rename detection for the\n - first patch is more expensive (just barely) for merge-ort than\n - merge-recursive, and that is also consistent. I won't investigate this\n - further, as I'm just going to focus on 1a & 2a.\n + improvements into merge-ort and into fast-rebase already.\n \n 3) just-one-mega\n \n @@ merge-ort.c: static void merge_start(struct merge_options *opt, struct merge_res\n \n \tassert(opt->branch1 && opt->branch2);\n @@ merge-ort.c: static void merge_start(struct merge_options *opt, struct merge_result *result)\n - \tassert(opt->obuf.len == 0);\n - \n - \tassert(opt->priv == NULL);\n + \t\tassert(!opt->priv->toplevel_dir ||\n + \t\t 0 == strlen(opt->priv->toplevel_dir));\n + \t}\n +\ttrace2_region_leave(\"merge\", \"sanity checks\", opt->repo);\n \n \t/* Default to histogram diff. Actually, just hardcode it...for now. */\n @@ merge-ort.c: static void merge_start(struct merge_options *opt, struct merge_res\n \n \t/* Initialization of opt->priv, our internal merge data */\n +\ttrace2_region_enter(\"merge\", \"allocate/init\", opt->repo);\n - \topt->priv = xcalloc(1, sizeof(*opt->priv));\n - \n - \t/* Initialization of various renames fields */\n + \tif (opt->priv) {\n + \t\tclear_or_reinit_internal_opts(opt->priv, 1);\n + \t\ttrace2_region_leave(\"merge\", \"allocate/init\", opt->repo);\n @@ merge-ort.c: static void merge_start(struct merge_options *opt, struct merge_result *result)\n \t * subset of the overall paths that have special output.\n \t */\n-- \n2.30.0.135.g7f7d4a3e17\n\n"},{"id":"415128","messageId":"20210124060112.1258291-3-newren@gmail.com","threadId":"54966","inReplyTo":"20210124060112.1258291-1-newren@gmail.com","subject":"[PATCH v4 2/3] merge-ort: ignore the directory rename split conflict for now","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-24T06:01:11Z","receivedAt":"2021-01-24T06:02:42Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"get_provisional_directory_renames() has code to detect directories being\nevenly split between different locations. However, as noted previously,\nif there are no new files added to that directory that was split evenly,\nour inability to determine where the directory was renamed to doesn't\nmatter since there are no new files to try to move into the new\nlocation. Unfortunately, that code is unaware of whether there are new\nfiles under the directory in question and we just ignore that, causing\nus to fail t6423 test 2b but pass test 2a; turn off the error for now,\nswapping which tests pass and fail.\n\nThe motivating reason for switching this off as a temporary measure is\nthat as we add optimizations, we'll start looking at only subsets of\nrenames, and subsets of renames can start switching the result we get\nwhen this error is (wrongly) on. Once we get enough optimizations,\nhowever, we can prevent that code from even running when there are no\nnew files added to the relevant directory, at which point we can revert\nthis commit and then both testcases 2a and 2b will pass simultaneously.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 13 ++++++++++++-\n 1 file changed, 12 insertions(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex b5845ff6e9..f04fab96d7 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -1439,7 +1439,18 @@ static void get_provisional_directory_renames(struct merge_options *opt,\n \t\t\t\t \"no destination getting a majority of the \"\n \t\t\t\t \"files.\"),\n \t\t\t source_dir);\n-\t\t\t*clean = 0;\n+\t\t\t/*\n+\t\t\t * We should mark this as unclean IF something attempts\n+\t\t\t * to use this rename. We do not yet have the logic\n+\t\t\t * in place to detect if this directory rename is being\n+\t\t\t * used, and optimizations that reduce the number of\n+\t\t\t * renames cause this to falsely trigger. For now,\n+\t\t\t * just disable it, causing t6423 testcase 2a to break.\n+\t\t\t * We'll later fix the detection, and when we do we\n+\t\t\t * will re-enable setting *clean to 0 (and thereby fix\n+\t\t\t * t6423 testcase 2a).\n+\t\t\t */\n+\t\t\t/* *clean = 0; */\n \t\t} else {\n \t\t\tstrmap_put(&renames->dir_renames[side],\n \t\t\t\t source_dir, (void*)best);\n-- \n2.30.0.135.g7f7d4a3e17\n\n"},{"id":"415130","messageId":"20210124060112.1258291-2-newren@gmail.com","threadId":"54966","inReplyTo":"20210124060112.1258291-1-newren@gmail.com","subject":"[PATCH v4 1/3] merge-ort: fix massive leak","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-24T06:01:10Z","receivedAt":"2021-01-24T06:02:42Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"When a series of merges was performed (such as for a rebase or series of\ncherry-picks), only the data structures allocated by the final merge\noperation were being freed. The problem was that while picking out\npieces of merge-ort to upstream, I previously misread a certain section\nof merge_start() and assumed it was associated with a later\noptimization. Include that section now, which ensures that if there was\na previous merge operation, that we clear out result->priv and then\nre-use it for opt->priv, and otherwise we allocate opt->priv.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 17 +++++++++++++++++\n 1 file changed, 17 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 05c6b2e0dc..b5845ff6e9 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -3227,11 +3227,28 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \tassert(opt->obuf.len == 0);\n \n \tassert(opt->priv == NULL);\n+\tif (result->priv) {\n+\t\topt->priv = result->priv;\n+\t\tresult->priv = NULL;\n+\t\t/*\n+\t\t * opt->priv non-NULL means we had results from a previous\n+\t\t * run; do a few sanity checks that user didn't mess with\n+\t\t * it in an obvious fashion.\n+\t\t */\n+\t\tassert(opt->priv->call_depth == 0);\n+\t\tassert(!opt->priv->toplevel_dir ||\n+\t\t 0 == strlen(opt->priv->toplevel_dir));\n+\t}\n \n \t/* Default to histogram diff. Actually, just hardcode it...for now. */\n \topt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);\n \n \t/* Initialization of opt->priv, our internal merge data */\n+\tif (opt->priv) {\n+\t\tclear_or_reinit_internal_opts(opt->priv, 1);\n+\t\ttrace2_region_leave(\"merge\", \"allocate/init\", opt->repo);\n+\t\treturn;\n+\t}\n \topt->priv = xcalloc(1, sizeof(*opt->priv));\n \n \t/* Initialization of various renames fields */\n-- \n2.30.0.135.g7f7d4a3e17\n\n"},{"id":"415131","messageId":"20210124060112.1258291-4-newren@gmail.com","threadId":"54966","inReplyTo":"20210124060112.1258291-1-newren@gmail.com","subject":"[PATCH v4 3/3] merge-ort: begin performance work; instrument with trace2_region_* calls","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-01-24T06:01:12Z","receivedAt":"2021-01-24T06:04:25Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Add some timing instrumentation for both merge-ort and diffcore-rename;\nI used these to measure and optimize performance in both, and several\nfuture patch series will build on these to reduce the timings of some\nselect testcases.\n\n=== Setup ===\n\nThe primary testcase I used involved rebasing a random topic in the\nlinux kernel (consisting of 35 patches) against an older version. I\nadded two variants, one where I rename a toplevel directory, and another\nwhere I only rebase one patch instead of the whole topic. The setup is\nas follows:\n\n $ git clone git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git\n $ git branch hwmon-updates fd8bdb23b91876ac1e624337bb88dc1dcc21d67e\n $ git branch hwmon-just-one fd8bdb23b91876ac1e624337bb88dc1dcc21d67e~34\n $ git branch base 4703d9119972bf586d2cca76ec6438f819ffa30e\n $ git switch -c 5.4-renames v5.4\n $ git mv drivers pilots # Introduce over 26,000 renames\n $ git commit -m \"Rename drivers/ to pilots/\"\n $ git config merge.renameLimit 30000\n $ git config merge.directoryRenames true\n\n=== Testcases ===\n\nNow with REBASE standing for either \"git rebase [--merge]\" (using\nmerge-recursive) or \"test-tool fast-rebase\" (using merge-ort), the\ntestcases are:\n\nTestcase #1: no-renames\n\n $ git checkout v5.4^0\n $ REBASE --onto HEAD base hwmon-updates\n\n Note: technically the name is misleading; there are some renames, but\n very few. Rename detection only takes about half the overall time.\n\nTestcase #2: mega-renames\n\n $ git checkout 5.4-renames^0\n $ REBASE --onto HEAD base hwmon-updates\n\nTestcase #3: just-one-mega\n\n $ git checkout 5.4-renames^0\n $ REBASE --onto HEAD base hwmon-just-one\n\n=== Timing results ===\n\nOverall timings, using hyperfine (1 warmup run, 3 runs for mega-renames,\n10 runs for the other two cases):\n\n merge-recursive merge-ort\n no-renames: 18.912 s ± 0.174 s 14.263 s ± 0.053 s\n mega-renames: 5964.031 s ± 10.459 s 5504.231 s ± 5.150 s\n just-one-mega: 149.583 s ± 0.751 s 158.534 s ± 0.498 s\n\nA single re-run of each with some breakdowns:\n\n --- no-renames ---\n merge-recursive merge-ort\n overall runtime: 19.302 s 14.257 s\n inexact rename detection: 7.603 s 7.906 s\n everything else: 11.699 s 6.351 s\n\n --- mega-renames ---\n merge-recursive merge-ort\n overall runtime: 5950.195 s 5499.672 s\n inexact rename detection: 5746.309 s 5487.120 s\n everything else: 203.886 s 17.552 s\n\n --- just-one-mega ---\n merge-recursive merge-ort\n overall runtime: 151.001 s 158.582 s\n inexact rename detection: 143.448 s 157.835 s\n everything else: 7.553 s 0.747 s\n\n=== Timing observations ===\n\n0) Maximum speedup\n\nThe \"everything else\" row represents the maximum speedup we could\nachieve if we were to somehow infinitely parallelize inexact rename\ndetection, but leave everything else alone. The fact that this is so\nmuch smaller than the real runtime (even in the case with virtually no\nrenames) makes it clear just how overwhelmingly large the time spent on\nrename detection can be.\n\n1) no-renames\n\n1a) merge-ort is faster than merge-recursive, which is nice. However,\nthis still should not be considered good enough. Although the \"merge\"\nbackend to rebase (merge-recursive) is sometimes faster than the \"apply\"\nbackend, this is one of those cases where it is not. In fact, even\nmerge-ort is slower. The \"apply\" backend can complete this testcase in\n 6.940 s ± 0.485 s\nwhich is about 2x faster than merge-ort and 3x faster than\nmerge-recursive. One goal of the merge-ort performance work will be to\nmake it faster than git-am on this (and similar) testcases.\n\n2) mega-renames\n\n2a) Obviously rename detection is a huge cost; it's where most the time\nis spent. We need to cut that down. If we could somehow infinitely\nparallelize it and drive its time to 0, the merge-recursive time would\ndrop to about 204s, and the merge-ort time would drop to about 17s. I\nthink this particular stat shows I've subtly baked a couple performance\nimprovements into merge-ort and into fast-rebase already.\n\n3) just-one-mega\n\n3a) not much to say here, it just gives some flavor for how rebasing\nonly one patch compares to rebasing 35.\n\n=== Goals ===\n\nThis patch is obviously just the beginning. Here are some of my goals\nthat this measurement will help us achieve:\n\n* Drive the cost of rename detection down considerably for merges\n* After the above has been achieved, see if there are other slowness\n factors (which would have previously been overshadowed by rename\n detection costs) which we can then focus on and also optimize.\n* Ensure our rebase testcase that requires little rename detection\n is noticeably faster with merge-ort than with apply-based rebase.\n\nSigned-off-by: Elijah Newren \nAcked-by: Taylor Blau \n---\n diffcore-rename.c | 8 +++++++\n merge-ort.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 65 insertions(+)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 90db9ebd6d..8fe6c9384b 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -465,6 +465,7 @@ void diffcore_rename(struct diff_options *options)\n \tint num_destinations, dst_cnt;\n \tstruct progress *progress = NULL;\n \n+\ttrace2_region_enter(\"diff\", \"setup\", options->repo);\n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n \n@@ -510,14 +511,17 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tregister_rename_src(p);\n \t\t}\n \t}\n+\ttrace2_region_leave(\"diff\", \"setup\", options->repo);\n \tif (rename_dst_nr == 0 || rename_src_nr == 0)\n \t\tgoto cleanup; /* nothing to do */\n \n+\ttrace2_region_enter(\"diff\", \"exact renames\", options->repo);\n \t/*\n \t * We really want to cull the candidates list early\n \t * with cheap tests in order to avoid doing deltas.\n \t */\n \trename_count = find_exact_renames(options);\n+\ttrace2_region_leave(\"diff\", \"exact renames\", options->repo);\n \n \t/* Did we only want exact renames? */\n \tif (minimum_score == MAX_SCORE)\n@@ -545,6 +549,7 @@ void diffcore_rename(struct diff_options *options)\n \t\tbreak;\n \t}\n \n+\ttrace2_region_enter(\"diff\", \"inexact renames\", options->repo);\n \tif (options->show_rename_progress) {\n \t\tprogress = start_delayed_progress(\n \t\t\t\t_(\"Performing inexact rename detection\"),\n@@ -600,11 +605,13 @@ void diffcore_rename(struct diff_options *options)\n \tif (detect_rename == DIFF_DETECT_COPY)\n \t\trename_count += find_renames(mx, dst_cnt, minimum_score, 1);\n \tfree(mx);\n+\ttrace2_region_leave(\"diff\", \"inexact renames\", options->repo);\n \n cleanup:\n \t/* At this point, we have found some renames and copies and they\n \t * are recorded in rename_dst. The original list is still in *q.\n \t */\n+\ttrace2_region_enter(\"diff\", \"write back to queue\", options->repo);\n \tDIFF_QUEUE_CLEAR(&outq);\n \tfor (i = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n@@ -680,5 +687,6 @@ void diffcore_rename(struct diff_options *options)\n \t\tstrintmap_clear(break_idx);\n \t\tFREE_AND_NULL(break_idx);\n \t}\n+\ttrace2_region_leave(\"diff\", \"write back to queue\", options->repo);\n \treturn;\n }\ndiff --git a/merge-ort.c b/merge-ort.c\nindex f04fab96d7..931b91438c 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -752,7 +752,9 @@ static int collect_merge_info(struct merge_options *opt,\n \tinit_tree_desc(t + 1, side1->buffer, side1->size);\n \tinit_tree_desc(t + 2, side2->buffer, side2->size);\n \n+\ttrace2_region_enter(\"merge\", \"traverse_trees\", opt->repo);\n \tret = traverse_trees(NULL, 3, t, &info);\n+\ttrace2_region_leave(\"merge\", \"traverse_trees\", opt->repo);\n \n \treturn ret;\n }\n@@ -2105,9 +2107,12 @@ static void detect_regular_renames(struct merge_options *opt,\n \tdiff_opts.show_rename_progress = opt->show_rename_progress;\n \tdiff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;\n \tdiff_setup_done(&diff_opts);\n+\n+\ttrace2_region_enter(\"diff\", \"diffcore_rename\", opt->repo);\n \tdiff_tree_oid(&merge_base->object.oid, &side->object.oid, \"\",\n \t\t &diff_opts);\n \tdiffcore_std(&diff_opts);\n+\ttrace2_region_leave(\"diff\", \"diffcore_rename\", opt->repo);\n \n \tif (diff_opts.needed_rename_limit > renames->needed_limit)\n \t\trenames->needed_limit = diff_opts.needed_rename_limit;\n@@ -2206,9 +2211,12 @@ static int detect_and_process_renames(struct merge_options *opt,\n \n \tmemset(&combined, 0, sizeof(combined));\n \n+\ttrace2_region_enter(\"merge\", \"regular renames\", opt->repo);\n \tdetect_regular_renames(opt, merge_base, side1, MERGE_SIDE1);\n \tdetect_regular_renames(opt, merge_base, side2, MERGE_SIDE2);\n+\ttrace2_region_leave(\"merge\", \"regular renames\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"directory renames\", opt->repo);\n \tneed_dir_renames =\n \t !opt->priv->call_depth &&\n \t (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_TRUE ||\n@@ -2230,8 +2238,11 @@ static int detect_and_process_renames(struct merge_options *opt,\n \t\t\t\t &renames->dir_renames[1],\n \t\t\t\t &renames->dir_renames[2]);\n \tQSORT(combined.queue, combined.nr, compare_pairs);\n+\ttrace2_region_leave(\"merge\", \"directory renames\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"process renames\", opt->repo);\n \tclean &= process_renames(opt, &combined);\n+\ttrace2_region_leave(\"merge\", \"process renames\", opt->repo);\n \n \t/* Free memory for renames->pairs[] and combined */\n \tfor (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {\n@@ -2913,20 +2924,30 @@ static void process_entries(struct merge_options *opt,\n \t\t\t\t\t\t STRING_LIST_INIT_NODUP,\n \t\t\t\t\t\t NULL, 0 };\n \n+\ttrace2_region_enter(\"merge\", \"process_entries setup\", opt->repo);\n \tif (strmap_empty(&opt->priv->paths)) {\n \t\toidcpy(result_oid, opt->repo->hash_algo->empty_tree);\n \t\treturn;\n \t}\n \n \t/* Hack to pre-allocate plist to the desired size */\n+\ttrace2_region_enter(\"merge\", \"plist grow\", opt->repo);\n \tALLOC_GROW(plist.items, strmap_get_size(&opt->priv->paths), plist.alloc);\n+\ttrace2_region_leave(\"merge\", \"plist grow\", opt->repo);\n \n \t/* Put every entry from paths into plist, then sort */\n+\ttrace2_region_enter(\"merge\", \"plist copy\", opt->repo);\n \tstrmap_for_each_entry(&opt->priv->paths, &iter, e) {\n \t\tstring_list_append(&plist, e->key)->util = e->value;\n \t}\n+\ttrace2_region_leave(\"merge\", \"plist copy\", opt->repo);\n+\n+\ttrace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n \tplist.cmp = string_list_df_name_compare;\n \tstring_list_sort(&plist);\n+\ttrace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n+\n+\ttrace2_region_leave(\"merge\", \"process_entries setup\", opt->repo);\n \n \t/*\n \t * Iterate over the items in reverse order, so we can handle paths\n@@ -2937,6 +2958,7 @@ static void process_entries(struct merge_options *opt,\n \t * (because it allows us to know whether the directory is still in\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 \tfor (entry = &plist.items[plist.nr-1]; entry >= plist.items; --entry) {\n \t\tchar *path = entry->string;\n \t\t/*\n@@ -2955,7 +2977,9 @@ static void process_entries(struct merge_options *opt,\n \t\t\tprocess_entry(opt, path, ci, &dir_metadata);\n \t\t}\n \t}\n+\ttrace2_region_leave(\"merge\", \"processing\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"process_entries cleanup\", opt->repo);\n \tif (dir_metadata.offsets.nr != 1 ||\n \t (uintptr_t)dir_metadata.offsets.items[0].util != 0) {\n \t\tprintf(\"dir_metadata.offsets.nr = %d (should be 1)\\n\",\n@@ -2970,6 +2994,7 @@ static void process_entries(struct merge_options *opt,\n \tstring_list_clear(&plist, 0);\n \tstring_list_clear(&dir_metadata.versions, 0);\n \tstring_list_clear(&dir_metadata.offsets, 0);\n+\ttrace2_region_leave(\"merge\", \"process_entries cleanup\", opt->repo);\n }\n \n /*** Function Grouping: functions related to merge_switch_to_result() ***/\n@@ -3128,12 +3153,15 @@ void merge_switch_to_result(struct merge_options *opt,\n \tif (result->clean >= 0 && update_worktree_and_index) {\n \t\tstruct merge_options_internal *opti = result->priv;\n \n+\t\ttrace2_region_enter(\"merge\", \"checkout\", opt->repo);\n \t\tif (checkout(opt, head, result->tree)) {\n \t\t\t/* failure to function */\n \t\t\tresult->clean = -1;\n \t\t\treturn;\n \t\t}\n+\t\ttrace2_region_leave(\"merge\", \"checkout\", opt->repo);\n \n+\t\ttrace2_region_enter(\"merge\", \"record_conflicted\", opt->repo);\n \t\tif (record_conflicted_index_entries(opt, opt->repo->index,\n \t\t\t\t\t\t &opti->paths,\n \t\t\t\t\t\t &opti->conflicted)) {\n@@ -3141,6 +3169,7 @@ void merge_switch_to_result(struct merge_options *opt,\n \t\t\tresult->clean = -1;\n \t\t\treturn;\n \t\t}\n+\t\ttrace2_region_leave(\"merge\", \"record_conflicted\", opt->repo);\n \t}\n \n \tif (display_update_msgs) {\n@@ -3150,6 +3179,8 @@ void merge_switch_to_result(struct merge_options *opt,\n \t\tstruct string_list olist = STRING_LIST_INIT_NODUP;\n \t\tint i;\n \n+\t\ttrace2_region_enter(\"merge\", \"display messages\", opt->repo);\n+\n \t\t/* Hack to pre-allocate olist to the desired size */\n \t\tALLOC_GROW(olist.items, strmap_get_size(&opti->output),\n \t\t\t olist.alloc);\n@@ -3171,6 +3202,8 @@ void merge_switch_to_result(struct merge_options *opt,\n \t\t/* Also include needed rename limit adjustment now */\n \t\tdiff_warn_rename_limit(\"merge.renamelimit\",\n \t\t\t\t opti->renames.needed_limit, 0);\n+\n+\t\ttrace2_region_leave(\"merge\", \"display messages\", opt->repo);\n \t}\n \n \tmerge_finalize(opt, result);\n@@ -3212,6 +3245,7 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \tint i;\n \n \t/* Sanity checks on opt */\n+\ttrace2_region_enter(\"merge\", \"sanity checks\", opt->repo);\n \tassert(opt->repo);\n \n \tassert(opt->branch1 && opt->branch2);\n@@ -3250,11 +3284,13 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \t\tassert(!opt->priv->toplevel_dir ||\n \t\t 0 == strlen(opt->priv->toplevel_dir));\n \t}\n+\ttrace2_region_leave(\"merge\", \"sanity checks\", opt->repo);\n \n \t/* Default to histogram diff. Actually, just hardcode it...for now. */\n \topt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);\n \n \t/* Initialization of opt->priv, our internal merge data */\n+\ttrace2_region_enter(\"merge\", \"allocate/init\", opt->repo);\n \tif (opt->priv) {\n \t\tclear_or_reinit_internal_opts(opt->priv, 1);\n \t\ttrace2_region_leave(\"merge\", \"allocate/init\", opt->repo);\n@@ -3292,6 +3328,8 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \t * subset of the overall paths that have special output.\n \t */\n \tstrmap_init(&opt->priv->output);\n+\n+\ttrace2_region_leave(\"merge\", \"allocate/init\", opt->repo);\n }\n \n /*** Function Grouping: merge_incore_*() and their internal variants ***/\n@@ -3307,6 +3345,7 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n {\n \tstruct object_id working_tree_oid;\n \n+\ttrace2_region_enter(\"merge\", \"collect_merge_info\", opt->repo);\n \tif (collect_merge_info(opt, merge_base, side1, side2) != 0) {\n \t\t/*\n \t\t * TRANSLATORS: The %s arguments are: 1) tree hash of a merge\n@@ -3319,10 +3358,16 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,\n \t\tresult->clean = -1;\n \t\treturn;\n \t}\n+\ttrace2_region_leave(\"merge\", \"collect_merge_info\", opt->repo);\n \n+\ttrace2_region_enter(\"merge\", \"renames\", opt->repo);\n \tresult->clean = detect_and_process_renames(opt, merge_base,\n \t\t\t\t\t\t side1, side2);\n+\ttrace2_region_leave(\"merge\", \"renames\", opt->repo);\n+\n+\ttrace2_region_enter(\"merge\", \"process_entries\", opt->repo);\n \tprocess_entries(opt, &working_tree_oid);\n+\ttrace2_region_leave(\"merge\", \"process_entries\", opt->repo);\n \n \t/* Set return values */\n \tresult->tree = parse_tree_indirect(&working_tree_oid);\n@@ -3423,9 +3468,15 @@ void merge_incore_nonrecursive(struct merge_options *opt,\n \t\t\t struct tree *side2,\n \t\t\t struct merge_result *result)\n {\n+\ttrace2_region_enter(\"merge\", \"incore_nonrecursive\", opt->repo);\n+\n+\ttrace2_region_enter(\"merge\", \"merge_start\", opt->repo);\n \tassert(opt->ancestor != NULL);\n \tmerge_start(opt, result);\n+\ttrace2_region_leave(\"merge\", \"merge_start\", opt->repo);\n+\n \tmerge_ort_nonrecursive_internal(opt, merge_base, side1, side2, result);\n+\ttrace2_region_leave(\"merge\", \"incore_nonrecursive\", opt->repo);\n }\n \n void merge_incore_recursive(struct merge_options *opt,\n@@ -3434,9 +3485,15 @@ void merge_incore_recursive(struct merge_options *opt,\n \t\t\t struct commit *side2,\n \t\t\t struct merge_result *result)\n {\n+\ttrace2_region_enter(\"merge\", \"incore_recursive\", opt->repo);\n+\n \t/* We set the ancestor label based on the merge_bases */\n \tassert(opt->ancestor == NULL);\n \n+\ttrace2_region_enter(\"merge\", \"merge_start\", opt->repo);\n \tmerge_start(opt, result);\n+\ttrace2_region_leave(\"merge\", \"merge_start\", opt->repo);\n+\n \tmerge_ort_internal(opt, merge_bases, side1, side2, result);\n+\ttrace2_region_leave(\"merge\", \"incore_recursive\", opt->repo);\n }\n-- \n2.30.0.135.g7f7d4a3e17\n\n"},{"id":"415179","messageId":"7e1c184f-4745-530d-8aca-879319786845@gmail.com","threadId":"54966","inReplyTo":"20210124060112.1258291-2-newren@gmail.com","subject":"Re: [PATCH v4 1/3] merge-ort: fix massive leak","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-01-24T19:11:54Z","receivedAt":"2021-01-24T19:13:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/24/2021 1:01 AM, Elijah Newren wrote:\n> When a series of merges was performed (such as for a rebase or series of\n> cherry-picks), only the data structures allocated by the final merge\n> operation were being freed. The problem was that while picking out\n> pieces of merge-ort to upstream, I previously misread a certain section\n> of merge_start() and assumed it was associated with a later\n> optimization. Include that section now, which ensures that if there was\n> a previous merge operation, that we clear out result->priv and then\n> re-use it for opt->priv, and otherwise we allocate opt->priv.\n> \n> Signed-off-by: Elijah Newren \n> ---\n> merge-ort.c | 17 +++++++++++++++++\n> 1 file changed, 17 insertions(+)\n> \n> diff --git a/merge-ort.c b/merge-ort.c\n> index 05c6b2e0dc..b5845ff6e9 100644\n> --- a/merge-ort.c\n> +++ b/merge-ort.c\n> @@ -3227,11 +3227,28 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n> \tassert(opt->obuf.len == 0);\n> \n> \tassert(opt->priv == NULL);\n> +\tif (result->priv) {\n> +\t\topt->priv = result->priv;\n> +\t\tresult->priv = NULL;\n> +\t\t/*\n> +\t\t * opt->priv non-NULL means we had results from a previous\n> +\t\t * run; do a few sanity checks that user didn't mess with\n> +\t\t * it in an obvious fashion.\n> +\t\t */\n> +\t\tassert(opt->priv->call_depth == 0);\n> +\t\tassert(!opt->priv->toplevel_dir ||\n> +\t\t 0 == strlen(opt->priv->toplevel_dir));\n> +\t}\n\nSo instead of simply leaking result->priv, we re-use the\ndata for the next round.\n\n> \n> \t/* Default to histogram diff. Actually, just hardcode it...for now. */\n> \topt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);\n> \n> \t/* Initialization of opt->priv, our internal merge data */\n> +\tif (opt->priv) {\n> +\t\tclear_or_reinit_internal_opts(opt->priv, 1);\n> +\t\ttrace2_region_leave(\"merge\", \"allocate/init\", opt->repo);\n> +\t\treturn;\n> +\t}\n> \topt->priv = xcalloc(1, sizeof(*opt->priv));\n\nand here you reset the data instead of reallocating it. OK.\n\n-Stolee\n\n"}]}