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

On 11/13/2014 08:50 AM, Steven Ross wrote:

Niall,

On Mon Nov 10 2014 at 1:05:28 PM Niall Douglas 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/LogLogBitwiseTreesS...

http://www.nedprod.com/programs/portable/nedtries/images/LogLogRedBlac kTreesScaling.png http://www.nedprod.com/programs/portable/nedtries/images/LogLogRedBlackTrees...

http://www.nedprod.com/programs/portable/nedtries/images/LogLogHashTab leScaling.png http://www.nedprod.com/programs/portable/nedtries/images/LogLogHashTableScal...

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-...

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