Re: [PATCH 08/15] name-rev: pull out deref handling from the recursion

From: René Scharfe <l.s.r@web.de>
Date: Sep 24, 2019, 17:03 UTC
Message-ID: <ce55a33b-aa8b-9325-fe87-8ff4c7e02627@web.de>
In-Reply-To: <20190923204714.GC2637@szeder.dev>

Am 23.09.19 um 22:47 schrieb SZEDER Gábor:

Show 17 quoted lines

> On Mon, Sep 23, 2019 at 09:55:11PM +0200, René Scharfe wrote:
>> -- >8 --
>> Subject: [PATCH] name-rev: use FLEX_ARRAY for tip_name in struct rev_name
>>
>> Give each rev_name its very own tip_name string.  This simplifies memory
>> ownership, as callers of name_rev() only have to make sure the tip_name
>> parameter exists for the duration of the call and don't have to preserve
>> it for the whole run of the program.
>>
>> It also saves four or eight bytes per object because this change removes
>> the pointer indirection.  Memory usage is still higher for linear
>> histories that previously shared the same tip_name value between
>> multiple name_rev instances.
>
> Besides looking at memory usage, have you run any performance
> benchmarks?  Here it seems to make 'git name-rev --all >out' slower by
> 17% in the git repo and by 19.5% in the linux repo.

Did measure now; I also see a slowdown with my patch applied:

git:
Benchmark #1: ~/src/git/git name-rev --all
  Time (mean ± σ):     462.8 ms ±   2.8 ms    [User: 440.6 ms, System: 20.5 ms]
  Range (min … max):   459.6 ms … 466.5 ms    10 runs

git w/ commit-graph:
Benchmark #1: ~/src/git/git name-rev --all
  Time (mean ± σ):     104.0 ms ±   1.5 ms    [User: 93.7 ms, System: 10.0 ms]
  Range (min … max):   101.5 ms … 107.1 ms    28 runs

git w/ patch:
Benchmark #1: ~/src/git/git name-rev --all
  Time (mean ± σ):     475.1 ms ±   3.7 ms    [User: 458.3 ms, System: 16.0 ms]
  Range (min … max):   470.4 ms … 481.4 ms    10 runs

git w/ commit-graph and patch:
Benchmark #1: ~/src/git/git name-rev --all
  Time (mean ± σ):     110.9 ms ±   1.5 ms    [User: 106.6 ms, System: 4.1 ms]
  Range (min … max):   109.0 ms … 114.7 ms    26 runs

linux:
Benchmark #1: ~/src/git/git name-rev --all
  Time (mean ± σ):      6.670 s ±  0.027 s    [User: 6.450 s, System: 0.208 s]
  Range (min … max):    6.640 s …  6.721 s    10 runs

linux w/ patch:
Benchmark #1: ~/src/git/git name-rev --all
  Time (mean ± σ):      6.784 s ±  0.160 s    [User: 6.567 s, System: 0.214 s]
  Range (min … max):    6.638 s …  7.211 s    10 runs

linux w/ commit-graph:
Benchmark #1: ~/src/git/git name-rev --all
  Time (mean ± σ):     929.6 ms ±   5.3 ms    [User: 881.4 ms, System: 46.8 ms]
  Range (min … max):   924.1 ms … 939.5 ms    10 runs

linux w/ commit-graph and patch:
Benchmark #1: ~/src/git/git name-rev --all
  Time (mean ± σ):      1.004 s ±  0.007 s    [User: 957.4 ms, System: 45.6 ms]
  Range (min … max):    0.997 s …  1.021 s    10 runs

We can reuse a strbuf instead of allocating new strings when adding suffixes to get some of the performance loss back. I guess it's easier after the recursion is removed. Numbers:

git w/ both patches:
Benchmark #1: ~/src/git/git name-rev --all
  Time (mean ± σ):     448.0 ms ±   2.4 ms    [User: 428.2 ms, System: 19.6 ms]
  Range (min … max):   445.3 ms … 453.4 ms    10 runs

git w/ commit-graph and both patches:
Benchmark #1: ~/src/git/git name-rev --all
  Time (mean ± σ):      98.7 ms ±   1.6 ms    [User: 93.5 ms, System: 5.0 ms]
  Range (min … max):    96.7 ms … 102.8 ms    30 runs

linux w/ both patches:
Benchmark #1: ~/src/git/git name-rev --all
  Time (mean ± σ):      6.727 s ±  0.063 s    [User: 6.486 s, System: 0.226 s]
  Range (min … max):    6.675 s …  6.872 s    10 runs

linux w/ commit-graph and both patches:
Benchmark #1: ~/src/git/git name-rev --all
  Time (mean ± σ):     988.8 ms ±   4.5 ms    [User: 937.5 ms, System: 49.2 ms]
  Range (min … max):   981.4 ms … 994.8 ms    10 runs

---
 builtin/name-rev.c | 39 +++++++++++++++++++--------------------
 1 file changed, 19 insertions(+), 20 deletions(-)

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 4162fb29ee..7fee664574 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -75,15 +75,14 @@ static int is_better_name(struct rev_name *name,
 	return 0;
 }

-static void name_rev(struct commit *commit,
-		const char *tip_name, timestamp_t taggerdate,
+static void name_rev(struct commit *commit, struct strbuf *sb,
+		timestamp_t taggerdate,
 		int generation, int distance, int from_tag,
 		int deref)
 {
 	struct rev_name *name = get_commit_rev_name(commit);
 	struct commit_list *parents;
 	int parent_number = 1;
-	char *to_free = NULL;

 	parse_commit(commit);

@@ -91,7 +90,7 @@ static void name_rev(struct commit *commit,
 		return;

 	if (deref) {
-		tip_name = to_free = xstrfmt("%s^0", tip_name);
+		strbuf_addstr(sb, "^0");

 		if (generation)
 			die("generation: %d, but deref?", generation);
@@ -99,14 +98,13 @@ static void name_rev(struct commit *commit,

 	if (!name || is_better_name(name, taggerdate, distance, from_tag)) {
 		free(name);
-		FLEX_ALLOC_STR(name, tip_name, tip_name);
+		FLEX_ALLOC_MEM(name, tip_name, sb->buf, sb->len);
 		name->taggerdate = taggerdate;
 		name->generation = generation;
 		name->distance = distance;
 		name->from_tag = from_tag;
 		set_commit_rev_name(commit, name);
 	} else {
-		free(to_free);
 		return;
 	}

@@ -114,28 +112,26 @@ static void name_rev(struct commit *commit,
 			parents;
 			parents = parents->next, parent_number++) {
 		if (parent_number > 1) {
-			size_t len;
-			char *new_name;
-
-			strip_suffix(tip_name, "^0", &len);
+			int stripped = strbuf_strip_suffix(sb, "^0");
+			size_t base_len = sb->len;
 			if (generation > 0)
-				new_name = xstrfmt("%.*s~%d^%d", (int)len, tip_name,
-						   generation, parent_number);
-			else
-				new_name = xstrfmt("%.*s^%d", (int)len, tip_name,
-						   parent_number);
+				strbuf_addf(sb, "~%d", generation);
+			strbuf_addf(sb, "^%d", parent_number);

-			name_rev(parents->item, new_name, taggerdate, 0,
+			name_rev(parents->item, sb, taggerdate, 0,
 				 distance + MERGE_TRAVERSAL_WEIGHT,
 				 from_tag, 0);
-			free(new_name);
+			strbuf_setlen(sb, base_len);
+			if (stripped)
+				strbuf_addstr(sb, "^0");
 		} else {
-			name_rev(parents->item, tip_name, taggerdate,
+			size_t base_len = sb->len;
+			name_rev(parents->item, sb, taggerdate,
 				 generation + 1, distance + 1,
 				 from_tag, 0);
+			strbuf_setlen(sb, base_len);
 		}
 	}
-	free(to_free);
 }

 static int subpath_matches(const char *path, const char *filter)
@@ -200,6 +196,7 @@ static int tipcmp(const void *a_, const void *b_)

 static int name_ref(const char *path, const struct object_id *oid, int flags, void *cb_data)
 {
+	static struct strbuf sb = STRBUF_INIT;
 	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;
@@ -269,7 +266,9 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
 		if (taggerdate == TIME_MAX)
 			taggerdate = ((struct commit *)o)->date;
 		path = name_ref_abbrev(path, can_abbreviate_output);
-		name_rev(commit, path, taggerdate, 0, 0, from_tag, deref);
+		strbuf_reset(&sb);
+		strbuf_addstr(&sb, path);
+		name_rev(commit, &sb, taggerdate, 0, 0, from_tag, deref);
 	}
 	return 0;
 }
--
2.23.0