代码

// V25: handle empty recursive base cases before the nonempty-range assumption.
// IPS2Ra sequential experiment. Upstream commit ef3407632348f58a6ab75832a749cde99f3b9ad8
// https://github.com/ips4o/ips2ra
// TBB includes replaced by forward declarations; parallel code is not instantiated.
/******************************************************************************
 * include/ips2ra.hpp
 *
 * In-place Parallel Super Scalar Radix Sort (IPS²Ra)
 *
 ******************************************************************************
 * BSD 2-Clause License
 *
 * Copyright © 2017, Michael Axtmann <michael.axtmann@gmail.com>
 * Copyright © 2017, Daniel Ferizovic <daniel.ferizovic@student.kit.edu>
 * Copyright © 2017, Sascha Witt <sascha.witt@kit.edu>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * * Redistributions of source code must retain the above copyright notice, this
 *   list of conditions and the following disclaimer.
 *
 * * Redistributions in binary form must reproduce the above copyright notice,
 *   this list of conditions and the following disclaimer in the documentation
 *   and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *****************************************************************************/
/******************************************************************************
 * include/ips2ra/ska_sort.hpp
 *
 * In-place Parallel Super Scalar Radix Sort (IPS²Ra)
 *
 ******************************************************************************
 * Boost Software License - Version 1.0 - August 17th, 2003
 * 
 * Permission is hereby granted, free of charge, to any person or organization
 * obtaining a copy of the software and accompanying documentation covered by
 * this license (the "Software") to use, reproduce, display, distribute,
 * execute, and transmit the Software, and to prepare derivative works of the
 * Software, and to permit third-parties to whom the Software is furnished to
 * do so, all subject to the following:
 * 
 * The copyright notices in the Software and this entire statement, including
 * the above license grant, this restriction and the following disclaimer,
 * must be included in all copies of the Software, in whole or in part, and
 * all derivative works of the Software, unless such copies or derivative
 * works are solely in the form of machine-executable object code generated by
 * a source language processor.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
 * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
 * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 *****************************************************************************/
#pragma GCC optimize("O3")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define NDEBUG
namespace tbb { template<class T> class concurrent_queue { public: bool try_pop(T&); void push(const T&); bool empty() const; }; }
#include <functional>
#include <iterator>
#include <type_traits>
#include <iterator>
#include <memory>
#include <utility>
#include <vector>
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <type_traits>
#include <utility>
#if defined(_REENTRANT)
#endif
#include <cassert>
#include <climits>
#include <limits>
#define IPS2RA_ASSUME_NOT(c) if (c) __builtin_unreachable()
#define IPS2RA_IS_NOT(c) assert(!(c))
namespace ips2ra {
namespace detail {
inline constexpr unsigned clz(unsigned int n) {
if (n == 0) return CHAR_BIT * sizeof(n);
return __builtin_clz(n);
}
inline constexpr unsigned clz(unsigned long n) {
if (n == 0) return CHAR_BIT * sizeof(n);
return __builtin_clzl(n);
}
inline constexpr unsigned clz(unsigned long long n) {
if (n == 0) return CHAR_BIT * sizeof(n);
return __builtin_clzll(n);
}
inline constexpr unsigned ctz(unsigned int n) {
if (n == 0) return CHAR_BIT * sizeof(n);
return __builtin_ctz(n);
}
inline constexpr unsigned ctz(unsigned long n) {
if (n == 0) return CHAR_BIT * sizeof(n);
return __builtin_ctzl(n);
}
inline constexpr unsigned ctz(unsigned long long n) {
if (n == 0) return CHAR_BIT * sizeof(n);
return __builtin_ctzll(n);
}
inline constexpr unsigned long log2(unsigned long n) {
return (std::numeric_limits<unsigned long>::digits - 1 - clz(n));
}
template <int tmpl_idx, int last, class E, typename... Ts>
void switchUnroll(E& e, int idx, Ts... args) {
assert(idx <= last);
if constexpr (tmpl_idx > last)
return;
else if constexpr (tmpl_idx < 0)
return;
else if (idx == tmpl_idx) {
e.template operator()<tmpl_idx>(args...);
} else {
switchUnroll<tmpl_idx + 1, last>(e, idx, args...);
}
}
}
}

#ifndef IPS2RA_SMALLEST_CASE_SIZE
#define IPS2RA_SMALLEST_CASE_SIZE 32
#endif
#ifndef IPS2RA_BASE_CASE_SIZE
#define IPS2RA_BASE_CASE_SIZE 128
#endif
#ifndef IPS2RA_AMERICAN_FLAG_SORT_SIZE
#define IPS2RA_AMERICAN_FLAG_SORT_SIZE 1024
#endif
#ifndef IPS2RA_SKA_SORT_SIZE
#define IPS2RA_SKA_SORT_SIZE 2048
#endif
#ifndef IPS2RA_SMALLEST_CASE_MULTIPLIER
#define IPS2RA_SMALLEST_CASE_MULTIPLIER 8
#endif
#ifndef IPS2RA_BLOCK_SIZE
#define IPS2RA_BLOCK_SIZE (2 << 10)
#endif
#ifndef IPS2RA_BUCKET_TYPE
#define IPS2RA_BUCKET_TYPE std::ptrdiff_t
#endif
#ifndef IPS2RA_DATA_ALIGNMENT
#define IPS2RA_DATA_ALIGNMENT (4 << 10)
#endif
#ifndef IPS2RA_LOG_BUCKETS
#define IPS2RA_LOG_BUCKETS 8
#endif
#ifndef IPS2RA_MIN_PARALLEL_BLOCKS_PER_THREAD
#define IPS2RA_MIN_PARALLEL_BLOCKS_PER_THREAD 4
#endif
#ifndef IPS2RA_OVERSAMPLING_FACTOR_PERCENT
#define IPS2RA_OVERSAMPLING_FACTOR_PERCENT 20
#endif
#ifndef IPS2RA_UNROLL_CLASSIFIER
#define IPS2RA_UNROLL_CLASSIFIER 7
#endif
namespace ips2ra {
template <std::ptrdiff_t SmallestSort_     = IPS2RA_SMALLEST_CASE_SIZE
, std::ptrdiff_t BaseCaseSize_     = IPS2RA_BASE_CASE_SIZE
, std::ptrdiff_t Skasort_          = IPS2RA_SKA_SORT_SIZE
, std::ptrdiff_t AmericanFlagSort_ = IPS2RA_AMERICAN_FLAG_SORT_SIZE
, std::ptrdiff_t SmallestSortM_    = IPS2RA_SMALLEST_CASE_MULTIPLIER
, std::ptrdiff_t BlockSize_        = IPS2RA_BLOCK_SIZE
, class BucketT_                   = IPS2RA_BUCKET_TYPE
, std::size_t DataAlign_           = IPS2RA_DATA_ALIGNMENT
, int LogBuckets_                  = IPS2RA_LOG_BUCKETS
, std::ptrdiff_t MinParBlks_       = IPS2RA_MIN_PARALLEL_BLOCKS_PER_THREAD
, int OversampleF_                 = IPS2RA_OVERSAMPLING_FACTOR_PERCENT
, int UnrollClass_                 = IPS2RA_UNROLL_CLASSIFIER
>
struct Config {
using bucket_type = BucketT_;
static constexpr const bool kIs64Bit = sizeof(std::uintptr_t) == 8;
static_assert(kIs64Bit || sizeof(std::uintptr_t) == 4,
"Architecture must be 32 or 64 bit");
static constexpr const std::ptrdiff_t kSmallestSortSize = SmallestSort_;
static constexpr const std::ptrdiff_t kBaseCaseSize = BaseCaseSize_;
static constexpr const std::ptrdiff_t kSkasort = Skasort_;
static constexpr const std::ptrdiff_t kAmericanFlagSort = AmericanFlagSort_;
static constexpr const int kSmallestSortMultiplier = SmallestSortM_;
static constexpr const std::ptrdiff_t kBlockSizeInBytes = BlockSize_;
static constexpr const std::size_t kDataAlignment = DataAlign_;
static constexpr const int kLogBuckets = LogBuckets_;
static constexpr const std::ptrdiff_t kMinParallelBlocksPerThread = MinParBlks_;
static_assert(kMinParallelBlocksPerThread > 0,
"Min. blocks per thread must be at least 1.");
static constexpr const int kUnrollClassifier = UnrollClass_;
static constexpr double oversamplingFactor(std::ptrdiff_t n) {
const double f = OversampleF_ / 100.0 * detail::log2(n);
return f < 1.0 ? 1.0 : f;
}
struct identity {
template <class T>
constexpr T&& operator()(T&& t) const {
return std::forward<T>(t);
}
};
template <class Extractor>
struct LessExtractor {
LessExtractor(Extractor extractor) : extractor_(extractor) {}
template <class T1, class T2>
bool operator()(T1&& x, T2&& y) const {
return extractor_(std::forward<T1>(x)) < extractor_(std::forward<T2>(y));
}
private:
Extractor extractor_;
};
template <class It>
#if defined(_REENTRANT) || defined(_OPENMP)
static constexpr int numThreadsFor(const It& begin, const It& end, int max_threads) {
const std::ptrdiff_t blocks =
(end - begin) * sizeof(decltype(*begin)) / kBlockSizeInBytes;
return (blocks < (kMinParallelBlocksPerThread * max_threads)) ? 1 : max_threads;
}
#else
static constexpr int numThreadsFor(const It&, const It&, int) {
return 1;
}
#endif
};
template <class It_, class Extractor_, class Cfg = Config<>
#if defined(_REENTRANT) || defined(_OPENMP)
, class ThreadPool_ = DefaultThreadPool
#endif
>
struct ExtendedConfig : public Cfg {
using BaseConfig = Cfg;
using iterator = It_;
using Extractor = Extractor_;
using difference_type = typename std::iterator_traits<iterator>::difference_type;
using value_type = typename std::iterator_traits<iterator>::value_type;
using key_type = std::remove_reference_t<std::invoke_result_t<Extractor, value_type>>;
static_assert(std::is_unsigned<key_type>::value);
#if defined(_REENTRANT) || defined(_OPENMP)
using ThreadPool = ThreadPool_;
using SubThreadPool = ThreadJoiningThreadPool;
using Sync = decltype(std::declval<ThreadPool&>().sync());
#else
struct Sync {
constexpr void barrier() const {}
template <class F>
constexpr void single(F&&) const {}
};
class SubThreadPool {
public:
explicit SubThreadPool(int) {}
void join(int) {}
void release_threads() {}
template <class F>
void operator()(F&&, int) {}
Sync& sync() { return sync_; }
int numThreads() const { return 1; }
private:
Sync sync_;
};
#endif
template <int level, class T>
static inline T getBucket(const T val) {
static_assert(sizeof(T) > level, "Too many levels");
return (val >> (8 * (sizeof(T) - level - 1))) & 0xFF;
}
template <class T>
static inline T getBucket(const T val, int level) {
assert(sizeof(T) > level);
return (val >> (8 * (sizeof(T) - level - 1))) & 0xFF;
}
static constexpr const int kMaxBuckets = 1ul << Cfg::kLogBuckets;
static constexpr const difference_type kBlockSize =
1ul << (detail::log2(
Cfg::kBlockSizeInBytes < sizeof(value_type)
? 1
: (Cfg::kBlockSizeInBytes / sizeof(value_type))));
static constexpr const difference_type kSmallestSortSize = Cfg::kSmallestSortSize;
static_assert(std::is_same<typename std::iterator_traits<iterator>::iterator_category,
std::random_access_iterator_tag>::value, "Iterator must be a random access iterator.");
static_assert((kBlockSize & (kBlockSize - 1)) == 0, "Block size must be a power of two.");
static_assert(Cfg::kUnrollClassifier <= kSmallestSortSize, "Base case size must be larger than unroll factor.");
static constexpr difference_type alignToNextBlock(difference_type p) {
return (p + kBlockSize - 1) & ~(kBlockSize - 1);
}
};
#undef IPS2RA_SMALLEST_CASE_SIZE
#undef IPS2RA_SKA_SORT_SIZE
#undef IPS2RA_AMERICAN_FLAG_SORT_SIZE
#undef IPS2RA_SMALLEST_CASE_MULTIPLIER
#undef IPS2RA_BLOCK_SIZE
#undef IPS2RA_BUCKET_TYPE
#undef IPS2RA_DATA_ALIGNMENT
#undef IPS2RA_LOG_BUCKETS
#undef IPS2RA_MIN_PARALLEL_BLOCKS_PER_THREAD
#undef IPS2RA_OVERSAMPLING_FACTOR_PERCENT
#undef IPS2RA_UNROLL_CLASSIFIER
}

