On Mon, Feb 5, 2018 at 11:44 AM, Stefan Beller [off-list ref] wrote:

quoted

quoted

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.