Boost logo

Boost :

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


ned Productions Limited Consulting

Boost list run by bdawes at, gregod at, cpdaniel at, john at