[PATCH 06/15] ref_remove_duplicates(): avoid redundant bisection

The old code called string_list_lookup(), and if that failed called string_list_insert(), thus doing the bisection search through the string list twice in the latter code path.

Instead, just call string_list_insert() right away. If an entry for that peer reference name already existed, then its util pointer is always non-NULL.

Of course this doesn't change the fact that the repeated string_list_insert() calls make the function scale like O(N^2) if the input reference list is not already approximately sorted.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---

The O(N^2) algorithm mentioned above essentially boils down to

    for each reference:
        insert reference into string_list (sorted)

Because the insertion requires later array entries to be shifted to the right, the algorithm scales like O(N^2) if the entries are not already approximately in order.

I can think of three easy ways to fix this:

* Use a hash map instead of a sorted string_list to record which
  entries have already been seen.

* If the order of the result doesn't matter and it doesn't matter
  *which* of the duplicates is retained, then insert all of the names
  into the string_list unsorted, then sort them all in one go, then
  iterate through looking for duplicates and stringing the survivors
  together in a new linked list.

* If the order is important, or it is important that the *first* of
  duplicates be retained, then iterate through the linked list twice.
  The first time, just add the entries to the string_list.  Then sort
  the string_list using a stable sort (e.g., git_qsort()).  Then
  iterate through the linked list a second time as in the current
  code.

See also my comments to commit 10.

However, I believe that the O(N^2) worst case is unlikely to bite in most cases. This function is called from builtin/fetch.c:get_ref_map(), and the input list is the concatenation of several sub-lists. Most sublists come from resolving refspecs, and the last comes from find_non_local_tags(). I believe that each of the sublists is sorted. So the O(N^2) worst-case could only occur if more than one of the sublists is large and at least two of the large sublists are not in the correct order relative to each other.

I tried to concoct such a test case by creating a repository with about 20k branches and 20k tags, instrumenting ref_remove_duplicates(), and then fetching with something like

    git fetch --prune origin refs/heads/*:refs/remotes/origin/* \
                             refs/tags/*:refs/tags/*

Indeed, the running time of ref_remove_duplicates() became significant when the order of the refspecs was reversed, but it was still less than a second out of a much longer command invocation.

So I didn't bother fixing the O(N^2) algorithm. If somebody reports real-world slowness here, we can always come back to it.

 remote.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)