#include <algorithm>
#include <atomic>
#include <cassert>
#include <cstddef>
#include <numeric>
#include <vector>
namespace ips2ra {
namespace detail {
template <class T>
class PrivateQueue {
public:
PrivateQueue(size_t init_size = ((1ul << 12) + sizeof(T) - 1) / sizeof(T))
: m_v(), m_off(0) {
m_v.reserve(init_size);
}
template <class Iterator>
void push(Iterator begin, Iterator end) {
m_v.insert(m_v.end(), begin, end);
}
template <class T1>
void push(const T1&& e) {
m_v.emplace_back(std::forward(e));
}
template <typename... Args>
void emplace(Args... args) {
m_v.emplace_back(args...);
}
size_t size() const { return m_v.size() - m_off; }
bool empty() const { return size() == 0; }
T popBack() {
assert(m_v.size() > m_off);
const T e = m_v.back();
m_v.pop_back();
if (m_v.size() == m_off) { clear(); }
return e;
}
T popFront() {
assert(m_v.size() > m_off);
const T e = m_v[m_off];
++m_off;
if (m_v.size() == m_off) { clear(); }
return e;
}
void clear() {
m_off = 0;
m_v.clear();
}
protected:
std::vector<T> m_v;
size_t m_off;
};
template <class Job>
class Scheduler {
public:
Scheduler(size_t num_threads) : m_num_idle_threads(0), m_num_threads(num_threads) {}
bool getJob(PrivateQueue<Job>& my_queue, Job& j) {
if (!my_queue.empty()) {
j = my_queue.popBack();
return true;
}
const bool succ = m_glob_queue.try_pop(j);
if (succ) return succ;
m_num_idle_threads.fetch_add(1, std::memory_order_relaxed);
while (m_num_idle_threads.load(std::memory_order_relaxed) != m_num_threads) {
if (!m_glob_queue.empty()) {
m_num_idle_threads.fetch_sub(1, std::memory_order_relaxed);
const bool succ = m_glob_queue.try_pop(j);
if (succ) { return succ; }
m_num_idle_threads.fetch_add(1, std::memory_order_relaxed);
}
}
return false;
}
void offerJob(PrivateQueue<Job>& my_queue) {
if (my_queue.size() > 1 && m_num_idle_threads.load(std::memory_order_relaxed) > 0
&& m_glob_queue.empty()) {
addJob(my_queue.popFront());
}
}
void addJob(const Job& j) { m_glob_queue.push(j); }
void addJob(const Job&& j) { m_glob_queue.push(j); }
void reset() { m_num_idle_threads.store(0, std::memory_order_relaxed); }
protected:
tbb::concurrent_queue<Job> m_glob_queue;
std::atomic_uint64_t m_num_idle_threads;
const size_t m_num_threads;
};
}
}

#include <cstddef>
namespace ips2ra {
namespace detail {
struct Task {
Task() {}
Task(std::ptrdiff_t begin, std::ptrdiff_t end, int level)
: begin(begin), end(end), level(level) {}
std::ptrdiff_t begin;
std::ptrdiff_t end;
int level;
};
}
}

namespace ips2ra {
template <class Cfg>
class SequentialSorter;
namespace detail {
template <class It, class Extractor>
inline void baseCaseSort(It begin, It end, Extractor&& extractor);
inline constexpr unsigned long log2(unsigned long n);
template <class It, class RandomGen>
inline void selectSample(It begin, It end,
typename std::iterator_traits<It>::difference_type num_samples,
RandomGen&& gen);
template <class Cfg>
class Sorter {
public:
using iterator = typename Cfg::iterator;
using diff_t = typename Cfg::difference_type;
using value_type = typename Cfg::value_type;
using SubThreadPool = typename Cfg::SubThreadPool;
using key_type = typename Cfg::key_type;
using LessExtractor =
typename Cfg::BaseConfig::template LessExtractor<typename Cfg::Extractor>;
class BufferStorage;
class Block;
class Buffers;
class BucketPointers;
class Classifier;
struct LocalData;
struct SharedData;
explicit Sorter(LocalData& local) : local_(local), level_end_(-1) {}
void sequential(const iterator begin, const Task& task, PrivateQueue<Task>& queue);
void sequentialRec(iterator begin, iterator end, const int level);
void sequential(iterator begin, iterator end);
std::pair<int, int> sampleLevels(iterator begin, iterator end);
std::pair<int, int> parallelGetLevels(iterator begin, iterator end,
std::vector<key_type>& tmp,
std::vector<bool>& sorted_tmp, int id,
int num_threads);
std::pair<int, int> sequentialGetLevels(iterator begin, iterator end);
bool nextLevelExists(int level);
bool levelExists(int level);
bool isLastLevel(int level);
#if defined(_REENTRANT) || defined(_OPENMP)
void parallelSortPrimary(iterator begin, iterator end, int num_threads,
BufferStorage& buffer_storage,
std::vector<std::shared_ptr<SubThreadPool>>& tp_trash,
int level_begin, int level_end);
void parallelSortSecondary(iterator begin, iterator end, int id, int num_threads,
BufferStorage& buffer_storage,
std::vector<std::shared_ptr<SubThreadPool>>& tp_trash,
int level_begin, int level_end);
std::vector<diff_t> parallelPartitionPrimary(iterator begin, iterator end, int level,
int level_end, int num_threads);
void parallelPartitionSecondary(iterator begin, iterator end, int level,
int level_end, int id, int num_threads);
void setShared(SharedData* shared_);
#endif
private:
LocalData& local_;
SharedData* shared_;
Classifier* classifier_;
diff_t* bucket_start_;
BucketPointers* bucket_pointers_;
Block* overflow_;
iterator begin_;
iterator end_;
int my_id_;
int num_threads_;
int level_;
int level_end_;
static inline int computeLogBuckets(diff_t n);
int buildClassifier(iterator begin, iterator end, Classifier& classifier,
double sample_multiplicator);
__attribute__((flatten))
diff_t classifyLocally(iterator my_begin, iterator my_end);
inline void parallelClassification();
inline void sequentialClassification();
void moveEmptyBlocks(diff_t my_begin, diff_t my_end, diff_t my_first_empty_block);
inline int computeOverflowBucket();
template <bool kIsParallel>
inline int classifyAndReadBlock(int read_bucket);
template <bool kIsParallel>
inline int swapBlock(diff_t max_off, int dest_bucket, bool current_swap);
template <bool kIsParallel>
void permuteBlocks();
inline std::pair<int, diff_t> saveMargins(int last_bucket);
template <bool kIsParallel>
void writeMargins(int first_bucket, int last_bucket, int overflow_bucket,
int swap_bucket, diff_t in_swap_buffer, int level);
template <bool kIsParallel>
void partition(iterator begin, iterator end, int level, diff_t* bucket_start,
int my_id, int num_threads);
void processSmallTasks(iterator begin, int num_threads);
void processBigTasks(const iterator begin, const diff_t stripe, const int my_id,
BufferStorage& buffer_storage,
std::vector<std::shared_ptr<SubThreadPool>>& tp_trash);
void processBigTaskPrimary(const iterator end, const diff_t stripe, const int my_id,
BufferStorage& buffer_storage,
std::vector<std::shared_ptr<SubThreadPool>>& tp_trash);
void processBigTasksSecondary(const int my_id, BufferStorage& buffer_storage);
void queueTasks(const int level, const diff_t stripe, const int id,
const int num_threads, const diff_t parent_task_size,
const diff_t offset, const diff_t* bucket_start);
};
}
template <class Cfg>
class ParallelSorter;
template <class It, class Extractor>
inline void sort(It begin, It end, Extractor extractor);
template <class It>
inline void sort(It begin, It end);
#if defined(_REENTRANT)
namespace parallel {
template <class It, class Extractor>
inline void sort(It begin, It end, Extractor extractor);
template <class It>
inline void sort(It begin, It end);
}
#endif
}

#include <algorithm>
#include <cstddef>
#include <utility>

namespace ips2ra {
namespace detail {
template <class It, class Comp>
void insertionSort(const It begin, const It end, Comp comp) {
if(begin==end)return;
IPS2RA_ASSUME_NOT(begin >= end);
for (It it = begin + 1; it < end; ++it) {
auto val = std::move(*it);
if (comp(val, *begin)) {
std::move_backward(begin, it, it + 1);
*begin = std::move(val);
} else {
auto cur = it;
for (auto next = it - 1; comp(val, *next); --next) {
*cur = std::move(*next);
cur = next;
}
*cur = std::move(val);
}
}
}
template <std::ptrdiff_t threshold, class It, class Comp>
bool insertionsortIfAtMostThreshold(It begin, It end, Comp&& comp) {
const bool is_small = end - begin <= threshold;
if (is_small) {
insertionSort(std::move(begin), std::move(end), std::forward<Comp>(comp));
}
return is_small;
}
template <std::ptrdiff_t kMaxSize, class It, class Comp>
inline bool smallestSortIfAtMostThreshold(It begin, It end, Comp&& comp) {
return insertionsortIfAtMostThreshold<kMaxSize>(begin, end, std::forward<Comp>(comp));
}
template <std::ptrdiff_t kMaxSize, class iterator, class T, class Comp>
iterator binPartition(iterator begin, iterator end, std::ptrdiff_t* offs, T splitter,
Comp comp) {
const std::ptrdiff_t size = end - begin;
assert(size <= kMaxSize);
std::ptrdiff_t sizes[2] = {0, (kMaxSize + 1) + 1};
offs[(kMaxSize + 1)] = -1;
for (std::ptrdiff_t i = 0; i != end - begin; ++i) {
const auto res = comp(begin[i], splitter);
offs[sizes[res]] = i;
++sizes[res];
}
offs[sizes[0]] = size;
++sizes[0];
std::ptrdiff_t l = 0;
std::ptrdiff_t r = sizes[1] - 1;
while (offs[r] > offs[l]) {
std::swap(begin[offs[r]], begin[offs[l]]);
++l;
--r;
}
return begin + sizes[1] - 1 - (kMaxSize + 1);
}
template <std::ptrdiff_t kMaxSize, class iterator, class T, class Comp>
iterator binPartitionSmallerEqual(iterator begin, iterator end, std::ptrdiff_t* offs,
T splitter, Comp comp) {
const std::ptrdiff_t size = end - begin;
assert(size <= kMaxSize);
std::ptrdiff_t sizes[2] = {1, (kMaxSize + 1)};
offs[0] = -1;
for (std::ptrdiff_t i = 0; i != end - begin; ++i) {
const auto res = comp(splitter, begin[i]);
offs[sizes[res]] = i;
++sizes[res];
}
offs[sizes[1]] = size;
++sizes[1];
std::ptrdiff_t l = (kMaxSize + 1);
std::ptrdiff_t r = sizes[0] - 1;
while (offs[r] > offs[l]) {
std::swap(begin[offs[r]], begin[offs[l]]);
++l;
--r;
}
return begin + sizes[0] - 1;
}
template <std::ptrdiff_t kMaxSize, std::ptrdiff_t kSmallestSortMaxSize, class It, class T,
class Comp>
void quickSortBranchless(const It begin, const It end, std::ptrdiff_t* offs, Comp comp,
T& prev_splitter) {
const auto splitter = begin[(end - begin) / 2];
if (comp(splitter, prev_splitter) || comp(prev_splitter, splitter)) {
const auto m =
binPartitionSmallerEqual<kMaxSize>(begin, end, offs, splitter, comp);
if (!smallestSortIfAtMostThreshold<kSmallestSortMaxSize>(begin, m, comp)) {
quickSortBranchless<kMaxSize, kSmallestSortMaxSize>(
begin, m, offs, std::forward<Comp>(comp), splitter);
}
if (!smallestSortIfAtMostThreshold<kSmallestSortMaxSize>(m, end, comp)) {
quickSortBranchless<kMaxSize, kSmallestSortMaxSize>(
m, end, offs, std::forward<Comp>(comp), splitter);
}
} else {
const auto m = binPartition<kMaxSize>(begin, end, offs, splitter, comp);
if (!smallestSortIfAtMostThreshold<kSmallestSortMaxSize>(begin, m, comp)) {
quickSortBranchless<kMaxSize, kSmallestSortMaxSize>(
begin, m, offs, std::forward<Comp>(comp), splitter);
}
}
}
template <std::ptrdiff_t kMaxSize, std::ptrdiff_t kSmallestSortMaxSize, class It,
class Comp>
void quickSortBranchless(const It begin, const It end, std::ptrdiff_t* offs, Comp comp) {
const auto splitter = begin[(end - begin) / 2];
const auto m = binPartitionSmallerEqual<kMaxSize>(begin, end, offs, splitter, comp);
if (!smallestSortIfAtMostThreshold<kSmallestSortMaxSize>(begin, m, comp)) {
quickSortBranchless<kMaxSize, kSmallestSortMaxSize>(
begin, m, offs, std::forward<Comp>(comp), splitter);
}
if (!smallestSortIfAtMostThreshold<kSmallestSortMaxSize>(m, end, comp)) {
quickSortBranchless<kMaxSize, kSmallestSortMaxSize>(
m, end, offs, std::forward<Comp>(comp), splitter);
}
}
template <std::ptrdiff_t kSmallestSortMaxSize, std::ptrdiff_t kMaxSize, class It,
class ExtractKey>
inline void baseCaseSort(It begin, It end, std::ptrdiff_t* offs,
ExtractKey&& extract_key) {
auto comp = [&](auto&& l, auto&& r) { return extract_key(l) < extract_key(r); };
if (!smallestSortIfAtMostThreshold<kSmallestSortMaxSize>(begin, end,
std::move(comp))) {
quickSortBranchless<kMaxSize, kSmallestSortMaxSize>(begin, end, offs,
std::move(comp));
}
}
}
}


#include <algorithm>
#include <atomic>
#include <condition_variable>
#include <cstddef>
#include <cstdint>
#include <mutex>
#include <random>
#include <utility>
#include <vector>

#include <atomic>
#include <climits>
#include <cstdint>
#include <mutex>
#include <new>
#include <tuple>
#include <utility>

namespace ips2ra {
namespace detail {
template <class Cfg>
class Sorter<Cfg>::BucketPointers {
using diff_t = typename Cfg::difference_type;
#if UINTPTR_MAX == UINT32_MAX || defined(__SIZEOF_INT128__)
#if UINTPTR_MAX == UINT32_MAX
using atomic_type = std::uint64_t;
#elif defined(__SIZEOF_INT128__)
using atomic_type = unsigned __int128;
#endif
class Uint128 {
public:
inline void set(diff_t l, diff_t m) {
single_.m_ = m;
single_.l_ = l;
}
inline diff_t getLeastSignificant() const { return single_.l_; }
template <bool kAtomic>
inline std::pair<diff_t, diff_t> fetchSubMostSignificant(diff_t m) {
if (kAtomic) {
const atomic_type atom_m = static_cast<atomic_type>(m) << kShift;
const auto p = __atomic_fetch_sub(&all_, atom_m, __ATOMIC_RELAXED);
return {p & kMask, p >> kShift};
} else {
const auto tmp = single_.m_;
single_.m_ -= m;
return {single_.l_, tmp};
}
}
template <bool kAtomic>
inline std::pair<diff_t, diff_t> fetchAddLeastSignificant(diff_t l) {
if (kAtomic) {
const auto p = __atomic_fetch_add(&all_, l, __ATOMIC_RELAXED);
return {p & kMask, p >> kShift};
} else {
const auto tmp = single_.l_;
single_.l_ += l;
return {tmp, single_.m_};
}
}
private:
static constexpr const int kShift = sizeof(atomic_type) * CHAR_BIT / 2;
static constexpr const atomic_type kMask =
(static_cast<atomic_type>(1) << kShift) - 1;
struct Pointers {
diff_t l_, m_;
};
union {
atomic_type all_;
Pointers single_;
};
};
#else
class Uint128 {
public:
inline void set(diff_t l, diff_t m) {
m_ = m;
l_ = l;
}
inline diff_t getLeastSignificant() const { return l_; }
template <bool kAtomic>
inline std::pair<diff_t, diff_t> fetchSubMostSignificant(diff_t m) {
if (kAtomic) {
std::lock_guard<std::mutex> lock(mtx_);
std::pair<diff_t, diff_t> p{l_, m_};
m_ -= m;
return p;
} else {
const auto tmp = m_;
m_ -= m;
return {l_, tmp};
}
}
template <bool kAtomic>
inline std::pair<diff_t, diff_t> fetchAddLeastSignificant(diff_t l) {
if (kAtomic) {
std::lock_guard<std::mutex> lock(mtx_);
std::pair<diff_t, diff_t> p{l_, m_};
l_ += l;
return p;
} else {
const auto tmp = l_;
l_ += l;
return {tmp, m_};
}
}
private:
diff_t m_, l_;
std::mutex mtx_;
};
#endif
public:
void set(diff_t w, diff_t r) {
ptr_.set(w, r);
num_reading_.store(0, std::memory_order_relaxed);
}
diff_t getWrite() const {
return ptr_.getLeastSignificant();
}
template <bool kAtomic>
std::pair<diff_t, diff_t> incWrite() {
return ptr_.template fetchAddLeastSignificant<kAtomic>(Cfg::kBlockSize);
}
template <bool kAtomic>
std::pair<diff_t, diff_t> decRead() {
if (kAtomic) {
num_reading_.fetch_add(1, std::memory_order_acquire);
const auto p =
ptr_.template fetchSubMostSignificant<kAtomic>(Cfg::kBlockSize);
return {p.first, p.second & ~(Cfg::kBlockSize - 1)};
} else {
return ptr_.template fetchSubMostSignificant<kAtomic>(Cfg::kBlockSize);
}
}
void stopRead() {
num_reading_.fetch_sub(1, std::memory_order_release);
}
bool isReading() {
return num_reading_.load(std::memory_order_acquire) != 0;
}
private:
Uint128 ptr_;
std::atomic_int num_reading_;
};
}
}

#include <algorithm>
#include <type_traits>
#include <utility>

namespace ips2ra {
namespace detail {
template <class Cfg>
class Sorter<Cfg>::Block {
using iterator = typename Cfg::iterator;
using diff_t = typename Cfg::difference_type;
using value_type = typename Cfg::value_type;
public:
static constexpr const bool kInitializedStorage =
std::is_trivially_default_constructible<value_type>::value;
static constexpr const bool kDestruct =
!kInitializedStorage && !std::is_trivially_destructible<value_type>::value;
value_type* data() { return static_cast<value_type*>(static_cast<void*>(storage_)); }
const value_type& head() { return *data(); }
void readFrom(iterator src) {
if (kInitializedStorage) {
std::move(src, src + Cfg::kBlockSize, data());
} else {
for (auto p = data(), end = p + Cfg::kBlockSize; p < end; ++p) {
IPS2RA_ASSUME_NOT(p == nullptr);
new (p) value_type(std::move(*src++));
}
}
}
void readFrom(iterator src, const diff_t n) {
if (kInitializedStorage) {
std::move(src, src + n, data());
} else {
for (auto p = data(), end = p + n; p < end; ++p) {
IPS2RA_ASSUME_NOT(p == nullptr);
new (p) value_type(std::move(*src++));
}
}
}
void reset(const diff_t n) {
if (kDestruct)
for (auto p = data(), end = p + n; p < end; ++p)
p->~value_type();
}
void writeTo(Block& block) {
if (kInitializedStorage) {
std::move(data(), data() + Cfg::kBlockSize, block.data());
} else {
for (auto src = data(), dst = block.data(), end = src + Cfg::kBlockSize;
src < end; ++src, ++dst) {
IPS2RA_ASSUME_NOT(dst == nullptr);
new (dst) value_type(std::move(*src));
}
}
if (kDestruct)
for (auto p = data(), end = p + Cfg::kBlockSize; p < end; ++p)
p->~value_type();
}
void writeTo(iterator dest) {
std::move(data(), data() + Cfg::kBlockSize, std::move(dest));
if (kDestruct)
for (auto p = data(), end = p + Cfg::kBlockSize; p < end; ++p)
p->~value_type();
}
private:
using storage_type = std::conditional_t<
kInitializedStorage, value_type,
std::aligned_storage_t<sizeof(value_type), alignof(value_type)>>;
storage_type storage_[Cfg::kBlockSize];
};
template <class Cfg>
class Sorter<Cfg>::Buffers {
using diff_t = typename Cfg::difference_type;
using value_type = typename Cfg::value_type;
public:
Buffers(char* storage) : storage_(static_cast<Block*>(static_cast<void*>(storage))) {
for (diff_t i = 0; i < Cfg::kMaxBuckets; ++i) {
resetBuffer(i);
buffer_[i].end = buffer_[i].ptr + Cfg::kBlockSize;
}
}
bool isFull(const int i) const { return buffer_[i].ptr == buffer_[i].end; }
value_type* data(const int i) {
return static_cast<value_type*>(static_cast<void*>(storage_))
+ i * Cfg::kBlockSize;
}
diff_t size(const int i) const {
return Cfg::kBlockSize - (buffer_[i].end - buffer_[i].ptr);
}
void reset(const int i) {
if (Block::kDestruct)
for (auto p = data(i), end = p + size(i); p < end; ++p)
p->~value_type();
resetBuffer(i);
}
void push(const int i, value_type&& value) {
if (Block::kInitializedStorage) {
*buffer_[i].ptr++ = std::move(value);
} else {
IPS2RA_ASSUME_NOT(buffer_[i].ptr == nullptr);
new (buffer_[i].ptr++) value_type(std::move(value));
}
}
void writeTo(const int i, typename Cfg::iterator dest) {
resetBuffer(i);
auto ptr = buffer_[i].ptr;
std::move(ptr, ptr + Cfg::kBlockSize, std::move(dest));
if (Block::kDestruct)
for (const auto end = buffer_[i].end; ptr < end; ++ptr)
ptr->~value_type();
}
private:
struct Info {
value_type* ptr;
const value_type* end;
};
void resetBuffer(const int i) {
buffer_[i].ptr = static_cast<value_type*>(static_cast<void*>(storage_))
+ i * Cfg::kBlockSize;
}
Info buffer_[Cfg::kMaxBuckets];
Block* storage_;
static_assert(sizeof(Block) == sizeof(typename Cfg::value_type) * Cfg::kBlockSize,
"Block size mismatch.");
static_assert(std::is_trivially_default_constructible<Block>::value,
"Block must be trivially default constructible.");
static_assert(std::is_trivially_destructible<Block>::value,
"Block must be trivially destructible.");
};
}
}

#include <type_traits>
#include <utility>


namespace ips2ra {
namespace detail {
template <class Cfg>
class Sorter<Cfg>::Classifier {
using iterator = typename Cfg::iterator;
using value_type = typename Cfg::value_type;
using bucket_type = typename Cfg::bucket_type;
using Extractor = typename Cfg::Extractor;
public:
Classifier(Extractor extract) : extractor_(std::move(extract)) {}
bucket_type classify(const value_type& value, int level) const {
return Cfg::getBucket(extractor_(value), level);
}
template <class Extractor>
class ClassifierUnrolled {
public:
ClassifierUnrolled(Extractor extractor) : extractor_(extractor) {}
template <int LEVEL, class iterator, class Yield>
void operator()(iterator begin, iterator end, Yield&& yield) {
static_assert(LEVEL >= 0);
constexpr const int kUnroll = Cfg::kUnrollClassifier;
IPS2RA_ASSUME_NOT(begin >= end);
IPS2RA_ASSUME_NOT(begin > (end - kUnroll));
for (auto cutoff = end - kUnroll; begin <= cutoff; begin += kUnroll) {
for (int i = 0; i < kUnroll; ++i) {
const auto key = extractor_(begin[i]);
const auto b = Cfg::template getBucket<LEVEL, decltype(key)>(key);
yield(b, begin + i);
}
}
IPS2RA_ASSUME_NOT(begin > end);
for (; begin != end; ++begin) {
const auto key = extractor_(*begin);
const auto b = Cfg::template getBucket<LEVEL, decltype(key)>(key);
yield(b, begin);
}
}
private:
Extractor extractor_;
};
template <typename Yield>
void classify(iterator begin, iterator end, int level, Yield&& yield) const {
ClassifierUnrolled<Extractor> classifier{extractor_};
switchUnroll<0, sizeof(key_type) - 1>(classifier, level, begin, end, yield);
}
const Extractor& getExtractor() const { return extractor_; }
Extractor extractor_;
};
}
}



namespace ips2ra {
namespace detail {
template <class T>
static T* alignPointer(T* ptr, std::size_t alignment) {
uintptr_t v = reinterpret_cast<std::uintptr_t>(ptr);
v = (v - 1 + alignment) & ~(alignment - 1);
return reinterpret_cast<T*>(v);
}
template <class T>
class AlignedPtr {
public:
AlignedPtr() {}
template <class... Args>
explicit AlignedPtr(std::size_t alignment, Args&&... args)
: alloc_(new char[sizeof(T) + alignment])
, value_(new (alignPointer(alloc_, alignment)) T(std::forward<Args>(args)...)) {}
AlignedPtr(const AlignedPtr&) = delete;
AlignedPtr& operator=(const AlignedPtr&) = delete;
AlignedPtr(AlignedPtr&& rhs) : alloc_(rhs.alloc_), value_(rhs.value_) {
rhs.alloc_ = nullptr;
}
AlignedPtr& operator=(AlignedPtr&& rhs) {
std::swap(alloc_, rhs.alloc_);
std::swap(value_, rhs.value_);
return *this;
}
~AlignedPtr() {
if (alloc_) {
value_->~T();
delete[] alloc_;
}
}
T& get() { return *value_; }
private:
char* alloc_ = nullptr;
T* value_;
};
template <>
class AlignedPtr<void> {
public:
AlignedPtr() {}
template <class... Args>
explicit AlignedPtr(std::size_t alignment, std::size_t size)
: alloc_(new char[size + alignment]), value_(alignPointer(alloc_, alignment)) {}
AlignedPtr(const AlignedPtr&) = delete;
AlignedPtr& operator=(const AlignedPtr&) = delete;
AlignedPtr(AlignedPtr&& rhs) : alloc_(rhs.alloc_), value_(rhs.value_) {
rhs.alloc_ = nullptr;
}
AlignedPtr& operator=(AlignedPtr&& rhs) {
std::swap(alloc_, rhs.alloc_);
std::swap(value_, rhs.value_);
return *this;
}
~AlignedPtr() {
if (alloc_) { delete[] alloc_; }
}
char* get() { return value_; }
private:
char* alloc_ = nullptr;
char* value_;
};
template <class Cfg>
class Sorter<Cfg>::BufferStorage : public AlignedPtr<void> {
public:
static constexpr const auto kPerThread = Cfg::kBlockSizeInBytes * Cfg::kMaxBuckets;
BufferStorage() {}
explicit BufferStorage(int num_threads)
: AlignedPtr<void>(Cfg::kDataAlignment, num_threads * kPerThread) {}
char* forThread(int id) { return this->get() + id * kPerThread; }
};
template <class Cfg>
struct Sorter<Cfg>::LocalData {
using diff_t = typename Cfg::difference_type;
diff_t bucket_size[Cfg::kMaxBuckets];
Buffers buffers;
Block swap[2];
Block overflow;
BucketPointers bucket_pointers[Cfg::kMaxBuckets];
PrivateQueue<Task> seq_task_queue;
Classifier classifier;
diff_t first_block;
diff_t first_empty_block;
std::linear_congruential_engine<
std::uintptr_t, Cfg::kIs64Bit ? 6364136223846793005u : 1664525u,
Cfg::kIs64Bit ? 1442695040888963407u : 1013904223u, 0u>
random_generator;
std::ptrdiff_t offs[2 * (Cfg::kBaseCaseSize + 1)];
LocalData(typename Cfg::Extractor extractor, char* buffer_storage)
: buffers(buffer_storage), classifier(std::move(extractor)) {
std::random_device rdev;
std::ptrdiff_t seed = rdev();
if (Cfg::kIs64Bit)
seed = (seed << (Cfg::kIs64Bit * 32)) | rdev();
random_generator.seed(seed);
reset();
}
void reset() { std::fill_n(bucket_size, Cfg::kMaxBuckets, 0); }
};
struct BigTask {
BigTask() : has_task{false} {}
std::ptrdiff_t begin;
std::ptrdiff_t end;
int level;
int task_thread_id;
int root_thread;
bool has_task;
};
template <class Cfg>
struct Sorter<Cfg>::SharedData {
typename Cfg::difference_type bucket_start[Cfg::kMaxBuckets + 1];
BucketPointers bucket_pointers[Cfg::kMaxBuckets];
Block* overflow;
Classifier classifier;
typename Cfg::Sync sync;
std::vector<LocalData*> local;
std::vector<std::shared_ptr<SubThreadPool>> thread_pools;
std::vector<BigTask> big_tasks;
Scheduler<Task> scheduler;
SharedData(typename Cfg::Extractor extractor, typename Cfg::Sync sync,
int num_threads)
: classifier(std::move(extractor))
, sync(std::forward<typename Cfg::Sync>(sync))
, local(num_threads)
, thread_pools(num_threads)
, big_tasks(num_threads)
, scheduler(num_threads) {
reset();
}
void reset() {
std::fill_n(bucket_start, Cfg::kMaxBuckets + 1, 0);
overflow = nullptr;
scheduler.reset();
}
};
}
}

