avoid toLower in std.algorithm.sort compare alias

[Steven Schveighoffer]

On Sat, 21 Apr 2012 19:24:56 -0400, Jay Norwood <jayn at prismnet.com> wrote:

> While playing with sorting the unzip archive entries I tried use of the  
> last example in http://dlang.org/phobos/std_algorithm.html#sort
>
> std.algorithm.sort!("toLower(a.name) <  
> toLower(b.name)",std.algorithm.SwapStrategy.stable)(entries);
>
> It was terribly slow  for sorting the 34k entries in my test case.  I'd  
> guess it is doing the toLower call on both strings for every compare.
>
> It was much, much faster to add an entries.lowerCaseName =  
> std.string.toLower(entries.name) foreach entry prior to the sort  
> execution and then use
>
> std.algorithm.sort!("a.lowerCaseName < b.lowerCaseName  
> ",std.algorithm.SwapStrategy.stable)(entries);
>
> The difference was on the order of 10 secs vs no noticeable delay when  
> executing the sort operation in the debugger.

I'll point out what I haven't seen yet:

the issue is not so much toLower being called on every comparison, but  
more that toLower allocates (and then throws away!).

I think using std.string.icmp is the best solution.  I would expect it to  
outperform even schwartz sort.

Note, to answer your question elsewhere, the comment is accurate,  
std.uni.toLower(a) is a function that accepts a dchar, not a string.  What  
the comment is saying is that for the "ranges" (i.e. strings) given, it  
runs the given comparison on the std.uni.toLower() result for each element  
(i.e. dchar).

-Steve