Re: [boost] [SORT] Parallel Algorithms

Subject: Re: [boost] [SORT] Parallel Algorithms
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2015-01-14 11:26:49

Hi Thorsten,

 The idea about the indirect sort is very easy. Instead of sort the
elements, create a vector of pointers, and sort the vector of pointers,
with this you don't move the elements , move the pointers. And at end with
the vector of pointers sorted, move the data only 1 time.

 In the stable sort, the algorithms usually need additional memory. The GCC
and TBB the same memory than the data, in my algorithms only 1 half.
Imagine you want to sort 10 million elements of 128 bytes each. With the
indirect sort you need 10 million pointers and additionally memory for to
allocate 5 million pointers.

 The memory used by the data is 1280 Megas, but pointers and the additional
memory are 15 million * 8 = 120 Megas, around a 10% of the memory used by
the data.

 In the first messages of this conversation, I sent a zip with code. In
this file you can find the code of the indirect sort. If don't understand,
something, please say me, and I will try to explain.

 Paul,

 about the name space, if at end, the results are satisfactory, and decide
to include in the library, only say me the name space and I will put. For
me it's indifferent . But, I need time for the new algorithm, and design a
complete test suite of the code, the benchmarks, for to compare with others
versions and the documentation.

 If you want a benchmark with multi precision numbers, we can do without
problem, even if you want to check the speed with different sizes of the
numbers

 Yours

 Francisco