Re: [PATCH v7 17/31] merge-recursive: add a new hashmap for storing directory renames

[Elijah Newren <newren@gmail.com>]

On Mon, Feb 5, 2018 at 11:44 AM, Stefan Beller <sbeller@google.com> wrote:
>>> Having a stringlist of potentially new dirs sounds like the algorithm is
>>> at least n^2, but how do I know? I'll read on.
>>
>> Yes, I suppose it's technically n^2, but n is expected to be O(1).
>> While one can trivially construct a case making n arbitrarily large,
>> statistically for real world repositories, I expected the mode of n to
>> be 1 and the mean to be less than 2.  My original idea was to use a
>> hash for possible_new_dirs, but since hashes are so painful in C and n
>> should be very small anyway, I didn't bother.  If anyone can find an
>> example of a real world open source repository (linux, webkit, git,
>> etc.) with a merge where n is greater than about 10, I'll be
>> surprised.
>>
>> Does that address your concern, or does it sound like I'm kicking the
>> can down the road?  If it's the latter, we can switch it out.
>
> I think that is fine for now; the real world usage matters more
> than the big O notation. But maybe you want to hint at the possibility of
> speedup (in the commit message or in code?), once someone produces
> a slow case and digs up the code.

Sounds like a good idea; I'll add a comment about this issue to the
commit message.