[PATCH 00/10] name-rev: improve memory usage

[PATCH 00/10] name-rev: improve memory usage

[René Scharfe]

This series seeks to get reduce the size of memory allocations, the
number of reallocations and the amount of leaks in git name-rev, to
improve its performance.  It starts with a few cleanups:

Martin Ågren (1):
  name-rev: rewrite create_or_update_name()

René Scharfe (9):
  name-rev: remove unused typedef
  name-rev: respect const qualifier
  name-rev: don't _peek() in create_or_update_name()

... then plugs a minor leak:

  name-rev: don't leak path copy in name_ref()

... and gets rid of a level of indirection in commit slab usage:

  name-rev: put struct rev_name into commit slab

The next two patches eliminate reallocations while building name strings
for parent commits, which can make a surprisingly big difference in some
cases:

  name-rev: factor out get_parent_name()
  name-rev: pre-size buffer in get_parent_name()

The next one avoids building names that are be discarded right away by
checking first if they are better than a possibly present other name
assigned earlier, which only provides a small speedup, but is the right
thing to do:

  name-rev: generate name strings only if they are better

And finally a tricky one whose commit message is a lot longer than its
diff, which adds a bit of overhead and which probably needs the most
reviewer attention to make sure it won't cause double frees:

  name-rev: release unused name strings

 builtin/name-rev.c | 133 ++++++++++++++++++++++++++-------------------
 1 file changed, 76 insertions(+), 57 deletions(-)

--
2.25.0

[PATCH 01/10] name-rev: rewrite create_or_update_name()

[René Scharfe]

This code was moved straight out of name_rev(). As such, we inherited
the "goto" to jump from an if into an else-if. We also inherited the
fact that "nothing to do -- return NULL" is handled last.

