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

[Junio C Hamano <gitster@pobox.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.

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