
Boost : 
Subject: Re: [boost] [review] Formal review period for Sort library begins today, November 10, and ends Wednesday, November 19
From: Steven Ross (spreadsort_at_[hidden])
Date: 20141110 10:48:14
Antony,
> Implementation is not tuned.
>
> For example, take a look
> here
> https://github.com/spreadsort/sort/blob/master/include/boost/sort/detail/spread_sort_common.hpp#L110
> and here
> https://github.com/spreadsort/sort/blob/master/include/boost/sort/detail/spread_sort_common.hpp#L116
> .
> Memory allocations occur at those points, however they could be easily
> avoided. Here's a typical use case of `size_bins` function:
> https://github.com/spreadsort/sort/blob/master/include/boost/sort/detail/string_sort.hpp#L170.
>
> Using a stack based buffer would significantly improve sort times on small
> datasets.
You have a good point that a stackbased buffer would eliminate memory
allocation for the bin_sizes (thanks!). On large data sets, there are
very few memory allocations, as it quickly hits the maximum size that
can be used. My optimization has concentrated on minimizing memory
overhead and optimizing speed on large data sets. Would you agree
that a fixed stackbased array of bin_sizes, passed down into the
recursive calls, would provide a good tradeoff between speed and
memory overhead?
It will still need memory allocation for the bin_cache, unless it
computes the worstcase size based on the size of the input data type
and the maximum number of bins per iteration. That could end up being
a substantial chunk of RAM to put on the stack (10s of kilobytes!) for
the nonfunctor versions of integer_sort and float_sort. It would be
tricky to add for the functor versions. string_sort can iterate to an
incredible depth in the worstcase, so it just doesn't seem practical
to put the bin_cache on the stack there. Do you think I should add
the bin_cache to the stack where feasible for integer_sort and
float_sort? It may add significant complication.
> Not in its current state. And not as a separate library. This must be a
> part of Boost.Algorithm library.
That's how I originally planned to add it, but apparently that doesn't
work so well with modular boost. I'm open to that possibility.
> This library must be accepted only after some good optimization. As a
> result, I'd like to see this library outperforming std::sort even on small
> datasets (~150 elements). At the current point std::sort and sort from the
> subject library differ on some constant value (see
> graph/windows_integer_sort.htm or graph/windows_string_sort.htm), not
> O(n*log(n)) vs O(n*log(k/s+s)).
n * (k/s + s) is the worstcase, rarely encountered for integer_sort
for normal data. What ends up happening on most data is that it tends
to run around log(n)/s expensive radixbased based iterations, plus
around s fast comparisonbased iterations.
So It works out to comparing log(n) vs C1*log(n)/s + s. This ends up
looking like a constant, though it does get a bit faster as the "+s"
term get proportionately smaller with large n (and the asymptote in
this regime is a constant). Eventually n gets close to k and the
worstcase guarantee kicks in. See the left side of
graph/osx_integer_sort.htm for examples of this faster bucket sorting.
Note that in the speed vs size graphs each increment in the normal
number of radixbased iterations causes a jump in relative
performance: this can be seen in windows_integer_sort between 2^23 and
2^24, and 2^13 to 2^14. string_sort shows similar changes in relative
performance vs size as the number of radixsorted bytes increases,
though I should note that for string_sort, the worstcase is much
superior to comparisonbased sorting, as each comparison may run over
the entire length of the string, where radixbased sorting will only
pass over each character once (or twice, if you include the scan for
all characters being identical). I didn't use this worstcase for
comparisonbased sorting when making the graphs, but I could if you'd
like to see spectacular speedups.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk