GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "../include/radix_sort_stl.hpp"
2
3			#include <algorithm>
4			#include <array>
5			#include <cstddef>
6			#include <cstdint>
7			#include <cstring>
8			#include <thread>
9			#include <utility>
10			#include <vector>
11
12			#include "util/include/util.hpp"
13
14			namespace golovanov_d_radix_merge {
15
16			namespace {
17			constexpr int kBytes = 8;
18			constexpr std::size_t kRadix = 256;
19			constexpr std::uint64_t kSignMask = 1ULL << 63;
20			constexpr std::uint64_t kByteMask = 0xFFULL;
21
22			std::uint64_t ToSortable(std::uint64_t bits) {
23		✗	return ((bits & kSignMask) != 0U) ? ~bits : (bits ^ kSignMask);
24			}
25
26			std::uint64_t FromSortable(std::uint64_t bits) {
27		✗	return ((bits & kSignMask) != 0U) ? (bits ^ kSignMask) : ~bits;
28			}
29
30			int GetThreadCount(std::size_t size) {
31		✗	if (size == 0) {
32			return 1;
33			}
34
35		✗	int num_threads = ppc::util::GetNumThreads();
36		✗	if (num_threads <= 0) {
37			num_threads = 1;
38			}
39
40		✗	const auto max_threads = static_cast<int>(size);
41			return std::min(num_threads, max_threads);
42			}
43
44		✗	std::vector<std::pair<std::size_t, std::size_t>> BuildRanges(std::size_t size, int num_threads) {
45		✗	if (num_threads <= 0) {
46			num_threads = 1;
47			}
48
49		✗	const auto threads_count = static_cast<std::size_t>(num_threads);
50		✗	std::vector<std::pair<std::size_t, std::size_t>> ranges(threads_count);
51
52		✗	const std::size_t base = size / threads_count;
53		✗	const std::size_t rem = size % threads_count;
54
55			std::size_t begin = 0;
56		✗	for (std::size_t i = 0; i < ranges.size(); ++i) {
57		✗	const std::size_t block_size = base + ((i < rem) ? 1U : 0U);
58		✗	ranges[i] = {begin, begin + block_size};
59			begin += block_size;
60			}
61
62		✗	return ranges;
63			}
64
65		✗	void SortParts(std::vector<double> &arr, const std::vector<std::pair<std::size_t, std::size_t>> &ranges) {
66		✗	std::vector<std::thread> workers;
67		✗	workers.reserve(ranges.size());
68
69		✗	for (const auto &range : ranges) {
70		✗	workers.emplace_back([&arr, range]() { RadixSortSTL::SortRange(arr, range.first, range.second); });
71			}
72
73		✗	for (auto &worker : workers) {
74		✗	worker.join();
75			}
76		✗	}
77
78		✗	std::vector<std::vector<double>> CopyParts(const std::vector<double> &arr,
79			const std::vector<std::pair<std::size_t, std::size_t>> &ranges) {
80		✗	std::vector<std::vector<double>> parts(ranges.size());
81
82		✗	for (std::size_t i = 0; i < ranges.size(); ++i) {
83		✗	parts[i] = std::vector<double>(arr.begin() + static_cast<std::ptrdiff_t>(ranges[i].first),
84		✗	arr.begin() + static_cast<std::ptrdiff_t>(ranges[i].second));
85			}
86
87		✗	return parts;
88		✗	}
89
90		✗	std::vector<std::vector<double>> MergeStep(const std::vector<std::vector<double>> &parts) {
91		✗	const std::size_t pair_count = parts.size() / 2;
92		✗	std::vector<std::vector<double>> next((parts.size() + 1) / 2);
93		✗	std::vector<std::thread> workers;
94		✗	workers.reserve(pair_count);
95
96		✗	for (std::size_t i = 0; i < pair_count; ++i) {
97		✗	workers.emplace_back([&parts, &next, i]() { next[i] = RadixSortSTL::Merge(parts[2 * i], parts[(2 * i) + 1]); });
98			}
99
100		✗	for (auto &worker : workers) {
101		✗	worker.join();
102			}
103
104		✗	if ((parts.size() % 2U) != 0U) {
105		✗	next.back() = parts.back();
106			}
107
108		✗	return next;
109		✗	}
110
111			} // namespace
112
113		✗	void RadixSortSTL::SortRange(std::vector<double> &arr, std::size_t left, std::size_t right) {
114		✗	if (right <= left) {
115		✗	return;
116			}
117
118		✗	const std::size_t n = right - left;
119		✗	std::vector<std::uint64_t> data(n);
120
121		✗	for (std::size_t i = 0; i < n; ++i) {
122			std::uint64_t bits = 0;
123		✗	std::memcpy(&bits, &arr[left + i], sizeof(double));
124		✗	data[i] = ToSortable(bits);
125			}
126
127		✗	std::vector<std::uint64_t> buffer(n);
128
129		✗	for (int byte = 0; byte < kBytes; ++byte) {
130		✗	std::array<std::size_t, kRadix> count{};
131
132		✗	for (std::size_t i = 0; i < n; ++i) {
133		✗	const auto bucket = static_cast<std::size_t>((data[i] >> (byte * 8)) & kByteMask);
134		✗	++count.at(bucket);
135			}
136
137			std::size_t sum = 0;
138		✗	for (std::size_t i = 0; i < kRadix; ++i) {
139		✗	const std::size_t tmp = count.at(i);
140		✗	count.at(i) = sum;
141		✗	sum += tmp;
142			}
143
144		✗	for (std::size_t i = 0; i < n; ++i) {
145		✗	const auto bucket = static_cast<std::size_t>((data[i] >> (byte * 8)) & kByteMask);
146		✗	const std::size_t pos = count.at(bucket);
147		✗	buffer[pos] = data[i];
148		✗	++count.at(bucket);
149			}
150
151			data.swap(buffer);
152			}
153
154		✗	for (std::size_t i = 0; i < n; ++i) {
155		✗	const std::uint64_t bits = FromSortable(data[i]);
156		✗	std::memcpy(&arr[left + i], &bits, sizeof(double));
157			}
158			}
159
160		✗	std::vector<double> RadixSortSTL::Merge(const std::vector<double> &a, const std::vector<double> &b) {
161		✗	std::vector<double> result;
162		✗	result.reserve(a.size() + b.size());
163
164			std::size_t i = 0;
165			std::size_t j = 0;
166
167		✗	while (i < a.size() && j < b.size()) {
168		✗	if (a[i] <= b[j]) {
169			result.push_back(a[i]);
170		✗	++i;
171			} else {
172			result.push_back(b[j]);
173		✗	++j;
174			}
175			}
176
177		✗	while (i < a.size()) {
178			result.push_back(a[i]);
179		✗	++i;
180			}
181
182		✗	while (j < b.size()) {
183			result.push_back(b[j]);
184		✗	++j;
185			}
186
187		✗	return result;
188			}
189
190		✗	void RadixSortSTL::Sort(std::vector<double> &arr) {
191		✗	if (arr.empty()) {
192		✗	return;
193			}
194
195			const int num_threads = GetThreadCount(arr.size());
196		✗	const auto ranges = BuildRanges(arr.size(), num_threads);
197
198		✗	SortParts(arr, ranges);
199
200		✗	std::vector<std::vector<double>> parts = CopyParts(arr, ranges);
201		✗	while (parts.size() > 1) {
202		✗	parts = MergeStep(parts);
203			}
204
205			arr = std::move(parts.front());
206		✗	}
207
208			} // namespace golovanov_d_radix_merge
209