1//----------------------------------------------------------------------------
2/// @file sample_sort.hpp
3/// @brief contains the class sample_sort
4///
5/// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
6/// Distributed under the Boost Software License, Version 1.0.\n
7/// ( See accompanying file LICENSE_1_0.txt or copy at
8/// http://www.boost.org/LICENSE_1_0.txt )
9/// @version 0.1
10///
11/// @remarks
12//-----------------------------------------------------------------------------
13#ifndef __BOOST_SORT_PARALLEL_DETAIL_SAMPLE_SORT_HPP
14#define __BOOST_SORT_PARALLEL_DETAIL_SAMPLE_SORT_HPP
15
16#include <ciso646>
17#include <functional>
18#include <future>
19#include <iterator>
20#include <memory>
21#include <type_traits>
22#include <vector>
23
24#include <algorithm>
25#include <boost/sort/spinsort/spinsort.hpp>
26#include <boost/sort/common/indirect.hpp>
27#include <boost/sort/common/util/atomic.hpp>
28#include <boost/sort/common/merge_four.hpp>
29#include <boost/sort/common/merge_vector.hpp>
30#include <boost/sort/common/range.hpp>
31
32namespace boost
33{
34namespace sort
35{
36namespace sample_detail
37{
38//---------------------------------------------------------------------------
39// USING SENTENCES
40//---------------------------------------------------------------------------
41namespace bsc = boost::sort::common;
42namespace bss = boost::sort::spin_detail;
43namespace bscu = boost::sort::common::util;
44using bsc::range;
45using bscu::atomic_add;
46using bsc::merge_vector4;
47using bsc::uninit_merge_level4;
48using bsc::less_ptr_no_null;
49
50//
51///---------------------------------------------------------------------------
52/// @struct sample_sort
53/// @brief This a structure for to implement a sample sort, exception
54/// safe
55/// @tparam
56/// @remarks
57//----------------------------------------------------------------------------
58template<class Iter_t, class Compare>
59struct sample_sort
60{
61 //------------------------------------------------------------------------
62 // DEFINITIONS
63 //------------------------------------------------------------------------
64 typedef value_iter<Iter_t> value_t;
65 typedef range<Iter_t> range_it;
66 typedef range<value_t *> range_buf;
67 typedef sample_sort<Iter_t, Compare> this_t;
68
69 //------------------------------------------------------------------------
70 // VARIABLES AND CONSTANTS
71 //------------------------------------------------------------------------
72 // minimun numbers of elements for to be sortd in parallel mode
73 static const uint32_t thread_min = (1 << 16);
74
75 // Number of threads to use in the algorithm
76 // Number of intervals for to do the internal division of the data
77 uint32_t nthread, ninterval;
78
79 // Bool variables indicating if the auxiliary memory is constructed
80 // and indicating in the auxiliary memory had been obtained inside the
81 /// algorithm or had been received as a parameter
82 bool construct = false, owner = false;
83
84 // Comparison object for to compare two elements
85 Compare comp;
86
87 // Range with all the elements to sort
88 range_it global_range;
89
90 // range with the auxiliary memory
91 range_buf global_buf;
92
93 // vector of futures
94 std::vector<std::future<void>> vfuture;
95
96 // vector of vectors which contains the ranges to merge obtained in the
97 // subdivision
98 std::vector<std::vector<range_it>> vv_range_it;
99
100 // each vector of ranges of the vv_range_it, need their corresponding buffer
101 // for to do the merge
102 std::vector<std::vector<range_buf>> vv_range_buf;
103
104 // Initial vector of ranges
105 std::vector<range_it> vrange_it_ini;
106
107 // Initial vector of buffers
108 std::vector<range_buf> vrange_buf_ini;
109
110 // atomic counter for to know when are finished the function_t created
111 // inside a function
112 std::atomic<uint32_t> njob;
113
114 // Indicate if an error in the algorithm for to undo all
115 bool error;
116
117 //------------------------------------------------------------------------
118 // FUNCTIONS OF THE STRUCT
119 //------------------------------------------------------------------------
120 void initial_configuration(void);
121
122 sample_sort (Iter_t first, Iter_t last, Compare cmp, uint32_t num_thread,
123 value_t *paux, size_t naux);
124
125 sample_sort(Iter_t first, Iter_t last)
126 : sample_sort (first, last, Compare(), std::thread::hardware_concurrency(),
127 nullptr, 0) { };
128
129 sample_sort(Iter_t first, Iter_t last, Compare cmp)
130 : sample_sort(first, last, cmp, std::thread::hardware_concurrency(),
131 nullptr, 0) { };
132
133 sample_sort(Iter_t first, Iter_t last, uint32_t num_thread)
134 : sample_sort(first, last, Compare(), num_thread, nullptr, 0) { };
135
136 sample_sort(Iter_t first, Iter_t last, Compare cmp, uint32_t num_thread)
137 : sample_sort(first, last, cmp, num_thread, nullptr, 0) { };
138
139 sample_sort(Iter_t first, Iter_t last, Compare cmp, uint32_t num_thread,
140 range_buf range_buf_initial)
141 : sample_sort(first, last, cmp, num_thread,
142 range_buf_initial.first, range_buf_initial.size()) { };
143
144 void destroy_all(void);
145 //
146 //-----------------------------------------------------------------------------
147 // function :~sample_sort
148 /// @brief destructor of the class. The utility is to destroy the temporary
149 /// buffer used in the sorting process
150 //-----------------------------------------------------------------------------
151 ~sample_sort(void) { destroy_all(); };
152 //
153 //-----------------------------------------------------------------------
154 // function : execute first
155 /// @brief this a function to assign to each thread in the first merge
156 //-----------------------------------------------------------------------
157 void execute_first(void)
158 {
159 uint32_t job = 0;
160 while ((job = atomic_add(at_var&: njob, num: 1)) < ninterval)
161 {
162 uninit_merge_level4(vrange_buf_ini[job], vv_range_it[job],
163 vv_range_buf[job], comp);
164 };
165 };
166 //
167 //-----------------------------------------------------------------------
168 // function : execute
169 /// @brief this is a function to assignt each thread the final merge
170 //-----------------------------------------------------------------------
171 void execute(void)
172 {
173 uint32_t job = 0;
174 while ((job = atomic_add(at_var&: njob, num: 1)) < ninterval)
175 {
176 merge_vector4(vrange_buf_ini[job], vrange_it_ini[job],
177 vv_range_buf[job], vv_range_it[job], comp);
178 };
179 };
180 //
181 //-----------------------------------------------------------------------
182 // function : first merge
183 /// @brief Implement the merge of the initially sparse ranges
184 //-----------------------------------------------------------------------
185 void first_merge(void)
186 { //---------------------------------- begin --------------------------
187 njob = 0;
188
189 for (uint32_t i = 0; i < nthread; ++i)
190 {
191 vfuture[i] = std::async(std::launch::async, &this_t::execute_first,
192 this);
193 };
194 for (uint32_t i = 0; i < nthread; ++i)
195 vfuture[i].get();
196 };
197 //
198 //-----------------------------------------------------------------------
199 // function : final merge
200 /// @brief Implement the final merge of the ranges
201 //-----------------------------------------------------------------------
202 void final_merge(void)
203 { //---------------------------------- begin --------------------------
204 njob = 0;
205
206 for (uint32_t i = 0; i < nthread; ++i)
207 {
208 vfuture[i] = std::async(std::launch::async, &this_t::execute, this);
209 };
210 for (uint32_t i = 0; i < nthread; ++i)
211 vfuture[i].get();
212 };
213 //----------------------------------------------------------------------------
214};
215// End class sample_sort
216//----------------------------------------------------------------------------
217//
218//############################################################################
219// ##
220// N O N I N L I N E F U N C T I O N S ##
221// ##
222// ##
223//############################################################################
224//
225//-----------------------------------------------------------------------------
226// function : sample_sort
227/// @brief constructor of the class
228///
229/// @param first : iterator to the first element of the range to sort
230/// @param last : iterator after the last element to the range to sort
231/// @param cmp : object for to compare two elements pointed by Iter_t iterators
232/// @param num_thread : Number of threads to use in the process. When this value
233/// is lower than 2, the sorting is done with 1 thread
234/// @param paux : pointer to the auxiliary memory. If nullptr, the memory is
235/// created inside the class
236/// @param naux : number of elements of the memory pointed by paux
237//-----------------------------------------------------------------------------
238template<class Iter_t, typename Compare>
239sample_sort<Iter_t, Compare>
240::sample_sort (Iter_t first, Iter_t last, Compare cmp, uint32_t num_thread,
241 value_t *paux, size_t naux)
242: nthread(num_thread), owner(false), comp(cmp), global_range(first, last),
243 global_buf(nullptr, nullptr), error(false)
244{
245 assert((last - first) >= 0);
246 size_t nelem = size_t(last - first);
247 construct = false;
248 njob = 0;
249 vfuture.resize(new_size: nthread);
250
251 // Adjust when have many threads and only a few elements
252 while (nelem > thread_min and (nthread * nthread) > (nelem >> 3))
253 {
254 nthread /= 2;
255 };
256 ninterval = (nthread << 3);
257
258 if (nthread < 2 or nelem <= (thread_min))
259 {
260 bss::spinsort<Iter_t, Compare>(first, last, comp);
261 return;
262 };
263
264 //------------------- check if sort --------------------------------------
265 bool sw = true;
266 for (Iter_t it1 = first, it2 = first + 1;
267 it2 != last and (sw = not comp(*it2, *it1)); it1 = it2++);
268 if (sw) return;
269
270 //------------------- check if reverse sort ---------------------------
271 sw = true;
272 for (Iter_t it1 = first, it2 = first + 1;
273 it2 != last and (sw = comp(*it2, *it1)); it1 = it2++);
274 if (sw)
275 {
276 using std::swap;
277 size_t nelem2 = nelem >> 1;
278 Iter_t it1 = first, it2 = last - 1;
279 for (size_t i = 0; i < nelem2; ++i)
280 swap(*(it1++), *(it2--));
281 return;
282 };
283
284 if (paux != nullptr)
285 {
286 assert(naux != 0);
287 global_buf.first = paux;
288 global_buf.last = paux + naux;
289 owner = false;
290 }
291 else
292 {
293 value_t * ptr = reinterpret_cast <value_t*>
294 (std::malloc (size: nelem * sizeof(value_t)));
295
296 if (ptr == nullptr) throw std::bad_alloc();
297 owner = true;
298 global_buf = range_buf(ptr, ptr + nelem);
299 };
300 //------------------------------------------------------------------------
301 // PROCESS
302 //------------------------------------------------------------------------
303 try
304 {
305 initial_configuration();
306 } catch (std::bad_alloc &)
307 {
308 error = true;
309 };
310 if (not error)
311 {
312 first_merge();
313 construct = true;
314 final_merge();
315 };
316 if (error)
317 {
318 destroy_all();
319 throw std::bad_alloc();
320 };
321}
322;
323//
324//-----------------------------------------------------------------------------
325// function : destroy_all
326/// @brief destructor of the class. The utility is to destroy the temporary
327/// buffer used in the sorting process
328//-----------------------------------------------------------------------------
329template<class Iter_t, typename Compare>
330void sample_sort<Iter_t, Compare>::destroy_all(void)
331{
332 if (construct)
333 {
334 destroy(global_buf);
335 construct = false;
336 }
337 if (global_buf.first != nullptr and owner)
338 std::free(ptr: global_buf.first);
339}
340//
341//-----------------------------------------------------------------------------
342// function : initial_configuration
343/// @brief Create the internal data structures, and obtain the inital set of
344/// ranges to merge
345//-----------------------------------------------------------------------------
346template<class Iter_t, typename Compare>
347void sample_sort<Iter_t, Compare>::initial_configuration(void)
348{
349 std::vector<range_it> vmem_thread;
350 std::vector<range_buf> vbuf_thread;
351 size_t nelem = global_range.size();
352
353 //------------------------------------------------------------------------
354 size_t cupo = nelem / nthread;
355 Iter_t it_first = global_range.first;
356 value_t *buf_first = global_buf.first;
357 vmem_thread.reserve(nthread + 1);
358 vbuf_thread.reserve(nthread + 1);
359
360 for (uint32_t i = 0; i < (nthread - 1); ++i, it_first += cupo, buf_first +=
361 cupo)
362 {
363 vmem_thread.emplace_back(it_first, it_first + cupo);
364 vbuf_thread.emplace_back(buf_first, buf_first + cupo);
365 };
366
367 vmem_thread.emplace_back(it_first, global_range.last);
368 vbuf_thread.emplace_back(buf_first, global_buf.last);
369
370 //------------------------------------------------------------------------
371 // Sorting of the ranges
372 //------------------------------------------------------------------------
373 std::vector<std::future<void>> vfuture(nthread);
374
375 for (uint32_t i = 0; i < nthread; ++i)
376 {
377 auto func = [this, &vmem_thread, i, &vbuf_thread]()
378 {
379 bss::spinsort<Iter_t, Compare> (vmem_thread[i].first,
380 vmem_thread[i].last, this->comp,
381 vbuf_thread[i]);
382 };
383 vfuture[i] = std::async(std::launch::async, func);
384 };
385
386 for (uint32_t i = 0; i < nthread; ++i)
387 vfuture[i].get();
388
389 //------------------------------------------------------------------------
390 // Obtain the vector of milestones
391 //------------------------------------------------------------------------
392 std::vector<Iter_t> vsample;
393 vsample.reserve(nthread * (ninterval - 1));
394
395 for (uint32_t i = 0; i < nthread; ++i)
396 {
397 size_t distance = vmem_thread[i].size() / ninterval;
398 for (size_t j = 1, pos = distance; j < ninterval; ++j, pos += distance)
399 {
400 vsample.push_back(vmem_thread[i].first + pos);
401 };
402 };
403 typedef less_ptr_no_null<Iter_t, Compare> compare_ptr;
404 typedef typename std::vector<Iter_t>::iterator it_to_it;
405
406 bss::spinsort<it_to_it, compare_ptr>(vsample.begin(), vsample.end(),
407 compare_ptr(comp));
408
409 //------------------------------------------------------------------------
410 // Create the final milestone vector
411 //------------------------------------------------------------------------
412 std::vector<Iter_t> vmilestone;
413 vmilestone.reserve(ninterval);
414
415 for (uint32_t pos = nthread >> 1; pos < vsample.size(); pos += nthread)
416 {
417 vmilestone.push_back(vsample[pos]);
418 };
419
420 //------------------------------------------------------------------------
421 // Creation of the first vector of ranges
422 //------------------------------------------------------------------------
423 std::vector<std::vector<range<Iter_t>>>vv_range_first (nthread);
424
425 for (uint32_t i = 0; i < nthread; ++i)
426 {
427 Iter_t itaux = vmem_thread[i].first;
428
429 for (uint32_t k = 0; k < (ninterval - 1); ++k)
430 {
431 Iter_t it2 = std::upper_bound(itaux, vmem_thread[i].last,
432 *vmilestone[k], comp);
433
434 vv_range_first[i].emplace_back(itaux, it2);
435 itaux = it2;
436 };
437 vv_range_first[i].emplace_back(itaux, vmem_thread[i].last);
438 };
439
440 //------------------------------------------------------------------------
441 // Copy in buffer and creation of the final matrix of ranges
442 //------------------------------------------------------------------------
443 vv_range_it.resize(ninterval);
444 vv_range_buf.resize(ninterval);
445 vrange_it_ini.reserve(ninterval);
446 vrange_buf_ini.reserve(ninterval);
447
448 for (uint32_t i = 0; i < ninterval; ++i)
449 {
450 vv_range_it[i].reserve(nthread);
451 vv_range_buf[i].reserve(nthread);
452 };
453
454 Iter_t it = global_range.first;
455 value_t *it_buf = global_buf.first;
456
457 for (uint32_t k = 0; k < ninterval; ++k)
458 {
459 size_t nelem_interval = 0;
460
461 for (uint32_t i = 0; i < nthread; ++i)
462 {
463 size_t nelem_range = vv_range_first[i][k].size();
464 if (nelem_range != 0)
465 {
466 vv_range_it[k].push_back(vv_range_first[i][k]);
467 };
468 nelem_interval += nelem_range;
469 };
470
471 vrange_it_ini.emplace_back(it, it + nelem_interval);
472 vrange_buf_ini.emplace_back(it_buf, it_buf + nelem_interval);
473
474 it += nelem_interval;
475 it_buf += nelem_interval;
476 };
477}
478;
479//
480//****************************************************************************
481}
482;
483// End namespace sample_detail
484//****************************************************************************
485//
486namespace bscu = boost::sort::common::util;
487//
488//############################################################################
489// ##
490// ##
491// S A M P L E _ S O R T ##
492// ##
493// ##
494//############################################################################
495//
496//-----------------------------------------------------------------------------
497// function : sample_sort
498/// @brief parallel sample sort algorithm (stable sort)
499///
500/// @param first : iterator to the first element of the range to sort
501/// @param last : iterator after the last element to the range to sort
502//-----------------------------------------------------------------------------
503template<class Iter_t>
504void sample_sort(Iter_t first, Iter_t last)
505{
506 typedef compare_iter<Iter_t> Compare;
507 sample_detail::sample_sort<Iter_t, Compare>(first, last);
508};
509//
510//-----------------------------------------------------------------------------
511// function : sample_sort
512/// @brief parallel sample sort algorithm (stable sort)
513///
514/// @param first : iterator to the first element of the range to sort
515/// @param last : iterator after the last element to the range to sort
516/// @param nthread : Number of threads to use in the process. When this value
517/// is lower than 2, the sorting is done with 1 thread
518//-----------------------------------------------------------------------------
519template<class Iter_t>
520void sample_sort(Iter_t first, Iter_t last, uint32_t nthread)
521{
522 typedef compare_iter<Iter_t> Compare;
523 sample_detail::sample_sort<Iter_t, Compare>(first, last, nthread);
524};
525//
526//-----------------------------------------------------------------------------
527// function : sample_sort
528/// @brief parallel sample sort algorithm (stable sort)
529///
530/// @param first : iterator to the first element of the range to sort
531/// @param last : iterator after the last element to the range to sort
532/// @param comp : object for to compare two elements pointed by Iter_t
533/// iterators
534//-----------------------------------------------------------------------------
535template<class Iter_t, class Compare, bscu::enable_if_not_integral<Compare> * =
536 nullptr>
537void sample_sort(Iter_t first, Iter_t last, Compare comp)
538{
539 sample_detail::sample_sort<Iter_t, Compare>(first, last, comp);
540};
541//
542//-----------------------------------------------------------------------------
543// function : sample_sort
544/// @brief parallel sample sort algorithm (stable sort)
545///
546/// @param first : iterator to the first element of the range to sort
547/// @param last : iterator after the last element to the range to sort
548/// @param comp : object for to compare two elements pointed by Iter_t
549/// iterators
550/// @param nthread : Number of threads to use in the process. When this value
551/// is lower than 2, the sorting is done with 1 thread
552//-----------------------------------------------------------------------------
553template<class Iter_t, class Compare>
554void sample_sort(Iter_t first, Iter_t last, Compare comp, uint32_t nthread)
555{
556 sample_detail::sample_sort<Iter_t, Compare>(first, last, comp, nthread);
557};
558//
559//****************************************************************************
560};// End namespace sort
561};// End namespace boost
562//****************************************************************************
563//
564#endif
565

source code of boost/libs/sort/include/boost/sort/sample_sort/sample_sort.hpp