Re: Why are ref_lists sorted?

[Linus Torvalds <torvalds@linux-foundation.org>]

On Mon, 19 Mar 2007, Julian Phillips wrote:
> 
> So my questions are:
> 
> 1) what have I broken by removing the sort?

The big thing is probably consistency.

I *really* think we need to sort these things. Otherwise you'll see two 
totally identical repositories giving different results to something as 
fundamental as "git ls-remote" just because they didn't get sorted.

So I think sorting is absolutely required, perhaps not so much because it 
is necessarily "incorrect" without the sorting, but because I think 
consistency in this area is too important *not* to sort it.

And sorting it really is simple. The fact that we use a O(n**2) list 
insertion thing that is also probably pessimal for the case of "already 
sorted" input is just a "hey, it was easy, we never actually hit it in 
practice" issue. 

> 2) is it worth trying to optimise the sort?

Absolutely. It might involve changing the "ref_list *" thing into an array 
of ref_entries, and that will cause a lot of (fairly trivial) changes, but 
it should all be entirely internal to refs.c, so it's hopefully not 
painful, just some boring grunt-work.

		Linus