Subject: Re: [boost] [SORT] Parallel Algorithms
From: Francisco JosÃ© Tapia (fjtapia_at_[hidden])
Date: 2015-01-14 11:26:49
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
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.
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk