Re: [PATCH] refs.c: add a function to sort a ref list, rather then sorting on add

From: Junio C Hamano <junkio@cox.net>
Date: Apr 17, 2007, 22:00 UTC
Message-ID: <7vslaymzk3.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <Pine.LNX.4.64.0704170901170.5473@woody.linux-foundation.org>

Linus Torvalds <torvalds@linux-foundation.org> writes:

Show 13 quoted lines

> On Tue, 17 Apr 2007, Julian Phillips wrote:
>>
>> Rather than sorting the refs list while building it, sort in one go
>> after it is built using a merge sort.  This has a large performance
>> boost with large numbers of refs.
>> 
>> Signed-off-by: Julian Phillips <julian@quantumfyre.co.uk>
>
> Acked-by: Linus Torvalds <torvalds@linux-foundation.org>
>
> Looks fine. I think that even your new times are a bit high (over two 
> seconds?) but things are clearly better. Have you looked at what takes so 
> long now?

I wonder why the loss of "we are replacing the same one" case in the original add_ref() was not compensated for in the new sort_ref_list().

I think we would not call add_ref() to the same list with duplicate names, unless (1) filesystem is grossly corrupt, (2) somebody added a new ref while we are walking (how does readdir() behave in such a case???), or (3) packed-refs file is corrupt.