Re: [RFC PATCH 2/2] merge-recursive: optimize time complexity for get_unmerged

From: Junio C Hamano <gitster@pobox.com>
Date: Feb 13, 2025, 18:30 UTC
Message-ID: <xmqqwmdtofxh.fsf@gitster.g>
In-Reply-To: <CABPp-BGqihkPq3o4jnqp2aGdqw12F8a8nOModuAB-5N7BQ1t0w@mail.gmail.com>

Elijah Newren <newren@gmail.com> writes:

> (As a side note, due to the specialized structure of the input, I
> suspect this code could be modified to run in O(n), i.e. we could skip
> the string_list_lookup and the string_list_sort and the
> string_list_remove_duplicates...

Are you talking about the input being already sorted so we can just walk the multiple input and merge them into a single stream? In the cost analysis you did earlier in the message I am responding to, being able to go down to O(n) sounds really like a great thing ;-)

> But, it'd make the code trickier, so
> it'd need to be carefully commented, the change would need to be
> justified, and it'd need to be carefully tested.

... and measured.

Show 6 quoted lines

> Even if we weren't
> planning to delete this entire file, I suspect it's not possible to
> find a case justifying such a change without optimizing several other
> things in merge-recursive first, but optimizing those things probably
> results in a significant rewrite...which we've already done with
> merge-ort.)

Sounds like unless the performance issues are shared between the two, it may not be worth to spend too much brain cycles only on the "recursive" one?

Thanks.