Re: [PATCH v2 7/8] diff: add ability to insert additional headers for paths

On Thu, Dec 30, 2021 at 02:04:30PM -0800, Elijah Newren wrote:

quoted

                                enqueue(file_pair_for(extra_headers[j]))

The queue is an array of sorted items, so enqueue here would be
insertion into an already sorted list.  Inserting N items into a list
of M items is quadratic (O(N*M)) -- unless you meant to just append to
the end and add a third sort at the end?

yeah I would have probably used a third sort

quoted

                        j++

At the end of the for loop, there may be remaining additional headers
that sort after all those found in the queue, so you'll need an
additional loop to handle those.

my bad, I should have tried it

It's actually considerably more code as you can see from the diffstat,
and feels like we're reaching into some ugly internals with tmp_queue
(the SWAP and the special-case freeing) in order to get the desired
performance improvements.  And it was already O(NlogN) overall (due to
the sort), which doesn't change with this new algorithm.  It's really,
really hard for me to imagine a case where we have large numbers of
additional headers.  Even if someone else can imagine that we for some
reason have a huge number of conflicts in order to generate a huge
number of additional headers...how could the performance of sorting
O(N) filenames and merging these lists possibly matter in comparison
to the O(N) three-way file merges that would likely have been
performed from those conflicts?

Yeah, I agree with that conclusion, it's surely not worth the added complexity.
Seeing the code definitely helps, thanks.

So, I'm going to throw this code away and keep the original.

It was an interesting idea and exercise; thanks for keeping me on my toes.