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