#include <utility>



#include <atomic>
#include <tuple>
#include <utility>

#include <tuple>



namespace ips2ra {
namespace detail {
template <class Cfg>
int Sorter<Cfg>::computeOverflowBucket() {
int bucket = Cfg::kMaxBuckets - 1;
while (bucket >= 0
&& (bucket_start_[bucket + 1] - bucket_start_[bucket]) <= Cfg::kBlockSize)
--bucket;
return bucket;
}
template <class Cfg>
template <bool kIsParallel>
int Sorter<Cfg>::classifyAndReadBlock(const int read_bucket) {
auto& bp = bucket_pointers_[read_bucket];
diff_t write, read;
std::tie(write, read) = bp.template decRead<kIsParallel>();
if (read < write) {
if (kIsParallel) bp.stopRead();
return -1;
}
local_.swap[0].readFrom(begin_ + read);
if (kIsParallel) bp.stopRead();
return classifier_->classify(local_.swap[0].head(), level_);
}
template <class Cfg>
template <bool kIsParallel>
int Sorter<Cfg>::swapBlock(const diff_t max_off, const int dest_bucket,
const bool current_swap) {
diff_t write, read;
int new_dest_bucket;
auto& bp = bucket_pointers_[dest_bucket];
do {
std::tie(write, read) = bp.template incWrite<kIsParallel>();
if (write > read) {
if (write >= max_off) {
local_.swap[current_swap].writeTo(local_.overflow);
overflow_ = &local_.overflow;
return -1;
}
while (kIsParallel && bp.isReading()) {}
local_.swap[current_swap].writeTo(begin_ + write);
return -1;
}
new_dest_bucket = classifier_->classify(begin_[write], level_);
} while (new_dest_bucket == dest_bucket);
local_.swap[!current_swap].readFrom(begin_ + write);
local_.swap[current_swap].writeTo(begin_ + write);
return new_dest_bucket;
}
template <class Cfg>
template <bool kIsParallel>
void Sorter<Cfg>::permuteBlocks() {
int read_bucket = (my_id_ * Cfg::kMaxBuckets / num_threads_) % Cfg::kMaxBuckets;
const diff_t max_off = Cfg::alignToNextBlock(end_ - begin_ + 1) - Cfg::kBlockSize;
for (int count = Cfg::kMaxBuckets; count; --count) {
int dest_bucket;
while ((dest_bucket = classifyAndReadBlock<kIsParallel>(read_bucket)) != -1) {
bool current_swap = 0;
while ((dest_bucket =
swapBlock<kIsParallel>(max_off, dest_bucket, current_swap))
!= -1) {
current_swap = !current_swap;
}
}
read_bucket = (read_bucket + 1) % Cfg::kMaxBuckets;
}
}
}
}

#include <limits>
#include <utility>




namespace ips2ra {
namespace detail {
template <class Cfg>
std::pair<int, typename Cfg::difference_type> Sorter<Cfg>::saveMargins(int last_bucket) {
diff_t tail = bucket_start_[last_bucket];
const diff_t end = Cfg::alignToNextBlock(tail);
if (tail == end || end >= (end_ - begin_)) return {-1, 0};
{
const auto start_of_last_block = end - Cfg::kBlockSize;
diff_t last_start;
do {
--last_bucket;
last_start = bucket_start_[last_bucket];
} while (last_start > start_of_last_block);
}
const auto write = shared_->bucket_pointers[last_bucket].getWrite();
if (write < end) return {-1, 0};
tail = bucket_start_[last_bucket + 1];
local_.swap[0].readFrom(begin_ + tail, end - tail);
return {last_bucket, end - tail};
}
template <class Cfg>
template <bool kIsParallel>
void Sorter<Cfg>::writeMargins(const int first_bucket, const int last_bucket,
const int overflow_bucket, const int swap_bucket,
const diff_t in_swap_buffer, const int level) {
const bool is_last_level = isLastLevel(level_);
const auto extractor = classifier_->getExtractor();
for (int i = first_bucket; i < last_bucket; ++i) {
const auto bstart = bucket_start_[i];
const auto bend = bucket_start_[i + 1];
const auto bwrite = bucket_pointers_[i].getWrite();
auto dst = begin_ + bstart;
auto remaining = Cfg::alignToNextBlock(bstart) - bstart;
if (i == overflow_bucket && overflow_) {
IPS2RA_ASSUME_NOT(Cfg::alignToNextBlock(bend) != bwrite);
auto src = overflow_->data();
IPS2RA_ASSUME_NOT((bend - (bwrite - Cfg::kBlockSize)) + remaining
< Cfg::kBlockSize);
auto tail_size = Cfg::kBlockSize - remaining;
std::move(src, src + remaining, dst);
src += remaining;
remaining = std::numeric_limits<diff_t>::max();
dst = begin_ + bwrite - Cfg::kBlockSize;
dst = std::move(src, src + tail_size, dst);
overflow_->reset(Cfg::kBlockSize);
} else if (i == swap_bucket && in_swap_buffer) {
auto src = local_.swap[0].data();
IPS2RA_ASSUME_NOT(in_swap_buffer > remaining);
dst = std::move(src, src + in_swap_buffer, dst);
remaining -= in_swap_buffer;
local_.swap[0].reset(in_swap_buffer);
} else if (bwrite > bend && bend - bstart > Cfg::kBlockSize) {
IPS2RA_ASSUME_NOT(Cfg::alignToNextBlock(bend) != bwrite);
auto src = begin_ + bend;
auto head_size = bwrite - bend;
IPS2RA_ASSUME_NOT(head_size > remaining);
dst = std::move(src, src + head_size, dst);
remaining -= head_size;
}
for (int t = 0; t < num_threads_; ++t) {
auto& buffers = kIsParallel ? shared_->local[t]->buffers : local_.buffers;
auto src = buffers.data(i);
auto count = buffers.size(i);
if (count <= remaining) {
dst = std::move(src, src + count, dst);
remaining -= count;
} else {
std::move(src, src + remaining, dst);
src += remaining;
count -= remaining;
remaining = std::numeric_limits<diff_t>::max();
dst = begin_ + bwrite;
dst = std::move(src, src + count, dst);
}
buffers.reset(i);
}
if (!is_last_level && !kIsParallel) {
#ifdef IPS4O_TIMER
g_cleanup.stop();
g_base_case.start();
#endif
auto comp = [&extractor](auto&& l, auto&& r) {
return extractor(l) < extractor(r);
};
detail::smallestSortIfAtMostThreshold<Cfg::kSmallestSortSize>(
begin_ + bstart, begin_ + bend, comp);
#ifdef IPS4O_TIMER
g_base_case.stop();
g_cleanup.start();
#endif
}
}
}
}
}



#include <algorithm>


