Boost logo

Boost :

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


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

> 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 It would be good to integrate
your testing with the tests in that library.

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