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: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2014-11-13 06:45:13

On 13 Nov 2014 at 5:50, Steven Ross wrote:

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

That is indeed a very useful graph which definitely should be near 
the first page of your docs. At a glance one can tell whether one 
should be interested in your algorithm or not.

Three items: I'd put everything in CPU cycles instead of seconds. 
This removes to some extent the effect of fast CPUs, or indeed of 
Intel CPUs, and lets the reader more quickly decide if this algorithm 
is worth using. I would assume you'll be mostly memory bound anyway, 
but I do see a small amount of logistic curve from LL cache effects 
in there. I would definitely say in your documentation the *exact* 
spec of the machine used for testing, including its RAM speed and 
bandwidth. I may be able to give you some benchmarks for your library 
on a quad core ARMv7 Tegra K1 board if you email me privately when 
you have a final benchmark package ready. You may find your algorithm 
has *very* different performance on an ARM :)

The second thing is that I would separate 4 threaded from single 
threaded graphs as too much information confuses. You could use the 
opportunity to put string sort on the same graph as int sort for 
single threaded.

And thirdly, I'd use more than 10,000 elements as I understand that's 
where your algorithm really pays off. You can then say "at > 100,000 
elements my algorithm is X.Y times the performance of std::sort".

I think for me at least Steven my only last remaining problem is the 
library name. Boost.Sort implies a library with at least three useful 
sorting algorithms not in the STL. Either you add those, or rename 
the library. I'd much prefer the former.

Niall

-- 
ned Productions Limited Consulting
http://www.nedproductions.biz/ 
http://ie.linkedin.com/in/nialldouglas/