| 89 | // Apply the sorting with qsort based algorithm. |
| 90 | template <typename T, class Compare> |
| 91 | void QSort(std::vector<T>& x, const Compare& comp) { |
| 92 | if (x.size() <= 1) return; |
| 93 | if (nthreads_ <= 1 || threadpool_ == nullptr) { |
| 94 | std::sort(x.begin(), x.end(), comp); |
| 95 | return; |
| 96 | } |
| 97 | |
| 98 | #define HALF_L1_CACHE_SIZE 16384 |
| 99 | const int block_size = HALF_L1_CACHE_SIZE / sizeof(T); |
| 100 | const int block_count = divup(x.size(), block_size); |
| 101 | #undef HALF_L1_CACHE_SIZE |
| 102 | BlockingCounter counter(block_count); |
| 103 | std::function<void(int, int)> SortRange; |
| 104 | SortRange = [this, &x, &comp, block_size, &counter, &SortRange](int first, |
| 105 | int last) { |
| 106 | VLOG(2) << "[Parallel QSort] Sorting " << first << " to " << last; |
| 107 | // Single block or less, execute directly. |
| 108 | if (last - first <= block_size) { |
| 109 | std::sort(x.begin() + first, x.begin() + last, comp); |
| 110 | counter.DecrementCount(); |
| 111 | return; |
| 112 | } |
| 113 | // Split into blocs and submit to the pool. |
| 114 | int mid = first + divup((last - first) / 2, block_size) * block_size; |
| 115 | DivideAtPos(x, comp, first, last, mid); |
| 116 | threadpool_->Schedule([=, &SortRange]() { SortRange(mid, last); }); |
| 117 | SortRange(first, mid); |
| 118 | }; |
| 119 | SortRange(0, x.size()); |
| 120 | counter.Wait(); |
| 121 | } |
| 122 | |
| 123 | private: |
| 124 | int nthreads_; |