[boost] [sort] Parallel sorting sub-library mini-review starts tomorrow, 11 November

Subject: [boost] [sort] Parallel sorting sub-library mini-review starts tomorrow, 11 November
From: Steven Ross (spreadsort_at_[hidden])
Date: 2016-11-10 20:25:17

Dear Boost community,

The mini-review of Francisco Tapia's Parallel sorting library begins
tomorrow November 11, and ends November 20th.  The purpose of this review
is to assess whether the sub-library is useful and up to Boost software
standards.  If the Boost community agrees on both, Francisco and I will
integrate it into the existing Boost.sort library as a separate sub-library
from Spreadsort.  In doing so we'll integrate the documentation with the
existing documentation for Boost.Sort, making it more consistent.

If you review Francisco's library, please make sure you're using a compiler
that supports C++11, and answer each of these questions:

   1. Were you able to run it and see accurate and fast results?  Please
   specify your compiler, OS, and processor type, and any problems (or
   slowdowns) encountered.
   2. Would you use this library if accepted?  Why or why not?
   3. What is your evaluation of the design?
   4. What is your evaluation of the implementation?
   5. How much effort did you put into your evaluation? A glance? A quick
   reading? In-depth study?

The library is here: https://github.com/fjtapia/sort_parallel
This library provides both stable and unstable sorting algorithms, in single
threaded and parallel versions.

   -

   All the algorithms have average and worst case runtime of O(NLogN).
   -

   These algorithms do not use any other library or utility. To compile and
   run these you will need a *C++11 compliant compiler.*
   -

   *This library is *include only, only requiring* the files in the
   boost/sort/parallel folder, with no external dependencies.*
   -

   The algorithms use a comparison object, in the same fashion as
   std::sort, defaulting to the std::less object, which uses the < operator
   internally for comparisons.
   -

   The algorithms are exception safe, meaning that the exceptions generated
   by the algorithms guarantee the integrity of the objects to sort, but not
   their relative order. If the exception is generated inside the objects (in
   the move or in the copy constructor) the results can be unpredictable.

The library has a a new parallel_sort algorithm *( internally named Block
Indirect)*, for processors connected with shared memory*,* invented for the
library. This new algorithm combines the speed of algorithms like the
GCC parallel
sort (based on OpenMP), or the Microsoft parallel buffered sort, with the small
memory consumption of algorithms like the TBB sort and the Microsoft
parallel Sort.

Results from running on an I7 5820 with 12 threads:

GCC parallel_sort

1,25 secs

1560 MB

TBB parallel_sort

1,64 secs

783 MB

Boost parallel_sort

1,08 secs

786 MB

In a separate repository (because it uses licence-restricted software like
TBB and Microsoft parallel sort, and can’t be included in the Boost
library), you can find all the code needed to run the benchmarks, the
library code, the benchmark programs, and shell scripts to compile and run
it on your machine in Linux and Windows. For the Linux benchmarks you will
need to install TBB. (https://github.com/fjtapia/sort_parallel_benchmark)

We look forward to your feedback!