namespace ips2ra {
namespace detail {
template <class Cfg>
void Sorter<Cfg>::moveEmptyBlocks(const diff_t my_begin, const diff_t my_end,
const diff_t my_first_empty_block) {
const int bucket_range_start = [&](int i) {
while (Cfg::alignToNextBlock(bucket_start_[i]) < my_begin) ++i;
return i;
}(0);
const int bucket_range_end = [&](int i) {
if (my_id_ == num_threads_ - 1) return Cfg::kMaxBuckets;
while (i < Cfg::kMaxBuckets && Cfg::alignToNextBlock(bucket_start_[i]) < my_end)
++i;
return i;
}(bucket_range_start);
const auto bucket_end = Cfg::alignToNextBlock(bucket_start_[bucket_range_end]);
const bool last_bucket_is_overlapping = bucket_end > my_end;
for (int b = bucket_range_start; b < bucket_range_end - last_bucket_is_overlapping;
++b) {
const auto start = Cfg::alignToNextBlock(bucket_start_[b]);
const auto stop = Cfg::alignToNextBlock(bucket_start_[b + 1]);
auto read = stop;
if (my_first_empty_block <= start) {
read = start;
} else if (my_first_empty_block < stop) {
read = my_first_empty_block;
}
bucket_pointers_[b].set(start, read - Cfg::kBlockSize);
}
if (last_bucket_is_overlapping) {
const int overlapping_bucket = bucket_range_end - 1;
const auto bucket_start =
Cfg::alignToNextBlock(bucket_start_[overlapping_bucket]);
diff_t flushed_elements_in_bucket = 0;
if (bucket_start < my_begin) {
int prev_id = my_id_ - 1;
while (bucket_start < shared_->local[prev_id]->first_block) {
const auto eb = shared_->local[prev_id]->first_empty_block;
flushed_elements_in_bucket += eb - shared_->local[prev_id]->first_block;
--prev_id;
}
const auto eb = shared_->local[prev_id]->first_empty_block;
if (eb > bucket_start)
flushed_elements_in_bucket += eb - bucket_start;
}
diff_t elements_reserved = 0;
if (my_begin > bucket_start) {
elements_reserved = my_begin - bucket_start - flushed_elements_in_bucket;
flushed_elements_in_bucket += my_first_empty_block - my_begin;
} else if (my_first_empty_block > bucket_start) {
flushed_elements_in_bucket += my_first_empty_block - bucket_start;
}
int read_from_thread = my_id_ + 1;
while (read_from_thread < num_threads_
&& bucket_end > shared_->local[read_from_thread]->first_block) {
const auto eb = std::min<diff_t>(
shared_->local[read_from_thread]->first_empty_block, bucket_end);
flushed_elements_in_bucket +=
eb - shared_->local[read_from_thread]->first_block;
++read_from_thread;
}
const auto first_empty_block_in_bucket =
bucket_start + flushed_elements_in_bucket;
auto write_ptr = begin_ + std::max(my_first_empty_block, bucket_start);
const auto write_ptr_end = begin_ + std::min(first_empty_block_in_bucket, my_end);
while (write_ptr < write_ptr_end) {
--read_from_thread;
auto read_ptr = std::min(shared_->local[read_from_thread]->first_empty_block,
bucket_end);
auto read_range_size =
read_ptr - shared_->local[read_from_thread]->first_block;
if (elements_reserved >= read_range_size) {
elements_reserved -= read_range_size;
continue;
}
read_ptr -= elements_reserved;
read_range_size -= elements_reserved;
elements_reserved = 0;
const auto size = std::min(read_range_size, write_ptr_end - write_ptr);
write_ptr = std::move(begin_ + read_ptr - size, begin_ + read_ptr, write_ptr);
}
if (my_begin <= bucket_start) {
bucket_pointers_[overlapping_bucket].set(
bucket_start, first_empty_block_in_bucket - Cfg::kBlockSize);
}
}
}
}
}


namespace ips2ra {
namespace detail {
template <class Cfg>
typename Cfg::difference_type Sorter<Cfg>::classifyLocally(const iterator my_begin,
const iterator my_end) {
auto write = my_begin;
auto& buffers = local_.buffers;
classifier_->template classify(my_begin, my_end, level_,
[&](typename Cfg::bucket_type bucket, iterator it) {
if (buffers.isFull(bucket)) {
buffers.writeTo(bucket, write);
write += Cfg::kBlockSize;
local_.bucket_size[bucket] += Cfg::kBlockSize;
}
buffers.push(bucket, std::move(*it));
});
for (int i = 0, end = Cfg::kMaxBuckets; i < end; ++i)
local_.bucket_size[i] += local_.buffers.size(i);
return write - begin_;
}
template <class Cfg>
void Sorter<Cfg>::sequentialClassification() {
const auto my_first_empty_block = classifyLocally(begin_, end_);
diff_t sum = 0;
bucket_start_[0] = 0;
for (int i = 0, end = Cfg::kMaxBuckets; i < end; ++i) {
sum += local_.bucket_size[i];
bucket_start_[i + 1] = sum;
}
IPS2RA_ASSUME_NOT(bucket_start_[Cfg::kMaxBuckets] != end_ - begin_);
for (int bucket = 0, end = Cfg::kMaxBuckets; bucket < end; ++bucket) {
const auto start = Cfg::alignToNextBlock(bucket_start_[bucket]);
const auto stop = Cfg::alignToNextBlock(bucket_start_[bucket + 1]);
bucket_pointers_[bucket].set(
start,
(start >= my_first_empty_block
? start
: (stop <= my_first_empty_block ? stop : my_first_empty_block))
- Cfg::kBlockSize);
}
}
template <class Cfg>
void Sorter<Cfg>::parallelClassification() {
const auto elements_per_thread = static_cast<double>(end_ - begin_) / num_threads_;
const auto my_begin =
begin_ + Cfg::alignToNextBlock(my_id_ * elements_per_thread + 0.5);
const auto my_end = [&] {
const auto size = end_ - begin_;
const auto e = Cfg::alignToNextBlock((my_id_ + 1) * elements_per_thread + 0.5);
if (size < e) {
return end_;
}
return begin_ + e;
}();
local_.first_block = my_begin - begin_;
if (my_begin >= my_end) {
local_.first_empty_block = my_begin - begin_;
shared_->sync.barrier();
shared_->sync.barrier();
} else {
const auto my_first_empty_block = classifyLocally(my_begin, my_end);
diff_t sum = 0;
for (int i = 0, end = Cfg::kMaxBuckets; i < end; ++i) {
sum += local_.bucket_size[i];
__atomic_fetch_add(&bucket_start_[i + 1], sum, __ATOMIC_RELAXED);
}
local_.first_empty_block = my_first_empty_block;
shared_->sync.barrier();
#ifdef IPS4O_TIMER
g_classification.stop(end_ - begin_, "class");
g_empty_block.start();
#endif
moveEmptyBlocks(my_begin - begin_, my_end - begin_, my_first_empty_block);
shared_->sync.barrier();
#ifdef IPS4O_TIMER
g_empty_block.stop();
g_classification.start();
#endif
}
}
}
}



namespace ips2ra {
namespace detail {
template <class Cfg>
template <bool kIsParallel>
void Sorter<Cfg>::partition(const iterator begin, const iterator end, int level,
diff_t* const bucket_start, const int my_id,
const int num_threads) {
#ifdef IPS4O_TIMER
g_overhead.stop();
g_classification.start();
#endif
this->classifier_ = kIsParallel ? &shared_->classifier : &local_.classifier;
this->bucket_start_ = bucket_start;
this->bucket_pointers_ =
kIsParallel ? shared_->bucket_pointers : local_.bucket_pointers;
this->overflow_ = nullptr;
this->begin_ = begin;
this->end_ = end;
this->my_id_ = my_id;
this->num_threads_ = num_threads;
this->level_ = level;
if (kIsParallel)
parallelClassification();
else
sequentialClassification();
#ifdef IPS4O_TIMER
g_classification.stop(end - begin, "class");
g_permutation.start();
#endif
const int overflow_bucket = computeOverflowBucket();
permuteBlocks<kIsParallel>();
if (kIsParallel && overflow_)
shared_->overflow = &local_.overflow;
if (kIsParallel) shared_->sync.barrier();
#ifdef IPS4O_TIMER
g_permutation.stop(end - begin, "perm");
g_cleanup.start();
#endif
{
if (kIsParallel) overflow_ = shared_->overflow;
const int buckets_per_thread =
(Cfg::kMaxBuckets + num_threads_ - 1) / num_threads_;
int my_first_bucket = my_id_ * buckets_per_thread;
int my_last_bucket = (my_id_ + 1) * buckets_per_thread;
my_first_bucket =
Cfg::kMaxBuckets < my_first_bucket ? Cfg::kMaxBuckets : my_first_bucket;
my_last_bucket =
Cfg::kMaxBuckets < my_last_bucket ? Cfg::kMaxBuckets : my_last_bucket;
const auto in_swap_buffer = !kIsParallel ? std::pair<int, diff_t>(-1, 0)
: saveMargins(my_last_bucket);
if (kIsParallel) shared_->sync.barrier();
writeMargins<kIsParallel>(my_first_bucket, my_last_bucket, overflow_bucket,
in_swap_buffer.first, in_swap_buffer.second, level);
}
if (kIsParallel) shared_->sync.barrier();
#ifdef IPS4O_TIMER
g_cleanup.stop();
g_overhead.start();
#endif
local_.reset();
}
}
}

#include <iterator>
#include <random>
#include <utility>





