GCC Code Coverage Report

Directory: ./
File: tasks/nikitina_v_hoar_sort_batcher/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 102 103 99.0%
Functions: 10 10 100.0%
Branches: 68 98 69.4%
Line Branch Exec Source
1 #include "nikitina_v_hoar_sort_batcher/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <limits>
8 #include <thread>
9 #include <utility>
10 #include <vector>
11
12 #include "nikitina_v_hoar_sort_batcher/common/include/common.hpp"
13
14 namespace nikitina_v_hoar_sort_batcher {
15
16 namespace {
17
18 14 void QuickSortHoare(std::vector<int> &arr, int low, int high) {
19
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 14 times.
 14 if (low >= high) {
20 ✗ return;
21 }
22 14 std::vector<std::pair<int, int>> stack;
23
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 stack.emplace_back(low, high);
24
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 14 times.
 104 while (!stack.empty()) {
25 auto [left_bound, right_bound] = stack.back();
26 stack.pop_back();
27
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 38 times.
 90 if (left_bound >= right_bound) {
28 52 continue;
29 }
30 38 int pivot = arr[left_bound + ((right_bound - left_bound) / 2)];
31 38 int left_idx = left_bound - 1;
32 38 int right_idx = right_bound + 1;
33 while (true) {
34 63 left_idx++;
35
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 63 times.
 75 while (arr[left_idx] < pivot) {
36 12 left_idx++;
37 }
38 63 right_idx--;
39
2/2
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 63 times.
 113 while (arr[right_idx] > pivot) {
40 50 right_idx--;
41 }
42
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 38 times.
 63 if (left_idx >= right_idx) {
43 break;
44 }
45 std::swap(arr[left_idx], arr[right_idx]);
46 }
47
1/2
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
 38 stack.emplace_back(left_bound, right_idx);
48
1/4
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 38 stack.emplace_back(right_idx + 1, right_bound);
49 }
50 }
51
52
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 void ThreadedSort(std::vector<int> &arr, int num_threads) {
53 6 int size = static_cast<int>(arr.size());
54
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (size <= 1) {
55 4 return;
56 }
57
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
 6 int active_threads = std::min(num_threads, size / 2);
58
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
 6 if (active_threads <= 1) {
59 4 QuickSortHoare(arr, 0, size - 1);
60 4 return;
61 }
62 2 std::vector<std::thread> threads;
63 2 int chunk_size = size / active_threads;
64
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 2 times.
 10 for (int iter = 0; iter < active_threads; ++iter) {
65 8 int start = iter * chunk_size;
66
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 6 times.
 8 int end = (iter == active_threads - 1) ? size - 1 : (start + chunk_size - 1);
67
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 16 threads.emplace_back([&arr, start, end]() { QuickSortHoare(arr, start, end); });
68 }
69
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 2 times.
 10 for (auto &thr : threads) {
70
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 thr.join();
71 }
72
73
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 QuickSortHoare(arr, 0, size - 1);
74 2 }
75
76 6 void MpiCompareSwap(std::vector<int> &local_arr, int neighbor, bool keep_low) {
77 6 int size = static_cast<int>(local_arr.size());
78
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 std::vector<int> neighbor_arr(size);
79
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Sendrecv(local_arr.data(), size, MPI_INT, neighbor, 0, neighbor_arr.data(), size, MPI_INT, neighbor, 0,
80 MPI_COMM_WORLD, MPI_STATUS_IGNORE);
81
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 6 std::vector<int> full_merge(static_cast<size_t>(size) * 2);
82 6 std::ranges::merge(local_arr, neighbor_arr, full_merge.begin());
83
84
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (keep_low) {
85 3 std::copy(full_merge.begin(), full_merge.begin() + size, local_arr.begin());
86 } else {
87 3 std::copy(full_merge.begin() + size, full_merge.end(), local_arr.begin());
88 }
89 6 }
90
91 6 void BatcherExchange(std::vector<int> &local_data, int mpi_rank, int mpi_size, int p_step, int k_step) {
92
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 for (int j_idx = k_step % p_step; j_idx + k_step < mpi_size; j_idx += (k_step << 1)) {
93
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 for (int i_idx = 0; i_idx < std::min(k_step, mpi_size - j_idx - k_step); ++i_idx) {
94 6 int r1 = j_idx + i_idx;
95 6 int r2 = j_idx + i_idx + k_step;
96
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (r1 / (p_step << 1) == r2 / (p_step << 1)) {
97
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (mpi_rank == r1) {
98 3 MpiCompareSwap(local_data, r2, true);
99
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 } else if (mpi_rank == r2) {
100 3 MpiCompareSwap(local_data, r1, false);
101 }
102 }
103 }
104 }
105 6 }
106
107 6 void BatcherMergeNetwork(std::vector<int> &local_data, int mpi_rank, int mpi_size) {
108
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 for (int p_step = 1; p_step < mpi_size; p_step <<= 1) {
109
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 for (int k_step = p_step; k_step > 0; k_step >>= 1) {
110 6 BatcherExchange(local_data, mpi_rank, mpi_size, p_step, k_step);
111 }
112 }
113 6 }
114
115 } // namespace
116
117
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 HoareSortBatcherALL::HoareSortBatcherALL(const InType &in) {
118 SetTypeOfTask(GetStaticTypeOfTask());
119
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetInput() = in;
120 8 }
121
122 8 bool HoareSortBatcherALL::ValidationImpl() {
123 8 return true;
124 }
125
126 8 bool HoareSortBatcherALL::PreProcessingImpl() {
127 8 data_ = GetInput();
128 8 return true;
129 }
130
131 8 bool HoareSortBatcherALL::RunImpl() {
132 8 int mpi_rank = 0;
133 8 int mpi_size = 0;
134 8 MPI_Comm_rank(MPI_COMM_WORLD, &mpi_rank);
135 8 MPI_Comm_size(MPI_COMM_WORLD, &mpi_size);
136
137
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 int total_n = (mpi_rank == 0) ? static_cast<int>(data_.size()) : 0;
138 8 MPI_Bcast(&total_n, 1, MPI_INT, 0, MPI_COMM_WORLD);
139
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 2 times.
 8 if (total_n == 0) {
140 return true;
141 }
142
143 6 int chunk = (total_n + mpi_size - 1) / mpi_size;
144 6 std::vector<int> local_data(chunk, std::numeric_limits<int>::max());
145 6 std::vector<int> send_buffer;
146
147
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (mpi_rank == 0) {
148
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 send_buffer = data_;
149
1/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 3 send_buffer.resize(static_cast<size_t>(chunk) * mpi_size, std::numeric_limits<int>::max());
150 }
151
152
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Scatter(send_buffer.data(), chunk, MPI_INT, local_data.data(), chunk, MPI_INT, 0, MPI_COMM_WORLD);
153
154 6 int hw_threads = static_cast<int>(std::thread::hardware_concurrency());
155
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 ThreadedSort(local_data, hw_threads);
156
157
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 BatcherMergeNetwork(local_data, mpi_rank, mpi_size);
158
159 6 std::vector<int> gather_buffer;
160
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (mpi_rank == 0) {
161
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 gather_buffer.resize(static_cast<size_t>(chunk) * mpi_size);
162 }
163
164
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Gather(local_data.data(), chunk, MPI_INT, gather_buffer.data(), chunk, MPI_INT, 0, MPI_COMM_WORLD);
165
166
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (mpi_rank == 0) {
167
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 gather_buffer.resize(total_n);
168 3 data_ = std::move(gather_buffer);
169 }
170
171 return true;
172 }
173
174 8 bool HoareSortBatcherALL::PostProcessingImpl() {
175 8 int mpi_rank = 0;
176 8 MPI_Comm_rank(MPI_COMM_WORLD, &mpi_rank);
177
178
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (mpi_rank != 0) {
179 data_.clear();
180 }
181
182 8 GetOutput() = data_;
183 8 return true;
184 }
185
186 } // namespace nikitina_v_hoar_sort_batcher
187