Rewrite the function to first handle the "nothing to do" case. Then we
can handle the conditional allocation early before going on to populate
the struct. No need for goto-ing.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
Original submission:
https://lore.kernel.org/git/20190922081846.14452-1-martin.agren@gmail.com/

 builtin/name-rev.c | 24 ++++++++++++------------
 1 file changed, 12 insertions(+), 12 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 6b9e8c850b..c2239ac3f7 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -88,21 +88,21 @@ static struct rev_name *create_or_update_name(struct commit *commit,
 {
 	struct rev_name *name = get_commit_rev_name(commit);

+	if (name && !is_better_name(name, taggerdate, distance, from_tag))
+		return NULL;
+
 	if (name == NULL) {
 		name = xmalloc(sizeof(*name));
 		set_commit_rev_name(commit, name);
-		goto copy_data;
-	} else if (is_better_name(name, taggerdate, distance, from_tag)) {
-copy_data:
-		name->tip_name = tip_name;
-		name->taggerdate = taggerdate;
-		name->generation = generation;
-		name->distance = distance;
-		name->from_tag = from_tag;
-
-		return name;
-	} else
-		return NULL;
+	}
+
+	name->tip_name = tip_name;
+	name->taggerdate = taggerdate;
+	name->generation = generation;
+	name->distance = distance;
+	name->from_tag = from_tag;
+
+	return name;
 }

 static void name_rev(struct commit *start_commit,
--
2.25.0

[PATCH 02/10] name-rev: remove unused typedef

[René Scharfe]

The type alias became unused with bf43abc6e6 (name-rev: use sizeof(*ptr)
instead of sizeof(type) in allocation, 2019-11-12); remove it.

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 builtin/name-rev.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index c2239ac3f7..a8de9cc561 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -16,13 +16,13 @@
  */
 #define CUTOFF_DATE_SLOP 86400

-typedef struct rev_name {
+struct rev_name {
 	const char *tip_name;
 	timestamp_t taggerdate;
 	int generation;
 	int distance;
 	int from_tag;
-} rev_name;
+};

 define_commit_slab(commit_rev_name, struct rev_name *);

--
2.25.0

[PATCH 03/10] name-rev: respect const qualifier

[René Scharfe]

Keep the const qualifier of the first parameter of get_rev_name() even
when casting the object pointer to a commit pointer, and further for the
parameter of get_commit_rev_name(), as all these uses are read-only.

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 builtin/name-rev.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index a8de9cc561..2e6820bd5b 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -32,7 +32,7 @@ static struct commit_rev_name rev_names;
 /* How many generations are maximally preferred over _one_ merge traversal? */
 #define MERGE_TRAVERSAL_WEIGHT 65535

-static struct rev_name *get_commit_rev_name(struct commit *commit)
+static struct rev_name *get_commit_rev_name(const struct commit *commit)
 {
 	struct rev_name **slot = commit_rev_name_peek(&rev_names, commit);

@@ -357,11 +357,11 @@ static const char *get_exact_ref_match(const struct object *o)
 static const char *get_rev_name(const struct object *o, struct strbuf *buf)
 {
 	struct rev_name *n;
-	struct commit *c;
+	const struct commit *c;

 	if (o->type != OBJ_COMMIT)
 		return get_exact_ref_match(o);
-	c = (struct commit *) o;
+	c = (const struct commit *) o;
 	n = get_commit_rev_name(c);
 	if (!n)
 		return NULL;
--
2.25.0

[PATCH 04/10] name-rev: don't leak path copy in name_ref()

[René Scharfe]

name_ref() duplicates the path string and passes it to name_rev(), which
either puts it into a commit slab or ignores it if there is already a
better name, leaking it.  Move the duplication to name_rev() and release
the copy in the latter case.

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 builtin/name-rev.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 2e6820bd5b..3e22a0503e 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -121,6 +121,8 @@ static void name_rev(struct commit *start_commit,

 	if (deref)
 		tip_name = to_free = xstrfmt("%s^0", tip_name);
+	else
+		tip_name = to_free = xstrdup(tip_name);

 	if (!create_or_update_name(start_commit, tip_name, taggerdate, 0, 0,
 				   from_tag)) {
@@ -323,7 +325,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
 		if (taggerdate == TIME_MAX)
 			taggerdate = commit->date;
 		path = name_ref_abbrev(path, can_abbreviate_output);
-		name_rev(commit, xstrdup(path), taggerdate, from_tag, deref);
+		name_rev(commit, path, taggerdate, from_tag, deref);
 	}
 	return 0;
 }
--
2.25.0

[PATCH 05/10] name-rev: don't _peek() in create_or_update_name()

[René Scharfe]

Look up the commit slab slot for the commit once using
commit_rev_name_at() and populate it in case it is empty, instead of
checking for emptiness in a separate step using commit_rev_name_peek()
via get_commit_rev_name().

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 builtin/name-rev.c | 14 ++++----------
 1 file changed, 4 insertions(+), 10 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 3e22a0503e..41aed436ca 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -39,11 +39,6 @@ static struct rev_name *get_commit_rev_name(const struct commit *commit)
 	return slot ? *slot : NULL;
 }

-static void set_commit_rev_name(struct commit *commit, struct rev_name *name)
-{
-	*commit_rev_name_at(&rev_names, commit) = name;
-}
-
 static int is_better_name(struct rev_name *name,
 			  timestamp_t taggerdate,
 			  int distance,
@@ -86,15 +81,14 @@ static struct rev_name *create_or_update_name(struct commit *commit,
 					      int generation, int distance,
 					      int from_tag)
 {
-	struct rev_name *name = get_commit_rev_name(commit);
+	struct rev_name **slot = commit_rev_name_at(&rev_names, commit);
+	struct rev_name *name = *slot;

 	if (name && !is_better_name(name, taggerdate, distance, from_tag))
 		return NULL;

-	if (name == NULL) {
-		name = xmalloc(sizeof(*name));
-		set_commit_rev_name(commit, name);
-	}
+	if (!name)
+		name = *slot = xmalloc(sizeof(*name));

 	name->tip_name = tip_name;
 	name->taggerdate = taggerdate;
--
2.25.0

[PATCH 06/10] name-rev: put struct rev_name into commit slab

[René Scharfe]

The commit slab commit_rev_name contains a pointer to a struct rev_name,
and the actual struct is allocated separatly.  Avoid that allocation and
pointer indirection by storing the full struct in the commit slab.  Use
the tip_name member pointer to determine if the returned struct is
initialized.

Performance in the Linux repository measured with hyperfine before:

Benchmark #1: ./git -C ../linux/ name-rev --all
  Time (mean ± σ):     953.5 ms ±   6.3 ms    [User: 901.2 ms, System: 52.1 ms]
  Range (min … max):   945.2 ms … 968.5 ms    10 runs

... and with this patch:

Benchmark #1: ./git -C ../linux/ name-rev --all
  Time (mean ± σ):     851.0 ms ±   3.1 ms    [User: 807.4 ms, System: 43.6 ms]
  Range (min … max):   846.7 ms … 857.0 ms    10 runs

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 builtin/name-rev.c | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 41aed436ca..14381a3c64 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -24,7 +24,7 @@ struct rev_name {
 	int from_tag;
 };

-define_commit_slab(commit_rev_name, struct rev_name *);
+define_commit_slab(commit_rev_name, struct rev_name);

 static timestamp_t cutoff = TIME_MAX;
 static struct commit_rev_name rev_names;
@@ -32,11 +32,16 @@ static struct commit_rev_name rev_names;
 /* How many generations are maximally preferred over _one_ merge traversal? */
 #define MERGE_TRAVERSAL_WEIGHT 65535

+static int is_valid_rev_name(const struct rev_name *name)
+{
+	return name && name->tip_name;
+}
+
 static struct rev_name *get_commit_rev_name(const struct commit *commit)
 {
-	struct rev_name **slot = commit_rev_name_peek(&rev_names, commit);
+	struct rev_name *name = commit_rev_name_peek(&rev_names, commit);

-	return slot ? *slot : NULL;
+	return is_valid_rev_name(name) ? name : NULL;
 }

 static int is_better_name(struct rev_name *name,
@@ -81,15 +86,12 @@ static struct rev_name *create_or_update_name(struct commit *commit,
 					      int generation, int distance,
 					      int from_tag)
 {
-	struct rev_name **slot = commit_rev_name_at(&rev_names, commit);
-	struct rev_name *name = *slot;
+	struct rev_name *name = commit_rev_name_at(&rev_names, commit);

-	if (name && !is_better_name(name, taggerdate, distance, from_tag))
+	if (is_valid_rev_name(name) &&
+	    !is_better_name(name, taggerdate, distance, from_tag))
 		return NULL;

-	if (!name)
-		name = *slot = xmalloc(sizeof(*name));
-
 	name->tip_name = tip_name;
 	name->taggerdate = taggerdate;
 	name->generation = generation;
--
2.25.0

[PATCH 07/10] name-rev: factor out get_parent_name()

[René Scharfe]

Reduce nesting by moving code to come up with a name for the parent into
its own function.

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 builtin/name-rev.c | 27 ++++++++++++++-------------
 1 file changed, 14 insertions(+), 13 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 14381a3c64..6701fb1569 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -101,6 +101,19 @@ static struct rev_name *create_or_update_name(struct commit *commit,
 	return name;
 }

+static char *get_parent_name(const struct rev_name *name, int parent_number)
+{
+	size_t len;
+
+	strip_suffix(name->tip_name, "^0", &len);
+	if (name->generation > 0)
+		return xstrfmt("%.*s~%d^%d", (int)len, name->tip_name,
+			       name->generation, parent_number);
+	else
+		return xstrfmt("%.*s^%d", (int)len, name->tip_name,
+			       parent_number);
+}
+
 static void name_rev(struct commit *start_commit,
 		const char *tip_name, timestamp_t taggerdate,
 		int from_tag, int deref)
@@ -148,19 +161,7 @@ static void name_rev(struct commit *start_commit,
 				continue;

 			if (parent_number > 1) {
-				size_t len;
-
-				strip_suffix(name->tip_name, "^0", &len);
-				if (name->generation > 0)
-					new_name = xstrfmt("%.*s~%d^%d",
-							   (int)len,
-							   name->tip_name,
-							   name->generation,
-							   parent_number);
-				else
-					new_name = xstrfmt("%.*s^%d", (int)len,
-							   name->tip_name,
-							   parent_number);
+				new_name = get_parent_name(name, parent_number);
 				generation = 0;
 				distance = name->distance + MERGE_TRAVERSAL_WEIGHT;
 			} else {
--
2.25.0

[PATCH 08/10] name-rev: pre-size buffer in get_parent_name()

[René Scharfe]

We can calculate the size of new name easily and precisely. Open-code
the xstrfmt() calls and grow the buffers as needed before filling them.
This provides a surprisingly large benefit when working with the
Chromium repository; here are the numbers measured using hyperfine
before:

Benchmark #1: ./git -C ../chromium/src name-rev --all
  Time (mean ± σ):      5.822 s ±  0.013 s    [User: 5.304 s, System: 0.516 s]
  Range (min … max):    5.803 s …  5.837 s    10 runs

... and with this patch:

Benchmark #1: ./git -C ../chromium/src name-rev --all
  Time (mean ± σ):      1.527 s ±  0.003 s    [User: 1.015 s, System: 0.511 s]
  Range (min … max):    1.524 s …  1.535 s    10 runs

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 builtin/name-rev.c | 20 ++++++++++++++------
 1 file changed, 14 insertions(+), 6 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 6701fb1569..793356edd1 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -103,15 +103,23 @@ static struct rev_name *create_or_update_name(struct commit *commit,

 static char *get_parent_name(const struct rev_name *name, int parent_number)
 {
+	struct strbuf sb = STRBUF_INIT;
 	size_t len;

 	strip_suffix(name->tip_name, "^0", &len);
-	if (name->generation > 0)
-		return xstrfmt("%.*s~%d^%d", (int)len, name->tip_name,
-			       name->generation, parent_number);
-	else
-		return xstrfmt("%.*s^%d", (int)len, name->tip_name,
-			       parent_number);
+	if (name->generation > 0) {
+		strbuf_grow(&sb, len +
+			    1 + decimal_width(name->generation) +
+			    1 + decimal_width(parent_number));
+		strbuf_addf(&sb, "%.*s~%d^%d", (int)len, name->tip_name,
+			    name->generation, parent_number);
+	} else {
+		strbuf_grow(&sb, len +
+			    1 + decimal_width(parent_number));
+		strbuf_addf(&sb, "%.*s^%d", (int)len, name->tip_name,
+			    parent_number);
+	}
+	return strbuf_detach(&sb, NULL);
 }

 static void name_rev(struct commit *start_commit,
--
2.25.0

[PATCH 09/10] name-rev: generate name strings only if they are better

[René Scharfe]

Leave setting the tip_name member of struct rev_name to callers of
create_or_update_name().  This avoids allocations for names that are
rejected by that function.  Here's how this affects the runtime when
working with a fresh clone of Git's own repository; performance numbers
by hyperfine before:

Benchmark #1: ./git -C ../git-pristine/ name-rev --all
  Time (mean ± σ):     437.8 ms ±   4.0 ms    [User: 422.5 ms, System: 15.2 ms]
  Range (min … max):   432.8 ms … 446.3 ms    10 runs

... and with this patch:

Benchmark #1: ./git -C ../git-pristine/ name-rev --all
  Time (mean ± σ):     408.5 ms ±   1.4 ms    [User: 387.2 ms, System: 21.2 ms]
  Range (min … max):   407.1 ms … 411.7 ms    10 runs

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 builtin/name-rev.c | 35 ++++++++++++++++++-----------------
 1 file changed, 18 insertions(+), 17 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 793356edd1..98f55bcea9 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -81,7 +81,6 @@ static int is_better_name(struct rev_name *name,
 }

 static struct rev_name *create_or_update_name(struct commit *commit,
-					      const char *tip_name,
 					      timestamp_t taggerdate,
 					      int generation, int distance,
 					      int from_tag)
@@ -92,7 +91,6 @@ static struct rev_name *create_or_update_name(struct commit *commit,
 	    !is_better_name(name, taggerdate, distance, from_tag))
 		return NULL;

-	name->tip_name = tip_name;
 	name->taggerdate = taggerdate;
 	name->generation = generation;
 	name->distance = distance;
@@ -130,22 +128,20 @@ static void name_rev(struct commit *start_commit,
 	struct commit *commit;
 	struct commit **parents_to_queue = NULL;
 	size_t parents_to_queue_nr, parents_to_queue_alloc = 0;
-	char *to_free = NULL;
+	struct rev_name *start_name;

 	parse_commit(start_commit);
 	if (start_commit->date < cutoff)
 		return;

+	start_name = create_or_update_name(start_commit, taggerdate, 0, 0,
+					   from_tag);
+	if (!start_name)
+		return;
 	if (deref)
-		tip_name = to_free = xstrfmt("%s^0", tip_name);
+		start_name->tip_name = xstrfmt("%s^0", tip_name);
 	else
-		tip_name = to_free = xstrdup(tip_name);
-
-	if (!create_or_update_name(start_commit, tip_name, taggerdate, 0, 0,
-				   from_tag)) {
-		free(to_free);
-		return;
-	}
+		start_name->tip_name = xstrdup(tip_name);

 	memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */
 	prio_queue_put(&queue, start_commit);
@@ -161,7 +157,7 @@ static void name_rev(struct commit *start_commit,
 				parents;
 				parents = parents->next, parent_number++) {
 			struct commit *parent = parents->item;
-			const char *new_name;
+			struct rev_name *parent_name;
 			int generation, distance;

 			parse_commit(parent);
@@ -169,18 +165,23 @@ static void name_rev(struct commit *start_commit,
 				continue;

 			if (parent_number > 1) {
-				new_name = get_parent_name(name, parent_number);
 				generation = 0;
 				distance = name->distance + MERGE_TRAVERSAL_WEIGHT;
 			} else {
-				new_name = name->tip_name;
 				generation = name->generation + 1;
 				distance = name->distance + 1;
 			}

-			if (create_or_update_name(parent, new_name, taggerdate,
-						  generation, distance,
-						  from_tag)) {
+			parent_name = create_or_update_name(parent, taggerdate,
+							    generation,
+							    distance, from_tag);
+			if (parent_name) {
+				if (parent_number > 1)
+					parent_name->tip_name =
+						get_parent_name(name,
+								parent_number);
+				else
+					parent_name->tip_name = name->tip_name;
 				ALLOC_GROW(parents_to_queue,
 					   parents_to_queue_nr + 1,
 					   parents_to_queue_alloc);
--
2.25.0

[PATCH 10/10] name-rev: release unused name strings

[René Scharfe]

name_rev() assigns a name to a commit and its parents and grandparents
and so on.  Commits share their name string with their first parent,
which in turn does the same, recursively to the root.  That saves a lot
of allocations.  When a better name is found, the old name is replaced,
but its memory is not released.  That leakage can become significant.

Can we release these old strings exactly once even though they are
referenced multiple times?  Yes, indeed -- we can make use of the fact
that name_rev() visits the ancestors of a commit after it set a new name
for it and tries to update their names as well.

Members of the first ancestral line have the same taggerdate and
from_tag values, but a higher distance value than their child commit at
generation 0.  These are the only criteria used by is_better_name().
Lower distance values are considered better, so a name that is better
for a child will also be better for its parent and grandparent etc.

That means we can free(3) an inferior name at generation 0 and rely on
name_rev() to replace all references in ancestors as well.

If we do that then we need to stop using the string pointer alone to
distinguish new empty rev_name slots from initialized ones, though, as
it technically becomes invalid after the free(3) call -- even though its
value is still different from NULL.

We can check the generation value first, as empty slots will have it
initialized to 0, and for the actual generation 0 we'll set a new valid
name right after the create_or_update_name() call that releases the
string.

For the Chromium repo, releasing superceded names reduces the memory
footprint of name-rev --all significantly.  Here's the output of GNU
time before:

0.98user 0.48system 0:01.46elapsed 99%CPU (0avgtext+0avgdata 2601812maxresident)k
0inputs+0outputs (0major+571470minor)pagefaults 0swaps

... and with this patch:

1.01user 0.26system 0:01.28elapsed 100%CPU (0avgtext+0avgdata 1559196maxresident)k
0inputs+0outputs (0major+314370minor)pagefaults 0swaps

It also gets faster; hyperfine before:

Benchmark #1: ./git -C ../chromium/src name-rev --all
  Time (mean ± σ):      1.534 s ±  0.006 s    [User: 1.039 s, System: 0.494 s]
  Range (min … max):    1.522 s …  1.542 s    10 runs

... and with this patch:

Benchmark #1: ./git -C ../chromium/src name-rev --all
  Time (mean ± σ):      1.338 s ±  0.006 s    [User: 1.047 s, System: 0.291 s]
  Range (min … max):    1.327 s …  1.346 s    10 runs

For the Linux repo it doesn't pay off; memory usage only gets down from:

0.76user 0.03system 0:00.80elapsed 99%CPU (0avgtext+0avgdata 292848maxresident)k
0inputs+0outputs (0major+44579minor)pagefaults 0swaps

... to:

0.78user 0.03system 0:00.81elapsed 100%CPU (0avgtext+0avgdata 284696maxresident)k
0inputs+0outputs (0major+44892minor)pagefaults 0swaps

The runtime actually increases slightly from:

Benchmark #1: ./git -C ../linux/ name-rev --all
  Time (mean ± σ):     828.8 ms ±   5.0 ms    [User: 797.2 ms, System: 31.6 ms]
  Range (min … max):   824.1 ms … 838.9 ms    10 runs

... to:

Benchmark #1: ./git -C ../linux/ name-rev --all
  Time (mean ± σ):     847.6 ms ±   3.4 ms    [User: 807.9 ms, System: 39.6 ms]
  Range (min … max):   843.4 ms … 854.3 ms    10 runs

Why is that?  In the Chromium repo, ca. 44000 free(3) calls in
create_or_update_name() release almost 1GB, while in the Linux repo
240000+ calls release a bit more than 5MB, so the average discarded
name is ca.  1000x longer in the latter.

Overall I think it's the right tradeoff to make, as it helps curb the
memory usage in repositories with big discarded names, and the added
overhead is small.

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 builtin/name-rev.c | 21 ++++++++++++++++-----
 1 file changed, 16 insertions(+), 5 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 98f55bcea9..23a639ff30 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -17,7 +17,7 @@
 #define CUTOFF_DATE_SLOP 86400

 struct rev_name {
-	const char *tip_name;
+	char *tip_name;
 	timestamp_t taggerdate;
 	int generation;
 	int distance;
@@ -34,7 +34,7 @@ static struct commit_rev_name rev_names;

 static int is_valid_rev_name(const struct rev_name *name)
 {
-	return name && name->tip_name;
+	return name && (name->generation || name->tip_name);
 }

 static struct rev_name *get_commit_rev_name(const struct commit *commit)
@@ -87,9 +87,20 @@ static struct rev_name *create_or_update_name(struct commit *commit,
 {
 	struct rev_name *name = commit_rev_name_at(&rev_names, commit);

-	if (is_valid_rev_name(name) &&
-	    !is_better_name(name, taggerdate, distance, from_tag))
-		return NULL;
+	if (is_valid_rev_name(name)) {
+		if (!is_better_name(name, taggerdate, distance, from_tag))
+			return NULL;
+
+		/*
+		 * This string might still be shared with ancestors
+		 * (generation > 0).  We can release it here regardless,
+		 * because the new name that has just won will be better
+		 * for them as well, so name_rev() will replace these
+		 * stale pointers when it processes the parents.
+		 */
+		if (!name->generation)
+			free(name->tip_name);
+	}

 	name->taggerdate = taggerdate;
 	name->generation = generation;
--
2.25.0

Re: [PATCH 01/10] name-rev: rewrite create_or_update_name()

[Derrick Stolee]

On 2/4/2020 4:14 PM, René Scharfe wrote:
> This code was moved straight out of name_rev(). As such, we inherited
> the "goto" to jump from an if into an else-if. We also inherited the
> fact that "nothing to do -- return NULL" is handled last.
> 
> Rewrite the function to first handle the "nothing to do" case. Then we
> can handle the conditional allocation early before going on to populate
> the struct. No need for goto-ing.

I read this carefully and agree it is functionally equivalent.

Since you are removing a goto and rearranging if/else blocks, I thought
this response needed to be explicit, at least more than usual. Good work.

Thanks,
-Stolee

Re: [PATCH 01/10] name-rev: rewrite create_or_update_name()

[Taylor Blau]

On Tue, Feb 04, 2020 at 09:00:23PM -0500, Derrick Stolee wrote:
> On 2/4/2020 4:14 PM, René Scharfe wrote:
> > This code was moved straight out of name_rev(). As such, we inherited
> > the "goto" to jump from an if into an else-if. We also inherited the
> > fact that "nothing to do -- return NULL" is handled last.
> >
> > Rewrite the function to first handle the "nothing to do" case. Then we
> > can handle the conditional allocation early before going on to populate
> > the struct. No need for goto-ing.
>
> I read this carefully and agree it is functionally equivalent.

As did I. I originally thought that my MUA was wrapping the 'else if'
line oddly, but then I discovered that it's the label's indentation that
was throwing me off.

In any case, this makes good sense. Well done indeed.

> Since you are removing a goto and rearranging if/else blocks, I thought
> this response needed to be explicit, at least more than usual. Good work.
>
> Thanks,
> -Stolee

Thanks,
Taylor

Re: [PATCH 08/10] name-rev: pre-size buffer in get_parent_name()

[Derrick Stolee]

On 2/4/2020 4:24 PM, René Scharfe wrote:
> We can calculate the size of new name easily and precisely. Open-code
> the xstrfmt() calls and grow the buffers as needed before filling them.
> This provides a surprisingly large benefit when working with the
> Chromium repository; here are the numbers measured using hyperfine
> before:
> 
> Benchmark #1: ./git -C ../chromium/src name-rev --all
>   Time (mean ± σ):      5.822 s ±  0.013 s    [User: 5.304 s, System: 0.516 s]
>   Range (min … max):    5.803 s …  5.837 s    10 runs
> 
> ... and with this patch:
> 
> Benchmark #1: ./git -C ../chromium/src name-rev --all
>   Time (mean ± σ):      1.527 s ±  0.003 s    [User: 1.015 s, System: 0.511 s]
>   Range (min … max):    1.524 s …  1.535 s    10 runs

Nice!

> +	if (name->generation > 0) {
> +		strbuf_grow(&sb, len +
> +			    1 + decimal_width(name->generation) +
> +			    1 + decimal_width(parent_number));

Just curious: these strbuf_grow() calls are what _really_ improve the
performance, right? If you dropped them, then can we expect the performance
to be similar to the old code?

> +		strbuf_addf(&sb, "%.*s~%d^%d", (int)len, name->tip_name,
> +			    name->generation, parent_number);
> +	} else {
> +		strbuf_grow(&sb, len +
> +			    1 + decimal_width(parent_number));
> +		strbuf_addf(&sb, "%.*s^%d", (int)len, name->tip_name,
> +			    parent_number);
> +	}
> +	return strbuf_detach(&sb, NULL);
>  }
> 
>  static void name_rev(struct commit *start_commit,
> --
> 2.25.0
> 

Re: [PATCH 00/10] name-rev: improve memory usage

[Derrick Stolee]

On 2/4/2020 4:12 PM, René Scharfe wrote:
> This series seeks to get reduce the size of memory allocations, the
> number of reallocations and the amount of leaks in git name-rev, to
> improve its performance.

I am generally very happy with the performance benefits and think
this series is very well organized.

>   name-rev: don't leak path copy in name_ref()
>   name-rev: generate name strings only if they are better
>   name-rev: release unused name strings

I don't have the right context to understand these patches without
applying them and investigating the methods around the changes.
They intrigue me, though, so I plan to pick this up again tomorrow.

The rest of the changes look good.

Thanks,
-Stolee

Re: [PATCH 04/10] name-rev: don't leak path copy in name_ref()

[Derrick Stolee]

On 2/4/2020 4:17 PM, René Scharfe wrote:
> name_ref() duplicates the path string and passes it to name_rev(), which
> either puts it into a commit slab or ignores it if there is already a
> better name, leaking it.  Move the duplication to name_rev() and release
> the copy in the latter case.
> 
> Signed-off-by: René Scharfe <l.s.r@web.de>
> ---
>  builtin/name-rev.c | 4 +++-
>  1 file changed, 3 insertions(+), 1 deletion(-)
> 
> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> index 2e6820bd5b..3e22a0503e 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -121,6 +121,8 @@ static void name_rev(struct commit *start_commit,
> 
>  	if (deref)
>  		tip_name = to_free = xstrfmt("%s^0", tip_name);
> +	else
> +		tip_name = to_free = xstrdup(tip_name);

We now unconditionally duplicate the input tip_name and free it
within the method. Good.

>  	if (!create_or_update_name(start_commit, tip_name, taggerdate, 0, 0,
>  				   from_tag)) {
> @@ -323,7 +325,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>  		if (taggerdate == TIME_MAX)
>  			taggerdate = commit->date;
>  		path = name_ref_abbrev(path, can_abbreviate_output);
> -		name_rev(commit, xstrdup(path), taggerdate, from_tag, deref);
> +		name_rev(commit, path, taggerdate, from_tag, deref);

And we no longer duplicate 'path' here, as it is unconditionally duplicated
in name_ref().

Thanks,
-Stolee

Re: [PATCH 09/10] name-rev: generate name strings only if they are better

[Derrick Stolee]

On 2/4/2020 4:25 PM, René Scharfe wrote:
> -			if (create_or_update_name(parent, new_name, taggerdate,
> -						  generation, distance,
> -						  from_tag)) {
> +			parent_name = create_or_update_name(parent, taggerdate,
> +							    generation,
> +							    distance, from_tag);
> +			if (parent_name) {

As someone unfamiliar with the name-rev code, it took me a while to see why
the algorithm isn't exponential in complexity. It technically _is_, but it
is of the form 2^{N / MERGE_TRAVERSAL_WEIGHT} = 2^{N / 65535} and only if
we create a particularly nasty commit history that would never appear in the wild.

But, the critical section is the block above. The confusing part was that
create_or_update_name() returns NULL if the name is updated, but non-NULL if
a better name is created. That makes it clear that this change is saving
allocations.

Thanks,
-Stolee

Re: [PATCH 08/10] name-rev: pre-size buffer in get_parent_name()

[René Scharfe]

Am 05.02.20 um 04:19 schrieb Derrick Stolee:
> On 2/4/2020 4:24 PM, René Scharfe wrote:
>> We can calculate the size of new name easily and precisely. Open-code
>> the xstrfmt() calls and grow the buffers as needed before filling them.
>> This provides a surprisingly large benefit when working with the
>> Chromium repository; here are the numbers measured using hyperfine
>> before:
>>
>> Benchmark #1: ./git -C ../chromium/src name-rev --all
>>   Time (mean ± σ):      5.822 s ±  0.013 s    [User: 5.304 s, System: 0.516 s]
>>   Range (min … max):    5.803 s …  5.837 s    10 runs
>>
>> ... and with this patch:
>>
>> Benchmark #1: ./git -C ../chromium/src name-rev --all
>>   Time (mean ± σ):      1.527 s ±  0.003 s    [User: 1.015 s, System: 0.511 s]
>>   Range (min … max):    1.524 s …  1.535 s    10 runs
>
> Nice!
>
>> +	if (name->generation > 0) {
>> +		strbuf_grow(&sb, len +
>> +			    1 + decimal_width(name->generation) +
>> +			    1 + decimal_width(parent_number));
>
> Just curious: these strbuf_grow() calls are what _really_ improve the
> performance, right? If you dropped them, then can we expect the performance
> to be similar to the old code?

The replaced xstrfmt() is defined in strbuf.c and trivially wraps
xstrvfmt(), which in turn does:

	struct strbuf buf = STRBUF_INIT;
	strbuf_vaddf(&buf, fmt, ap);
	return strbuf_detach(&buf, NULL);

And strbuf_addf() trivially wraps strbuf_vaddf().  So indeed, all
I did was to inline xstrfmt() and add the strbuf_grow() calls.

Their high impact shocked me a bit.  vsnprintf(3) really doesn't seem
to like working with a buffer that is too small (when it's supposed to
just calculate how many bytes it would have needed), at least not in
the one from glibc 2.29.

>> +		strbuf_addf(&sb, "%.*s~%d^%d", (int)len, name->tip_name,
>> +			    name->generation, parent_number);
>> +	} else {
>> +		strbuf_grow(&sb, len +
>> +			    1 + decimal_width(parent_number));
>> +		strbuf_addf(&sb, "%.*s^%d", (int)len, name->tip_name,
>> +			    parent_number);
>> +	}
>> +	return strbuf_detach(&sb, NULL);
>>  }
>>
>>  static void name_rev(struct commit *start_commit,
>> --
>> 2.25.0
>>
>

Re: [PATCH 10/10] name-rev: release unused name strings

[Derrick Stolee]

On 2/4/2020 4:26 PM, René Scharfe wrote:
> The runtime actually increases slightly from:
> 
> Benchmark #1: ./git -C ../linux/ name-rev --all
>   Time (mean ± σ):     828.8 ms ±   5.0 ms    [User: 797.2 ms, System: 31.6 ms]
>   Range (min … max):   824.1 ms … 838.9 ms    10 runs
> 
> ... to:
> 
> Benchmark #1: ./git -C ../linux/ name-rev --all
>   Time (mean ± σ):     847.6 ms ±   3.4 ms    [User: 807.9 ms, System: 39.6 ms]
>   Range (min … max):   843.4 ms … 854.3 ms    10 runs
> 
> Why is that?  In the Chromium repo, ca. 44000 free(3) calls in
> create_or_update_name() release almost 1GB, while in the Linux repo
> 240000+ calls release a bit more than 5MB, so the average discarded
> name is ca.  1000x longer in the latter.
> 
> Overall I think it's the right tradeoff to make, as it helps curb the
> memory usage in repositories with big discarded names, and the added
> overhead is small.

I agree this trade-off is worth it. Your reasoning for why it is
happening makes sense, too.

> +	if (is_valid_rev_name(name)) {
> +		if (!is_better_name(name, taggerdate, distance, from_tag))
> +			return NULL;
> +
> +		/*
> +		 * This string might still be shared with ancestors
> +		 * (generation > 0).  We can release it here regardless,
> +		 * because the new name that has just won will be better
> +		 * for them as well, so name_rev() will replace these
> +		 * stale pointers when it processes the parents.
> +		 */
> +		if (!name->generation)
> +			free(name->tip_name);
> +	}

And here, this idea of "still be shared with ancestors" is confusing
without the additional context that the name-rev algorithm is using
depth-first-search to find the "best" name. At this point, we are
trying to replace the existing name with a better one, and use
"generation == 0" to declare "I am the initial owner of tip_name".
The rest of the ancestors will replace their tip_name pointer with
the new name, all while not accessing this freed memory.

Keeping such dangling references to freed memory is certainly
dangerous, but these references are short-lived within the name_rev()
method. That limits the possible ways this could cause issues in
the future.

Thanks,
-Stolee

Re: [PATCH 00/10] name-rev: improve memory usage

[Derrick Stolee]

On 2/4/2020 10:28 PM, Derrick Stolee wrote:
> On 2/4/2020 4:12 PM, René Scharfe wrote:
>> This series seeks to get reduce the size of memory allocations, the
>> number of reallocations and the amount of leaks in git name-rev, to
>> improve its performance.
> 
> I am generally very happy with the performance benefits and think
> this series is very well organized.
> 
>>   name-rev: don't leak path copy in name_ref()
>>   name-rev: generate name strings only if they are better
>>   name-rev: release unused name strings
> 
> I don't have the right context to understand these patches without
> applying them and investigating the methods around the changes.
> They intrigue me, though, so I plan to pick this up again tomorrow.

After looking closely at these three, they LGTM.

Thanks,
-Stolee

Re: [PATCH 09/10] name-rev: generate name strings only if they are better

[René Scharfe]

Am 05.02.20 um 16:11 schrieb Derrick Stolee:
> On 2/4/2020 4:25 PM, René Scharfe wrote:
>> -			if (create_or_update_name(parent, new_name, taggerdate,
>> -						  generation, distance,
>> -						  from_tag)) {
>> +			parent_name = create_or_update_name(parent, taggerdate,
>> +							    generation,
>> +							    distance, from_tag);
>> +			if (parent_name) {
>
> As someone unfamiliar with the name-rev code, it took me a while to see why
> the algorithm isn't exponential in complexity. It technically _is_, but it
> is of the form 2^{N / MERGE_TRAVERSAL_WEIGHT} = 2^{N / 65535} and only if
> we create a particularly nasty commit history that would never appear in the wild.

As I understand it, name_rev() attaches a name (a tag or other reference) to a
commit, and then goes through all its ancestors, depth first, and attaches a
name based on that to all of them as well.  It stops traversal if the name is
not better than a previously attached name.  Each commit has at most one name.

If we have N commits and M tags then we could traverse N * M commits and set
their names in the worst case, if the M tags are all for the very latest
commit and if the tags are ordered from worst to best.  Right?

Which implies that ordering names before attaching them one by one should
yield another speedup.  Older tags are preferred and should be tried first,
followed by younger tags and non-tags.  Hmm.. :)

> But, the critical section is the block above. The confusing part was that
> create_or_update_name() returns NULL if the name is updated, but non-NULL if
> a better name is created. That makes it clear that this change is saving
> allocations.

create_or_update_name() returns NULL if the new name is not better than an
existing one, and the old name is left untouched.  It returns a pointer to
the name record if there either was no old name or if that name was worse.
In that case it updates the name.

After this patch it doesn't set the name string (tip_name) anymore, which
is left for the caller.  And the benefit is that the caller only needs to
prepare said name string if the new name is better.

René

Re: [PATCH 01/10] name-rev: rewrite create_or_update_name()

[Andrei Rybak]

Hi René,

On 2020-02-04 22:14, René Scharfe wrote:
> This code was moved straight out of name_rev(). As such, we inherited
> the "goto" to jump from an if into an else-if. We also inherited the
> fact that "nothing to do -- return NULL" is handled last.
>
> Rewrite the function to first handle the "nothing to do" case. Then we
> can handle the conditional allocation early before going on to populate
> the struct. No need for goto-ing.
>
> Signed-off-by: Martin Ågren <martin.agren@gmail.com>
> ---
> Original submission:
> https://lore.kernel.org/git/20190922081846.14452-1-martin.agren@gmail.com/

Judging by this sign-off, link to Martin's email, and shortlog from the cover letter ...

> Martin Ågren (1):
>   name-rev: rewrite create_or_update_name()

... it seems that "From: Martin Ågren <martin.agren@gmail.com>" is missing.

Re: [PATCH 01/10] name-rev: rewrite create_or_update_name()

[René Scharfe]

Am 05.02.20 um 17:45 schrieb Andrei Rybak:
> Hi René,
>
> On 2020-02-04 22:14, René Scharfe wrote:
>> This code was moved straight out of name_rev(). As such, we inherited
>> the "goto" to jump from an if into an else-if. We also inherited the
>> fact that "nothing to do -- return NULL" is handled last.
>>
>> Rewrite the function to first handle the "nothing to do" case. Then we
>> can handle the conditional allocation early before going on to populate
>> the struct. No need for goto-ing.
>>
>> Signed-off-by: Martin Ågren <martin.agren@gmail.com>
>> ---
>> Original submission:
>> https://lore.kernel.org/git/20190922081846.14452-1-martin.agren@gmail.com/
>
> Judging by this sign-off, link to Martin's email, and shortlog from the cover letter ...
>
>> Martin Ågren (1):
>>   name-rev: rewrite create_or_update_name()
>
> ... it seems that "From: Martin Ågren <martin.agren@gmail.com>" is missing.

Yes, indeed.  Sorry for that. :(

René

[PATCH 01/10 RESEND AUTHOR FIXED] name-rev: rewrite create_or_update_name()

[René Scharfe]

From: =?UTF-8?q?Martin=20=C3=85gren?= <martin.agren@gmail.com>

This code was moved straight out of name_rev(). As such, we inherited
the "goto" to jump from an if into an else-if. We also inherited the
fact that "nothing to do -- return NULL" is handled last.

Rewrite the function to first handle the "nothing to do" case. Then we
can handle the conditional allocation early before going on to populate
the struct. No need for goto-ing.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
Missing From: line added; thanks Andrei!

Original submission:
https://lore.kernel.org/git/20190922081846.14452-1-martin.agren@gmail.com/

 builtin/name-rev.c | 24 ++++++++++++------------
 1 file changed, 12 insertions(+), 12 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 6b9e8c850b..c2239ac3f7 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -88,21 +88,21 @@ static struct rev_name *create_or_update_name(struct commit *commit,
 {
 	struct rev_name *name = get_commit_rev_name(commit);

+	if (name && !is_better_name(name, taggerdate, distance, from_tag))
+		return NULL;
+
 	if (name == NULL) {
 		name = xmalloc(sizeof(*name));
 		set_commit_rev_name(commit, name);
-		goto copy_data;
-	} else if (is_better_name(name, taggerdate, distance, from_tag)) {
-copy_data:
-		name->tip_name = tip_name;
-		name->taggerdate = taggerdate;
-		name->generation = generation;
-		name->distance = distance;
-		name->from_tag = from_tag;
-
-		return name;
-	} else
-		return NULL;
+	}
+
+	name->tip_name = tip_name;
+	name->taggerdate = taggerdate;
+	name->generation = generation;
+	name->distance = distance;
+	name->from_tag = from_tag;
+
+	return name;
 }

 static void name_rev(struct commit *start_commit,
--
2.25.0

[PATCH 11/10] name-rev: sort tip names before applying

[René Scharfe]

name_ref() is called for each ref and checks if its a better name for
the referenced commit.  If that's the case it remembers it and checks if
a name based on it is better for its ancestors as well.  This in done in
the the order for_each_ref() imposes on us.

That might not be optimal.  If bad names happen to be encountered first
(as defined by is_better_name()), names derived from them may spread to
a lot of commits, only to be replaced by better names later.  Setting
better names first can avoid that.

is_better_name() prefers tags, short distances and old references.  The
distance is a measure that we need to calculate for each candidate
commit, but the other two properties are not dependent on the
relationships of commits.  Sorting the refs by them should yield better
performance than the essentially random order we currently use.

And applying older references first should also help to reduce rework
due to the fact that older commits have less ancestors than newer ones.

So add all details of names to the tip table first, then sort them
to prefer tags and older references and then apply them in this order.
Here's the performance as measures by hyperfine for the Linux repo
before:

Benchmark #1: ./git -C ../linux/ name-rev --all
  Time (mean ± σ):     851.1 ms ±   4.5 ms    [User: 806.7 ms, System: 44.4 ms]
  Range (min … max):   845.9 ms … 859.5 ms    10 runs

... and with this patch:

Benchmark #1: ./git -C ../linux/ name-rev --all
  Time (mean ± σ):     736.2 ms ±   8.7 ms    [User: 688.4 ms, System: 47.5 ms]
  Range (min … max):   726.0 ms … 755.2 ms    10 runs

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 builtin/name-rev.c | 60 +++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 52 insertions(+), 8 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 23a639ff30..a9dcd25e46 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -247,6 +247,10 @@ static struct tip_table {
 	struct tip_table_entry {
 		struct object_id oid;
 		const char *refname;
+		struct commit *commit;
+		timestamp_t taggerdate;
+		unsigned int from_tag:1;
+		unsigned int deref:1;
 	} *table;
 	int nr;
 	int alloc;
@@ -254,13 +258,18 @@ static struct tip_table {
 } tip_table;

 static void add_to_tip_table(const struct object_id *oid, const char *refname,
-			     int shorten_unambiguous)
+			     int shorten_unambiguous, struct commit *commit,
+			     timestamp_t taggerdate, int from_tag, int deref)
 {
 	refname = name_ref_abbrev(refname, shorten_unambiguous);

 	ALLOC_GROW(tip_table.table, tip_table.nr + 1, tip_table.alloc);
 	oidcpy(&tip_table.table[tip_table.nr].oid, oid);
 	tip_table.table[tip_table.nr].refname = xstrdup(refname);
+	tip_table.table[tip_table.nr].commit = commit;
+	tip_table.table[tip_table.nr].taggerdate = taggerdate;
+	tip_table.table[tip_table.nr].from_tag = from_tag;
+	tip_table.table[tip_table.nr].deref = deref;
 	tip_table.nr++;
 	tip_table.sorted = 0;
 }
@@ -271,12 +280,30 @@ static int tipcmp(const void *a_, const void *b_)
 	return oidcmp(&a->oid, &b->oid);
 }

+static int cmp_by_tag_and_age(const void *a_, const void *b_)
+{
+	const struct tip_table_entry *a = a_, *b = b_;
+	int cmp;
+
+	/* Prefer tags. */
+	cmp = b->from_tag - a->from_tag;
+	if (cmp)
+		return cmp;
+
+	/* Older is better. */
+	if (a->taggerdate < b->taggerdate)
+		return -1;
+	return a->taggerdate != b->taggerdate;
+}
+
 static int name_ref(const char *path, const struct object_id *oid, int flags, void *cb_data)
 {
 	struct object *o = parse_object(the_repository, oid);
 	struct name_ref_data *data = cb_data;
 	int can_abbreviate_output = data->tags_only && data->name_only;
 	int deref = 0;
+	int from_tag = 0;
+	struct commit *commit = NULL;
 	timestamp_t taggerdate = TIME_MAX;

 	if (data->tags_only && !starts_with(path, "refs/tags/"))
@@ -325,8 +352,6 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
 			return 0;
 	}

-	add_to_tip_table(oid, path, can_abbreviate_output);
-
 	while (o && o->type == OBJ_TAG) {
 		struct tag *t = (struct tag *) o;
 		if (!t->tagged)
@@ -336,17 +361,35 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
 		taggerdate = t->date;
 	}
 	if (o && o->type == OBJ_COMMIT) {
-		struct commit *commit = (struct commit *)o;
-		int from_tag = starts_with(path, "refs/tags/");
-
+		commit = (struct commit *)o;
+		from_tag = starts_with(path, "refs/tags/");
 		if (taggerdate == TIME_MAX)
 			taggerdate = commit->date;
-		path = name_ref_abbrev(path, can_abbreviate_output);
-		name_rev(commit, path, taggerdate, from_tag, deref);
 	}
+
+	add_to_tip_table(oid, path, can_abbreviate_output, commit, taggerdate,
+			 from_tag, deref);
 	return 0;
 }

+static void name_tips(void)
+{
+	int i;
+
+	/*
+	 * Try to set better names first, so that worse ones spread
+	 * less.
+	 */
+	QSORT(tip_table.table, tip_table.nr, cmp_by_tag_and_age);
+	for (i = 0; i < tip_table.nr; i++) {
+		struct tip_table_entry *e = &tip_table.table[i];
+		if (e->commit) {
+			name_rev(e->commit, e->refname, e->taggerdate,
+				 e->from_tag, e->deref);
+		}
+	}
+}
+
 static const unsigned char *nth_tip_table_ent(size_t ix, void *table_)
 {
 	struct tip_table_entry *table = table_;
@@ -559,6 +602,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 			cutoff = TIME_MIN;
 	}
 	for_each_ref(name_ref, &data);
+	name_tips();

 	if (transform_stdin) {
 		char buffer[2048];
--
2.25.0

Re: [PATCH 11/10] name-rev: sort tip names before applying

[Junio C Hamano]

René Scharfe <l.s.r@web.de> writes:

> Subject: Re: [PATCH 11/10] name-rev: sort tip names before applying

"before applying" what?

> name_ref() is called for each ref and checks if its a better name for

s/its/it's/

> the referenced commit.  If that's the case it remembers it and checks if

s/case/&,/

> a name based on it is better for its ancestors as well.  This in done in
> the the order for_each_ref() imposes on us.

s/the the/the/

> That might not be optimal.  If bad names happen to be encountered first
> (as defined by is_better_name()), names derived from them may spread to
> a lot of commits, only to be replaced by better names later.  Setting
> better names first can avoid that.
>
> is_better_name() prefers tags, short distances and old references.  The
> distance is a measure that we need to calculate for each candidate
> commit, but the other two properties are not dependent on the
> relationships of commits.  Sorting the refs by them should yield better
> performance than the essentially random order we currently use.

Good insight.

> And applying older references first should also help to reduce rework
> due to the fact that older commits have less ancestors than newer ones.

"older" in the sense of committer/tagger timestamp.  I wonder it
would further help if the commit-graph is available and give us
generation number.

> So add all details of names to the tip table first, then sort them
> to prefer tags and older references and then apply them in this order.
> Here's the performance as measures by hyperfine for the Linux repo
> before:
>
> Benchmark #1: ./git -C ../linux/ name-rev --all
>   Time (mean ± σ):     851.1 ms ±   4.5 ms    [User: 806.7 ms, System: 44.4 ms]
>   Range (min … max):   845.9 ms … 859.5 ms    10 runs
>
> ... and with this patch:
>
> Benchmark #1: ./git -C ../linux/ name-rev --all
>   Time (mean ± σ):     736.2 ms ±   8.7 ms    [User: 688.4 ms, System: 47.5 ms]
>   Range (min … max):   726.0 ms … 755.2 ms    10 runs
>
> Signed-off-by: René Scharfe <l.s.r@web.de>
> ---
>  builtin/name-rev.c | 60 +++++++++++++++++++++++++++++++++++++++-------
>  1 file changed, 52 insertions(+), 8 deletions(-)
>
> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> index 23a639ff30..a9dcd25e46 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -247,6 +247,10 @@ static struct tip_table {
>  	struct tip_table_entry {
>  		struct object_id oid;
>  		const char *refname;
> +		struct commit *commit;
> +		timestamp_t taggerdate;
> +		unsigned int from_tag:1;
> +		unsigned int deref:1;
>  	} *table;
>  	int nr;
>  	int alloc;
> @@ -254,13 +258,18 @@ static struct tip_table {
>  } tip_table;
>
>  static void add_to_tip_table(const struct object_id *oid, const char *refname,
> -			     int shorten_unambiguous)
> +			     int shorten_unambiguous, struct commit *commit,
> +			     timestamp_t taggerdate, int from_tag, int deref)
>  {
>  	refname = name_ref_abbrev(refname, shorten_unambiguous);
>
>  	ALLOC_GROW(tip_table.table, tip_table.nr + 1, tip_table.alloc);
>  	oidcpy(&tip_table.table[tip_table.nr].oid, oid);
>  	tip_table.table[tip_table.nr].refname = xstrdup(refname);
> +	tip_table.table[tip_table.nr].commit = commit;
> +	tip_table.table[tip_table.nr].taggerdate = taggerdate;
> +	tip_table.table[tip_table.nr].from_tag = from_tag;
> +	tip_table.table[tip_table.nr].deref = deref;
>  	tip_table.nr++;
>  	tip_table.sorted = 0;
>  }
> @@ -271,12 +280,30 @@ static int tipcmp(const void *a_, const void *b_)
>  	return oidcmp(&a->oid, &b->oid);
>  }
>
> +static int cmp_by_tag_and_age(const void *a_, const void *b_)
> +{
> +	const struct tip_table_entry *a = a_, *b = b_;
> +	int cmp;
> +
> +	/* Prefer tags. */
> +	cmp = b->from_tag - a->from_tag;

We end up with negative -1 if b is not from tag and a is from tag,
even though the from_tag field is unsigned, so this is not wrong
per-se but feels a bit subtle.

> +	if (cmp)
> +		return cmp;
> +
> +	/* Older is better. */
> +	if (a->taggerdate < b->taggerdate)
> +		return -1;

We are here if both are from tag or neither is from tag.  Mental
note: let's make sure that add_to_tip_table() is always called with
usable timestamp even for a commit that is not from tag.

> +	return a->taggerdate != b->taggerdate;

OK, we know a is either of the same age as or younger than b at this
point, so we would return 1 if a is not the same age as b.

>  static int name_ref(const char *path, const struct object_id *oid, int flags, void *cb_data)
>  {
>  	struct object *o = parse_object(the_repository, oid);
>  	struct name_ref_data *data = cb_data;
>  	int can_abbreviate_output = data->tags_only && data->name_only;
>  	int deref = 0;
> +	int from_tag = 0;
> +	struct commit *commit = NULL;
>  	timestamp_t taggerdate = TIME_MAX;
>
>  	if (data->tags_only && !starts_with(path, "refs/tags/"))
> @@ -325,8 +352,6 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>  			return 0;
>  	}
>
> -	add_to_tip_table(oid, path, can_abbreviate_output);
> -
>  	while (o && o->type == OBJ_TAG) {
>  		struct tag *t = (struct tag *) o;
>  		if (!t->tagged)
> @@ -336,17 +361,35 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>  		taggerdate = t->date;
>  	}
>  	if (o && o->type == OBJ_COMMIT) {
> -		struct commit *commit = (struct commit *)o;
> -		int from_tag = starts_with(path, "refs/tags/");
> -
> +		commit = (struct commit *)o;
> +		from_tag = starts_with(path, "refs/tags/");
>  		if (taggerdate == TIME_MAX)
>  			taggerdate = commit->date;

OK, so a lightweight tag gets the commit date, while an annotated
tag gets the tagger date (while peeling in the loop just above this
part).

I never make an annotated tag long after creating the commit the tag
refers to myself (i.e. on the day I tag a release or a release
candidate, I know that the commit I am creating is what I will tag
even before creating the commit, and I tag the commit soon after
that), but I can imagine that in some other workflows the
maintainers may be tagging long after the commit was made, and more
importantly, the interval of time between comitting and tagging
might be different from release to release.  I wonder if it mimicks
the topological ordering better if always compare the timestamps of
underlying commits.

> -		path = name_ref_abbrev(path, can_abbreviate_output);
> -		name_rev(commit, path, taggerdate, from_tag, deref);
>  	}
> +
> +	add_to_tip_table(oid, path, can_abbreviate_output, commit, taggerdate,
> +			 from_tag, deref);
>  	return 0;
>  }
>
> +static void name_tips(void)
> +{
> +	int i;
> +
> +	/*
> +	 * Try to set better names first, so that worse ones spread
> +	 * less.
> +	 */
> +	QSORT(tip_table.table, tip_table.nr, cmp_by_tag_and_age);
> +	for (i = 0; i < tip_table.nr; i++) {
> +		struct tip_table_entry *e = &tip_table.table[i];
> +		if (e->commit) {

Sorry, I am confused.  I didn't see anything that clears
tip_table.table[i].commit in the code.

> +			name_rev(e->commit, e->refname, e->taggerdate,
> +				 e->from_tag, e->deref);
> +		}
> +	}
> +}
> +
>  static const unsigned char *nth_tip_table_ent(size_t ix, void *table_)
>  {
>  	struct tip_table_entry *table = table_;
> @@ -559,6 +602,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
>  			cutoff = TIME_MIN;
>  	}
>  	for_each_ref(name_ref, &data);
> +	name_tips();
>
>  	if (transform_stdin) {
>  		char buffer[2048];
> --
> 2.25.0

Re: [PATCH 11/10] name-rev: sort tip names before applying

[René Scharfe]

Am 05.02.20 um 19:23 schrieb Junio C Hamano:
> René Scharfe <l.s.r@web.de> writes:
>
>> Subject: Re: [PATCH 11/10] name-rev: sort tip names before applying
>
> "before applying" what?

The tip name.  "Using" or "attaching to commits" might be better than
"applying" here.

>> name_ref() is called for each ref and checks if its a better name for
>
> s/its/it's/
>
>> the referenced commit.  If that's the case it remembers it and checks if
>
> s/case/&,/
>
>> a name based on it is better for its ancestors as well.  This in done in
>> the the order for_each_ref() imposes on us.
>
> s/the the/the/

Right.  I was just too excited..

>> And applying older references first should also help to reduce rework
>> due to the fact that older commits have less ancestors than newer ones.
>
> "older" in the sense of committer/tagger timestamp.  I wonder it
> would further help if the commit-graph is available and give us
> generation number.

To sort by generation number instead of by timestamp?  That would at
the very least help in repos whose timestamps are wonky (imported from
timeless version control system, or commits from a computer with a broken
clock).

>> So add all details of names to the tip table first, then sort them
>> to prefer tags and older references and then apply them in this order.
>> Here's the performance as measures by hyperfine for the Linux repo
>> before:
>>
>> Benchmark #1: ./git -C ../linux/ name-rev --all
>>   Time (mean ± σ):     851.1 ms ±   4.5 ms    [User: 806.7 ms, System: 44.4 ms]
>>   Range (min … max):   845.9 ms … 859.5 ms    10 runs
>>
>> ... and with this patch:
>>
>> Benchmark #1: ./git -C ../linux/ name-rev --all
>>   Time (mean ± σ):     736.2 ms ±   8.7 ms    [User: 688.4 ms, System: 47.5 ms]
>>   Range (min … max):   726.0 ms … 755.2 ms    10 runs
>>
>> Signed-off-by: René Scharfe <l.s.r@web.de>
>> ---
>>  builtin/name-rev.c | 60 +++++++++++++++++++++++++++++++++++++++-------
>>  1 file changed, 52 insertions(+), 8 deletions(-)
>>
>> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
>> index 23a639ff30..a9dcd25e46 100644
>> --- a/builtin/name-rev.c
>> +++ b/builtin/name-rev.c
>> @@ -247,6 +247,10 @@ static struct tip_table {
>>  	struct tip_table_entry {
>>  		struct object_id oid;
>>  		const char *refname;
>> +		struct commit *commit;
>> +		timestamp_t taggerdate;
>> +		unsigned int from_tag:1;
>> +		unsigned int deref:1;
>>  	} *table;
>>  	int nr;
>>  	int alloc;
>> @@ -254,13 +258,18 @@ static struct tip_table {
>>  } tip_table;
>>
>>  static void add_to_tip_table(const struct object_id *oid, const char *refname,
>> -			     int shorten_unambiguous)
>> +			     int shorten_unambiguous, struct commit *commit,
>> +			     timestamp_t taggerdate, int from_tag, int deref)
>>  {
>>  	refname = name_ref_abbrev(refname, shorten_unambiguous);
>>
>>  	ALLOC_GROW(tip_table.table, tip_table.nr + 1, tip_table.alloc);
>>  	oidcpy(&tip_table.table[tip_table.nr].oid, oid);
>>  	tip_table.table[tip_table.nr].refname = xstrdup(refname);
>> +	tip_table.table[tip_table.nr].commit = commit;
>> +	tip_table.table[tip_table.nr].taggerdate = taggerdate;
>> +	tip_table.table[tip_table.nr].from_tag = from_tag;
>> +	tip_table.table[tip_table.nr].deref = deref;
>>  	tip_table.nr++;
>>  	tip_table.sorted = 0;
>>  }
>> @@ -271,12 +280,30 @@ static int tipcmp(const void *a_, const void *b_)
>>  	return oidcmp(&a->oid, &b->oid);
>>  }
>>
>> +static int cmp_by_tag_and_age(const void *a_, const void *b_)
>> +{
>> +	const struct tip_table_entry *a = a_, *b = b_;
>> +	int cmp;
>> +
>> +	/* Prefer tags. */
>> +	cmp = b->from_tag - a->from_tag;
>
> We end up with negative -1 if b is not from tag and a is from tag,
> even though the from_tag field is unsigned, so this is not wrong
> per-se but feels a bit subtle.

Integer promotion -- I admit I looked it up just before sending the
patch to be sure C does the right thing here.  Comparing explicitly
would be more readable.

>
>> +	if (cmp)
>> +		return cmp;
>> +
>> +	/* Older is better. */
>> +	if (a->taggerdate < b->taggerdate)
>> +		return -1;
>
> We are here if both are from tag or neither is from tag.  Mental
> note: let's make sure that add_to_tip_table() is always called with
> usable timestamp even for a commit that is not from tag.
>
>> +	return a->taggerdate != b->taggerdate;
>
> OK, we know a is either of the same age as or younger than b at this
> point, so we would return 1 if a is not the same age as b.
>
>>  static int name_ref(const char *path, const struct object_id *oid, int flags, void *cb_data)
>>  {
>>  	struct object *o = parse_object(the_repository, oid);
>>  	struct name_ref_data *data = cb_data;
>>  	int can_abbreviate_output = data->tags_only && data->name_only;
>>  	int deref = 0;
>> +	int from_tag = 0;
>> +	struct commit *commit = NULL;

Please remember this line.

>>  	timestamp_t taggerdate = TIME_MAX;
>>
>>  	if (data->tags_only && !starts_with(path, "refs/tags/"))
>> @@ -325,8 +352,6 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>>  			return 0;
>>  	}
>>
>> -	add_to_tip_table(oid, path, can_abbreviate_output);
>> -
>>  	while (o && o->type == OBJ_TAG) {
>>  		struct tag *t = (struct tag *) o;
>>  		if (!t->tagged)
>> @@ -336,17 +361,35 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>>  		taggerdate = t->date;
>>  	}
>>  	if (o && o->type == OBJ_COMMIT) {
>> -		struct commit *commit = (struct commit *)o;
>> -		int from_tag = starts_with(path, "refs/tags/");
>> -
>> +		commit = (struct commit *)o;
>> +		from_tag = starts_with(path, "refs/tags/");
>>  		if (taggerdate == TIME_MAX)
>>  			taggerdate = commit->date;
>
> OK, so a lightweight tag gets the commit date, while an annotated
> tag gets the tagger date (while peeling in the loop just above this
> part).
>
> I never make an annotated tag long after creating the commit the tag
> refers to myself (i.e. on the day I tag a release or a release
> candidate, I know that the commit I am creating is what I will tag
> even before creating the commit, and I tag the commit soon after
> that), but I can imagine that in some other workflows the
> maintainers may be tagging long after the commit was made, and more
> importantly, the interval of time between comitting and tagging
> might be different from release to release.  I wonder if it mimicks
> the topological ordering better if always compare the timestamps of
> underlying commits.

I also don't understand why lightweight tags are preferred over tag
objects both by having from_tag set and by having an older timestamp.
In my mind an annotated tag should have more weight since it's harder
to create.

>
>> -		path = name_ref_abbrev(path, can_abbreviate_output);
>> -		name_rev(commit, path, taggerdate, from_tag, deref);
>>  	}
>> +
>> +	add_to_tip_table(oid, path, can_abbreviate_output, commit, taggerdate,
>> +			 from_tag, deref);
>>  	return 0;
>>  }
>>
>> +static void name_tips(void)
>> +{
>> +	int i;
>> +
>> +	/*
>> +	 * Try to set better names first, so that worse ones spread
>> +	 * less.
>> +	 */
>> +	QSORT(tip_table.table, tip_table.nr, cmp_by_tag_and_age);
>> +	for (i = 0; i < tip_table.nr; i++) {
>> +		struct tip_table_entry *e = &tip_table.table[i];
>> +		if (e->commit) {
>
> Sorry, I am confused.  I didn't see anything that clears
> tip_table.table[i].commit in the code.

The line we remembered initializes commit to NULL.  It stays NULL for
refs that don't resolve to commits.

>
>> +			name_rev(e->commit, e->refname, e->taggerdate,
>> +				 e->from_tag, e->deref);
>> +		}
>> +	}
>> +}
>> +
>>  static const unsigned char *nth_tip_table_ent(size_t ix, void *table_)
>>  {
>>  	struct tip_table_entry *table = table_;
>> @@ -559,6 +602,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
>>  			cutoff = TIME_MIN;
>>  	}
>>  	for_each_ref(name_ref, &data);
>> +	name_tips();
>>
>>  	if (transform_stdin) {
>>  		char buffer[2048];
>> --
>> 2.25.0