namespace ips2ra {
namespace detail {
template <class It, class RandomGen>
void selectSample(It begin, const It end,
typename std::iterator_traits<It>::difference_type num_samples,
RandomGen&& gen) {
assert(end - begin >= num_samples);
using std::swap;
auto n = end - begin;
while (num_samples--) {
const auto i = std::uniform_int_distribution<
typename std::iterator_traits<It>::difference_type>(0, --n)(gen);
swap(*begin, begin[i]);
++begin;
}
}
template <class Cfg>
std::pair<int, int> Sorter<Cfg>::sampleLevels(const iterator begin, const iterator end) {
if (begin == end) return {0, 0};
const auto n = end - begin;
const auto oversampling = std::max<diff_t>(1, 0.25 * detail::log2(n));
const auto buckets = std::min<diff_t>(std::max<diff_t>(1, detail::log2(n)), 256);
const auto num_samples = oversampling * buckets;
assert(num_samples <= n);
detail::selectSample(begin, end, num_samples, local_.random_generator);
const typename Cfg::Extractor& extractor = local_.classifier.getExtractor();
key_type ref = extractor(*begin);
key_type differing_bits{0};
for (auto it = begin + 1; it != begin + num_samples; ++it) {
differing_bits |= ref ^ extractor(*it);
}
const int lz = detail::clz(differing_bits);
const int tz = detail::ctz(differing_bits);
return {lz / 8, sizeof(key_type) - tz / 8};
}
template <class Cfg>
std::pair<int, int> Sorter<Cfg>::parallelGetLevels(const iterator begin,
const iterator end,
std::vector<key_type>& tmp,
std::vector<bool>& sorted_tmp, int id,
int num_threads) {
assert(tmp.size() == num_threads);
assert(sorted_tmp.size() == num_threads);
if (begin == end) return {0, 0};
const auto n = end - begin;
const auto stripe = (n + num_threads - 1) / num_threads;
const auto stripe_begin = begin + stripe * id;
const auto stripe_end = begin + std::min(n, stripe * (id + 1));
const typename Cfg::Extractor& extractor = local_.classifier.getExtractor();
key_type differing_bits{0};
key_type ref = extractor(*begin);
if (stripe_begin == stripe_end) {
sorted_tmp[id] = true;
} else if (extractor(*stripe_begin) <= extractor(*(stripe_end - 1))) {
bool my_sorted = true;
iterator it = stripe_begin;
for (; (it + 1) != stripe_end; ++it) {
differing_bits |= ref ^ extractor(*it);
my_sorted &= extractor(*it) <= extractor(*(it + 1));
}
differing_bits |= ref ^ extractor(*it);
sorted_tmp[id] = my_sorted;
} else {
iterator it = stripe_begin;
for (; it != stripe_end; ++it) { differing_bits |= ref ^ extractor(*it); }
sorted_tmp[id] = false;
}
tmp[id] = differing_bits;
shared_->sync.barrier();
if (id == 0) {
const bool all_sorted = std::all_of(sorted_tmp.begin(), sorted_tmp.end(),
[](const bool& a) { return a; });
if (all_sorted) { return {0, 0}; }
differing_bits = std::accumulate(
tmp.begin(), tmp.end(), key_type{0},
[](const key_type& ka, const key_type& kb) { return ka | kb; });
const int lz = detail::clz(differing_bits);
const int tz = detail::ctz(differing_bits);
return {lz / 8, sizeof(key_type) - tz / 8};
} else {
return {0, 0};
}
}
template <class Cfg>
std::pair<int, int> Sorter<Cfg>::sequentialGetLevels(iterator begin, iterator end) {
if (begin == end) { return {0, 0}; }
auto [level_begin, level_end] = sampleLevels(begin, end);
if (level_begin != 0 || level_end != sizeof(key_type)) {
const typename Cfg::Extractor& extractor = local_.classifier.getExtractor();
key_type ref = extractor(*begin);
key_type differing_bits{0};
if (extractor(*begin) <= extractor(*(end - 1))) {
bool sorted = true;
iterator it = begin;
for (; (it + 1) != end; ++it) {
differing_bits |= ref ^ extractor(*it);
sorted &= extractor(*it) <= extractor(*(it + 1));
}
if (sorted) { return {0, 0}; }
differing_bits |= ref ^ extractor(*it);
} else {
bool reverse_sorted = true;
iterator it = begin;
for (; (it + 1) != end; ++it) {
differing_bits |= ref ^ extractor(*it);
reverse_sorted &= extractor(*(it + 1)) < extractor(*it);
}
if (reverse_sorted) {
std::reverse(begin, end);
return {0, 0};
}
differing_bits |= ref ^ extractor(*it);
}
const int lz = detail::clz(differing_bits);
const int tz = detail::ctz(differing_bits);
return {lz / 8, sizeof(key_type) - tz / 8};
} else {
return {level_begin, level_end};
}
}
template <class Cfg>
bool Sorter<Cfg>::nextLevelExists(int level) {
return level + 1 < level_end_;
}
template <class Cfg>
bool Sorter<Cfg>::levelExists(int level) {
return level < level_end_;
}
template <class Cfg>
bool Sorter<Cfg>::isLastLevel(int level) {
assert(levelExists(level));
return level + 1 == level_end_;
}
}
}

#include <algorithm>
#include <cstdint>
#include <tuple>
#include <type_traits>
#include <utility>

namespace ips2ra {
namespace detail {
struct PartitionInfo {
PartitionInfo() : count(0) {}
union {
size_t count;
size_t offset;
};
size_t next_offset;
};
template <typename It, typename Func>
inline void unroll_loop_four_times(It begin, size_t iteration_count, Func&& to_call) {
size_t loop_count = iteration_count / 4;
size_t remainder_count = iteration_count - loop_count * 4;
for (; loop_count > 0; --loop_count) {
to_call(begin);
++begin;
to_call(begin);
++begin;
to_call(begin);
++begin;
to_call(begin);
++begin;
}
switch (remainder_count) {
case 3: to_call(begin); ++begin;
case 2: to_call(begin); ++begin;
case 1: to_call(begin);
}
}
template <typename It, typename F>
inline It custom_std_partition(It begin, It end, F&& func) {
for (;; ++begin) {
if (begin == end) return end;
if (!func(*begin)) break;
}
It it = begin;
for (++it; it != end; ++it) {
if (!func(*it)) continue;
std::iter_swap(begin, it);
++begin;
}
return begin;
}
template <std::ptrdiff_t kSmallestSortSize, std::ptrdiff_t kBaseCaseMaxSize,
std::ptrdiff_t kAmericanFlagSortThreshold, typename KeyType>
class SimpleSkaSort {
public:
template <typename It, typename ExtractKey>
static void Sort(It begin, It end, std::ptrdiff_t* offs, ExtractKey& extract_key,
std::size_t offset, std::size_t offset_end) {
SimpleSkaSort<kSmallestSortSize, kBaseCaseMaxSize, kAmericanFlagSortThreshold,
KeyType>
sorter;
switchUnroll<0, sizeof(KeyType) - 1>(sorter, offset, begin, end, offset_end, offs,
extract_key);
}
template <std::size_t Offset, typename It, typename ExtractKey>
void operator()(It begin, It end, std::size_t offset_end, std::ptrdiff_t* offs,
ExtractKey& extract_key) {
SimpleSkaSort<kSmallestSortSize, kBaseCaseMaxSize, kAmericanFlagSortThreshold,
KeyType>::RecSort<Offset>(begin, end, offset_end, offs,
extract_key);
}
private:
template <std::size_t Offset>
constexpr inline static std::size_t ShiftAmount() {
return (((sizeof(KeyType) - 1) - Offset) * 8);
}
template <std::size_t Offset, typename T>
inline static uint8_t CurrentByte(T&& elem) {
return elem >> ShiftAmount<Offset>();
}
template <std::size_t Offset, typename It, typename ExtractKey>
static void RecSort(It begin, It end, std::size_t offset_end, std::ptrdiff_t* offs,
ExtractKey& extract_key) {
const std::ptrdiff_t num_elements = end - begin;
if (!BaseCaseIfLessThanThreshold(begin, end, num_elements, offs, extract_key)) {
if (num_elements < kAmericanFlagSortThreshold)
AmericanFlagSort<Offset>(begin, end, offset_end, offs, extract_key);
else
SkaByteSort<Offset>(begin, end, offset_end, offs, extract_key);
}
}
template <typename It, typename ExtractKey>
static bool BaseCaseIfLessThanThreshold(It begin, It end, std::ptrdiff_t num_elements,
std::ptrdiff_t* offs,
ExtractKey& extract_key) {
if (num_elements >= kBaseCaseMaxSize) return false;
ips2ra::detail::baseCaseSort<kSmallestSortSize, kBaseCaseMaxSize - 1>(
begin, end, offs, extract_key);
return true;
}
template <std::size_t Offset, typename It, typename ExtractKey>
static void AmericanFlagSort(It begin, It end, std::size_t offset_end,
std::ptrdiff_t* offs, ExtractKey& extract_key) {
PartitionInfo partitions[256];
for (It it = begin; it != end; ++it) {
++partitions[CurrentByte<Offset>(extract_key(*it))].count;
}
size_t total = 0;
uint8_t remaining_partitions[256];
int num_partitions = 0;
for (int i = 0; i < 256; ++i) {
size_t count = partitions[i].count;
if (!count) continue;
partitions[i].offset = total;
total += count;
partitions[i].next_offset = total;
remaining_partitions[num_partitions] = i;
++num_partitions;
}
if (num_partitions > 1) {
uint8_t* current_block_ptr = remaining_partitions;
PartitionInfo* current_block = partitions + *current_block_ptr;
uint8_t* last_block = remaining_partitions + num_partitions - 1;
It it = begin;
It block_end = begin + current_block->next_offset;
It last_element = end - 1;
for (;;) {
PartitionInfo* block = partitions + CurrentByte<Offset>(extract_key(*it));
if (block == current_block) {
++it;
if (it == last_element)
break;
else if (it == block_end) {
for (;;) {
++current_block_ptr;
if (current_block_ptr == last_block) goto recurse;
current_block = partitions + *current_block_ptr;
if (current_block->offset != current_block->next_offset)
break;
}
it = begin + current_block->offset;
block_end = begin + current_block->next_offset;
}
} else {
size_t offset = block->offset++;
std::iter_swap(it, begin + offset);
}
}
}
recurse:
if constexpr (Offset + 1 < sizeof(KeyType)) {
if (Offset + 1 != offset_end) {
size_t start_offset = 0;
It partition_begin = begin;
for (uint8_t *it = remaining_partitions,
*end = remaining_partitions + num_partitions;
it != end; ++it) {
size_t end_offset = partitions[*it].next_offset;
It partition_end = begin + end_offset;
SimpleSkaSort<kSmallestSortSize, kBaseCaseMaxSize,
kAmericanFlagSortThreshold,
KeyType>::RecSort<Offset + 1>(partition_begin,
partition_end, offset_end,
offs, extract_key);
start_offset = end_offset;
partition_begin = partition_end;
}
}
}
}
template <std::size_t Offset, typename It, typename ExtractKey>
static void SkaByteSort(It begin, It end, std::size_t offset_end,
std::ptrdiff_t* offs, ExtractKey& extract_key) {
PartitionInfo partitions[256];
for (It it = begin; it != end; ++it) {
++partitions[CurrentByte<Offset>(extract_key(*it))].count;
}
uint8_t remaining_partitions[256];
size_t total = 0;
int num_partitions = 0;
for (int i = 0; i < 256; ++i) {
size_t count = partitions[i].count;
if (count) {
partitions[i].offset = total;
total += count;
remaining_partitions[num_partitions] = i;
++num_partitions;
}
partitions[i].next_offset = total;
}
for (uint8_t *last_remaining = remaining_partitions + num_partitions,
*end_partition = remaining_partitions + 1;
last_remaining > end_partition;) {
last_remaining = custom_std_partition(
remaining_partitions, last_remaining, [&](uint8_t partition) {
size_t& begin_offset = partitions[partition].offset;
size_t& end_offset = partitions[partition].next_offset;
if (begin_offset == end_offset) return false;
unroll_loop_four_times(
begin + begin_offset, end_offset - begin_offset,
[partitions = partitions, begin, &extract_key](It it) {
uint8_t this_partition =
CurrentByte<Offset>(extract_key(*it));
size_t offset = partitions[this_partition].offset++;
std::iter_swap(it, begin + offset);
});
return begin_offset != end_offset;
});
}
if constexpr (Offset + 1 < sizeof(KeyType)) {
if (Offset + 1 != offset_end) {
for (uint8_t* it = remaining_partitions + num_partitions;
it != remaining_partitions; --it) {
uint8_t partition = it[-1];
size_t start_offset =
(partition == 0 ? 0 : partitions[partition - 1].next_offset);
size_t end_offset = partitions[partition].next_offset;
It partition_begin = begin + start_offset;
It partition_end = begin + end_offset;
SimpleSkaSort<kSmallestSortSize, kBaseCaseMaxSize,
kAmericanFlagSortThreshold,
KeyType>::RecSort<Offset + 1>(partition_begin,
partition_end, offset_end,
offs, extract_key);
}
}
}
}
};
}
}


