[boost] [sort] Review of the Sort library by Steven Ross

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 
problems?
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