Boost logo

Boost :

Subject: [boost] [sort] Review of the Sort library by Steven Ross
From: Edward Diener (eldiener_at_[hidden])
Date: 2014-11-14 07:21:53

As review manager I am forwarding this review sent to me:

- What is your evaluation of the design?
- What is your evaluation of the implementation?
Design an implementation look good to me. Spreadsort has a clean
interface and the code is readable. I tried the algorithm out a few
years ago in a project at work (our product in the EDA industry) for
sorting 32-bit {x,y} coordinate data cast to a 64-bit integer, and for
sorting 32-bit values within scanlines. The speedup was about 1.8x that
of std::sort() for ~100M values. This translated into a 10-20% overall
runtime reduction in that tool, with only a few lines of code changes.

- What is your evaluation of the documentation?
I haven't read through the documentation in detail, but I have read
through the code and the comments so I feel I understand the basics of
how the sorting algorithm works.

- What is your evaluation of the potential usefulness of the library?
I would say this library is very useful for specific tasks involving
large datasets that need to be sorted, especially in cases where the
data is already partially sorted and contains many duplicate values. For
example, it could be useful for EDA applications, computational
geometry, some types of databases, etc. It may be a fairly narrow user
base but I think it could add significant value.

- Did you try to use the library? With what compiler? Did you have any
I built and tested spreadsort on both linux/gcc and Windows/MSVC++. I
was never successful in running the tests in Cygwin. It seemed to work
as expected when I tried using it inside an EDA tool and caused no problems.

- How much effort did you put into your evaluation? A glance? A quick
reading? In-depth study?
I spent some hours reviewing the algorithm a few years ago, and I
provided Steve with feedback to improve the code. I was mostly
interested in the integer sorting aspect at that time, but did
experiment with floating-point numbers as well. I read through the code
again recently to familiarize myself with it.

- Are you knowledgeable about the problem domain?
I would say that I'm knowledgeable of applications and uses of sorting
large datasets, and algorithms in general. I don't have any specific
experience in developing or testing sorting algorithms.

- Do you think the library should be accepted as a Boost library?
Yes, I believe Steve has put in enough work to make this a well
designed, tested, and documented library. There are real numbers to show
the performance improvements over other sorting algorithms. If this was
part of Boost, I would probably use it in our product at my company.

Frank Gennari

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