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

From: "René Scharfe" <l.s.r@web.de>
To: "SZEDER Gábor" <szeder.dev@gmail.com>
Cc: Junio C Hamano <gitster@pobox.com>, git@vger.kernel.org
Subject: Re: [PATCH 08/15] name-rev: pull out deref handling from the recursion
Date: Mon, 23 Sep 2019 21:55:11 +0200	[thread overview]
Message-ID: <0febc113-ce84-4794-890f-4703c07057dc@web.de> (raw)
In-Reply-To: <20190923185908.GB2637@szeder.dev>

Am 23.09.19 um 20:59 schrieb SZEDER Gábor:
> On Mon, Sep 23, 2019 at 08:43:11PM +0200, René Scharfe wrote:
>>> It's overall memory usage, the avarage of five runs of:
>>>
>>>   /usr/bin/time --format='%M' ~/src/git/git name-rev --all
>>>
>>>> And how much is that in absolute terms?
>>>
>>> git:     29801 ->  28514
>>> linux:  317018 -> 332218
>>> gcc:    106462 -> 114140
>>> gecko:  315448 -> 344486
>>> webkit:  55847 ->  62780
>>> llvm:   112867 -> 134384
>>
>> I only have the first two handy, and I get numbers like this with
>> master:
>>
>> git, lots of branches with long names: 3075476
>> git, local clone, single branch:       1349016
>> linux, single branch:                  1520468
>>
>> O_o
>
> I have commit graph present and enabled.  Without that I get approx.
> the same memory usage in my linux repo as you did (along with much
> longer runtime).

OK.  Cloned git afresh and tried with master and without commit-graph
again, after "git commit-graph write" and both again with the patch
below:

git:                           109880
git w/ commit-graph:            47208
git w/ patch:                   94304
git w/ commit-graph and patch:  31220

Strange numbers, at least compared to my number for the clone above:
One order of magnitude less!  Not sure what to make of it.  (Tried
the clone again, same result.)

Anyway, here's the patch:

-- >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.

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

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index c785fe16ba..4162fb29ee 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -12,11 +12,11 @@
 #define CUTOFF_DATE_SLOP 86400 /* one day */

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

 define_commit_slab(commit_rev_name, struct rev_name *);
@@ -97,17 +97,14 @@ static void name_rev(struct commit *commit,
 			die("generation: %d, but deref?", generation);
 	}

-	if (name == NULL) {
-		name = xmalloc(sizeof(rev_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;
+	if (!name || is_better_name(name, taggerdate, distance, from_tag)) {
+		free(name);
+		FLEX_ALLOC_STR(name, tip_name, tip_name);
 		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;
@@ -131,12 +128,14 @@ static void name_rev(struct commit *commit,
 			name_rev(parents->item, new_name, taggerdate, 0,
 				 distance + MERGE_TRAVERSAL_WEIGHT,
 				 from_tag, 0);
+			free(new_name);
 		} else {
 			name_rev(parents->item, tip_name, taggerdate,
 				 generation + 1, distance + 1,
 				 from_tag, 0);
 		}
 	}
+	free(to_free);
 }

 static int subpath_matches(const char *path, const char *filter)
@@ -270,8 +269,7 @@ 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, xstrdup(path), taggerdate, 0, 0,
-			 from_tag, deref);
+		name_rev(commit, path, taggerdate, 0, 0, from_tag, deref);
 	}
 	return 0;
 }
--
2.23.0
