From: Derrick Stolee <stolee@gmail.com>
Date: Wed, 05 Feb 2020 15:11:44 GMT
Subject: Re: [PATCH 09/10] name-rev: generate name strings only if they are better
Message-ID: <3a59d8b4-3c3d-3812-9b7e-ac7e331ccd1c@gmail.com>
In-Reply-To: <77d1d053-8680-5cbe-9182-b6aec9e9b446@web.de>

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.

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.

Thanks,
-Stolee