All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH 0/5] Optimization batch 12: miscellaneous unthemed stuff
@ 2021-05-27  8:37 Elijah Newren via GitGitGadget
  2021-05-27  8:37 ` [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
                   ` (5 more replies)
  0 siblings, 6 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-05-27  8:37 UTC (permalink / raw)
  To: git; +Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, Elijah Newren

This series depends on en/ort-perf-batch-11 textually, but is semantically
independent of it.

This short series has a few optimizations, but only one of which affects the
testcases of interest (namely, reducing our time spent on sorting an array).
It also fixes a few comments.

For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28), the
changes in just this series improves the performance as follows:

                     Before Series           After Series
no-renames:        5.622 s ±  0.059 s     5.235 s ±  0.042 s
mega-renames:     10.127 s ±  0.073 s     9.419 s ±  0.107 s
just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms


As a reminder, before any merge-ort/diffcore-rename performance work, the
performance results we started with were:

no-renames-am:      6.940 s ±  0.485 s
no-renames:        18.912 s ±  0.174 s
mega-renames:    5964.031 s ± 10.459 s
just-one-mega:    149.583 s ±  0.751 s


Elijah Newren (5):
  merge-ort: replace string_list_df_name_compare with faster alternative
  diffcore-rename: avoid unnecessary strdup'ing in break_idx
  diffcore-rename: enable limiting rename detection to relevant
    destinations
  Fix various issues found in comments
  merge-ort: miscellaneous touch-ups

 diffcore-rename.c                   | 52 ++++++++++++++++---
 diffcore.h                          |  2 +
 merge-ort.c                         | 78 +++++++++++++++++++----------
 t/t6423-merge-rename-directories.sh |  2 +-
 4 files changed, 99 insertions(+), 35 deletions(-)


base-commit: 76e253793c9a1d7fdd1836d5e4db26dabd3d713a
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-962%2Fnewren%2Fort-perf-batch-12-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-962/newren/ort-perf-batch-12-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/962
-- 
gitgitgadget

