Re: [boost] [SORT] Parallel Algorithms

Subject: Re: [boost] [SORT] Parallel Algorithms
From: Steven Ross (spreadsort_at_[hidden])
Date: 2015-01-13 21:52:47

Francisco,

On Tue Jan 13 2015 at 12:43:00 PM Francisco José Tapia <fjtapia_at_[hidden]>
wrote:

> Hi Steven,
>
>  This Christmas I had been working hard. I developed a new version of the
> merge sort about 10-15% faster than the previous, using an additional
> memory only ½ of the memory used by the data. The GCC and TBB algorithms
> use an additional memory as the size of the data.
>

>
>  This version is exception safe. If an exception occurs due to the
> algorithm ( only throw exceptions in the allocation and deallocation of the
> additional memory), the integrity of the data is guarantee. You have all
> the original data (unordered in the allocation, and ordered in the
> deallocation)
>
> Less memory, comparable speed, and exception safety sounds good.

>  I examined the TBB version and the secret is the sample sort algorithm.
> The version of TBB is provisional and it's not exception safe. I am working
> in the design of a new version of this algorithm exception safe. The actual
> version of the parallel stable algorithm is about 20% slower than the TBB
> version in the worse case, but when the size of the elements grows, the
> indirect version is faster than all the others, with 64 bytes, is around
> 10% faster than the best TBB version, with 128 bytes , the best version of
> TBB is around a 90% slower, and with 256 is 240% slower.
>
> Yes, indirect sorting is clearly superior for large data types, and it
would be good to make it as easy as possible to use.  It'd be nice to also
have a simple wrapper that can be use the spreadsort algorithm with
indirect sorting too.

I am in the process of integrating the first version of the boost sort
library in https://github.com/boostorg/sort.  It would be good to integrate
your testing with the tests in that library.