All of
 help / color / mirror / Atom feed
From: "René Scharfe" <>
To: Derrick Stolee <>,
	Git Mailing List <>
Cc: "SZEDER Gábor" <>,
	"Martin Ågren" <>,
	"Junio C Hamano" <>
Subject: Re: [PATCH 09/10] name-rev: generate name strings only if they are better
Date: Wed, 5 Feb 2020 16:50:23 +0100	[thread overview]
Message-ID: <> (raw)
In-Reply-To: <>

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.


  reply	other threads:[~2020-02-05 15:50 UTC|newest]

Thread overview: 27+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-02-04 21:12 [PATCH 00/10] name-rev: improve memory usage René Scharfe
2020-02-04 21:14 ` [PATCH 01/10] name-rev: rewrite create_or_update_name() René Scharfe
2020-02-05  2:00   ` Derrick Stolee
2020-02-05  2:35     ` Taylor Blau
2020-02-05 16:45   ` Andrei Rybak
2020-02-05 16:47     ` René Scharfe
2020-02-04 21:15 ` [PATCH 02/10] name-rev: remove unused typedef René Scharfe
2020-02-04 21:16 ` [PATCH 03/10] name-rev: respect const qualifier René Scharfe
2020-02-04 21:17 ` [PATCH 04/10] name-rev: don't leak path copy in name_ref() René Scharfe
2020-02-05 14:35   ` Derrick Stolee
2020-02-04 21:20 ` [PATCH 05/10] name-rev: don't _peek() in create_or_update_name() René Scharfe
2020-02-04 21:22 ` [PATCH 06/10] name-rev: put struct rev_name into commit slab René Scharfe
2020-02-04 21:23 ` [PATCH 07/10] name-rev: factor out get_parent_name() René Scharfe
2020-02-04 21:24 ` [PATCH 08/10] name-rev: pre-size buffer in get_parent_name() René Scharfe
2020-02-05  3:19   ` Derrick Stolee
2020-02-05 15:16     ` René Scharfe
2020-02-04 21:25 ` [PATCH 09/10] name-rev: generate name strings only if they are better René Scharfe
2020-02-05 15:11   ` Derrick Stolee
2020-02-05 15:50     ` René Scharfe [this message]
2020-02-04 21:26 ` [PATCH 10/10] name-rev: release unused name strings René Scharfe
2020-02-05 15:19   ` Derrick Stolee
2020-02-05  3:28 ` [PATCH 00/10] name-rev: improve memory usage Derrick Stolee
2020-02-05 15:20   ` Derrick Stolee
2020-02-05 17:19 ` [PATCH 01/10 RESEND AUTHOR FIXED] name-rev: rewrite create_or_update_name() René Scharfe
2020-02-05 17:50 ` [PATCH 11/10] name-rev: sort tip names before applying René Scharfe
2020-02-05 18:23   ` Junio C Hamano
2020-02-05 18:55     ` René Scharfe

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \ \ \ \ \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.