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

Commit Message

René Scharfe Feb. 4, 2020, 9:26 p.m. UTC

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 <[e-mail]>
---
 builtin/name-rev.c | 21 ++++++++++++++++-----
 1 file changed, 16 insertions(+), 5 deletions(-)

--
2.25.0

Comments

Derrick Stolee Feb. 5, 2020, 3:19 p.m. UTC | #1

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

Patch

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;