Re: [PATCH 3/6] prune_remote(): sort delete_refs_list references en masse

[Michael Haggerty <mhagger@alum.mit.edu>]

On 11/21/2014 05:44 PM, Junio C Hamano wrote:
> On Fri, Nov 21, 2014 at 6:09 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
>> Inserting items into a list in sorted order is O(N^2) whereas
>> appending them unsorted and then sorting the list all at once is
>> O(N lg N).
>>
>> string_list_insert() also removes duplicates, and this change loses
>> that functionality. But the strings in this list, which ultimately
>> come from a for_each_ref() iteration, cannot contain duplicates.
>>
> 
> A similar conversion in other places we may do in the future
> might find a need for an equivalent to "-u" option of "sort" in the
> string_list_sort() function, but the above nicely explains why
> it is not necessary for this one.  Good.

The only reason to integrate "-u" functionality into the sort would be
if one expects a significant fraction of entries to be duplicates, in
which case the sort could be structured to discard duplicates as it
works, thereby reducing the work needed for the sort. I can't think of
such a case in our code. Otherwise, calling sort_string_list() followed
by string_list_remove_duplicates() should be just as clear and
approximately as efficient.

A couple of times I've also felt that an all-purpose *stable* sort would
be convenient (though I can't remember the context offhand). I don't
think we have such a thing.

> Eh, why is that called sort_string_list()?  Perhaps it is a good
> opening to introduce string_list_sort(list, flag) where flag would
> be a bitmask that represents ignore-case, uniquify, etc., and
> then either deprecate the current one or make it a thin wrapper
> of the one that is more consistently named.

I agree. Indeed, I typed that function's name wrong once when
constructing this patch. It would be better to name it consistently with
the other string_list_*() functions.

I put it on my todo list (but don't let that dissuade somebody else from
doing it).

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu