Re: [boost] [sort] Re: [review] Formal review period for Sort library begins today, November 10, and ends Wednesday, November 1

Subject: Re: [boost] [sort] Re: [review] Formal review period for Sort library begins today, November 10, and ends Wednesday, November 1
From: Vladimir Prus (vladimir_at_[hidden])
Date: 2014-11-13 02:07:54

On 11/13/2014 08:50 AM, Steven Ross wrote:
> Niall,
>
> On Mon Nov 10 2014 at 1:05:28 PM Niall Douglas <s_sourceforge_at_[hidden]>
> wrote:
>
>> Sounds good. You'd get a graph of CPU cycle scaling to N looking
>> like:
>>
>> http://www.nedprod.com/programs/portable/nedtries/images/LogLogBitwise
>> TreesScaling.png
>> <http://www.nedprod.com/programs/portable/nedtries/images/LogLogBitwiseTreesScaling.png>
>>
>> http://www.nedprod.com/programs/portable/nedtries/images/LogLogRedBlac
>> kTreesScaling.png
>> <http://www.nedprod.com/programs/portable/nedtries/images/LogLogRedBlackTreesScaling.png>
>>
>> http://www.nedprod.com/programs/portable/nedtries/images/LogLogHashTab
>> leScaling.png
>> <http://www.nedprod.com/programs/portable/nedtries/images/LogLogHashTableScaling.png>
>>
>> For your situation you just sort, so a combined graph showing a
>> comparative to other algorithms makes much more sense.
>
>
> I've created an integer_sort graph here (click the graph tab at the bottom):
> https://docs.google.com/spreadsheets/d/1fUvIJQPaAbsUv54RGgNd-hWmJY996qvocaw-ylnUDG0/edit?usp=sharing
>
> If that's what you're looking for, I can create the equivalent graph for
> string_sort too.  The crossover point of about 1000 elements is quite
> visible, and both std::sort and integer_sort have some minor
> parallelization inefficiency, but I see no surprises, and expect none for
> string_sort.

Steven,

what input data distribution is this? Could you run the tests with worst-case data distribution
for your algorithm?

-- 
Vladimir Prus
CodeSourcery / Mentor Embedded
http://vladimirprus.com