[PATCH] osutil.c: Win32 implementation with review notes from crew incorporated

[Adrian Buehlmann]

On 11.09.2008 14:23, Petr Kodl wrote:
> Adrian Buehlmann wrote:
>> On 11.09.2008 05:32, Matt Mackall wrote:
>>   
>>> On Wed, 2008-09-10 at 13:45 -0400, Petr Kodl wrote:
>>>     
>>>> +	if (PyList_Sort(list))
>>>> +		goto error_file;
>>>>       
>>> Similar arguments apply here. But we actually don't even want to sort at
>>> this level anyway.
>>>     
>> Both the unix C implementation and the default python implementation of
>> listdir [1] currently _do_ sort the list.
>>
>> Now Petr has removed the sorting altogether from the Windows implementation
>> of listdir in his newest version of the patch he sent to this list.
>>
>> I thought the sorting was one of the main speedup reasons for what bos
>> contributed?
>>
>> So should the sorting now be removed from listdir or what?
>>
>> This is again very confusing.
>>   
> I removed it based on the comment, but looking at the code it should 
> have stayed - the walk code uses bisect_left to search for nested 
> repositories - which assumes sorted list.
> The question is if this is the best approach - we trade O(n log n) sort 
> + O(log n) search for no sort + O(n) search - maybe dropping the sort 
> and using simple linear search would do the same service. There does not 
> seem to be
> any other place that would benefit or depend on results being sorted.

Here is bos' old posting and cset (just for reference):

http://www.selenic.com/pipermail/mercurial-devel/2007-September/003063.html
http://hg.intevation.org/mercurial/crew/rev/5105b119edd2