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
> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk