Re: [boost] [review] Last day for formal review for Sort library

Subject: Re: [boost] [review] Last day for formal review for Sort library
From: Thijs van den Berg (thijs_at_[hidden])
Date: 2014-11-20 05:53:25

>> -----Original Message-----
>> From: Boost [mailto:boost-bounces_at_[hidden]] On Behalf Of Steven Ross
>> Sent: 19 November 2014 23:18
>> To: boost_at_[hidden]
>> Subject: Re: [boost] [review] Last day for formal review for Sort library
>> 
>> It's the better of O(N*log(N)) and O(N*((K/S)+S)), where K is the key length
> in bits and
>> S is the division factor (11 by default).  Practically, it ends up being a
> slightly better
>> than constant speedup for integer_sort and float_sort (that fluctuates based
> on the
>> number of radix iterations
>> required) from N=10000 up until N gets close to 2^K when it starts switching
> to
>> bucketsort.  For string_sort the speedup can be much more dramatic for long
> keys
>> (because it does O(N) comparisons, and string comparisons take time
> proportional
>> to the length of the key, making comparison-based sort worst-case be
>> O(N*log(N)*K/C), where C may be as high as 64), but for shorter strings it has
> a
>> speedup similar to integer_sort and float_sort.  Bottom line is: it's faster,
> but
>> complicated to summarize.
>> Do you have a recommendation on how to summarize that better?
> 
> Put the bottom line first ;-)
> 
> But do include all of this (and more) in the docs - we are not short of space
> :-)
> 
> It is important that people realize just how complicated sort-speed is - if
> nothing else.
> 
> Paul

I thinks that’s a very good idea.

The reason of existence of this code is “performance” so be as transparent as possible about that aspect. If people think this is to technical then they’ll skip the paragraph, but I I doubt it: typical users are likely looking for alternatives to std::sort because of performance. Knowing this will make it easier for developers to stress test performance benchmarks and know where to look for corner cases.