Re: [PATCH 09/10] name-rev: generate name strings only if they are better

From: Derrick Stolee <stolee@gmail.com>
Date: Feb 5, 2020, 15:11 UTC
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:

Show 7 quoted lines

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