^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative
  2021-05-27  8:37 [PATCH 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
@ 2021-05-27  8:37 ` Elijah Newren via GitGitGadget
  2021-05-27 21:00   ` René Scharfe
  2021-05-28  1:32   ` Taylor Blau
  2021-05-27  8:37 ` [PATCH 2/5] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
                   ` (4 subsequent siblings)
  5 siblings, 2 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-05-27  8:37 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, Elijah Newren, Elijah Newren

From: Elijah Newren <newren@gmail.com>

Gathering accumulated times from trace2 output on the mega-renames
testcase, I saw the following timings (where I'm only showing a few
lines to highlight the portions of interest):

    10.120 : label:incore_nonrecursive
        4.462 : ..label:process_entries
           3.143 : ....label:process_entries setup
              2.988 : ......label:plist special sort
           1.305 : ....label:processing
        2.604 : ..label:collect_merge_info
        2.018 : ..label:merge_start
        1.018 : ..label:renames

In the above output, note that the 4.462 seconds for process_entries was
split as 3.143 seconds for "process_entries setup" and 1.305 seconds for
"processing" (and a little time for other stuff removed from the
highlight).  Most of the "process_entries setup" time was spent on
"plist special sort" which corresponds to the following code:

    trace2_region_enter("merge", "plist special sort", opt->repo);
    plist.cmp = string_list_df_name_compare;
    string_list_sort(&plist);
    trace2_region_leave("merge", "plist special sort", opt->repo);

In other words, in a merge strategy that would be invoked by passing
"-sort" to either rebase or merge, sorting an array takes more time than
anything else.  Serves me right for naming my merge strategy this way.

Rewrite the comparison function and remove as many levels of indirection
as possible (e.g. the old code had
    cmp_items() ->
      string_list_df_name_compare() ->
        df_name_compare()
now we just have sort_dirs_next_to_their_children()), and tweak it to be
as optimized as possible for our specific case.  These changes reduced
the time spent in "plist special sort" by ~25% in the mega-renames case.

For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:

                            Before                  After
    no-renames:        5.622 s ±  0.059 s     5.235 s ±  0.042 s
    mega-renames:     10.127 s ±  0.073 s     9.419 s ±  0.107 s
    just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-ort.c | 64 ++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 41 insertions(+), 23 deletions(-)

diff --git a/merge-ort.c b/merge-ort.c
index 142d44d74d63..367aec4b7def 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2746,31 +2746,50 @@ static int detect_and_process_renames(struct merge_options *opt,
 
 /*** Function Grouping: functions related to process_entries() ***/
 
-static int string_list_df_name_compare(const char *one, const char *two)
+static int sort_dirs_next_to_their_children(const void *a, const void *b)
 {
-	int onelen = strlen(one);
-	int twolen = strlen(two);
 	/*
-	 * Here we only care that entries for D/F conflicts are
-	 * adjacent, in particular with the file of the D/F conflict
-	 * appearing before files below the corresponding directory.
-	 * The order of the rest of the list is irrelevant for us.
+	 * Here we only care that entries for directories appear adjacent
+	 * to and before files underneath the directory.  In other words,
+	 * we do not want the natural sorting of
+	 *     foo
+	 *     foo.txt
+	 *     foo/bar
+	 * Instead, we want "foo" to sort as though it were "foo/", so that
+	 * we instead get
+	 *     foo.txt
+	 *     foo
+	 *     foo/bar
+	 * To achieve this, we basically implement our own strcmp, except that
+	 * if we get to the end of either string instead of comparing NUL to
+	 * another character, we compare '/' to it.
 	 *
-	 * To achieve this, we sort with df_name_compare and provide
-	 * the mode S_IFDIR so that D/F conflicts will sort correctly.
-	 * We use the mode S_IFDIR for everything else for simplicity,
-	 * since in other cases any changes in their order due to
-	 * sorting cause no problems for us.
+	 * The reason to not use df_name_compare directly was that it was
+	 * just too expensive, so I had to reimplement it.
 	 */
-	int cmp = df_name_compare(one, onelen, S_IFDIR,
-				  two, twolen, S_IFDIR);
-	/*
-	 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
-	 * that 'foo' comes before 'foo/bar'.
-	 */
-	if (cmp)
-		return cmp;
-	return onelen - twolen;
+	const char *one = ((struct string_list_item *)a)->string;
+	const char *two = ((struct string_list_item *)b)->string;
+	unsigned char c1, c2;
+
+	while (*one && (*one == *two)) {
+		one++;
+		two++;
+	}
+
+	c1 = *one;
+	if (!c1)
+		c1 = '/';
+
+	c2 = *two;
+	if (!c2)
+		c2 = '/';
+
+	if (c1 == c2) {
+		/* Getting here means one is a leading directory of the other */
+		return (*one) ? 1 : -1;
+	}
+	else
+		return c1-c2;
 }
 
 static int read_oid_strbuf(struct merge_options *opt,
@@ -3481,8 +3500,7 @@ static void process_entries(struct merge_options *opt,
 	trace2_region_leave("merge", "plist copy", opt->repo);
 
 	trace2_region_enter("merge", "plist special sort", opt->repo);
-	plist.cmp = string_list_df_name_compare;
-	string_list_sort(&plist);
+	QSORT(plist.items, plist.nr, sort_dirs_next_to_their_children);
 	trace2_region_leave("merge", "plist special sort", opt->repo);
 
 	trace2_region_leave("merge", "process_entries setup", opt->repo);
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH 2/5] diffcore-rename: avoid unnecessary strdup'ing in break_idx
  2021-05-27  8:37 [PATCH 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
  2021-05-27  8:37 ` [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
@ 2021-05-27  8:37 ` Elijah Newren via GitGitGadget
  2021-05-27  8:37 ` [PATCH 3/5] diffcore-rename: enable limiting rename detection to relevant destinations Elijah Newren via GitGitGadget
                   ` (3 subsequent siblings)
  5 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-05-27  8:37 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, Elijah Newren, Elijah Newren

From: Elijah Newren <newren@gmail.com>

The keys of break_idx are strings from the diff_filepairs of
diff_queued_diff.  break_idx is only used in location_rename_dst(), and
that usage is always before any free'ing of the pairs (and thus the
strings in the pairs).  As such, there is no need to strdup these keys;
we can just reuse the existing strings as-is.

The merge logic doesn't make use of break detection, so this does not
affect the performance of any of my testcases.  It was just a minor
unrelated optimization noted in passing while looking at the code.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 diffcore-rename.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 3375e24659ea..e333a6d64791 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -54,7 +54,7 @@ static void register_rename_src(struct diff_filepair *p)
 	if (p->broken_pair) {
 		if (!break_idx) {
 			break_idx = xmalloc(sizeof(*break_idx));
-			strintmap_init(break_idx, -1);
+			strintmap_init_with_options(break_idx, -1, NULL, 0);
 		}
 		strintmap_set(break_idx, p->one->path, rename_dst_nr);
 	}
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH 3/5] diffcore-rename: enable limiting rename detection to relevant destinations
  2021-05-27  8:37 [PATCH 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
  2021-05-27  8:37 ` [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
  2021-05-27  8:37 ` [PATCH 2/5] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
@ 2021-05-27  8:37 ` Elijah Newren via GitGitGadget
  2021-05-27  8:37 ` [PATCH 4/5] Fix various issues found in comments Elijah Newren via GitGitGadget
                   ` (2 subsequent siblings)
  5 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-05-27  8:37 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, Elijah Newren, Elijah Newren

From: Elijah Newren <newren@gmail.com>

Our former optimizations focused on limiting rename detection to a
pre-specified set of relevant sources.  This was because the merge logic
only had a way of knowing which sources were relevant.  However, other
callers of rename detection might benefit from being able to limit
rename detection to a known set of relevant destinations.  In
particular, a properly implemented `git log --follow` might benefit from
such an ability.

Since the code to implement such limiting is very similar to what we've
already done, just implement it now even though we do not yet have any
callers making use of this ability.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 diffcore-rename.c | 48 +++++++++++++++++++++++++++++++++++++++++------
 diffcore.h        |  2 ++
 merge-ort.c       |  1 +
 3 files changed, 45 insertions(+), 6 deletions(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index e333a6d64791..8ff83a9f3b99 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -372,6 +372,7 @@ struct dir_rename_info {
 	struct strmap dir_rename_guess;
 	struct strmap *dir_rename_count;
 	struct strintmap *relevant_source_dirs;
+	struct strset *relevant_destination_dirs;
 	unsigned setup;
 };
 
@@ -491,8 +492,11 @@ static void update_dir_rename_counts(struct dir_rename_info *info,
 		    !strintmap_contains(info->relevant_source_dirs, old_dir))
 			break;
 
-		/* Get new_dir */
+		/* Get new_dir, skip if its directory isn't relevant. */
 		dirname_munge(new_dir);
+		if (info->relevant_destination_dirs &&
+		    !strset_contains(info->relevant_destination_dirs, new_dir))
+			break;
 
 		/*
 		 * When renaming
@@ -567,6 +571,7 @@ static void update_dir_rename_counts(struct dir_rename_info *info,
 
 static void initialize_dir_rename_info(struct dir_rename_info *info,
 				       struct strintmap *relevant_sources,
+				       struct strset *relevant_destinations,
 				       struct strintmap *dirs_removed,
 				       struct strmap *dir_rename_count,
 				       struct strmap *cached_pairs)
@@ -575,7 +580,7 @@ static void initialize_dir_rename_info(struct dir_rename_info *info,
 	struct strmap_entry *entry;
 	int i;
 
-	if (!dirs_removed && !relevant_sources) {
+	if (!dirs_removed && !relevant_sources && !relevant_destinations) {
 		info->setup = 0;
 		return;
 	}
@@ -589,6 +594,18 @@ static void initialize_dir_rename_info(struct dir_rename_info *info,
 	strintmap_init_with_options(&info->idx_map, -1, NULL, 0);
 	strmap_init_with_options(&info->dir_rename_guess, NULL, 0);
 
+	/* Setup info->relevant_destination_dirs */
+	info->relevant_destination_dirs = NULL;
+	if (relevant_destinations) {
+		info->relevant_destination_dirs = xmalloc(sizeof(struct strset));
+		strset_init(info->relevant_destination_dirs);
+		strset_for_each_entry(relevant_destinations, &iter, entry) {
+			char *dirname = get_dirname(entry->key);
+			strset_add(info->relevant_destination_dirs, dirname);
+			free(dirname);
+		}
+	}
+
 	/* Setup info->relevant_source_dirs */
 	info->relevant_source_dirs = NULL;
 	if (dirs_removed || !relevant_sources) {
@@ -700,6 +717,12 @@ static void cleanup_dir_rename_info(struct dir_rename_info *info,
 		FREE_AND_NULL(info->relevant_source_dirs);
 	}
 
+	/* relevant_destination_dirs */
+	if (info->relevant_destination_dirs) {
+		strset_clear(info->relevant_destination_dirs);
+		FREE_AND_NULL(info->relevant_destination_dirs);
+	}
+
 	/* dir_rename_count */
 	if (!keep_dir_rename_count) {
 		partial_clear_dir_rename_count(info->dir_rename_count);
@@ -827,6 +850,7 @@ static int find_basename_matches(struct diff_options *options,
 				 int minimum_score,
 				 struct dir_rename_info *info,
 				 struct strintmap *relevant_sources,
+				 struct strset *relevant_destinations,
 				 struct strintmap *dirs_removed)
 {
 	/*
@@ -949,9 +973,15 @@ static int find_basename_matches(struct diff_options *options,
 			if (rename_dst[dst_index].is_rename)
 				continue; /* already used previously */
 
-			/* Estimate the similarity */
 			one = rename_src[src_index].p->one;
 			two = rename_dst[dst_index].p->two;
+
+			/* Skip irrelevant destinations */
+			if (relevant_destinations &&
+			    !strset_contains(relevant_destinations, two->path))
+				continue;
+
+			/* Estimate the similarity */
 			score = estimate_similarity(options->repo, one, two,
 						    minimum_score, skip_unmodified);
 
@@ -1258,6 +1288,7 @@ static void handle_early_known_dir_renames(struct dir_rename_info *info,
 
 void diffcore_rename_extended(struct diff_options *options,
 			      struct strintmap *relevant_sources,
+			      struct strset *relevant_destinations,
 			      struct strintmap *dirs_removed,
 			      struct strmap *dir_rename_count,
 			      struct strmap *cached_pairs)
@@ -1376,8 +1407,8 @@ void diffcore_rename_extended(struct diff_options *options,
 		/* Preparation for basename-driven matching. */
 		trace2_region_enter("diff", "dir rename setup", options->repo);
 		initialize_dir_rename_info(&info, relevant_sources,
-					   dirs_removed, dir_rename_count,
-					   cached_pairs);
+					   relevant_destinations, dirs_removed,
+					   dir_rename_count, cached_pairs);
 		trace2_region_leave("diff", "dir rename setup", options->repo);
 
 		/* Utilize file basenames to quickly find renames. */
@@ -1386,6 +1417,7 @@ void diffcore_rename_extended(struct diff_options *options,
 						      min_basename_score,
 						      &info,
 						      relevant_sources,
+						      relevant_destinations,
 						      dirs_removed);
 		trace2_region_leave("diff", "basename matches", options->repo);
 
@@ -1441,6 +1473,10 @@ void diffcore_rename_extended(struct diff_options *options,
 		if (rename_dst[i].is_rename)
 			continue; /* exact or basename match already handled */
 
+		if (relevant_destinations &&
+		    !strset_contains(relevant_destinations, two->path))
+			continue;
+
 		m = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];
 		for (j = 0; j < NUM_CANDIDATE_PER_DST; j++)
 			m[j].dst = -1;
@@ -1574,5 +1610,5 @@ void diffcore_rename_extended(struct diff_options *options,
 
 void diffcore_rename(struct diff_options *options)
 {
-	diffcore_rename_extended(options, NULL, NULL, NULL, NULL);
+	diffcore_rename_extended(options, NULL, NULL, NULL, NULL, NULL);
 }
diff --git a/diffcore.h b/diffcore.h
index 533b30e21e7f..435c7094f403 100644
--- a/diffcore.h
+++ b/diffcore.h
@@ -10,6 +10,7 @@ struct diff_options;
 struct repository;
 struct strintmap;
 struct strmap;
+struct strset;
 struct userdiff_driver;
 
 /* This header file is internal between diff.c and its diff transformers
@@ -180,6 +181,7 @@ void diffcore_break(struct repository *, int);
 void diffcore_rename(struct diff_options *);
 void diffcore_rename_extended(struct diff_options *options,
 			      struct strintmap *relevant_sources,
+			      struct strset *relevant_destinations,
 			      struct strintmap *dirs_removed,
 			      struct strmap *dir_rename_count,
 			      struct strmap *cached_pairs);
diff --git a/merge-ort.c b/merge-ort.c
index 367aec4b7def..db16cbc3bd33 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2568,6 +2568,7 @@ static void detect_regular_renames(struct merge_options *opt,
 	trace2_region_enter("diff", "diffcore_rename", opt->repo);
 	diffcore_rename_extended(&diff_opts,
 				 &renames->relevant_sources[side_index],
+				 NULL,
 				 &renames->dirs_removed[side_index],
 				 &renames->dir_rename_count[side_index],
 				 &renames->cached_pairs[side_index]);
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH 4/5] Fix various issues found in comments
  2021-05-27  8:37 [PATCH 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
                   ` (2 preceding siblings ...)
  2021-05-27  8:37 ` [PATCH 3/5] diffcore-rename: enable limiting rename detection to relevant destinations Elijah Newren via GitGitGadget
@ 2021-05-27  8:37 ` Elijah Newren via GitGitGadget
  2021-05-27  8:37 ` [PATCH 5/5] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget
  2021-06-01 14:58 ` [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
  5 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-05-27  8:37 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, Elijah Newren, Elijah Newren

From: Elijah Newren <newren@gmail.com>

A random hodge-podge of incorrect or out-of-date comments that I found:

  * t6423 had a comment that has referred to the wrong test for years;
    fix it to refer to the right one.
  * diffcore-rename had a FIXME comment meant to remind myself to
    investigate if I could make another code change.  I later
    investigated and removed the FIXME, but while cherry-picking the
    patch to submit upstream I missed the later update.  Remove the
    comment now.
  * merge-ort had the early part of a comment for a function; I had
    meant to include the more involved description when I updated the
    function.  Update the comment now.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 diffcore-rename.c                   | 2 +-
 merge-ort.c                         | 8 +++++---
 t/t6423-merge-rename-directories.sh | 2 +-
 3 files changed, 7 insertions(+), 5 deletions(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 8ff83a9f3b99..c9f7d59cf62b 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -1579,7 +1579,7 @@ void diffcore_rename_extended(struct diff_options *options,
 			/* all the usual ones need to be kept */
 			diff_q(&outq, p);
 		else
-			/* no need to keep unmodified pairs; FIXME: remove earlier? */
+			/* no need to keep unmodified pairs */
 			pair_to_free = p;
 
 		if (pair_to_free)
diff --git a/merge-ort.c b/merge-ort.c
index db16cbc3bd33..6cb103c8e855 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2533,7 +2533,7 @@ static int compare_pairs(const void *a_, const void *b_)
 	return strcmp(a->one->path, b->one->path);
 }
 
-/* Call diffcore_rename() to compute which files have changed on given side */
+/* Call diffcore_rename() to update deleted/added pairs into rename pairs */
 static void detect_regular_renames(struct merge_options *opt,
 				   unsigned side_index)
 {
@@ -2587,8 +2587,10 @@ static void detect_regular_renames(struct merge_options *opt,
 }
 
 /*
- * Get information of all renames which occurred in 'side_pairs', discarding
- * non-renames.
+ * Get information of all renames which occurred in 'side_pairs', making use
+ * of any implicit directory renames in side_dir_renames (also making use of
+ * implicit directory renames rename_exclusions as needed by
+ * check_for_directory_rename()).  Add all (updated) renames into result.
  */
 static int collect_renames(struct merge_options *opt,
 			   struct diff_queue_struct *result,
diff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh
index be84d22419d9..e834b7e6efe0 100755
--- a/t/t6423-merge-rename-directories.sh
+++ b/t/t6423-merge-rename-directories.sh
@@ -454,7 +454,7 @@ test_expect_success '1f: Split a directory into two other directories' '
 #   the directory renamed, but the files within it. (see 1b)
 #
 #   If renames split a directory into two or more others, the directory
-#   with the most renames, "wins" (see 1c).  However, see the testcases
+#   with the most renames, "wins" (see 1f).  However, see the testcases
 #   in section 2, plus testcases 3a and 4a.
 ###########################################################################
 
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH 5/5] merge-ort: miscellaneous touch-ups
  2021-05-27  8:37 [PATCH 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
                   ` (3 preceding siblings ...)
  2021-05-27  8:37 ` [PATCH 4/5] Fix various issues found in comments Elijah Newren via GitGitGadget
@ 2021-05-27  8:37 ` Elijah Newren via GitGitGadget
  2021-06-01 14:58 ` [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
  5 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-05-27  8:37 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, Elijah Newren, Elijah Newren

From: Elijah Newren <newren@gmail.com>

Add some notes in the code about invariants with match_mask when adding
pairs.  Also add a comment that seems to have been left out in my work
of pushing these changes upstream.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-ort.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/merge-ort.c b/merge-ort.c
index 6cb103c8e855..e174a8734a41 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -765,6 +765,7 @@ static void add_pair(struct merge_options *opt,
 	int names_idx = is_add ? side : 0;
 
 	if (is_add) {
+		assert(match_mask == 0 || match_mask == 6);
 		if (strset_contains(&renames->cached_target_names[side],
 				    pathname))
 			return;
@@ -772,6 +773,8 @@ static void add_pair(struct merge_options *opt,
 		unsigned content_relevant = (match_mask == 0);
 		unsigned location_relevant = (dir_rename_mask == 0x07);
 
+		assert(match_mask == 0 || match_mask == 3 || match_mask == 5);
+
 		/*
 		 * If pathname is found in cached_irrelevant[side] due to
 		 * previous pick but for this commit content is relevant,
@@ -3470,6 +3473,8 @@ static void process_entry(struct merge_options *opt,
 	 */
 	if (!ci->merged.clean)
 		strmap_put(&opt->priv->conflicted, path, ci);
+
+	/* Record metadata for ci->merged in dir_metadata */
 	record_entry_for_tree(dir_metadata, path, &ci->merged);
 }
 
-- 
gitgitgadget

^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative
  2021-05-27  8:37 ` [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
@ 2021-05-27 21:00   ` René Scharfe
  2021-05-27 22:47     ` Elijah Newren
  2021-05-28  1:32   ` Taylor Blau
  1 sibling, 1 reply; 39+ messages in thread
From: René Scharfe @ 2021-05-27 21:00 UTC (permalink / raw)
  To: Elijah Newren via GitGitGadget, git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, Elijah Newren

Am 27.05.21 um 10:37 schrieb Elijah Newren via GitGitGadget:
> From: Elijah Newren <newren@gmail.com>
>
> Gathering accumulated times from trace2 output on the mega-renames
> testcase, I saw the following timings (where I'm only showing a few
> lines to highlight the portions of interest):
>
>     10.120 : label:incore_nonrecursive
>         4.462 : ..label:process_entries
>            3.143 : ....label:process_entries setup
>               2.988 : ......label:plist special sort
>            1.305 : ....label:processing
>         2.604 : ..label:collect_merge_info
>         2.018 : ..label:merge_start
>         1.018 : ..label:renames
>
> In the above output, note that the 4.462 seconds for process_entries was
> split as 3.143 seconds for "process_entries setup" and 1.305 seconds for
> "processing" (and a little time for other stuff removed from the
> highlight).  Most of the "process_entries setup" time was spent on
> "plist special sort" which corresponds to the following code:
>
>     trace2_region_enter("merge", "plist special sort", opt->repo);
>     plist.cmp = string_list_df_name_compare;
>     string_list_sort(&plist);
>     trace2_region_leave("merge", "plist special sort", opt->repo);
>
> In other words, in a merge strategy that would be invoked by passing
> "-sort" to either rebase or merge, sorting an array takes more time than
> anything else.  Serves me right for naming my merge strategy this way.
>
> Rewrite the comparison function and remove as many levels of indirection
> as possible (e.g. the old code had
>     cmp_items() ->
>       string_list_df_name_compare() ->
>         df_name_compare()
> now we just have sort_dirs_next_to_their_children()), and tweak it to be
> as optimized as possible for our specific case.  These changes reduced
> the time spent in "plist special sort" by ~25% in the mega-renames case.
>
> For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
> performance work; instrument with trace2_region_* calls", 2020-10-28),
> this change improves the performance as follows:
>
>                             Before                  After
>     no-renames:        5.622 s ±  0.059 s     5.235 s ±  0.042 s
>     mega-renames:     10.127 s ±  0.073 s     9.419 s ±  0.107 s
>     just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms

Interesting.

>
> Signed-off-by: Elijah Newren <newren@gmail.com>
> ---
>  merge-ort.c | 64 ++++++++++++++++++++++++++++++++++-------------------
>  1 file changed, 41 insertions(+), 23 deletions(-)
>
> diff --git a/merge-ort.c b/merge-ort.c
> index 142d44d74d63..367aec4b7def 100644
> --- a/merge-ort.c
> +++ b/merge-ort.c
> @@ -2746,31 +2746,50 @@ static int detect_and_process_renames(struct merge_options *opt,
>
>  /*** Function Grouping: functions related to process_entries() ***/
>
> -static int string_list_df_name_compare(const char *one, const char *two)
> +static int sort_dirs_next_to_their_children(const void *a, const void *b)
>  {
> -	int onelen = strlen(one);
> -	int twolen = strlen(two);

The old code scans both strings fully, while the new one stops when it
reaches a difference and doesn't look at any further characters.  How
much does that contribute to the speedup?  (I suspect a lot.)

>  	/*
> -	 * Here we only care that entries for D/F conflicts are
> -	 * adjacent, in particular with the file of the D/F conflict
> -	 * appearing before files below the corresponding directory.
> -	 * The order of the rest of the list is irrelevant for us.
> +	 * Here we only care that entries for directories appear adjacent
> +	 * to and before files underneath the directory.  In other words,
> +	 * we do not want the natural sorting of
> +	 *     foo
> +	 *     foo.txt
> +	 *     foo/bar
> +	 * Instead, we want "foo" to sort as though it were "foo/", so that
> +	 * we instead get
> +	 *     foo.txt
> +	 *     foo
> +	 *     foo/bar
> +	 * To achieve this, we basically implement our own strcmp, except that
> +	 * if we get to the end of either string instead of comparing NUL to
> +	 * another character, we compare '/' to it.
>  	 *
> -	 * To achieve this, we sort with df_name_compare and provide
> -	 * the mode S_IFDIR so that D/F conflicts will sort correctly.
> -	 * We use the mode S_IFDIR for everything else for simplicity,
> -	 * since in other cases any changes in their order due to
> -	 * sorting cause no problems for us.
> +	 * The reason to not use df_name_compare directly was that it was
> +	 * just too expensive, so I had to reimplement it.
>  	 */
> -	int cmp = df_name_compare(one, onelen, S_IFDIR,
> -				  two, twolen, S_IFDIR);
> -	/*
> -	 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
> -	 * that 'foo' comes before 'foo/bar'.
> -	 */
> -	if (cmp)
> -		return cmp;
> -	return onelen - twolen;
> +	const char *one = ((struct string_list_item *)a)->string;
> +	const char *two = ((struct string_list_item *)b)->string;

Casting away const, hmm. :-/  Harmless because no actual write is
attempted, but still looks needlessly scary to me.

> +	unsigned char c1, c2;
> +
> +	while (*one && (*one == *two)) {
> +		one++;
> +		two++;
> +	}
> +
> +	c1 = *one;
> +	if (!c1)
> +		c1 = '/';
> +
> +	c2 = *two;
> +	if (!c2)
> +		c2 = '/';
> +
> +	if (c1 == c2) {
> +		/* Getting here means one is a leading directory of the other */
> +		return (*one) ? 1 : -1;
> +	}
> +	else
> +		return c1-c2;
>  }
>
>  static int read_oid_strbuf(struct merge_options *opt,
> @@ -3481,8 +3500,7 @@ static void process_entries(struct merge_options *opt,
>  	trace2_region_leave("merge", "plist copy", opt->repo);
>
>  	trace2_region_enter("merge", "plist special sort", opt->repo);
> -	plist.cmp = string_list_df_name_compare;
> -	string_list_sort(&plist);
> +	QSORT(plist.items, plist.nr, sort_dirs_next_to_their_children);

How much does the direct use of QSORT instead of string_list_sort()
contribute to the speedup?  (I suspect only a bit.)

>  	trace2_region_leave("merge", "plist special sort", opt->repo);
>
>  	trace2_region_leave("merge", "process_entries setup", opt->repo);
>


^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative
  2021-05-27 21:00   ` René Scharfe
@ 2021-05-27 22:47     ` Elijah Newren
  2021-05-28 16:12       ` René Scharfe
  0 siblings, 1 reply; 39+ messages in thread
From: Elijah Newren @ 2021-05-27 22:47 UTC (permalink / raw)
  To: René Scharfe
  Cc: Elijah Newren via GitGitGadget, Git Mailing List, Derrick Stolee,
	Jonathan Tan, Taylor Blau

On Thu, May 27, 2021 at 2:00 PM René Scharfe <l.s.r@web.de> wrote:
>
> Am 27.05.21 um 10:37 schrieb Elijah Newren via GitGitGadget:
> > From: Elijah Newren <newren@gmail.com>
> >
> > Gathering accumulated times from trace2 output on the mega-renames
> > testcase, I saw the following timings (where I'm only showing a few
> > lines to highlight the portions of interest):
> >
> >     10.120 : label:incore_nonrecursive
> >         4.462 : ..label:process_entries
> >            3.143 : ....label:process_entries setup
> >               2.988 : ......label:plist special sort
> >            1.305 : ....label:processing
> >         2.604 : ..label:collect_merge_info
> >         2.018 : ..label:merge_start
> >         1.018 : ..label:renames
> >
> > In the above output, note that the 4.462 seconds for process_entries was
> > split as 3.143 seconds for "process_entries setup" and 1.305 seconds for
> > "processing" (and a little time for other stuff removed from the
> > highlight).  Most of the "process_entries setup" time was spent on
> > "plist special sort" which corresponds to the following code:
> >
> >     trace2_region_enter("merge", "plist special sort", opt->repo);
> >     plist.cmp = string_list_df_name_compare;
> >     string_list_sort(&plist);
> >     trace2_region_leave("merge", "plist special sort", opt->repo);
> >
> > In other words, in a merge strategy that would be invoked by passing
> > "-sort" to either rebase or merge, sorting an array takes more time than
> > anything else.  Serves me right for naming my merge strategy this way.
> >
> > Rewrite the comparison function and remove as many levels of indirection
> > as possible (e.g. the old code had
> >     cmp_items() ->
> >       string_list_df_name_compare() ->
> >         df_name_compare()
> > now we just have sort_dirs_next_to_their_children()), and tweak it to be
> > as optimized as possible for our specific case.  These changes reduced
> > the time spent in "plist special sort" by ~25% in the mega-renames case.
> >
> > For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
> > performance work; instrument with trace2_region_* calls", 2020-10-28),
> > this change improves the performance as follows:
> >
> >                             Before                  After
> >     no-renames:        5.622 s ±  0.059 s     5.235 s ±  0.042 s
> >     mega-renames:     10.127 s ±  0.073 s     9.419 s ±  0.107 s
> >     just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms
>
> Interesting.
>
> >
> > Signed-off-by: Elijah Newren <newren@gmail.com>
> > ---
> >  merge-ort.c | 64 ++++++++++++++++++++++++++++++++++-------------------
> >  1 file changed, 41 insertions(+), 23 deletions(-)
> >
> > diff --git a/merge-ort.c b/merge-ort.c
> > index 142d44d74d63..367aec4b7def 100644
> > --- a/merge-ort.c
> > +++ b/merge-ort.c
> > @@ -2746,31 +2746,50 @@ static int detect_and_process_renames(struct merge_options *opt,
> >
> >  /*** Function Grouping: functions related to process_entries() ***/
> >
> > -static int string_list_df_name_compare(const char *one, const char *two)
> > +static int sort_dirs_next_to_their_children(const void *a, const void *b)
> >  {
> > -     int onelen = strlen(one);
> > -     int twolen = strlen(two);
>
> The old code scans both strings fully, while the new one stops when it
> reaches a difference and doesn't look at any further characters.  How
> much does that contribute to the speedup?  (I suspect a lot.)

Oh, indeed, good catch.  It appears to be responsible for essentially all of it.

> >       /*
> > -      * Here we only care that entries for D/F conflicts are
> > -      * adjacent, in particular with the file of the D/F conflict
> > -      * appearing before files below the corresponding directory.
> > -      * The order of the rest of the list is irrelevant for us.
> > +      * Here we only care that entries for directories appear adjacent
> > +      * to and before files underneath the directory.  In other words,
> > +      * we do not want the natural sorting of
> > +      *     foo
> > +      *     foo.txt
> > +      *     foo/bar
> > +      * Instead, we want "foo" to sort as though it were "foo/", so that
> > +      * we instead get
> > +      *     foo.txt
> > +      *     foo
> > +      *     foo/bar
> > +      * To achieve this, we basically implement our own strcmp, except that
> > +      * if we get to the end of either string instead of comparing NUL to
> > +      * another character, we compare '/' to it.
> >        *
> > -      * To achieve this, we sort with df_name_compare and provide
> > -      * the mode S_IFDIR so that D/F conflicts will sort correctly.
> > -      * We use the mode S_IFDIR for everything else for simplicity,
> > -      * since in other cases any changes in their order due to
> > -      * sorting cause no problems for us.
> > +      * The reason to not use df_name_compare directly was that it was
> > +      * just too expensive, so I had to reimplement it.
> >        */
> > -     int cmp = df_name_compare(one, onelen, S_IFDIR,
> > -                               two, twolen, S_IFDIR);
> > -     /*
> > -      * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
> > -      * that 'foo' comes before 'foo/bar'.
> > -      */
> > -     if (cmp)
> > -             return cmp;
> > -     return onelen - twolen;
> > +     const char *one = ((struct string_list_item *)a)->string;
> > +     const char *two = ((struct string_list_item *)b)->string;
>
> Casting away const, hmm. :-/  Harmless because no actual write is
> attempted, but still looks needlessly scary to me.

Right, that should have been
+     const char *one = ((const struct string_list_item *)a)->string;
+     const char *two = ((const struct string_list_item *)b)->string;
but since I was just assigning to a const char * on those lines, I'm
not sure why it'd qualify as scary.  Regardless, I'm happy to put
these consts back in.

> > +     unsigned char c1, c2;
> > +
> > +     while (*one && (*one == *two)) {
> > +             one++;
> > +             two++;
> > +     }
> > +
> > +     c1 = *one;
> > +     if (!c1)
> > +             c1 = '/';
> > +
> > +     c2 = *two;
> > +     if (!c2)
> > +             c2 = '/';
> > +
> > +     if (c1 == c2) {
> > +             /* Getting here means one is a leading directory of the other */
> > +             return (*one) ? 1 : -1;
> > +     }
> > +     else
> > +             return c1-c2;
> >  }
> >
> >  static int read_oid_strbuf(struct merge_options *opt,
> > @@ -3481,8 +3500,7 @@ static void process_entries(struct merge_options *opt,
> >       trace2_region_leave("merge", "plist copy", opt->repo);
> >
> >       trace2_region_enter("merge", "plist special sort", opt->repo);
> > -     plist.cmp = string_list_df_name_compare;
> > -     string_list_sort(&plist);
> > +     QSORT(plist.items, plist.nr, sort_dirs_next_to_their_children);
>
> How much does the direct use of QSORT instead of string_list_sort()
> contribute to the speedup?  (I suspect only a bit.)

Yep, I'll fix up the commit message.

^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative
  2021-05-27  8:37 ` [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
  2021-05-27 21:00   ` René Scharfe
@ 2021-05-28  1:32   ` Taylor Blau
  2021-05-28  4:10     ` Elijah Newren
  1 sibling, 1 reply; 39+ messages in thread
From: Taylor Blau @ 2021-05-28  1:32 UTC (permalink / raw)
  To: Elijah Newren via GitGitGadget
  Cc: git, Derrick Stolee, Jonathan Tan, Taylor Blau, Elijah Newren

On Thu, May 27, 2021 at 08:37:17AM +0000, Elijah Newren via GitGitGadget wrote:
> -static int string_list_df_name_compare(const char *one, const char *two)
> +static int sort_dirs_next_to_their_children(const void *a, const void *b)

I looked at the new implementation of this function (and
df_name_compare() to double check it) and am convinced that it's
correctness, with the exception of one question.

Some thoughts I had while trying to make sure this was all OK:

> +	const char *one = ((struct string_list_item *)a)->string;
> +	const char *two = ((struct string_list_item *)b)->string;
> +	unsigned char c1, c2;
> +
> +	while (*one && (*one == *two)) {
> +		one++;
> +		two++;
> +	}

Advancing 'one' and 'two' to point at either the end of 'a' (and the
same position within 'b'), or the first place where the two have
different characters. If 'b' is shorter than 'a', '*one != *two' will
terminate the loop (since '*two' will be NUL, and '*one' will not).

> +	c1 = *one;
> +	if (!c1)
> +		c1 = '/';
> +
> +	c2 = *two;
> +	if (!c2)
> +		c2 = '/';

Store off the last character of each, or '/' if we got to the end. Hmm,
is this right (the guard in 'df_name_compare()' read 'if (!c1 &&
S_ISDIR(mode1))'). Suppose both strings were "foo", then both c1 and c2
would be "/", and I think we would return -1.

That doesn't seem quite right to me. I think it *would* be right if we
checked the mode of each entry before assigning c1 or c2 to '/',
though. (Being generally unfamiliar with this area, I haven't looked to
see whether getting access to the modes of each entry at this point is
easy or not).

> +
> +	if (c1 == c2) {
> +		/* Getting here means one is a leading directory of the other */
> +		return (*one) ? 1 : -1;
> +	}

> +	else

I did find this spacing awkward (would have expected '} else' or even '}
else {'), but it hardly matters.

Thanks,
Taylor

^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative
  2021-05-28  1:32   ` Taylor Blau
@ 2021-05-28  4:10     ` Elijah Newren
  0 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren @ 2021-05-28  4:10 UTC (permalink / raw)
  To: Taylor Blau
  Cc: Elijah Newren via GitGitGadget, Git Mailing List, Derrick Stolee,
	Jonathan Tan

On Thu, May 27, 2021 at 6:32 PM Taylor Blau <me@ttaylorr.com> wrote:
>
> On Thu, May 27, 2021 at 08:37:17AM +0000, Elijah Newren via GitGitGadget wrote:
> > -static int string_list_df_name_compare(const char *one, const char *two)
> > +static int sort_dirs_next_to_their_children(const void *a, const void *b)
>
> I looked at the new implementation of this function (and
> df_name_compare() to double check it) and am convinced that it's
> correctness, with the exception of one question.
>
> Some thoughts I had while trying to make sure this was all OK:
>
> > +     const char *one = ((struct string_list_item *)a)->string;
> > +     const char *two = ((struct string_list_item *)b)->string;
> > +     unsigned char c1, c2;
> > +
> > +     while (*one && (*one == *two)) {
> > +             one++;
> > +             two++;
> > +     }
>
> Advancing 'one' and 'two' to point at either the end of 'a' (and the
> same position within 'b'), or the first place where the two have
> different characters. If 'b' is shorter than 'a', '*one != *two' will
> terminate the loop (since '*two' will be NUL, and '*one' will not).
>
> > +     c1 = *one;
> > +     if (!c1)
> > +             c1 = '/';
> > +
> > +     c2 = *two;
> > +     if (!c2)
> > +             c2 = '/';
>
> Store off the last character of each, or '/' if we got to the end. Hmm,
> is this right (the guard in 'df_name_compare()' read 'if (!c1 &&
> S_ISDIR(mode1))'). Suppose both strings were "foo", then both c1 and c2
> would be "/", and I think we would return -1.
>
> That doesn't seem quite right to me. I think it *would* be right if we
> checked the mode of each entry before assigning c1 or c2 to '/',
> though. (Being generally unfamiliar with this area, I haven't looked to
> see whether getting access to the modes of each entry at this point is
> easy or not).

Good reasoning; I should have been clearer about one of the
assumptions that this function operates under which precludes that
possibility.

> > +
> > +     if (c1 == c2) {
> > +             /* Getting here means one is a leading directory of the other */

Your example case of both strings being "foo" obviously conflicts with
this comment; but the comment is correct.  This function will never be
given two equal strings because it is called to sort the keys of a
strmap, and strmap keys are unique by construction.  (If one side of
history has "foo" as a directory, and the other side has "foo" as a
path, then there is still only one "foo" in opt->priv->paths.  Every
entry in opt->priv->paths records 3 hashes and modes and whatnot in
order to know what each side of history had at the given path.)

Also, even in that case (when two strings are equal), getting the
right return value would only matter if we cared about a stable sort.
But we call this function with QSORT, not STABLE_QSORT.

Interestingly, this function technically doesn't even need to fully
sort the array either.  For example, if you took the output of 'git
ls-tree -rt HEAD' and permuted the order of files within the same
directory, that kind of level of quasi-sorted would be good enough for
my purposes; I just need files underneath the same directory to be
"together" and the containing directory to appear immediately before
those.  There is a later call to write_tree() that will hande sorting
within a single directory to ensure fully-sorted-ness.  Unfortunately,
I don't know of a way to take advantage of that less strict sorting
requirement for this point of the code to improve the performance
further, so this function just implemented "pretend that every path
has a '/' appended and then fully sort them".

> > +             return (*one) ? 1 : -1;
> > +     }
>
> > +     else
>
> I did find this spacing awkward (would have expected '} else' or even '}
> else {'), but it hardly matters.

I'll fix that up while adding some comments about the purpose of the
function and the fact that it assumes there will be no duplicates in
the array being sorted.

^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative
  2021-05-27 22:47     ` Elijah Newren
@ 2021-05-28 16:12       ` René Scharfe
  2021-05-28 18:09         ` Elijah Newren
  0 siblings, 1 reply; 39+ messages in thread
From: René Scharfe @ 2021-05-28 16:12 UTC (permalink / raw)
  To: Elijah Newren
  Cc: Elijah Newren via GitGitGadget, Git Mailing List, Derrick Stolee,
	Jonathan Tan, Taylor Blau

Am 28.05.21 um 00:47 schrieb Elijah Newren:
> On Thu, May 27, 2021 at 2:00 PM René Scharfe <l.s.r@web.de> wrote:
>>
>> Am 27.05.21 um 10:37 schrieb Elijah Newren via GitGitGadget:
>>> From: Elijah Newren <newren@gmail.com>
>>>
>>> Gathering accumulated times from trace2 output on the mega-renames
>>> testcase, I saw the following timings (where I'm only showing a few
>>> lines to highlight the portions of interest):
>>>
>>>     10.120 : label:incore_nonrecursive
>>>         4.462 : ..label:process_entries
>>>            3.143 : ....label:process_entries setup
>>>               2.988 : ......label:plist special sort
>>>            1.305 : ....label:processing
>>>         2.604 : ..label:collect_merge_info
>>>         2.018 : ..label:merge_start
>>>         1.018 : ..label:renames
>>>
>>> In the above output, note that the 4.462 seconds for process_entries was
>>> split as 3.143 seconds for "process_entries setup" and 1.305 seconds for
>>> "processing" (and a little time for other stuff removed from the
>>> highlight).  Most of the "process_entries setup" time was spent on
>>> "plist special sort" which corresponds to the following code:
>>>
>>>     trace2_region_enter("merge", "plist special sort", opt->repo);
>>>     plist.cmp = string_list_df_name_compare;
>>>     string_list_sort(&plist);
>>>     trace2_region_leave("merge", "plist special sort", opt->repo);
>>>
>>> In other words, in a merge strategy that would be invoked by passing
>>> "-sort" to either rebase or merge, sorting an array takes more time than
>>> anything else.  Serves me right for naming my merge strategy this way.
>>>
>>> Rewrite the comparison function and remove as many levels of indirection
>>> as possible (e.g. the old code had
>>>     cmp_items() ->
>>>       string_list_df_name_compare() ->
>>>         df_name_compare()
>>> now we just have sort_dirs_next_to_their_children()), and tweak it to be
>>> as optimized as possible for our specific case.  These changes reduced
>>> the time spent in "plist special sort" by ~25% in the mega-renames case.
>>>
>>> For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
>>> performance work; instrument with trace2_region_* calls", 2020-10-28),
>>> this change improves the performance as follows:
>>>
>>>                             Before                  After
>>>     no-renames:        5.622 s ±  0.059 s     5.235 s ±  0.042 s
>>>     mega-renames:     10.127 s ±  0.073 s     9.419 s ±  0.107 s
>>>     just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms
>>
>> Interesting.
>>
>>>
>>> Signed-off-by: Elijah Newren <newren@gmail.com>
>>> ---
>>>  merge-ort.c | 64 ++++++++++++++++++++++++++++++++++-------------------
>>>  1 file changed, 41 insertions(+), 23 deletions(-)
>>>
>>> diff --git a/merge-ort.c b/merge-ort.c
>>> index 142d44d74d63..367aec4b7def 100644
>>> --- a/merge-ort.c
>>> +++ b/merge-ort.c
>>> @@ -2746,31 +2746,50 @@ static int detect_and_process_renames(struct merge_options *opt,
>>>
>>>  /*** Function Grouping: functions related to process_entries() ***/
>>>
>>> -static int string_list_df_name_compare(const char *one, const char *two)
>>> +static int sort_dirs_next_to_their_children(const void *a, const void *b)
>>>  {
>>> -     int onelen = strlen(one);
>>> -     int twolen = strlen(two);
>>
>> The old code scans both strings fully, while the new one stops when it
>> reaches a difference and doesn't look at any further characters.  How
>> much does that contribute to the speedup?  (I suspect a lot.)
>
> Oh, indeed, good catch.  It appears to be responsible for essentially all of it.

Then you can keep the original function signature (as well as the use of
string_list_sort) and avoid explicit casts.

The same function exists in merge-recursive.c, by the way.  I suspect we
could avoid sorting entirely there by taking advantage of the index
order and a mechanism like the one in the second half of
fsck.c::verify_ordered().  That's a bit tricky, though (for me anyway).

All tests still pass when I replace string_list_df_name_compare() with
strcmp() in merge-recursive.c, so the first thing needed would be tests
that highlight the difference between those comparison functions,
however.  Not sure if it's worth it -- merge-recursive is on its way
out, right?

Not sure if d/f conflicts could also be detected in merge-ort.c without
sorting -- the original order is lost when the paths are thrown into
a strmap.

>
>>>       /*
>>> -      * Here we only care that entries for D/F conflicts are
>>> -      * adjacent, in particular with the file of the D/F conflict
>>> -      * appearing before files below the corresponding directory.
>>> -      * The order of the rest of the list is irrelevant for us.
>>> +      * Here we only care that entries for directories appear adjacent
>>> +      * to and before files underneath the directory.  In other words,
>>> +      * we do not want the natural sorting of
>>> +      *     foo
>>> +      *     foo.txt
>>> +      *     foo/bar
>>> +      * Instead, we want "foo" to sort as though it were "foo/", so that
>>> +      * we instead get
>>> +      *     foo.txt
>>> +      *     foo
>>> +      *     foo/bar
>>> +      * To achieve this, we basically implement our own strcmp, except that
>>> +      * if we get to the end of either string instead of comparing NUL to
>>> +      * another character, we compare '/' to it.
>>>        *
>>> -      * To achieve this, we sort with df_name_compare and provide
>>> -      * the mode S_IFDIR so that D/F conflicts will sort correctly.
>>> -      * We use the mode S_IFDIR for everything else for simplicity,
>>> -      * since in other cases any changes in their order due to
>>> -      * sorting cause no problems for us.
>>> +      * The reason to not use df_name_compare directly was that it was
>>> +      * just too expensive, so I had to reimplement it.
>>>        */
>>> -     int cmp = df_name_compare(one, onelen, S_IFDIR,
>>> -                               two, twolen, S_IFDIR);
>>> -     /*
>>> -      * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
>>> -      * that 'foo' comes before 'foo/bar'.
>>> -      */
>>> -     if (cmp)
>>> -             return cmp;
>>> -     return onelen - twolen;
>>> +     const char *one = ((struct string_list_item *)a)->string;
>>> +     const char *two = ((struct string_list_item *)b)->string;
>>
>> Casting away const, hmm. :-/  Harmless because no actual write is
>> attempted, but still looks needlessly scary to me.
>
> Right, that should have been
> +     const char *one = ((const struct string_list_item *)a)->string;
> +     const char *two = ((const struct string_list_item *)b)->string;
> but since I was just assigning to a const char * on those lines, I'm
> not sure why it'd qualify as scary.  Regardless, I'm happy to put
> these consts back in.

Explicit casts are a red flag already (anything could be cast to
anything else) and if they remove const their severity increases.  The
resulting object text is fine, but the code yells "TYPE SYSTEM
OVERRRULED!"  And type checks in C are weak to begin with, so a casual
reader has to wonder what kind of black magic is at work.  None in
this case, as an implicit casts would have sufficed:

	const struct string_list_item *item_a = a, *item_b = b;
	const char *one = item_a->string, *two = item_b->string;

Boring.  Calming.  Nice. ;)  The compiler would warn us if the pieces
didn't fit.

René

^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative
  2021-05-28 16:12       ` René Scharfe
@ 2021-05-28 18:09         ` Elijah Newren
  0 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren @ 2021-05-28 18:09 UTC (permalink / raw)
  To: René Scharfe
  Cc: Elijah Newren via GitGitGadget, Git Mailing List, Derrick Stolee,
	Jonathan Tan, Taylor Blau

On Fri, May 28, 2021 at 9:12 AM René Scharfe <l.s.r@web.de> wrote:
>
> Am 28.05.21 um 00:47 schrieb Elijah Newren:
> > On Thu, May 27, 2021 at 2:00 PM René Scharfe <l.s.r@web.de> wrote:
> >>
> >> Am 27.05.21 um 10:37 schrieb Elijah Newren via GitGitGadget:
...
> >>>  /*** Function Grouping: functions related to process_entries() ***/
> >>>
> >>> -static int string_list_df_name_compare(const char *one, const char *two)
> >>> +static int sort_dirs_next_to_their_children(const void *a, const void *b)
> >>>  {
> >>> -     int onelen = strlen(one);
> >>> -     int twolen = strlen(two);
> >>
> >> The old code scans both strings fully, while the new one stops when it
> >> reaches a difference and doesn't look at any further characters.  How
> >> much does that contribute to the speedup?  (I suspect a lot.)
> >
> > Oh, indeed, good catch.  It appears to be responsible for essentially all of it.
>
> Then you can keep the original function signature (as well as the use of
> string_list_sort) and avoid explicit casts.

Fair enough; though I'll probably still apply the function rename,
even if I keep the old signature.  The function has a completely
different purpose in merge-ort.c than it does in merge-recursive.c.

> The same function exists in merge-recursive.c, by the way.  I suspect we
> could avoid sorting entirely there by taking advantage of the index
> order and a mechanism like the one in the second half of
> fsck.c::verify_ordered().  That's a bit tricky, though (for me anyway).
>
> All tests still pass when I replace string_list_df_name_compare() with
> strcmp() in merge-recursive.c, so the first thing needed would be tests
> that highlight the difference between those comparison functions,
> however.  Not sure if it's worth it -- merge-recursive is on its way
> out, right?

Interesting idea (and interesting that the function might not matter
anymore in merge-recursive.c and might be replaceable by strcmp), but
yeah merge-recursive.c is on its way out.  In fact, there are two
other reasons to also not modify merge-recursive.c along these lines:
(1) We want to keep merge-recursive stable right now as we push people
to try out merge-ort, so that we have a good comparison point if they
run into problems; if we modify merge-recursive, especially in tricky
ways, then our comparison point might get invalidated.  (2) This
codepath is relatively hot in merge-ort.c because it has optimized all
the other stuff, so saving approximately half a second is significant.
In merge-recursive.c, saving half a second is a small blip in the
overall timing that would be lost in the run-to-run variability.
(Saving 0.7s off of 10.127 s ±  0.073 s is huge; but removing that
much time from 5964.031 s ± 10.459 is wasted effort.)

> Not sure if d/f conflicts could also be detected in merge-ort.c without
> sorting -- the original order is lost when the paths are thrown into
> a strmap.

While string_list_df_name_compare() in merge-recursive.c is used for
the purpose of detecting D/F conflicts, this function in merge-ort.c
had nothing to do with detecting D/F conflicts.  In fact, D/F
conflicts were already detected in collect_merge_info_callback() on
this line:

    unsigned df_conflict = (filemask != 0) && (dirmask != 0);

and recorded in setup_path_info(), which was done long before it got
to this point in the code.  The point of this sorting in merge-ort.c
is just to put paths in an order that allows us to write out trees as
we process them and record the resulting hash for the next directory
up the chain as we go.

^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff
  2021-05-27  8:37 [PATCH 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
                   ` (4 preceding siblings ...)
  2021-05-27  8:37 ` [PATCH 5/5] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget
@ 2021-06-01 14:58 ` Elijah Newren via GitGitGadget
  2021-06-01 14:58   ` [PATCH v2 1/5] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
                     ` (6 more replies)
  5 siblings, 7 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-01 14:58 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Elijah Newren

This series depends on en/ort-perf-batch-11 textually, but is semantically
independent of it.

Changes since v1 (all for the first patch):

 * Add more comments explaining the sorting function, its purpose, and how
   its expected to be called
 * Small style fixup
 * Switch back to using string_list_sort() instead of direct QSORT()

This short series has a few optimizations, but only one of which affects the
testcases of interest (namely, reducing our time spent on sorting an array).
It also fixes a few comments.

For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28), the
changes in just this series improves the performance as follows:

                     Before Series           After Series
no-renames:        5.622 s ±  0.059 s     5.235 s ±  0.042 s
mega-renames:     10.127 s ±  0.073 s     9.419 s ±  0.107 s
just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms


As a reminder, before any merge-ort/diffcore-rename performance work, the
performance results we started with were:

no-renames-am:      6.940 s ±  0.485 s
no-renames:        18.912 s ±  0.174 s
mega-renames:    5964.031 s ± 10.459 s
just-one-mega:    149.583 s ±  0.751 s


Elijah Newren (5):
  merge-ort: replace string_list_df_name_compare with faster alternative
  diffcore-rename: avoid unnecessary strdup'ing in break_idx
  diffcore-rename: enable limiting rename detection to relevant
    destinations
  Fix various issues found in comments
  merge-ort: miscellaneous touch-ups

 diffcore-rename.c                   | 52 ++++++++++++++---
 diffcore.h                          |  2 +
 merge-ort.c                         | 86 +++++++++++++++++++++--------
 t/t6423-merge-rename-directories.sh |  2 +-
 4 files changed, 110 insertions(+), 32 deletions(-)


base-commit: 76e253793c9a1d7fdd1836d5e4db26dabd3d713a
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-962%2Fnewren%2Fort-perf-batch-12-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-962/newren/ort-perf-batch-12-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/962

Range-diff vs v1:

 1:  5055dfce3281 ! 1:  c4a0f6a9510c merge-ort: replace string_list_df_name_compare with faster alternative
     @@ Commit message
          "-sort" to either rebase or merge, sorting an array takes more time than
          anything else.  Serves me right for naming my merge strategy this way.
      
     -    Rewrite the comparison function and remove as many levels of indirection
     -    as possible (e.g. the old code had
     -        cmp_items() ->
     -          string_list_df_name_compare() ->
     -            df_name_compare()
     -    now we just have sort_dirs_next_to_their_children()), and tweak it to be
     -    as optimized as possible for our specific case.  These changes reduced
     -    the time spent in "plist special sort" by ~25% in the mega-renames case.
     +    Rewrite the comparison function in a way that does not require finding
     +    out the lengths of the strings when comparing them.  While at it, tweak
     +    the code for our specific case -- no need to handle a variety of modes,
     +    for example.  The combination of these changes reduced the time spent in
     +    "plist special sort" by ~25% in the mega-renames case.
      
          For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
          performance work; instrument with trace2_region_* calls", 2020-10-28),
     @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,
       /*** Function Grouping: functions related to process_entries() ***/
       
      -static int string_list_df_name_compare(const char *one, const char *two)
     -+static int sort_dirs_next_to_their_children(const void *a, const void *b)
     ++static int sort_dirs_next_to_their_children(const char *one, const char *two)
       {
      -	int onelen = strlen(one);
      -	int twolen = strlen(two);
     ++	unsigned char c1, c2;
     ++
       	/*
      -	 * Here we only care that entries for D/F conflicts are
      -	 * adjacent, in particular with the file of the D/F conflict
      -	 * appearing before files below the corresponding directory.
      -	 * The order of the rest of the list is irrelevant for us.
      +	 * Here we only care that entries for directories appear adjacent
     -+	 * to and before files underneath the directory.  In other words,
     -+	 * we do not want the natural sorting of
     ++	 * to and before files underneath the directory.  We can achieve
     ++	 * that by pretending to add a trailing slash to every file and
     ++	 * then sorting.  In other words, we do not want the natural
     ++	 * sorting of
      +	 *     foo
      +	 *     foo.txt
      +	 *     foo/bar
     @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,
      +	 * To achieve this, we basically implement our own strcmp, except that
      +	 * if we get to the end of either string instead of comparing NUL to
      +	 * another character, we compare '/' to it.
     ++	 *
     ++	 * If this unusual "sort as though '/' were appended" perplexes
     ++	 * you, perhaps it will help to note that this is not the final
     ++	 * sort.  write_tree() will sort again without the trailing slash
     ++	 * magic, but just on paths immediately under a given tree.
       	 *
      -	 * To achieve this, we sort with df_name_compare and provide
      -	 * the mode S_IFDIR so that D/F conflicts will sort correctly.
     @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,
      -	 * since in other cases any changes in their order due to
      -	 * sorting cause no problems for us.
      +	 * The reason to not use df_name_compare directly was that it was
     -+	 * just too expensive, so I had to reimplement it.
     ++	 * just too expensive (we don't have the string lengths handy), so
     ++	 * I had to reimplement it.
       	 */
      -	int cmp = df_name_compare(one, onelen, S_IFDIR,
      -				  two, twolen, S_IFDIR);
     --	/*
     ++
     + 	/*
      -	 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
      -	 * that 'foo' comes before 'foo/bar'.
     --	 */
     ++	 * NOTE: This function will never be called with two equal strings,
     ++	 * because it is used to sort the keys of a strmap, and strmaps have
     ++	 * unique keys by construction.  That simplifies our c1==c2 handling
     ++	 * below.
     + 	 */
      -	if (cmp)
      -		return cmp;
      -	return onelen - twolen;
     -+	const char *one = ((struct string_list_item *)a)->string;
     -+	const char *two = ((struct string_list_item *)b)->string;
     -+	unsigned char c1, c2;
      +
      +	while (*one && (*one == *two)) {
      +		one++;
     @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,
      +	if (c1 == c2) {
      +		/* Getting here means one is a leading directory of the other */
      +		return (*one) ? 1 : -1;
     -+	}
     -+	else
     ++	} else
      +		return c1-c2;
       }
       
     @@ merge-ort.c: static void process_entries(struct merge_options *opt,
       
       	trace2_region_enter("merge", "plist special sort", opt->repo);
      -	plist.cmp = string_list_df_name_compare;
     --	string_list_sort(&plist);
     -+	QSORT(plist.items, plist.nr, sort_dirs_next_to_their_children);
     ++	plist.cmp = sort_dirs_next_to_their_children;
     + 	string_list_sort(&plist);
       	trace2_region_leave("merge", "plist special sort", opt->repo);
       
     - 	trace2_region_leave("merge", "process_entries setup", opt->repo);
 2:  7212816c8d47 = 2:  38713ed48273 diffcore-rename: avoid unnecessary strdup'ing in break_idx
 3:  19150b575058 = 3:  45e1de5fe780 diffcore-rename: enable limiting rename detection to relevant destinations
 4:  98c9a419b313 = 4:  2f26d7e935c0 Fix various issues found in comments
 5:  e85dad887f95 = 5:  7156f26ab299 merge-ort: miscellaneous touch-ups

-- 
gitgitgadget

^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v2 1/5] merge-ort: replace string_list_df_name_compare with faster alternative
  2021-06-01 14:58 ` [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
@ 2021-06-01 14:58   ` Elijah Newren via GitGitGadget
  2021-06-02 11:29     ` Derrick Stolee
  2021-06-01 14:58   ` [PATCH v2 2/5] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
                     ` (5 subsequent siblings)
  6 siblings, 1 reply; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-01 14:58 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Elijah Newren, Elijah Newren

From: Elijah Newren <newren@gmail.com>

Gathering accumulated times from trace2 output on the mega-renames
testcase, I saw the following timings (where I'm only showing a few
lines to highlight the portions of interest):

    10.120 : label:incore_nonrecursive
        4.462 : ..label:process_entries
           3.143 : ....label:process_entries setup
              2.988 : ......label:plist special sort
           1.305 : ....label:processing
        2.604 : ..label:collect_merge_info
        2.018 : ..label:merge_start
        1.018 : ..label:renames

In the above output, note that the 4.462 seconds for process_entries was
split as 3.143 seconds for "process_entries setup" and 1.305 seconds for
"processing" (and a little time for other stuff removed from the
highlight).  Most of the "process_entries setup" time was spent on
"plist special sort" which corresponds to the following code:

    trace2_region_enter("merge", "plist special sort", opt->repo);
    plist.cmp = string_list_df_name_compare;
    string_list_sort(&plist);
    trace2_region_leave("merge", "plist special sort", opt->repo);

In other words, in a merge strategy that would be invoked by passing
"-sort" to either rebase or merge, sorting an array takes more time than
anything else.  Serves me right for naming my merge strategy this way.

Rewrite the comparison function in a way that does not require finding
out the lengths of the strings when comparing them.  While at it, tweak
the code for our specific case -- no need to handle a variety of modes,
for example.  The combination of these changes reduced the time spent in
"plist special sort" by ~25% in the mega-renames case.

For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:

                            Before                  After
    no-renames:        5.622 s ±  0.059 s     5.235 s ±  0.042 s
    mega-renames:     10.127 s ±  0.073 s     9.419 s ±  0.107 s
    just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-ort.c | 72 ++++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 52 insertions(+), 20 deletions(-)

diff --git a/merge-ort.c b/merge-ort.c
index 142d44d74d63..0fe2eaf02eb2 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2746,31 +2746,63 @@ static int detect_and_process_renames(struct merge_options *opt,
 
 /*** Function Grouping: functions related to process_entries() ***/
 
-static int string_list_df_name_compare(const char *one, const char *two)
+static int sort_dirs_next_to_their_children(const char *one, const char *two)
 {
-	int onelen = strlen(one);
-	int twolen = strlen(two);
+	unsigned char c1, c2;
+
 	/*
-	 * Here we only care that entries for D/F conflicts are
-	 * adjacent, in particular with the file of the D/F conflict
-	 * appearing before files below the corresponding directory.
-	 * The order of the rest of the list is irrelevant for us.
+	 * Here we only care that entries for directories appear adjacent
+	 * to and before files underneath the directory.  We can achieve
+	 * that by pretending to add a trailing slash to every file and
+	 * then sorting.  In other words, we do not want the natural
+	 * sorting of
+	 *     foo
+	 *     foo.txt
+	 *     foo/bar
+	 * Instead, we want "foo" to sort as though it were "foo/", so that
+	 * we instead get
+	 *     foo.txt
+	 *     foo
+	 *     foo/bar
+	 * To achieve this, we basically implement our own strcmp, except that
+	 * if we get to the end of either string instead of comparing NUL to
+	 * another character, we compare '/' to it.
+	 *
+	 * If this unusual "sort as though '/' were appended" perplexes
+	 * you, perhaps it will help to note that this is not the final
+	 * sort.  write_tree() will sort again without the trailing slash
+	 * magic, but just on paths immediately under a given tree.
 	 *
-	 * To achieve this, we sort with df_name_compare and provide
-	 * the mode S_IFDIR so that D/F conflicts will sort correctly.
-	 * We use the mode S_IFDIR for everything else for simplicity,
-	 * since in other cases any changes in their order due to
-	 * sorting cause no problems for us.
+	 * The reason to not use df_name_compare directly was that it was
+	 * just too expensive (we don't have the string lengths handy), so
+	 * I had to reimplement it.
 	 */
-	int cmp = df_name_compare(one, onelen, S_IFDIR,
-				  two, twolen, S_IFDIR);
+
 	/*
-	 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
-	 * that 'foo' comes before 'foo/bar'.
+	 * NOTE: This function will never be called with two equal strings,
+	 * because it is used to sort the keys of a strmap, and strmaps have
+	 * unique keys by construction.  That simplifies our c1==c2 handling
+	 * below.
 	 */
-	if (cmp)
-		return cmp;
-	return onelen - twolen;
+
+	while (*one && (*one == *two)) {
+		one++;
+		two++;
+	}
+
+	c1 = *one;
+	if (!c1)
+		c1 = '/';
+
+	c2 = *two;
+	if (!c2)
+		c2 = '/';
+
+	if (c1 == c2) {
+		/* Getting here means one is a leading directory of the other */
+		return (*one) ? 1 : -1;
+	} else
+		return c1-c2;
 }
 
 static int read_oid_strbuf(struct merge_options *opt,
@@ -3481,7 +3513,7 @@ static void process_entries(struct merge_options *opt,
 	trace2_region_leave("merge", "plist copy", opt->repo);
 
 	trace2_region_enter("merge", "plist special sort", opt->repo);
-	plist.cmp = string_list_df_name_compare;
+	plist.cmp = sort_dirs_next_to_their_children;
 	string_list_sort(&plist);
 	trace2_region_leave("merge", "plist special sort", opt->repo);
 
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v2 2/5] diffcore-rename: avoid unnecessary strdup'ing in break_idx
  2021-06-01 14:58 ` [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
  2021-06-01 14:58   ` [PATCH v2 1/5] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
@ 2021-06-01 14:58   ` Elijah Newren via GitGitGadget
  2021-06-01 14:58   ` [PATCH v2 3/5] diffcore-rename: enable limiting rename detection to relevant destinations Elijah Newren via GitGitGadget
                     ` (4 subsequent siblings)
  6 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-01 14:58 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Elijah Newren, Elijah Newren

From: Elijah Newren <newren@gmail.com>

The keys of break_idx are strings from the diff_filepairs of
diff_queued_diff.  break_idx is only used in location_rename_dst(), and
that usage is always before any free'ing of the pairs (and thus the
strings in the pairs).  As such, there is no need to strdup these keys;
we can just reuse the existing strings as-is.

The merge logic doesn't make use of break detection, so this does not
affect the performance of any of my testcases.  It was just a minor
unrelated optimization noted in passing while looking at the code.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 diffcore-rename.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 3375e24659ea..e333a6d64791 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -54,7 +54,7 @@ static void register_rename_src(struct diff_filepair *p)
 	if (p->broken_pair) {
 		if (!break_idx) {
 			break_idx = xmalloc(sizeof(*break_idx));
-			strintmap_init(break_idx, -1);
+			strintmap_init_with_options(break_idx, -1, NULL, 0);
 		}
 		strintmap_set(break_idx, p->one->path, rename_dst_nr);
 	}
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v2 3/5] diffcore-rename: enable limiting rename detection to relevant destinations
  2021-06-01 14:58 ` [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
  2021-06-01 14:58   ` [PATCH v2 1/5] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
  2021-06-01 14:58   ` [PATCH v2 2/5] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
@ 2021-06-01 14:58   ` Elijah Newren via GitGitGadget
  2021-06-03 12:54     ` Derrick Stolee
  2021-06-01 14:58   ` [PATCH v2 4/5] Fix various issues found in comments Elijah Newren via GitGitGadget
                     ` (3 subsequent siblings)
  6 siblings, 1 reply; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-01 14:58 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Elijah Newren, Elijah Newren

From: Elijah Newren <newren@gmail.com>

Our former optimizations focused on limiting rename detection to a
pre-specified set of relevant sources.  This was because the merge logic
only had a way of knowing which sources were relevant.  However, other
callers of rename detection might benefit from being able to limit
rename detection to a known set of relevant destinations.  In
particular, a properly implemented `git log --follow` might benefit from
such an ability.

Since the code to implement such limiting is very similar to what we've
already done, just implement it now even though we do not yet have any
callers making use of this ability.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 diffcore-rename.c | 48 +++++++++++++++++++++++++++++++++++++++++------
 diffcore.h        |  2 ++
 merge-ort.c       |  1 +
 3 files changed, 45 insertions(+), 6 deletions(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index e333a6d64791..8ff83a9f3b99 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -372,6 +372,7 @@ struct dir_rename_info {
 	struct strmap dir_rename_guess;
 	struct strmap *dir_rename_count;
 	struct strintmap *relevant_source_dirs;
+	struct strset *relevant_destination_dirs;
 	unsigned setup;
 };
 
@@ -491,8 +492,11 @@ static void update_dir_rename_counts(struct dir_rename_info *info,
 		    !strintmap_contains(info->relevant_source_dirs, old_dir))
 			break;
 
-		/* Get new_dir */
+		/* Get new_dir, skip if its directory isn't relevant. */
 		dirname_munge(new_dir);
+		if (info->relevant_destination_dirs &&
+		    !strset_contains(info->relevant_destination_dirs, new_dir))
+			break;
 
 		/*
 		 * When renaming
@@ -567,6 +571,7 @@ static void update_dir_rename_counts(struct dir_rename_info *info,
 
 static void initialize_dir_rename_info(struct dir_rename_info *info,
 				       struct strintmap *relevant_sources,
+				       struct strset *relevant_destinations,
 				       struct strintmap *dirs_removed,
 				       struct strmap *dir_rename_count,
 				       struct strmap *cached_pairs)
@@ -575,7 +580,7 @@ static void initialize_dir_rename_info(struct dir_rename_info *info,
 	struct strmap_entry *entry;
 	int i;
 
-	if (!dirs_removed && !relevant_sources) {
+	if (!dirs_removed && !relevant_sources && !relevant_destinations) {
 		info->setup = 0;
 		return;
 	}
@@ -589,6 +594,18 @@ static void initialize_dir_rename_info(struct dir_rename_info *info,
 	strintmap_init_with_options(&info->idx_map, -1, NULL, 0);
 	strmap_init_with_options(&info->dir_rename_guess, NULL, 0);
 
+	/* Setup info->relevant_destination_dirs */
+	info->relevant_destination_dirs = NULL;
+	if (relevant_destinations) {
+		info->relevant_destination_dirs = xmalloc(sizeof(struct strset));
+		strset_init(info->relevant_destination_dirs);
+		strset_for_each_entry(relevant_destinations, &iter, entry) {
+			char *dirname = get_dirname(entry->key);
+			strset_add(info->relevant_destination_dirs, dirname);
+			free(dirname);
+		}
+	}
+
 	/* Setup info->relevant_source_dirs */
 	info->relevant_source_dirs = NULL;
 	if (dirs_removed || !relevant_sources) {
@@ -700,6 +717,12 @@ static void cleanup_dir_rename_info(struct dir_rename_info *info,
 		FREE_AND_NULL(info->relevant_source_dirs);
 	}
 
+	/* relevant_destination_dirs */
+	if (info->relevant_destination_dirs) {
+		strset_clear(info->relevant_destination_dirs);
+		FREE_AND_NULL(info->relevant_destination_dirs);
+	}
+
 	/* dir_rename_count */
 	if (!keep_dir_rename_count) {
 		partial_clear_dir_rename_count(info->dir_rename_count);
@@ -827,6 +850,7 @@ static int find_basename_matches(struct diff_options *options,
 				 int minimum_score,
 				 struct dir_rename_info *info,
 				 struct strintmap *relevant_sources,
+				 struct strset *relevant_destinations,
 				 struct strintmap *dirs_removed)
 {
 	/*
@@ -949,9 +973,15 @@ static int find_basename_matches(struct diff_options *options,
 			if (rename_dst[dst_index].is_rename)
 				continue; /* already used previously */
 
-			/* Estimate the similarity */
 			one = rename_src[src_index].p->one;
 			two = rename_dst[dst_index].p->two;
+
+			/* Skip irrelevant destinations */
+			if (relevant_destinations &&
+			    !strset_contains(relevant_destinations, two->path))
+				continue;
+
+			/* Estimate the similarity */
 			score = estimate_similarity(options->repo, one, two,
 						    minimum_score, skip_unmodified);
 
@@ -1258,6 +1288,7 @@ static void handle_early_known_dir_renames(struct dir_rename_info *info,
 
 void diffcore_rename_extended(struct diff_options *options,
 			      struct strintmap *relevant_sources,
+			      struct strset *relevant_destinations,
 			      struct strintmap *dirs_removed,
 			      struct strmap *dir_rename_count,
 			      struct strmap *cached_pairs)
@@ -1376,8 +1407,8 @@ void diffcore_rename_extended(struct diff_options *options,
 		/* Preparation for basename-driven matching. */
 		trace2_region_enter("diff", "dir rename setup", options->repo);
 		initialize_dir_rename_info(&info, relevant_sources,
-					   dirs_removed, dir_rename_count,
-					   cached_pairs);
+					   relevant_destinations, dirs_removed,
+					   dir_rename_count, cached_pairs);
 		trace2_region_leave("diff", "dir rename setup", options->repo);
 
 		/* Utilize file basenames to quickly find renames. */
@@ -1386,6 +1417,7 @@ void diffcore_rename_extended(struct diff_options *options,
 						      min_basename_score,
 						      &info,
 						      relevant_sources,
+						      relevant_destinations,
 						      dirs_removed);
 		trace2_region_leave("diff", "basename matches", options->repo);
 
@@ -1441,6 +1473,10 @@ void diffcore_rename_extended(struct diff_options *options,
 		if (rename_dst[i].is_rename)
 			continue; /* exact or basename match already handled */
 
+		if (relevant_destinations &&
+		    !strset_contains(relevant_destinations, two->path))
+			continue;
+
 		m = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];
 		for (j = 0; j < NUM_CANDIDATE_PER_DST; j++)
 			m[j].dst = -1;
@@ -1574,5 +1610,5 @@ void diffcore_rename_extended(struct diff_options *options,
 
 void diffcore_rename(struct diff_options *options)
 {
-	diffcore_rename_extended(options, NULL, NULL, NULL, NULL);
+	diffcore_rename_extended(options, NULL, NULL, NULL, NULL, NULL);
 }
diff --git a/diffcore.h b/diffcore.h
index 533b30e21e7f..435c7094f403 100644
--- a/diffcore.h
+++ b/diffcore.h
@@ -10,6 +10,7 @@ struct diff_options;
 struct repository;
 struct strintmap;
 struct strmap;
+struct strset;
 struct userdiff_driver;
 
 /* This header file is internal between diff.c and its diff transformers
@@ -180,6 +181,7 @@ void diffcore_break(struct repository *, int);
 void diffcore_rename(struct diff_options *);
 void diffcore_rename_extended(struct diff_options *options,
 			      struct strintmap *relevant_sources,
+			      struct strset *relevant_destinations,
 			      struct strintmap *dirs_removed,
 			      struct strmap *dir_rename_count,
 			      struct strmap *cached_pairs);
diff --git a/merge-ort.c b/merge-ort.c
index 0fe2eaf02eb2..28951c35ddc2 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2568,6 +2568,7 @@ static void detect_regular_renames(struct merge_options *opt,
 	trace2_region_enter("diff", "diffcore_rename", opt->repo);
 	diffcore_rename_extended(&diff_opts,
 				 &renames->relevant_sources[side_index],
+				 NULL,
 				 &renames->dirs_removed[side_index],
 				 &renames->dir_rename_count[side_index],
 				 &renames->cached_pairs[side_index]);
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v2 4/5] Fix various issues found in comments
  2021-06-01 14:58 ` [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
                     ` (2 preceding siblings ...)
  2021-06-01 14:58   ` [PATCH v2 3/5] diffcore-rename: enable limiting rename detection to relevant destinations Elijah Newren via GitGitGadget
@ 2021-06-01 14:58   ` Elijah Newren via GitGitGadget
  2021-06-01 14:58   ` [PATCH v2 5/5] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget
                     ` (2 subsequent siblings)
  6 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-01 14:58 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Elijah Newren, Elijah Newren

From: Elijah Newren <newren@gmail.com>

A random hodge-podge of incorrect or out-of-date comments that I found:

  * t6423 had a comment that has referred to the wrong test for years;
    fix it to refer to the right one.
  * diffcore-rename had a FIXME comment meant to remind myself to
    investigate if I could make another code change.  I later
    investigated and removed the FIXME, but while cherry-picking the
    patch to submit upstream I missed the later update.  Remove the
    comment now.
  * merge-ort had the early part of a comment for a function; I had
    meant to include the more involved description when I updated the
    function.  Update the comment now.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 diffcore-rename.c                   | 2 +-
 merge-ort.c                         | 8 +++++---
 t/t6423-merge-rename-directories.sh | 2 +-
 3 files changed, 7 insertions(+), 5 deletions(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 8ff83a9f3b99..c9f7d59cf62b 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -1579,7 +1579,7 @@ void diffcore_rename_extended(struct diff_options *options,
 			/* all the usual ones need to be kept */
 			diff_q(&outq, p);
 		else
-			/* no need to keep unmodified pairs; FIXME: remove earlier? */
+			/* no need to keep unmodified pairs */
 			pair_to_free = p;
 
 		if (pair_to_free)
diff --git a/merge-ort.c b/merge-ort.c
index 28951c35ddc2..14b3e14bbe47 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2533,7 +2533,7 @@ static int compare_pairs(const void *a_, const void *b_)
 	return strcmp(a->one->path, b->one->path);
 }
 
-/* Call diffcore_rename() to compute which files have changed on given side */
+/* Call diffcore_rename() to update deleted/added pairs into rename pairs */
 static void detect_regular_renames(struct merge_options *opt,
 				   unsigned side_index)
 {
@@ -2587,8 +2587,10 @@ static void detect_regular_renames(struct merge_options *opt,
 }
 
 /*
- * Get information of all renames which occurred in 'side_pairs', discarding
- * non-renames.
+ * Get information of all renames which occurred in 'side_pairs', making use
+ * of any implicit directory renames in side_dir_renames (also making use of
+ * implicit directory renames rename_exclusions as needed by
+ * check_for_directory_rename()).  Add all (updated) renames into result.
  */
 static int collect_renames(struct merge_options *opt,
 			   struct diff_queue_struct *result,
diff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh
index be84d22419d9..e834b7e6efe0 100755
--- a/t/t6423-merge-rename-directories.sh
+++ b/t/t6423-merge-rename-directories.sh
@@ -454,7 +454,7 @@ test_expect_success '1f: Split a directory into two other directories' '
 #   the directory renamed, but the files within it. (see 1b)
 #
 #   If renames split a directory into two or more others, the directory
-#   with the most renames, "wins" (see 1c).  However, see the testcases
+#   with the most renames, "wins" (see 1f).  However, see the testcases
 #   in section 2, plus testcases 3a and 4a.
 ###########################################################################
 
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v2 5/5] merge-ort: miscellaneous touch-ups
  2021-06-01 14:58 ` [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
                     ` (3 preceding siblings ...)
  2021-06-01 14:58   ` [PATCH v2 4/5] Fix various issues found in comments Elijah Newren via GitGitGadget
@ 2021-06-01 14:58   ` Elijah Newren via GitGitGadget
  2021-06-03 12:55   ` [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff Derrick Stolee
  2021-06-04  4:39   ` [PATCH v3 0/4] " Elijah Newren via GitGitGadget
  6 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-01 14:58 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Elijah Newren, Elijah Newren

From: Elijah Newren <newren@gmail.com>

Add some notes in the code about invariants with match_mask when adding
pairs.  Also add a comment that seems to have been left out in my work
of pushing these changes upstream.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-ort.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/merge-ort.c b/merge-ort.c
index 14b3e14bbe47..d428b73dedd4 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -765,6 +765,7 @@ static void add_pair(struct merge_options *opt,
 	int names_idx = is_add ? side : 0;
 
 	if (is_add) {
+		assert(match_mask == 0 || match_mask == 6);
 		if (strset_contains(&renames->cached_target_names[side],
 				    pathname))
 			return;
@@ -772,6 +773,8 @@ static void add_pair(struct merge_options *opt,
 		unsigned content_relevant = (match_mask == 0);
 		unsigned location_relevant = (dir_rename_mask == 0x07);
 
+		assert(match_mask == 0 || match_mask == 3 || match_mask == 5);
+
 		/*
 		 * If pathname is found in cached_irrelevant[side] due to
 		 * previous pick but for this commit content is relevant,
@@ -3483,6 +3486,8 @@ static void process_entry(struct merge_options *opt,
 	 */
 	if (!ci->merged.clean)
 		strmap_put(&opt->priv->conflicted, path, ci);
+
+	/* Record metadata for ci->merged in dir_metadata */
 	record_entry_for_tree(dir_metadata, path, &ci->merged);
 }
 
-- 
gitgitgadget

^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH v2 1/5] merge-ort: replace string_list_df_name_compare with faster alternative
  2021-06-01 14:58   ` [PATCH v2 1/5] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
@ 2021-06-02 11:29     ` Derrick Stolee
  0 siblings, 0 replies; 39+ messages in thread
From: Derrick Stolee @ 2021-06-02 11:29 UTC (permalink / raw)
  To: Elijah Newren via GitGitGadget, git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren

On 6/1/21 10:58 AM, Elijah Newren via GitGitGadget wrote:
> From: Elijah Newren <newren@gmail.com>
> 
...
>  	/*
> -	 * Here we only care that entries for D/F conflicts are
> -	 * adjacent, in particular with the file of the D/F conflict
> -	 * appearing before files below the corresponding directory.
> -	 * The order of the rest of the list is irrelevant for us.
> +	 * Here we only care that entries for directories appear adjacent
> +	 * to and before files underneath the directory.  We can achieve
> +	 * that by pretending to add a trailing slash to every file and
> +	 * then sorting.  In other words, we do not want the natural
> +	 * sorting of
> +	 *     foo
> +	 *     foo.txt
> +	 *     foo/bar
> +	 * Instead, we want "foo" to sort as though it were "foo/", so that
> +	 * we instead get
> +	 *     foo.txt
> +	 *     foo
> +	 *     foo/bar
> +	 * To achieve this, we basically implement our own strcmp, except that
> +	 * if we get to the end of either string instead of comparing NUL to
> +	 * another character, we compare '/' to it.
> +	 *
> +	 * If this unusual "sort as though '/' were appended" perplexes
> +	 * you, perhaps it will help to note that this is not the final
> +	 * sort.  write_tree() will sort again without the trailing slash
> +	 * magic, but just on paths immediately under a given tree.

I find this comment to be helpful.

> +	 * The reason to not use df_name_compare directly was that it was
> +	 * just too expensive (we don't have the string lengths handy), so
> +	 * I had to reimplement it.

Just a hyper-nit I think first person works great in commit
messages, as the author's name is clearly listed in context.
Here, I'd prefer "so it was reimplemented" over "so I had to
reimplement it" as the author will not be present in context.

> +
> +	while (*one && (*one == *two)) {
> +		one++;
> +		two++;
> +	}
> +
> +	c1 = *one;
> +	if (!c1)
> +		c1 = '/';
> +
> +	c2 = *two;
> +	if (!c2)
> +		c2 = '/';

While I'm making other nits on this patch, perhaps this is
an appropriate place for some ternary operators to compress
the vertical space in this method:

	c1 = *one ? *one : '/';
	c2 = *two ? *two : '/';

> +	if (c1 == c2) {
> +		/* Getting here means one is a leading directory of the other */
> +		return (*one) ? 1 : -1;
> +	} else
> +		return c1-c2;

nit: "c1 - c2"

Thanks,
-Stolee

^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH v2 3/5] diffcore-rename: enable limiting rename detection to relevant destinations
  2021-06-01 14:58   ` [PATCH v2 3/5] diffcore-rename: enable limiting rename detection to relevant destinations Elijah Newren via GitGitGadget
@ 2021-06-03 12:54     ` Derrick Stolee
  2021-06-03 14:13       ` Elijah Newren
  0 siblings, 1 reply; 39+ messages in thread
From: Derrick Stolee @ 2021-06-03 12:54 UTC (permalink / raw)
  To: Elijah Newren via GitGitGadget, git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren

On 6/1/2021 10:58 AM, Elijah Newren via GitGitGadget wrote:
> From: Elijah Newren <newren@gmail.com>
> 
> Our former optimizations focused on limiting rename detection to a
> pre-specified set of relevant sources.  This was because the merge logic
> only had a way of knowing which sources were relevant.  However, other
> callers of rename detection might benefit from being able to limit
> rename detection to a known set of relevant destinations.  In
> particular, a properly implemented `git log --follow` might benefit from
> such an ability.

I would be interested in seeing such an improvement. It could also
help the batch-download of missing blobs in a partial clone situation
because it would only need the "deletes" portion of the diff, since we
only care about one "add" (we'd need that blob, too, of course).
 
> Since the code to implement such limiting is very similar to what we've
> already done, just implement it now even though we do not yet have any
> callers making use of this ability.

However, I'm not sure that this change is warranted without such an
integration. Perhaps keep this patch here on the list as a reference
for anyone who wants to do the `git log --follow` speedup? This person
can include "you in the future".

I'm just worried that without a consumer, this code has no automated
validation and can either be buggy now or become buggy in the future
before someone starts trying to use the logic.

Thanks,
-Stolee


^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff
  2021-06-01 14:58 ` [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
                     ` (4 preceding siblings ...)
  2021-06-01 14:58   ` [PATCH v2 5/5] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget
@ 2021-06-03 12:55   ` Derrick Stolee
  2021-06-04  4:39   ` [PATCH v3 0/4] " Elijah Newren via GitGitGadget
  6 siblings, 0 replies; 39+ messages in thread
From: Derrick Stolee @ 2021-06-03 12:55 UTC (permalink / raw)
  To: Elijah Newren via GitGitGadget, git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren

On 6/1/2021 10:58 AM, Elijah Newren via GitGitGadget wrote:
> This series depends on en/ort-perf-batch-11 textually, but is semantically
> independent of it.

I have read this series and really only found some nits in
Patch 1, but also think Patch 3 should be ejected until it can
be consumed by a full integration with a testable command.

The other patches look good to me.

Thanks,
-Stolee

^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH v2 3/5] diffcore-rename: enable limiting rename detection to relevant destinations
  2021-06-03 12:54     ` Derrick Stolee
@ 2021-06-03 14:13       ` Elijah Newren
  0 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren @ 2021-06-03 14:13 UTC (permalink / raw)
  To: Derrick Stolee
  Cc: Elijah Newren via GitGitGadget, Git Mailing List, Derrick Stolee,
	Jonathan Tan, Taylor Blau, René Scharfe

On Thu, Jun 3, 2021 at 5:54 AM Derrick Stolee <stolee@gmail.com> wrote:
>
> On 6/1/2021 10:58 AM, Elijah Newren via GitGitGadget wrote:
> > From: Elijah Newren <newren@gmail.com>
> >
> > Our former optimizations focused on limiting rename detection to a
> > pre-specified set of relevant sources.  This was because the merge logic
> > only had a way of knowing which sources were relevant.  However, other
> > callers of rename detection might benefit from being able to limit
> > rename detection to a known set of relevant destinations.  In
> > particular, a properly implemented `git log --follow` might benefit from
> > such an ability.
>
> I would be interested in seeing such an improvement. It could also
> help the batch-download of missing blobs in a partial clone situation
> because it would only need the "deletes" portion of the diff, since we
> only care about one "add" (we'd need that blob, too, of course).

Oh, good point.  And in order to work well with the new prefetching
improvements (which will be the next series submitted), I should
really rename remove_unneeded_paths_from_src() to
remove_unneeded_paths() and add a relevant_destinations parameter and
use it, instead of having the strset_contains() check in
diffcore_rename_extended.

> > Since the code to implement such limiting is very similar to what we've
> > already done, just implement it now even though we do not yet have any
> > callers making use of this ability.
>
> However, I'm not sure that this change is warranted without such an
> integration. Perhaps keep this patch here on the list as a reference
> for anyone who wants to do the `git log --follow` speedup? This person
> can include "you in the future".
>
> I'm just worried that without a consumer, this code has no automated
> validation and can either be buggy now or become buggy in the future
> before someone starts trying to use the logic.

Fair enough; I'll pull it out.

^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff
  2021-06-01 14:58 ` [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
                     ` (5 preceding siblings ...)
  2021-06-03 12:55   ` [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff Derrick Stolee
@ 2021-06-04  4:39   ` Elijah Newren via GitGitGadget
  2021-06-04  4:39     ` [PATCH v3 1/4] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
                       ` (5 more replies)
  6 siblings, 6 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-04  4:39 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Derrick Stolee, Elijah Newren

This series depends on en/ort-perf-batch-11 textually, but is semantically
independent of it.

Changes since v2:

 * Made suggested minor tweaks from Stolee on Patch 1
 * Dropped patch 3, for now
 * Added Stolee's Acked-by

Changes since v1 (all for the first patch):

 * Add more comments explaining the sorting function, its purpose, and how
   its expected to be called
 * Small style fixup
 * Switch back to using string_list_sort() instead of direct QSORT()

This short series has a few optimizations, but only one of which affects the
testcases of interest (namely, reducing our time spent on sorting an array).
It also fixes a few comments.

For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28), the
changes in just this series improves the performance as follows:

                     Before Series           After Series
no-renames:        5.622 s ±  0.059 s     5.235 s ±  0.042 s
mega-renames:     10.127 s ±  0.073 s     9.419 s ±  0.107 s
just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms


As a reminder, before any merge-ort/diffcore-rename performance work, the
performance results we started with were:

no-renames-am:      6.940 s ±  0.485 s
no-renames:        18.912 s ±  0.174 s
mega-renames:    5964.031 s ± 10.459 s
just-one-mega:    149.583 s ±  0.751 s


Elijah Newren (4):
  merge-ort: replace string_list_df_name_compare with faster alternative
  diffcore-rename: avoid unnecessary strdup'ing in break_idx
  Fix various issues found in comments
  merge-ort: miscellaneous touch-ups

 diffcore-rename.c                   |  4 +-
 merge-ort.c                         | 80 ++++++++++++++++++++---------
 t/t6423-merge-rename-directories.sh |  2 +-
 3 files changed, 60 insertions(+), 26 deletions(-)


base-commit: 76e253793c9a1d7fdd1836d5e4db26dabd3d713a
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-962%2Fnewren%2Fort-perf-batch-12-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-962/newren/ort-perf-batch-12-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/962

Range-diff vs v2:

 1:  c4a0f6a9510c ! 1:  f63ffc2a7c22 merge-ort: replace string_list_df_name_compare with faster alternative
     @@ Commit message
              just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms
      
          Signed-off-by: Elijah Newren <newren@gmail.com>
     +    Acked-by: Derrick Stolee <dstolee@microsoft.com>
      
       ## merge-ort.c ##
      @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,
     @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,
      -	 * sorting cause no problems for us.
      +	 * The reason to not use df_name_compare directly was that it was
      +	 * just too expensive (we don't have the string lengths handy), so
     -+	 * I had to reimplement it.
     ++	 * it was reimplemented.
       	 */
      -	int cmp = df_name_compare(one, onelen, S_IFDIR,
      -				  two, twolen, S_IFDIR);
     @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,
      +		two++;
      +	}
      +
     -+	c1 = *one;
     -+	if (!c1)
     -+		c1 = '/';
     -+
     -+	c2 = *two;
     -+	if (!c2)
     -+		c2 = '/';
     ++	c1 = *one ? *one : '/';
     ++	c2 = *two ? *two : '/';
      +
      +	if (c1 == c2) {
      +		/* Getting here means one is a leading directory of the other */
      +		return (*one) ? 1 : -1;
      +	} else
     -+		return c1-c2;
     ++		return c1 - c2;
       }
       
       static int read_oid_strbuf(struct merge_options *opt,
 2:  38713ed48273 ! 2:  cd13499a6ff5 diffcore-rename: avoid unnecessary strdup'ing in break_idx
     @@ Commit message
          unrelated optimization noted in passing while looking at the code.
      
          Signed-off-by: Elijah Newren <newren@gmail.com>
     +    Acked-by: Derrick Stolee <dstolee@microsoft.com>
      
       ## diffcore-rename.c ##
      @@ diffcore-rename.c: static void register_rename_src(struct diff_filepair *p)
 3:  45e1de5fe780 < -:  ------------ diffcore-rename: enable limiting rename detection to relevant destinations
 4:  2f26d7e935c0 ! 3:  91c0962a7d75 Fix various issues found in comments
     @@ Commit message
              function.  Update the comment now.
      
          Signed-off-by: Elijah Newren <newren@gmail.com>
     +    Acked-by: Derrick Stolee <dstolee@microsoft.com>
      
       ## diffcore-rename.c ##
      @@ diffcore-rename.c: void diffcore_rename_extended(struct diff_options *options,
 5:  7156f26ab299 ! 4:  01352fcdf3a9 merge-ort: miscellaneous touch-ups
     @@ Commit message
          of pushing these changes upstream.
      
          Signed-off-by: Elijah Newren <newren@gmail.com>
     +    Acked-by: Derrick Stolee <dstolee@microsoft.com>
      
       ## merge-ort.c ##
      @@ merge-ort.c: static void add_pair(struct merge_options *opt,

-- 
gitgitgadget

^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v3 1/4] merge-ort: replace string_list_df_name_compare with faster alternative
  2021-06-04  4:39   ` [PATCH v3 0/4] " Elijah Newren via GitGitGadget
@ 2021-06-04  4:39     ` Elijah Newren via GitGitGadget
  2021-06-04  4:39     ` [PATCH v3 2/4] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
                       ` (4 subsequent siblings)
  5 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-04  4:39 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Derrick Stolee, Elijah Newren, Elijah Newren

From: Elijah Newren <newren@gmail.com>

Gathering accumulated times from trace2 output on the mega-renames
testcase, I saw the following timings (where I'm only showing a few
lines to highlight the portions of interest):

    10.120 : label:incore_nonrecursive
        4.462 : ..label:process_entries
           3.143 : ....label:process_entries setup
              2.988 : ......label:plist special sort
           1.305 : ....label:processing
        2.604 : ..label:collect_merge_info
        2.018 : ..label:merge_start
        1.018 : ..label:renames

In the above output, note that the 4.462 seconds for process_entries was
split as 3.143 seconds for "process_entries setup" and 1.305 seconds for
"processing" (and a little time for other stuff removed from the
highlight).  Most of the "process_entries setup" time was spent on
"plist special sort" which corresponds to the following code:

    trace2_region_enter("merge", "plist special sort", opt->repo);
    plist.cmp = string_list_df_name_compare;
    string_list_sort(&plist);
    trace2_region_leave("merge", "plist special sort", opt->repo);

In other words, in a merge strategy that would be invoked by passing
"-sort" to either rebase or merge, sorting an array takes more time than
anything else.  Serves me right for naming my merge strategy this way.

Rewrite the comparison function in a way that does not require finding
out the lengths of the strings when comparing them.  While at it, tweak
the code for our specific case -- no need to handle a variety of modes,
for example.  The combination of these changes reduced the time spent in
"plist special sort" by ~25% in the mega-renames case.

For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:

                            Before                  After
    no-renames:        5.622 s ±  0.059 s     5.235 s ±  0.042 s
    mega-renames:     10.127 s ±  0.073 s     9.419 s ±  0.107 s
    just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms

Signed-off-by: Elijah Newren <newren@gmail.com>
Acked-by: Derrick Stolee <dstolee@microsoft.com>
---
 merge-ort.c | 67 +++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 47 insertions(+), 20 deletions(-)

diff --git a/merge-ort.c b/merge-ort.c
index 142d44d74d63..061f15701359 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2746,31 +2746,58 @@ static int detect_and_process_renames(struct merge_options *opt,
 
 /*** Function Grouping: functions related to process_entries() ***/
 
-static int string_list_df_name_compare(const char *one, const char *two)
+static int sort_dirs_next_to_their_children(const char *one, const char *two)
 {
-	int onelen = strlen(one);
-	int twolen = strlen(two);
+	unsigned char c1, c2;
+
 	/*
-	 * Here we only care that entries for D/F conflicts are
-	 * adjacent, in particular with the file of the D/F conflict
-	 * appearing before files below the corresponding directory.
-	 * The order of the rest of the list is irrelevant for us.
+	 * Here we only care that entries for directories appear adjacent
+	 * to and before files underneath the directory.  We can achieve
+	 * that by pretending to add a trailing slash to every file and
+	 * then sorting.  In other words, we do not want the natural
+	 * sorting of
+	 *     foo
+	 *     foo.txt
+	 *     foo/bar
+	 * Instead, we want "foo" to sort as though it were "foo/", so that
+	 * we instead get
+	 *     foo.txt
+	 *     foo
+	 *     foo/bar
+	 * To achieve this, we basically implement our own strcmp, except that
+	 * if we get to the end of either string instead of comparing NUL to
+	 * another character, we compare '/' to it.
+	 *
+	 * If this unusual "sort as though '/' were appended" perplexes
+	 * you, perhaps it will help to note that this is not the final
+	 * sort.  write_tree() will sort again without the trailing slash
+	 * magic, but just on paths immediately under a given tree.
 	 *
-	 * To achieve this, we sort with df_name_compare and provide
-	 * the mode S_IFDIR so that D/F conflicts will sort correctly.
-	 * We use the mode S_IFDIR for everything else for simplicity,
-	 * since in other cases any changes in their order due to
-	 * sorting cause no problems for us.
+	 * The reason to not use df_name_compare directly was that it was
+	 * just too expensive (we don't have the string lengths handy), so
+	 * it was reimplemented.
 	 */
-	int cmp = df_name_compare(one, onelen, S_IFDIR,
-				  two, twolen, S_IFDIR);
+
 	/*
-	 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
-	 * that 'foo' comes before 'foo/bar'.
+	 * NOTE: This function will never be called with two equal strings,
+	 * because it is used to sort the keys of a strmap, and strmaps have
+	 * unique keys by construction.  That simplifies our c1==c2 handling
+	 * below.
 	 */
-	if (cmp)
-		return cmp;
-	return onelen - twolen;
+
+	while (*one && (*one == *two)) {
+		one++;
+		two++;
+	}
+
+	c1 = *one ? *one : '/';
+	c2 = *two ? *two : '/';
+
+	if (c1 == c2) {
+		/* Getting here means one is a leading directory of the other */
+		return (*one) ? 1 : -1;
+	} else
+		return c1 - c2;
 }
 
 static int read_oid_strbuf(struct merge_options *opt,
@@ -3481,7 +3508,7 @@ static void process_entries(struct merge_options *opt,
 	trace2_region_leave("merge", "plist copy", opt->repo);
 
 	trace2_region_enter("merge", "plist special sort", opt->repo);
-	plist.cmp = string_list_df_name_compare;
+	plist.cmp = sort_dirs_next_to_their_children;
 	string_list_sort(&plist);
 	trace2_region_leave("merge", "plist special sort", opt->repo);
 
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v3 2/4] diffcore-rename: avoid unnecessary strdup'ing in break_idx
  2021-06-04  4:39   ` [PATCH v3 0/4] " Elijah Newren via GitGitGadget
  2021-06-04  4:39     ` [PATCH v3 1/4] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
@ 2021-06-04  4:39     ` Elijah Newren via GitGitGadget
  2021-06-04  4:39     ` [PATCH v3 3/4] Fix various issues found in comments Elijah Newren via GitGitGadget
                       ` (3 subsequent siblings)
  5 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-04  4:39 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Derrick Stolee, Elijah Newren, Elijah Newren

From: Elijah Newren <newren@gmail.com>

The keys of break_idx are strings from the diff_filepairs of
diff_queued_diff.  break_idx is only used in location_rename_dst(), and
that usage is always before any free'ing of the pairs (and thus the
strings in the pairs).  As such, there is no need to strdup these keys;
we can just reuse the existing strings as-is.

The merge logic doesn't make use of break detection, so this does not
affect the performance of any of my testcases.  It was just a minor
unrelated optimization noted in passing while looking at the code.

Signed-off-by: Elijah Newren <newren@gmail.com>
Acked-by: Derrick Stolee <dstolee@microsoft.com>
---
 diffcore-rename.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 3375e24659ea..e333a6d64791 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -54,7 +54,7 @@ static void register_rename_src(struct diff_filepair *p)
 	if (p->broken_pair) {
 		if (!break_idx) {
 			break_idx = xmalloc(sizeof(*break_idx));
-			strintmap_init(break_idx, -1);
+			strintmap_init_with_options(break_idx, -1, NULL, 0);
 		}
 		strintmap_set(break_idx, p->one->path, rename_dst_nr);
 	}
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v3 3/4] Fix various issues found in comments
  2021-06-04  4:39   ` [PATCH v3 0/4] " Elijah Newren via GitGitGadget
  2021-06-04  4:39     ` [PATCH v3 1/4] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
  2021-06-04  4:39     ` [PATCH v3 2/4] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
@ 2021-06-04  4:39     ` Elijah Newren via GitGitGadget
  2021-06-04  4:39     ` [PATCH v3 4/4] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget
                       ` (2 subsequent siblings)
  5 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-04  4:39 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Derrick Stolee, Elijah Newren, Elijah Newren

From: Elijah Newren <newren@gmail.com>

A random hodge-podge of incorrect or out-of-date comments that I found:

  * t6423 had a comment that has referred to the wrong test for years;
    fix it to refer to the right one.
  * diffcore-rename had a FIXME comment meant to remind myself to
    investigate if I could make another code change.  I later
    investigated and removed the FIXME, but while cherry-picking the
    patch to submit upstream I missed the later update.  Remove the
    comment now.
  * merge-ort had the early part of a comment for a function; I had
    meant to include the more involved description when I updated the
    function.  Update the comment now.

Signed-off-by: Elijah Newren <newren@gmail.com>
Acked-by: Derrick Stolee <dstolee@microsoft.com>
---
 diffcore-rename.c                   | 2 +-
 merge-ort.c                         | 8 +++++---
 t/t6423-merge-rename-directories.sh | 2 +-
 3 files changed, 7 insertions(+), 5 deletions(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index e333a6d64791..35378d84e8f1 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -1543,7 +1543,7 @@ void diffcore_rename_extended(struct diff_options *options,
 			/* all the usual ones need to be kept */
 			diff_q(&outq, p);
 		else
-			/* no need to keep unmodified pairs; FIXME: remove earlier? */
+			/* no need to keep unmodified pairs */
 			pair_to_free = p;
 
 		if (pair_to_free)
diff --git a/merge-ort.c b/merge-ort.c
index 061f15701359..2ec382e292a6 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2533,7 +2533,7 @@ static int compare_pairs(const void *a_, const void *b_)
 	return strcmp(a->one->path, b->one->path);
 }
 
-/* Call diffcore_rename() to compute which files have changed on given side */
+/* Call diffcore_rename() to update deleted/added pairs into rename pairs */
 static void detect_regular_renames(struct merge_options *opt,
 				   unsigned side_index)
 {
@@ -2586,8 +2586,10 @@ static void detect_regular_renames(struct merge_options *opt,
 }
 
 /*
- * Get information of all renames which occurred in 'side_pairs', discarding
- * non-renames.
+ * Get information of all renames which occurred in 'side_pairs', making use
+ * of any implicit directory renames in side_dir_renames (also making use of
+ * implicit directory renames rename_exclusions as needed by
+ * check_for_directory_rename()).  Add all (updated) renames into result.
  */
 static int collect_renames(struct merge_options *opt,
 			   struct diff_queue_struct *result,
diff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh
index be84d22419d9..e834b7e6efe0 100755
--- a/t/t6423-merge-rename-directories.sh
+++ b/t/t6423-merge-rename-directories.sh
@@ -454,7 +454,7 @@ test_expect_success '1f: Split a directory into two other directories' '
 #   the directory renamed, but the files within it. (see 1b)
 #
 #   If renames split a directory into two or more others, the directory
-#   with the most renames, "wins" (see 1c).  However, see the testcases
+#   with the most renames, "wins" (see 1f).  However, see the testcases
 #   in section 2, plus testcases 3a and 4a.
 ###########################################################################
 
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v3 4/4] merge-ort: miscellaneous touch-ups
  2021-06-04  4:39   ` [PATCH v3 0/4] " Elijah Newren via GitGitGadget
                       ` (2 preceding siblings ...)
  2021-06-04  4:39     ` [PATCH v3 3/4] Fix various issues found in comments Elijah Newren via GitGitGadget
@ 2021-06-04  4:39     ` Elijah Newren via GitGitGadget
  2021-06-04 13:11     ` [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff Derrick Stolee
  2021-06-08 16:11     ` [PATCH v4 " Elijah Newren via GitGitGadget
  5 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-04  4:39 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Derrick Stolee, Elijah Newren, Elijah Newren

From: Elijah Newren <newren@gmail.com>

Add some notes in the code about invariants with match_mask when adding
pairs.  Also add a comment that seems to have been left out in my work
of pushing these changes upstream.

Signed-off-by: Elijah Newren <newren@gmail.com>
Acked-by: Derrick Stolee <dstolee@microsoft.com>
---
 merge-ort.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/merge-ort.c b/merge-ort.c
index 2ec382e292a6..cfa751053b01 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -765,6 +765,7 @@ static void add_pair(struct merge_options *opt,
 	int names_idx = is_add ? side : 0;
 
 	if (is_add) {
+		assert(match_mask == 0 || match_mask == 6);
 		if (strset_contains(&renames->cached_target_names[side],
 				    pathname))
 			return;
@@ -772,6 +773,8 @@ static void add_pair(struct merge_options *opt,
 		unsigned content_relevant = (match_mask == 0);
 		unsigned location_relevant = (dir_rename_mask == 0x07);
 
+		assert(match_mask == 0 || match_mask == 3 || match_mask == 5);
+
 		/*
 		 * If pathname is found in cached_irrelevant[side] due to
 		 * previous pick but for this commit content is relevant,
@@ -3477,6 +3480,8 @@ static void process_entry(struct merge_options *opt,
 	 */
 	if (!ci->merged.clean)
 		strmap_put(&opt->priv->conflicted, path, ci);
+
+	/* Record metadata for ci->merged in dir_metadata */
 	record_entry_for_tree(dir_metadata, path, &ci->merged);
 }
 
-- 
gitgitgadget

^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff
  2021-06-04  4:39   ` [PATCH v3 0/4] " Elijah Newren via GitGitGadget
                       ` (3 preceding siblings ...)
  2021-06-04  4:39     ` [PATCH v3 4/4] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget
@ 2021-06-04 13:11     ` Derrick Stolee
  2021-06-04 15:48       ` Elijah Newren
  2021-06-08 16:11     ` [PATCH v4 " Elijah Newren via GitGitGadget
  5 siblings, 1 reply; 39+ messages in thread
From: Derrick Stolee @ 2021-06-04 13:11 UTC (permalink / raw)
  To: Elijah Newren via GitGitGadget, git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren

On 6/4/2021 12:39 AM, Elijah Newren via GitGitGadget wrote:
> This series depends on en/ort-perf-batch-11 textually, but is semantically
> independent of it.
> 
> Changes since v2:
> 
>  * Made suggested minor tweaks from Stolee on Patch 1
>  * Dropped patch 3, for now

With these changes, I think the code is good to go.

>  * Added Stolee's Acked-by
...
>  1:  c4a0f6a9510c ! 1:  f63ffc2a7c22 merge-ort: replace string_list_df_name_compare with faster alternative
>      @@ Commit message
>               just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms
>       
>           Signed-off-by: Elijah Newren <newren@gmail.com>
>      +    Acked-by: Derrick Stolee <dstolee@microsoft.com>

I believe the sign-off should always be the last thing in
the message. Perhaps Junio is willing to fix this without a
re-roll?

Feel free to replace Acked-by with Reviewed-by.

Thanks,
-Stolee

^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff
  2021-06-04 13:11     ` [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff Derrick Stolee
@ 2021-06-04 15:48       ` Elijah Newren
  2021-06-04 16:30         ` Elijah Newren
  2021-06-04 16:35         ` Jeff King
  0 siblings, 2 replies; 39+ messages in thread
From: Elijah Newren @ 2021-06-04 15:48 UTC (permalink / raw)
  To: Derrick Stolee
  Cc: Elijah Newren via GitGitGadget, Git Mailing List, Derrick Stolee,
	Jonathan Tan, Taylor Blau, René Scharfe

On Fri, Jun 4, 2021 at 6:11 AM Derrick Stolee <stolee@gmail.com> wrote:
>
> On 6/4/2021 12:39 AM, Elijah Newren via GitGitGadget wrote:
> > This series depends on en/ort-perf-batch-11 textually, but is semantically
> > independent of it.
> >
> > Changes since v2:
> >
> >  * Made suggested minor tweaks from Stolee on Patch 1
> >  * Dropped patch 3, for now
>
> With these changes, I think the code is good to go.
>
> >  * Added Stolee's Acked-by
> ...
> >  1:  c4a0f6a9510c ! 1:  f63ffc2a7c22 merge-ort: replace string_list_df_name_compare with faster alternative
> >      @@ Commit message
> >               just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms
> >
> >           Signed-off-by: Elijah Newren <newren@gmail.com>
> >      +    Acked-by: Derrick Stolee <dstolee@microsoft.com>
>
> I believe the sign-off should always be the last thing in
> the message. Perhaps Junio is willing to fix this without a
> re-roll?

Interesting, this is the first I've ever heard of such a requirement,
and I've submitted patches this way numerous times and have seen
others do it.  A quick search through git.git history says there are
5133 commits that place such trailers before the author's
Signed-off-by, and 1175 that place them after.  While the former is
clearly more common, and some of the latter could have been Junio
adding trailers while applying the patches, there still seem like
plenty of counter-examples suggesting that there is no rule here.

Digging into Documentation/SubmittingPatches, I find three places that
suggest or state something about placement of trailers.

'''
[[real-name]]
Also notice that a real name is used in the `Signed-off-by` trailer. Please
don't hide your real name.

[[commit-trailers]]
If you like, you can put extra tags at the end:
'''

Which isn't definitive but seems like it could be easy to accidentally
construe as a rule that says the opposite, namely that other trailers
come after the Signed-off-by.  Another part of the document states:

'''
you add a "Signed-off-by" trailer to your commit, that looks like
this:

....
        Signed-off-by: Random J Developer <random@developer.example.org>
....
'''

which possibly suggests that the relative location compared to other
trailers does not matter.  The wording in that document that comes
closest to your interpretation is

'''
At the beginning of the
patch should come your commit message, ending with the
`Signed-off-by` trailers'''
'''

but if it had really meant to convey the rule you suggest here, it
should have said "ending with your Signed-off-by trailer"; the
"trailers" here to me suggest the phrasing here has a totally
different meaning than your rule.

So, if "Signed-off-by should come last" is a rule, then neither
existing practice nor our documentation seem to cover it.  I'll assume
it's not a rule for now.

> Feel free to replace Acked-by with Reviewed-by.

Thanks.

^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff
  2021-06-04 15:48       ` Elijah Newren
@ 2021-06-04 16:30         ` Elijah Newren
  2021-06-04 16:35         ` Jeff King
  1 sibling, 0 replies; 39+ messages in thread
From: Elijah Newren @ 2021-06-04 16:30 UTC (permalink / raw)
  To: Derrick Stolee
  Cc: Elijah Newren via GitGitGadget, Git Mailing List, Derrick Stolee,
	Jonathan Tan, Taylor Blau, René Scharfe

On Fri, Jun 4, 2021 at 8:48 AM Elijah Newren <newren@gmail.com> wrote:
>
> On Fri, Jun 4, 2021 at 6:11 AM Derrick Stolee <stolee@gmail.com> wrote:
> >
> > On 6/4/2021 12:39 AM, Elijah Newren via GitGitGadget wrote:

> > >  * Added Stolee's Acked-by
> > ...
> > >  1:  c4a0f6a9510c ! 1:  f63ffc2a7c22 merge-ort: replace string_list_df_name_compare with faster alternative
> > >      @@ Commit message
> > >               just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms
> > >
> > >           Signed-off-by: Elijah Newren <newren@gmail.com>
> > >      +    Acked-by: Derrick Stolee <dstolee@microsoft.com>
> >
> > I believe the sign-off should always be the last thing in
> > the message. Perhaps Junio is willing to fix this without a
> > re-roll?
>
> Interesting, this is the first I've ever heard of such a requirement,
> and I've submitted patches this way numerous times and have seen
> others do it.  A quick search through git.git history says there are
> 5133 commits that place such trailers before the author's
> Signed-off-by, and 1175 that place them after.  While the former is

Sorry, there was a bug in my script, found while running it on the
linux kernel (where the Signed-off-by stuff came from) to see if it
was different.  The corrected numbers are:

Author Signed-off-by comes after all non-Signed-off-by trailers: 2990
non-Signed-off-by trailers follow the Author's Signed-off-by line: 3069

So, this suggests it's even less of a rule.  For those curious, the
Linux kernel has these numbers:

Author Signed-off-by comes after all non-Signed-off-by trailers: 83530
non-Signed-off-by trailers follow the Author's Signed-off-by line: 199778

> ...
> So, if "Signed-off-by should come last" is a rule, then neither
> existing practice nor our documentation seem to cover it.  I'll assume
> it's not a rule for now.

^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff
  2021-06-04 15:48       ` Elijah Newren
  2021-06-04 16:30         ` Elijah Newren
@ 2021-06-04 16:35         ` Jeff King
  2021-06-04 18:42           ` Derrick Stolee
  1 sibling, 1 reply; 39+ messages in thread
From: Jeff King @ 2021-06-04 16:35 UTC (permalink / raw)
  To: Elijah Newren
  Cc: Derrick Stolee, Elijah Newren via GitGitGadget, Git Mailing List,
	Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe

On Fri, Jun 04, 2021 at 08:48:21AM -0700, Elijah Newren wrote:

> > >           Signed-off-by: Elijah Newren <newren@gmail.com>
> > >      +    Acked-by: Derrick Stolee <dstolee@microsoft.com>
> >
> > I believe the sign-off should always be the last thing in
> > the message. Perhaps Junio is willing to fix this without a
> > re-roll?
> 
> Interesting, this is the first I've ever heard of such a requirement,
> and I've submitted patches this way numerous times and have seen
> others do it.  A quick search through git.git history says there are
> 5133 commits that place such trailers before the author's
> Signed-off-by, and 1175 that place them after.  While the former is
> clearly more common, and some of the latter could have been Junio
> adding trailers while applying the patches, there still seem like
> plenty of counter-examples suggesting that there is no rule here.

I don't think there's a hard rule here. The usual advice (which I also
didn't find documented from a quick grep, but hopefully is kind of
intuitive) is that trailers should be chronological.

So if you picked up a patch from person X who signed off, then you
modified and signed off the result, then Junio signed off after
applying, we'd expect that chain of custody to be represented by reading
top to bottom. And that's what happens if you use "am -s", "commit -s",
etc.

Whether "Acked-by" happens after the author signs off or not is
debatable. Obviously it happens after the version of the patch that is
sent out. But if you re-send with an Acked-by, is the signoff your one
from before that happened first, or a new one that happened as you sent
out the patch? Perhaps a question for the philosophers. ;)

Anyway, I think it is perfectly fine either way (as your numbers
indicate).

-Peff

^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff
  2021-06-04 16:35         ` Jeff King
@ 2021-06-04 18:42           ` Derrick Stolee
  2021-06-04 19:43             ` Elijah Newren
  2021-06-04 19:53             ` Jeff King
  0 siblings, 2 replies; 39+ messages in thread
From: Derrick Stolee @ 2021-06-04 18:42 UTC (permalink / raw)
  To: Jeff King, Elijah Newren
  Cc: Elijah Newren via GitGitGadget, Git Mailing List, Derrick Stolee,
	Jonathan Tan, Taylor Blau, René Scharfe

On 6/4/2021 12:35 PM, Jeff King wrote:
> On Fri, Jun 04, 2021 at 08:48:21AM -0700, Elijah Newren wrote:
> 
>>>>           Signed-off-by: Elijah Newren <newren@gmail.com>
>>>>      +    Acked-by: Derrick Stolee <dstolee@microsoft.com>
>>>
>>> I believe the sign-off should always be the last thing in
>>> the message. Perhaps Junio is willing to fix this without a
>>> re-roll?
>>
>> Interesting, this is the first I've ever heard of such a requirement,
>> and I've submitted patches this way numerous times and have seen
>> others do it.  A quick search through git.git history says there are
>> 5133 commits that place such trailers before the author's
>> Signed-off-by, and 1175 that place them after.  While the former is
>> clearly more common, and some of the latter could have been Junio
>> adding trailers while applying the patches, there still seem like
>> plenty of counter-examples suggesting that there is no rule here.
> 
> I don't think there's a hard rule here. The usual advice (which I also
> didn't find documented from a quick grep, but hopefully is kind of
> intuitive) is that trailers should be chronological.
> 
> So if you picked up a patch from person X who signed off, then you
> modified and signed off the result, then Junio signed off after
> applying, we'd expect that chain of custody to be represented by reading
> top to bottom. And that's what happens if you use "am -s", "commit -s",
> etc.
> 
> Whether "Acked-by" happens after the author signs off or not is
> debatable. Obviously it happens after the version of the patch that is
> sent out. But if you re-send with an Acked-by, is the signoff your one
> from before that happened first, or a new one that happened as you sent
> out the patch? Perhaps a question for the philosophers. ;)

I guess I was just interpreting that the "Acked-by" was part of
the content you created, and hence it should be covered by the
sign-off. I can imagine that if Junio added it, then it would be
after your sign-off but before his.
 
> Anyway, I think it is perfectly fine either way (as your numbers
> indicate).

I agree. I didn't mean to make a big deal of it.

Thanks,
-Stolee

^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff
  2021-06-04 18:42           ` Derrick Stolee
@ 2021-06-04 19:43             ` Elijah Newren
  2021-06-04 19:53             ` Jeff King
  1 sibling, 0 replies; 39+ messages in thread
From: Elijah Newren @ 2021-06-04 19:43 UTC (permalink / raw)
  To: Derrick Stolee
  Cc: Jeff King, Elijah Newren via GitGitGadget, Git Mailing List,
	Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe

On Fri, Jun 4, 2021 at 11:42 AM Derrick Stolee <stolee@gmail.com> wrote:
>
> On 6/4/2021 12:35 PM, Jeff King wrote:
> > On Fri, Jun 04, 2021 at 08:48:21AM -0700, Elijah Newren wrote:
> >
> >>>>           Signed-off-by: Elijah Newren <newren@gmail.com>
> >>>>      +    Acked-by: Derrick Stolee <dstolee@microsoft.com>
> >>>
> >>> I believe the sign-off should always be the last thing in
> >>> the message. Perhaps Junio is willing to fix this without a
> >>> re-roll?
> >>
> >> Interesting, this is the first I've ever heard of such a requirement,
> >> and I've submitted patches this way numerous times and have seen
> >> others do it.  A quick search through git.git history says there are
> >> 5133 commits that place such trailers before the author's
> >> Signed-off-by, and 1175 that place them after.  While the former is
> >> clearly more common, and some of the latter could have been Junio
> >> adding trailers while applying the patches, there still seem like
> >> plenty of counter-examples suggesting that there is no rule here.
> >
> > I don't think there's a hard rule here. The usual advice (which I also
> > didn't find documented from a quick grep, but hopefully is kind of
> > intuitive) is that trailers should be chronological.
> >
> > So if you picked up a patch from person X who signed off, then you
> > modified and signed off the result, then Junio signed off after
> > applying, we'd expect that chain of custody to be represented by reading
> > top to bottom. And that's what happens if you use "am -s", "commit -s",
> > etc.
> >
> > Whether "Acked-by" happens after the author signs off or not is
> > debatable. Obviously it happens after the version of the patch that is
> > sent out. But if you re-send with an Acked-by, is the signoff your one
> > from before that happened first, or a new one that happened as you sent
> > out the patch? Perhaps a question for the philosophers. ;)
>
> I guess I was just interpreting that the "Acked-by" was part of
> the content you created, and hence it should be covered by the
> sign-off. I can imagine that if Junio added it, then it would be
> after your sign-off but before his.
>
> > Anyway, I think it is perfectly fine either way (as your numbers
> > indicate).
>
> I agree. I didn't mean to make a big deal of it.

Sorry, it was me who made a big deal out of it.  I was just really
surprised that I had missed another rule (you correctly caught one I
did miss on a recent other series I submitted), and so I thought it
was prudent to go digging and see how I had _also_ missed this rule
and refresh myself on the rules in general.  And once I did that,
although I felt this one probably didn't qualify, I thought it was
useful to share what I found and highlight what I thought needed
clarification if I was wrong.

^ permalink raw reply	[flat|nested] 39+ messages in thread

* Re: [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff
  2021-06-04 18:42           ` Derrick Stolee
  2021-06-04 19:43             ` Elijah Newren
@ 2021-06-04 19:53             ` Jeff King
  1 sibling, 0 replies; 39+ messages in thread
From: Jeff King @ 2021-06-04 19:53 UTC (permalink / raw)
  To: Derrick Stolee
  Cc: Elijah Newren, Elijah Newren via GitGitGadget, Git Mailing List,
	Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe

On Fri, Jun 04, 2021 at 02:42:03PM -0400, Derrick Stolee wrote:

> > Whether "Acked-by" happens after the author signs off or not is
> > debatable. Obviously it happens after the version of the patch that is
> > sent out. But if you re-send with an Acked-by, is the signoff your one
> > from before that happened first, or a new one that happened as you sent
> > out the patch? Perhaps a question for the philosophers. ;)
> 
> I guess I was just interpreting that the "Acked-by" was part of
> the content you created, and hence it should be covered by the
> sign-off. I can imagine that if Junio added it, then it would be
> after your sign-off but before his.

FWIW, that's how I interpret it, too. I was curious how it looks for my
own patches, which is easy-ish to dig up with:

  git log --author=peff --grep=Acked-by --format='%H%n%(trailers)'

They're mostly after my signoff there, but I think that's because I very
rarely add in the Ack, and mostly Junio does it (likewise for
Reviewed-by).

My workflow is maybe a little different than others, too, in that I very
rarely signoff patches in my repo, but add it via "format-patch -s" when
sending them out (so naturally it would come after anything I had
typed).

> > Anyway, I think it is perfectly fine either way (as your numbers
> > indicate).
> 
> I agree. I didn't mean to make a big deal of it.

It was a little bit of an interesting diversion, though. :)

-Peff

^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v4 0/4] Optimization batch 12: miscellaneous unthemed stuff
  2021-06-04  4:39   ` [PATCH v3 0/4] " Elijah Newren via GitGitGadget
                       ` (4 preceding siblings ...)
  2021-06-04 13:11     ` [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff Derrick Stolee
@ 2021-06-08 16:11     ` Elijah Newren via GitGitGadget
  2021-06-08 16:11       ` [PATCH v4 1/4] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
                         ` (3 more replies)
  5 siblings, 4 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-08 16:11 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Derrick Stolee, Jeff King, Elijah Newren

This series depends on en/ort-perf-batch-11 textually, but is semantically
independent of it.

Changes since v3:

 * Changed Acked-by from Stolee to Reviewed-by.

Changes since v2:

 * Made suggested minor tweaks from Stolee on Patch 1
 * Dropped patch 3, for now
 * Added Stolee's Acked-by

Changes since v1 (all for the first patch):

 * Add more comments explaining the sorting function, its purpose, and how
   its expected to be called
 * Small style fixup
 * Switch back to using string_list_sort() instead of direct QSORT()

This short series has a few optimizations, but only one of which affects the
testcases of interest (namely, reducing our time spent on sorting an array).
It also fixes a few comments.

For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28), the
changes in just this series improves the performance as follows:

                     Before Series           After Series
no-renames:        5.622 s ±  0.059 s     5.235 s ±  0.042 s
mega-renames:     10.127 s ±  0.073 s     9.419 s ±  0.107 s
just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms


As a reminder, before any merge-ort/diffcore-rename performance work, the
performance results we started with were:

no-renames-am:      6.940 s ±  0.485 s
no-renames:        18.912 s ±  0.174 s
mega-renames:    5964.031 s ± 10.459 s
just-one-mega:    149.583 s ±  0.751 s


Elijah Newren (4):
  merge-ort: replace string_list_df_name_compare with faster alternative
  diffcore-rename: avoid unnecessary strdup'ing in break_idx
  Fix various issues found in comments
  merge-ort: miscellaneous touch-ups

 diffcore-rename.c                   |  4 +-
 merge-ort.c                         | 80 ++++++++++++++++++++---------
 t/t6423-merge-rename-directories.sh |  2 +-
 3 files changed, 60 insertions(+), 26 deletions(-)


base-commit: 76e253793c9a1d7fdd1836d5e4db26dabd3d713a
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-962%2Fnewren%2Fort-perf-batch-12-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-962/newren/ort-perf-batch-12-v4
Pull-Request: https://github.com/gitgitgadget/git/pull/962

Range-diff vs v3:

 1:  f63ffc2a7c22 ! 1:  140c1e89e0ec merge-ort: replace string_list_df_name_compare with faster alternative
     @@ Commit message
              just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms
      
          Signed-off-by: Elijah Newren <newren@gmail.com>
     -    Acked-by: Derrick Stolee <dstolee@microsoft.com>
     +    Reviewed-by: Derrick Stolee <dstolee@microsoft.com>
      
       ## merge-ort.c ##
      @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,
 2:  cd13499a6ff5 ! 2:  be858c46cfe7 diffcore-rename: avoid unnecessary strdup'ing in break_idx
     @@ Commit message
          unrelated optimization noted in passing while looking at the code.
      
          Signed-off-by: Elijah Newren <newren@gmail.com>
     -    Acked-by: Derrick Stolee <dstolee@microsoft.com>
     +    Reviewed-by: Derrick Stolee <dstolee@microsoft.com>
      
       ## diffcore-rename.c ##
      @@ diffcore-rename.c: static void register_rename_src(struct diff_filepair *p)
 3:  91c0962a7d75 ! 3:  55c0f2c4560a Fix various issues found in comments
     @@ Commit message
              function.  Update the comment now.
      
          Signed-off-by: Elijah Newren <newren@gmail.com>
     -    Acked-by: Derrick Stolee <dstolee@microsoft.com>
     +    Reviewed-by: Derrick Stolee <dstolee@microsoft.com>
      
       ## diffcore-rename.c ##
      @@ diffcore-rename.c: void diffcore_rename_extended(struct diff_options *options,
 4:  01352fcdf3a9 ! 4:  6de569e6ac49 merge-ort: miscellaneous touch-ups
     @@ Commit message
          of pushing these changes upstream.
      
          Signed-off-by: Elijah Newren <newren@gmail.com>
     -    Acked-by: Derrick Stolee <dstolee@microsoft.com>
     +    Reviewed-by: Derrick Stolee <dstolee@microsoft.com>
      
       ## merge-ort.c ##
      @@ merge-ort.c: static void add_pair(struct merge_options *opt,

-- 
gitgitgadget

^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v4 1/4] merge-ort: replace string_list_df_name_compare with faster alternative
  2021-06-08 16:11     ` [PATCH v4 " Elijah Newren via GitGitGadget
@ 2021-06-08 16:11       ` Elijah Newren via GitGitGadget
  2021-06-08 16:11       ` [PATCH v4 2/4] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
                         ` (2 subsequent siblings)
  3 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-08 16:11 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Derrick Stolee, Jeff King, Elijah Newren,
	Elijah Newren

From: Elijah Newren <newren@gmail.com>

Gathering accumulated times from trace2 output on the mega-renames
testcase, I saw the following timings (where I'm only showing a few
lines to highlight the portions of interest):

    10.120 : label:incore_nonrecursive
        4.462 : ..label:process_entries
           3.143 : ....label:process_entries setup
              2.988 : ......label:plist special sort
           1.305 : ....label:processing
        2.604 : ..label:collect_merge_info
        2.018 : ..label:merge_start
        1.018 : ..label:renames

In the above output, note that the 4.462 seconds for process_entries was
split as 3.143 seconds for "process_entries setup" and 1.305 seconds for
"processing" (and a little time for other stuff removed from the
highlight).  Most of the "process_entries setup" time was spent on
"plist special sort" which corresponds to the following code:

    trace2_region_enter("merge", "plist special sort", opt->repo);
    plist.cmp = string_list_df_name_compare;
    string_list_sort(&plist);
    trace2_region_leave("merge", "plist special sort", opt->repo);

In other words, in a merge strategy that would be invoked by passing
"-sort" to either rebase or merge, sorting an array takes more time than
anything else.  Serves me right for naming my merge strategy this way.

Rewrite the comparison function in a way that does not require finding
out the lengths of the strings when comparing them.  While at it, tweak
the code for our specific case -- no need to handle a variety of modes,
for example.  The combination of these changes reduced the time spent in
"plist special sort" by ~25% in the mega-renames case.

For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:

                            Before                  After
    no-renames:        5.622 s ±  0.059 s     5.235 s ±  0.042 s
    mega-renames:     10.127 s ±  0.073 s     9.419 s ±  0.107 s
    just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms

Signed-off-by: Elijah Newren <newren@gmail.com>
Reviewed-by: Derrick Stolee <dstolee@microsoft.com>
---
 merge-ort.c | 67 +++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 47 insertions(+), 20 deletions(-)

diff --git a/merge-ort.c b/merge-ort.c
index 142d44d74d63..061f15701359 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2746,31 +2746,58 @@ static int detect_and_process_renames(struct merge_options *opt,
 
 /*** Function Grouping: functions related to process_entries() ***/
 
-static int string_list_df_name_compare(const char *one, const char *two)
+static int sort_dirs_next_to_their_children(const char *one, const char *two)
 {
-	int onelen = strlen(one);
-	int twolen = strlen(two);
+	unsigned char c1, c2;
+
 	/*
-	 * Here we only care that entries for D/F conflicts are
-	 * adjacent, in particular with the file of the D/F conflict
-	 * appearing before files below the corresponding directory.
-	 * The order of the rest of the list is irrelevant for us.
+	 * Here we only care that entries for directories appear adjacent
+	 * to and before files underneath the directory.  We can achieve
+	 * that by pretending to add a trailing slash to every file and
+	 * then sorting.  In other words, we do not want the natural
+	 * sorting of
+	 *     foo
+	 *     foo.txt
+	 *     foo/bar
+	 * Instead, we want "foo" to sort as though it were "foo/", so that
+	 * we instead get
+	 *     foo.txt
+	 *     foo
+	 *     foo/bar
+	 * To achieve this, we basically implement our own strcmp, except that
+	 * if we get to the end of either string instead of comparing NUL to
+	 * another character, we compare '/' to it.
+	 *
+	 * If this unusual "sort as though '/' were appended" perplexes
+	 * you, perhaps it will help to note that this is not the final
+	 * sort.  write_tree() will sort again without the trailing slash
+	 * magic, but just on paths immediately under a given tree.
 	 *
-	 * To achieve this, we sort with df_name_compare and provide
-	 * the mode S_IFDIR so that D/F conflicts will sort correctly.
-	 * We use the mode S_IFDIR for everything else for simplicity,
-	 * since in other cases any changes in their order due to
-	 * sorting cause no problems for us.
+	 * The reason to not use df_name_compare directly was that it was
+	 * just too expensive (we don't have the string lengths handy), so
+	 * it was reimplemented.
 	 */
-	int cmp = df_name_compare(one, onelen, S_IFDIR,
-				  two, twolen, S_IFDIR);
+
 	/*
-	 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
-	 * that 'foo' comes before 'foo/bar'.
+	 * NOTE: This function will never be called with two equal strings,
+	 * because it is used to sort the keys of a strmap, and strmaps have
+	 * unique keys by construction.  That simplifies our c1==c2 handling
+	 * below.
 	 */
-	if (cmp)
-		return cmp;
-	return onelen - twolen;
+
+	while (*one && (*one == *two)) {
+		one++;
+		two++;
+	}
+
+	c1 = *one ? *one : '/';
+	c2 = *two ? *two : '/';
+
+	if (c1 == c2) {
+		/* Getting here means one is a leading directory of the other */
+		return (*one) ? 1 : -1;
+	} else
+		return c1 - c2;
 }
 
 static int read_oid_strbuf(struct merge_options *opt,
@@ -3481,7 +3508,7 @@ static void process_entries(struct merge_options *opt,
 	trace2_region_leave("merge", "plist copy", opt->repo);
 
 	trace2_region_enter("merge", "plist special sort", opt->repo);
-	plist.cmp = string_list_df_name_compare;
+	plist.cmp = sort_dirs_next_to_their_children;
 	string_list_sort(&plist);
 	trace2_region_leave("merge", "plist special sort", opt->repo);
 
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v4 2/4] diffcore-rename: avoid unnecessary strdup'ing in break_idx
  2021-06-08 16:11     ` [PATCH v4 " Elijah Newren via GitGitGadget
  2021-06-08 16:11       ` [PATCH v4 1/4] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
@ 2021-06-08 16:11       ` Elijah Newren via GitGitGadget
  2021-06-08 16:11       ` [PATCH v4 3/4] Fix various issues found in comments Elijah Newren via GitGitGadget
  2021-06-08 16:11       ` [PATCH v4 4/4] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget
  3 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-08 16:11 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Derrick Stolee, Jeff King, Elijah Newren,
	Elijah Newren

From: Elijah Newren <newren@gmail.com>

The keys of break_idx are strings from the diff_filepairs of
diff_queued_diff.  break_idx is only used in location_rename_dst(), and
that usage is always before any free'ing of the pairs (and thus the
strings in the pairs).  As such, there is no need to strdup these keys;
we can just reuse the existing strings as-is.

The merge logic doesn't make use of break detection, so this does not
affect the performance of any of my testcases.  It was just a minor
unrelated optimization noted in passing while looking at the code.

Signed-off-by: Elijah Newren <newren@gmail.com>
Reviewed-by: Derrick Stolee <dstolee@microsoft.com>
---
 diffcore-rename.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 3375e24659ea..e333a6d64791 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -54,7 +54,7 @@ static void register_rename_src(struct diff_filepair *p)
 	if (p->broken_pair) {
 		if (!break_idx) {
 			break_idx = xmalloc(sizeof(*break_idx));
-			strintmap_init(break_idx, -1);
+			strintmap_init_with_options(break_idx, -1, NULL, 0);
 		}
 		strintmap_set(break_idx, p->one->path, rename_dst_nr);
 	}
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v4 3/4] Fix various issues found in comments
  2021-06-08 16:11     ` [PATCH v4 " Elijah Newren via GitGitGadget
  2021-06-08 16:11       ` [PATCH v4 1/4] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
  2021-06-08 16:11       ` [PATCH v4 2/4] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
@ 2021-06-08 16:11       ` Elijah Newren via GitGitGadget
  2021-06-08 16:11       ` [PATCH v4 4/4] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget
  3 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-08 16:11 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Derrick Stolee, Jeff King, Elijah Newren,
	Elijah Newren

From: Elijah Newren <newren@gmail.com>

A random hodge-podge of incorrect or out-of-date comments that I found:

  * t6423 had a comment that has referred to the wrong test for years;
    fix it to refer to the right one.
  * diffcore-rename had a FIXME comment meant to remind myself to
    investigate if I could make another code change.  I later
    investigated and removed the FIXME, but while cherry-picking the
    patch to submit upstream I missed the later update.  Remove the
    comment now.
  * merge-ort had the early part of a comment for a function; I had
    meant to include the more involved description when I updated the
    function.  Update the comment now.

Signed-off-by: Elijah Newren <newren@gmail.com>
Reviewed-by: Derrick Stolee <dstolee@microsoft.com>
---
 diffcore-rename.c                   | 2 +-
 merge-ort.c                         | 8 +++++---
 t/t6423-merge-rename-directories.sh | 2 +-
 3 files changed, 7 insertions(+), 5 deletions(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index e333a6d64791..35378d84e8f1 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -1543,7 +1543,7 @@ void diffcore_rename_extended(struct diff_options *options,
 			/* all the usual ones need to be kept */
 			diff_q(&outq, p);
 		else
-			/* no need to keep unmodified pairs; FIXME: remove earlier? */
+			/* no need to keep unmodified pairs */
 			pair_to_free = p;
 
 		if (pair_to_free)
diff --git a/merge-ort.c b/merge-ort.c
index 061f15701359..2ec382e292a6 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2533,7 +2533,7 @@ static int compare_pairs(const void *a_, const void *b_)
 	return strcmp(a->one->path, b->one->path);
 }
 
-/* Call diffcore_rename() to compute which files have changed on given side */
+/* Call diffcore_rename() to update deleted/added pairs into rename pairs */
 static void detect_regular_renames(struct merge_options *opt,
 				   unsigned side_index)
 {
@@ -2586,8 +2586,10 @@ static void detect_regular_renames(struct merge_options *opt,
 }
 
 /*
- * Get information of all renames which occurred in 'side_pairs', discarding
- * non-renames.
+ * Get information of all renames which occurred in 'side_pairs', making use
+ * of any implicit directory renames in side_dir_renames (also making use of
+ * implicit directory renames rename_exclusions as needed by
+ * check_for_directory_rename()).  Add all (updated) renames into result.
  */
 static int collect_renames(struct merge_options *opt,
 			   struct diff_queue_struct *result,
diff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh
index be84d22419d9..e834b7e6efe0 100755
--- a/t/t6423-merge-rename-directories.sh
+++ b/t/t6423-merge-rename-directories.sh
@@ -454,7 +454,7 @@ test_expect_success '1f: Split a directory into two other directories' '
 #   the directory renamed, but the files within it. (see 1b)
 #
 #   If renames split a directory into two or more others, the directory
-#   with the most renames, "wins" (see 1c).  However, see the testcases
+#   with the most renames, "wins" (see 1f).  However, see the testcases
 #   in section 2, plus testcases 3a and 4a.
 ###########################################################################
 
-- 
gitgitgadget


^ permalink raw reply	[flat|nested] 39+ messages in thread

* [PATCH v4 4/4] merge-ort: miscellaneous touch-ups
  2021-06-08 16:11     ` [PATCH v4 " Elijah Newren via GitGitGadget
                         ` (2 preceding siblings ...)
  2021-06-08 16:11       ` [PATCH v4 3/4] Fix various issues found in comments Elijah Newren via GitGitGadget
@ 2021-06-08 16:11       ` Elijah Newren via GitGitGadget
  3 siblings, 0 replies; 39+ messages in thread
From: Elijah Newren via GitGitGadget @ 2021-06-08 16:11 UTC (permalink / raw)
  To: git
  Cc: Derrick Stolee, Jonathan Tan, Taylor Blau, René Scharfe,
	Elijah Newren, Derrick Stolee, Jeff King, Elijah Newren,
	Elijah Newren

From: Elijah Newren <newren@gmail.com>

Add some notes in the code about invariants with match_mask when adding
pairs.  Also add a comment that seems to have been left out in my work
of pushing these changes upstream.

Signed-off-by: Elijah Newren <newren@gmail.com>
Reviewed-by: Derrick Stolee <dstolee@microsoft.com>
---
 merge-ort.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/merge-ort.c b/merge-ort.c
index 2ec382e292a6..cfa751053b01 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -765,6 +765,7 @@ static void add_pair(struct merge_options *opt,
 	int names_idx = is_add ? side : 0;
 
 	if (is_add) {
+		assert(match_mask == 0 || match_mask == 6);
 		if (strset_contains(&renames->cached_target_names[side],
 				    pathname))
 			return;
@@ -772,6 +773,8 @@ static void add_pair(struct merge_options *opt,
 		unsigned content_relevant = (match_mask == 0);
 		unsigned location_relevant = (dir_rename_mask == 0x07);
 
+		assert(match_mask == 0 || match_mask == 3 || match_mask == 5);
+
 		/*
 		 * If pathname is found in cached_irrelevant[side] due to
 		 * previous pick but for this commit content is relevant,
@@ -3477,6 +3480,8 @@ static void process_entry(struct merge_options *opt,
 	 */
 	if (!ci->merged.clean)
 		strmap_put(&opt->priv->conflicted, path, ci);
+
+	/* Record metadata for ci->merged in dir_metadata */
 	record_entry_for_tree(dir_metadata, path, &ci->merged);
 }
 
-- 
gitgitgadget

^ permalink raw reply	[flat|nested] 39+ messages in thread

end of thread, other threads:[~2021-06-08 16:13 UTC | newest]

Thread overview: 39+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-05-27  8:37 [PATCH 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
2021-05-27  8:37 ` [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
2021-05-27 21:00   ` René Scharfe
2021-05-27 22:47     ` Elijah Newren
2021-05-28 16:12       ` René Scharfe
2021-05-28 18:09         ` Elijah Newren
2021-05-28  1:32   ` Taylor Blau
2021-05-28  4:10     ` Elijah Newren
2021-05-27  8:37 ` [PATCH 2/5] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
2021-05-27  8:37 ` [PATCH 3/5] diffcore-rename: enable limiting rename detection to relevant destinations Elijah Newren via GitGitGadget
2021-05-27  8:37 ` [PATCH 4/5] Fix various issues found in comments Elijah Newren via GitGitGadget
2021-05-27  8:37 ` [PATCH 5/5] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget
2021-06-01 14:58 ` [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
2021-06-01 14:58   ` [PATCH v2 1/5] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
2021-06-02 11:29     ` Derrick Stolee
2021-06-01 14:58   ` [PATCH v2 2/5] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
2021-06-01 14:58   ` [PATCH v2 3/5] diffcore-rename: enable limiting rename detection to relevant destinations Elijah Newren via GitGitGadget
2021-06-03 12:54     ` Derrick Stolee
2021-06-03 14:13       ` Elijah Newren
2021-06-01 14:58   ` [PATCH v2 4/5] Fix various issues found in comments Elijah Newren via GitGitGadget
2021-06-01 14:58   ` [PATCH v2 5/5] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget
2021-06-03 12:55   ` [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff Derrick Stolee
2021-06-04  4:39   ` [PATCH v3 0/4] " Elijah Newren via GitGitGadget
2021-06-04  4:39     ` [PATCH v3 1/4] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
2021-06-04  4:39     ` [PATCH v3 2/4] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
2021-06-04  4:39     ` [PATCH v3 3/4] Fix various issues found in comments Elijah Newren via GitGitGadget
2021-06-04  4:39     ` [PATCH v3 4/4] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget
2021-06-04 13:11     ` [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff Derrick Stolee
2021-06-04 15:48       ` Elijah Newren
2021-06-04 16:30         ` Elijah Newren
2021-06-04 16:35         ` Jeff King
2021-06-04 18:42           ` Derrick Stolee
2021-06-04 19:43             ` Elijah Newren
2021-06-04 19:53             ` Jeff King
2021-06-08 16:11     ` [PATCH v4 " Elijah Newren via GitGitGadget
2021-06-08 16:11       ` [PATCH v4 1/4] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
2021-06-08 16:11       ` [PATCH v4 2/4] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
2021-06-08 16:11       ` [PATCH v4 3/4] Fix various issues found in comments Elijah Newren via GitGitGadget
2021-06-08 16:11       ` [PATCH v4 4/4] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.