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

[Matt Mackall]

On Thu, 2008-09-11 at 08:23 -0400, 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.

If we wanted to be clever, we would skip both the sort and the search.
Instead, if listdir finds a .hg directory, it makes it the first
element.

-- 
Mathematics is the supreme nostalgia of our time.