namespace ips2ra {
namespace detail {
#if defined(_REENTRANT)
template <class Cfg>
void Sorter<Cfg>::sequential(const iterator begin, const Task& task,
PrivateQueue<Task>& queue) {
IPS2RA_IS_NOT(!levelExists(task.level));
IPS2RA_IS_NOT(task.end - task.begin <= Cfg::kSmallestSortSize);
IPS2RA_IS_NOT(level_end_ == -1);
const auto n = task.end - task.begin;
if (n < Cfg::kSkasort) {
#ifdef IPS4O_TIMER
g_overhead.stop();
g_base_case.start();
#endif
ips2ra::detail::SimpleSkaSort<Cfg::kSmallestSortSize, Cfg::kBaseCaseSize,
Cfg::kAmericanFlagSort,
key_type>::Sort(begin + task.begin,
begin + task.end, local_.offs,
local_.classifier.getExtractor(),
task.level, level_end_);
#ifdef IPS4O_TIMER
g_base_case.stop();
g_overhead.start();
#endif
return;
}
diff_t bucket_start[Cfg::kMaxBuckets + 1];
partition<false>(begin + task.begin, begin + task.end, task.level, bucket_start, 0,
1);
if (isLastLevel(task.level)) { return; }
for (int i = Cfg::kMaxBuckets - 1; i >= 0; --i) {
const auto start = bucket_start[i];
const auto stop = bucket_start[i + 1];
if (stop - start > Cfg::kSmallestSortSize)
queue.emplace(task.begin + start, task.begin + stop, task.level + 1);
}
}
#endif
template <class Cfg>
void Sorter<Cfg>::sequential(const iterator begin, const iterator end) {
static constexpr std::ptrdiff_t threshold = Cfg::kSmallestSortSize;
auto& extract_key = local_.classifier.getExtractor();
auto comp = [&extract_key](auto&& l, auto&& r) {
return extract_key(l) < extract_key(r);
};
if (!detail::smallestSortIfAtMostThreshold<threshold>(begin, end, comp)) {
const auto [level_begin, level_end] = sequentialGetLevels(begin, end);
level_end_ = level_end;
if (levelExists(level_begin)) { sequentialRec(begin, end, level_begin); }
}
}
template <class Cfg>
void Sorter<Cfg>::sequentialRec(const iterator begin, const iterator end,
const int level) {
IPS2RA_IS_NOT(!levelExists(level));
IPS2RA_IS_NOT(end - begin <= Cfg::kSmallestSortSize);
IPS2RA_IS_NOT(level_end_ == -1);
const auto n = end - begin;
if (n < Cfg::kSkasort) {
#ifdef IPS4O_TIMER
g_overhead.stop();
g_base_case.start();
#endif
ips2ra::detail::SimpleSkaSort<Cfg::kSmallestSortSize, Cfg::kBaseCaseSize,
Cfg::kAmericanFlagSort,
key_type>::Sort(begin, end, local_.offs,
local_.classifier.getExtractor(),
level, level_end_);
#ifdef IPS4O_TIMER
g_base_case.stop();
g_overhead.start();
#endif
return;
}
diff_t bucket_start[Cfg::kMaxBuckets + 1];
partition<false>(begin, end, level, bucket_start, 0, 1);
if (isLastLevel(level)) return;
#ifdef IPS4O_TIMER
g_ips4o_level++;
#endif
for (int i = 0; i < Cfg::kMaxBuckets; ++i) {
const auto start = bucket_start[i];
const auto stop = bucket_start[i + 1];
if (stop - start > Cfg::kSmallestSortSize)
sequentialRec(begin + start, begin + stop, level + 1);
}
#ifdef IPS4O_TIMER
g_ips4o_level--;
#endif
}
}
template <class Cfg>
class SequentialSorter {
using Sorter = detail::Sorter<Cfg>;
using iterator = typename Cfg::iterator;
public:
explicit SequentialSorter(typename Cfg::Extractor extractor)
: buffer_storage_(1)
, local_ptr_(Cfg::kDataAlignment, std::move(extractor), buffer_storage_.get()) {}
explicit SequentialSorter(typename Cfg::Extractor extractor, char* buffer_storage)
: local_ptr_(Cfg::kDataAlignment, std::move(extractor), buffer_storage) {}
void operator()(iterator begin, iterator end) {
Sorter(local_ptr_.get()).sequential(std::move(begin), std::move(end));
}
private:
typename Sorter::BufferStorage buffer_storage_;
detail::AlignedPtr<typename Sorter::LocalData> local_ptr_;
};
}

namespace ips2ra {
template <class It, class Extractor = Config<>::identity, class Cfg = Config<>>
SequentialSorter<ExtendedConfig<It, Extractor, Cfg>> make_sorter(
Extractor extractor = Extractor{}) {
return SequentialSorter<ExtendedConfig<It, Extractor, Cfg>>{std::move(extractor)};
}
template <class Cfg, class It, class Extractor = Config<>::identity>
void sort(It begin, It end, Extractor extractor = Extractor{}) {
#ifdef IPS4O_TIMER
g_active_counters = -1;
g_total.start();
g_overhead.start();
#endif
static constexpr std::ptrdiff_t threshold =
Cfg::kSmallestSortMultiplier * Cfg::kSmallestSortSize;
if (end - begin <= threshold) {
#ifdef IPS4O_TIMER
g_overhead.stop();
g_base_case.start();
#endif
std::ptrdiff_t offs[2 * (threshold + 1)];
detail::baseCaseSort<Cfg::kSmallestSortSize, threshold>(begin, end, offs,
extractor);
#ifdef IPS4O_TIMER
g_base_case.stop();
g_overhead.start();
#endif
} else {
ips2ra::make_sorter<It, Extractor, Cfg>(std::move(extractor))(std::move(begin),
std::move(end));
}
#ifdef IPS4O_TIMER
g_overhead.stop();
g_total.stop();
#endif
}
template <class It, class Extractor>
void sort(It begin, It end, Extractor extractor) {
ips2ra::sort<Config<>>(std::move(begin), std::move(end), std::move(extractor));
}
template <class It>
void sort(It begin, It end) {
ips2ra::sort<Config<>>(std::move(begin), std::move(end), Config<>::identity{});
}
#if defined(_REENTRANT) || defined(_OPENMP)
namespace parallel {
template <class It, class Cfg = Config<>, class ThreadPool,
class Extractor = Config<>::identity>
std::enable_if_t<std::is_class<std::remove_reference_t<ThreadPool>>::value,
ParallelSorter<ExtendedConfig<It, Extractor, Cfg, ThreadPool>>>
make_sorter(ThreadPool&& thread_pool, Extractor extractor = Extractor{}) {
return ParallelSorter<ExtendedConfig<It, Extractor, Cfg, ThreadPool>>(
std::move(extractor), std::forward<ThreadPool>(thread_pool));
}
template <class It, class Cfg = Config<>, class Extractor = Config<>::identity>
ParallelSorter<ExtendedConfig<It, Extractor, Cfg>> make_sorter(
int num_threads = DefaultThreadPool::maxNumThreads(),
Extractor extractor = Extractor{}) {
return ParallelSorter<ExtendedConfig<It, Extractor, Cfg>>(
std::move(extractor), DefaultThreadPool(num_threads));
}
template <class Cfg = Config<>, class It, class Extractor, class ThreadPool>
std::enable_if_t<std::is_class<std::remove_reference_t<ThreadPool>>::value> sort(
It begin, It end, Extractor extractor, ThreadPool&& thread_pool) {
#ifdef IPS4O_TIMER
g_active_counters = -1;
g_total.start();
g_overhead.start();
#endif
if (Cfg::numThreadsFor(begin, end, thread_pool.numThreads()) < 2) {
ips2ra::sort<Cfg>(std::move(begin), std::move(end), std::move(extractor));
} else {
ips2ra::parallel::make_sorter<It, Cfg>(std::forward<ThreadPool>(thread_pool),
std::move(extractor))(std::move(begin),
std::move(end));
}
#ifdef IPS4O_TIMER
g_overhead.stop();
g_total.stop();
#endif
}
template <class Cfg = Config<>, class It, class Extractor>
void sort(It begin, It end, Extractor extractor, int num_threads) {
#ifdef IPS4O_TIMER
g_active_counters = -1;
g_total.start();
g_overhead.start();
#endif
num_threads = Cfg::numThreadsFor(begin, end, num_threads);
if (num_threads < 2) {
ips2ra::sort<Cfg>(std::move(begin), std::move(end), std::move(extractor));
} else {
ips2ra::parallel::make_sorter<It, Cfg>(num_threads, std::move(extractor))(
std::move(begin), std::move(end));
}
#ifdef IPS4O_TIMER
g_overhead.stop();
g_total.stop();
#endif
}
template <class It, class Extractor>
void sort(It begin, It end, Extractor extractor) {
ips2ra::parallel::sort<Config<>>(std::move(begin), std::move(end),
std::move(extractor),
DefaultThreadPool::maxNumThreads());
}
template <class It>
void sort(It begin, It end) {
ips2ra::parallel::sort<Config<>>(std::move(begin), std::move(end),
Config<>::identity{},
DefaultThreadPool::maxNumThreads());
}
}
#endif
}


void sort(unsigned* a,int n){if(n>1)ips2ra::sort(a,a+n);}

评测结果