10#ifndef INCLUDED_COMPHELPER_PARALLELSORT_HXX
11#define INCLUDED_COMPHELPER_PARALLELSORT_HXX
32static thread_local std::mt19937
aGenerator{ std::random_device{}() };
34#define PARALLELSORT_ENABLEPZ 0
41#if PARALLELSORT_ENABLEPZ
42 ProfileZone(
const char* pTag)
44 ,
maStart(std::chrono::steady_clock::now())
61 ProfileZone(
const char* )
74#if PARALLELSORT_ENABLEPZ
76 void showTimeElapsed()
78 auto end = std::chrono::steady_clock::now();
80 = std::chrono::duration_cast<std::chrono::milliseconds>(
end -
maStart).count();
81 std::cout <<
maTag <<
" : " << elapsed <<
" ms" << std::endl << std::flush;
85 std::chrono::steady_clock::time_point
maStart;
98 Executor(
const std::shared_ptr<comphelper::ThreadTaskTag>& rTag,
99 std::function<
void()> aFunc)
101 ,
maFunc(std::move(aFunc))
105 virtual void doWork()
override {
maFunc(); }
114 void enqueue(std::function<
void()> aFunc)
122 std::shared_ptr<comphelper::ThreadTaskTag>
maTag;
125constexpr size_t nMaxTreeArraySize = 64;
127size_t lcl_round_down_pow2(
size_t nNum)
130 for (nPow2 = 1; nPow2 <= nNum; nPow2 <<= 1)
132 return std::min((nPow2 >> 1), nMaxTreeArraySize);
135template <
class RandItr>
struct Sampler
137 using ValueType =
typename std::iterator_traits<RandItr>::value_type;
139 static void sample(RandItr aBegin, RandItr aEnd,
ValueType* pSamples,
size_t nSamples,
142 ProfileZone aZone(
"\tsample()");
143 assert(aBegin <= aEnd);
144 size_t nLen =
static_cast<std::size_t
>(aEnd - aBegin);
145 assert(std::mt19937::max() >= nLen);
147 for (
size_t nIdx = 0; nIdx < nSamples; ++nIdx)
151 swap(*(aBegin + nSel), *(aBegin + nLen));
152 pSamples[nIdx] = *(aBegin + nLen);
157template <
class RandItr,
class Compare>
class Binner
159 using ValueType =
typename std::iterator_traits<RandItr>::value_type;
173 Binner(
const ValueType* pSamples,
size_t nSamples,
size_t nBins,
bool bThreaded)
182 fillTreeArray(1, pSamples, pSamples + nSamples);
187 assert(pLow <= pHigh);
188 const ValueType* pMid = pLow + (pHigh - pLow) / 2;
193 fillTreeArray(2 * nPos, pLow, pMid);
194 fillTreeArray(2 * nPos + 1, pMid + 1, pHigh);
198 constexpr inline size_t findBin(
const ValueType& rVal, Compare& aComp)
202 nIdx = ((nIdx << 1) + aComp(
maDividers[nIdx], rVal));
206 void label(
const RandItr aBegin,
const RandItr aEnd, Compare& aComp)
208 ProfileZone aZoneSetup(
"\tlabel():setup");
209 size_t nLen =
static_cast<std::size_t
>(aEnd - aBegin);
211 pLabels = std::make_unique<uint8_t[]>(nLen);
214 ProfileZone aZoneFindBins(
"\tFindBins()");
217 ParallelRunner aPRunner;
219 for (
size_t nTIdx = 0; nTIdx < nBins; ++nTIdx)
221 aPRunner.enqueue([
this, nTIdx, nBins, nLen, aBegin, pLabelsRaw, &aComp] {
222 ProfileZone aZoneIn(
"\t\tFindBinsThreaded()");
225 size_t aBinEndsF[nMaxTreeArraySize] = { 0 };
226 for (
size_t nIdx = nTIdx; nIdx < nLen; nIdx += nBins)
228 size_t nBinIdx = findBin(*(aBegin + nIdx), aComp);
229 pLabelsRaw[nIdx] =
static_cast<uint8_t
>(nBinIdx);
230 ++aBinEndsF[nBinIdx];
234 pBinEnds[nIdx] = aBinEndsF[nIdx];
249 uint8_t* pLabel = pLabelsRaw;
250 for (RandItr aItr = aBegin; aItr != aEnd; ++aItr)
252 size_t nBinIdx = findBin(*aItr, aComp);
258 aZoneFindBins.stop();
272 void bin(
const RandItr aBegin,
const RandItr aEnd,
ValueType* pOut)
274 ProfileZone aZone(
"\tbin()");
275 const size_t nLen =
static_cast<std::size_t
>(aEnd - aBegin);
278 for (nIdx = 0; nIdx < nLen; ++nIdx)
285template <
class RandItr,
class Compare = std::less<>>
286void s3sort(
const RandItr aBegin,
const RandItr aEnd, Compare aComp = Compare(),
287 bool bThreaded =
true)
291 constexpr size_t nBaseCaseSize = 1024;
292 const std::size_t nLen =
static_cast<std::size_t
>(aEnd - aBegin);
293 if (nLen < nBaseCaseSize)
295 std::stable_sort(aBegin, aEnd, aComp);
299 using ValueType =
typename std::iterator_traits<RandItr>::value_type;
300 auto pOut = std::make_unique<ValueType[]>(nLen);
302 const size_t nBins = lcl_round_down_pow2(nThreadCount);
303 const size_t nOverSamplingFactor = std::max(1.0, std::sqrt(
static_cast<double>(nLen) / 64));
304 const size_t nSamples = nOverSamplingFactor * nBins;
305 auto aSamples = std::make_unique<ValueType[]>(nSamples);
306 ProfileZone aZoneSampleAnsSort(
"SampleAndSort");
308 Sampler<RandItr>::sample(aBegin, aEnd, aSamples.get(), nSamples, nBins);
309 std::sort(aSamples.get(), aSamples.get() + nSamples, aComp);
310 aZoneSampleAnsSort.stop();
312 if (!aComp(aSamples[0], aSamples[nSamples - 1]))
315 std::sort(aBegin, aEnd, aComp);
319 ProfileZone aZoneBinner(
"Binner");
321 Binner<RandItr, Compare> aBinner(aSamples.get(), nSamples, nBins, bThreaded);
322 aBinner.label(aBegin, aEnd, aComp);
323 aBinner.bin(aBegin, aEnd,
pOut.get());
326 ProfileZone aZoneSortBins(
"SortBins");
330 ParallelRunner aPRunner;
332 for (
size_t nBinIdx = 0, nBinStart = 0; nBinIdx < nBins; ++nBinIdx)
334 size_t nBinEnd = aBinner.maBinEnds[nBinIdx];
335 aPRunner.enqueue([pOutRaw, nBinStart, nBinEnd, &aComp] {
336 std::sort(pOutRaw + nBinStart, pOutRaw + nBinEnd, aComp);
346 for (
size_t nBinIdx = 0, nBinStart = 0; nBinIdx < nBins; ++nBinIdx)
348 auto nBinEnd = aBinner.maBinEnds[nBinIdx];
349 std::sort(pOutRaw + nBinStart, pOutRaw + nBinEnd, aComp);
354 aZoneSortBins.stop();
357 std::move(pOutRaw, pOutRaw + nLen, aBegin);
362template <
class RandItr,
class Compare = std::less<>>
363void parallelSort(
const RandItr aBegin,
const RandItr aEnd, Compare aComp = Compare())
365 assert(aBegin <= aEnd);
366 s3sort(aBegin, aEnd, aComp);
A very basic thread-safe thread pool implementation.
static ThreadPool & getSharedOptimalPool()
returns a pointer to a shared pool with optimal thread count for the CPU
void waitUntilDone(const std::shared_ptr< ThreadTaskTag > &, bool bJoin=true)
Wait until all queued tasks associated with the tag are completed.
static std::shared_ptr< ThreadTaskTag > createThreadTaskTag()
void pushTask(std::unique_ptr< ThreadTask > pTask)
push a new task onto the work queue
static thread_local std::mt19937 aGenerator
const size_t nThreadCountGlobal
const bool bHyperThreadingActive
void parallelSort(const RandItr aBegin, const RandItr aEnd, Compare aComp=Compare())
static comphelper::ThreadPool & rTPool(comphelper::ThreadPool::getSharedOptimalPool())
void swap(cow_wrapper< T, P > &a, cow_wrapper< T, P > &b)
uint8_t maLabels[mnMaxStaticSize]
static constexpr size_t mnMaxStaticSize
size_t maSepBinEnds[nMaxTreeArraySize *nMaxTreeArraySize]
const std::function< void()> maFunc
size_t maBinEnds[nMaxTreeArraySize]
std::unique_ptr< uint8_t[]> pLabels
std::shared_ptr< comphelper::ThreadTaskTag > maTag
ValueType maDividers[nMaxTreeArraySize]
const size_t mnTreeArraySize