path: root/builtin/name-rev.c
diff options
authorRené Scharfe <>2020-02-04 21:26:18 (GMT)
committerJunio C Hamano <>2020-02-05 18:24:15 (GMT)
commit2d53975488df195e1431c3f90bfb5b60018d5bf6 (patch)
tree8c8a98adb4bff18368818dc91fc0a8e1f146e989 /builtin/name-rev.c
parent977dc1912bd74dbc7f94581f36b7e78eae49a8c3 (diff)
name-rev: release unused name strings
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 <> Signed-off-by: Junio C Hamano <>
Diffstat (limited to 'builtin/name-rev.c')
1 files changed, 16 insertions, 5 deletions
diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 98f55bc..23a639f 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;