|
1
|
1 #include "foobar2000-sdk-pch.h"
|
|
|
2 #include "foosort.h"
|
|
|
3 #include "threadPool.h"
|
|
|
4 #include "genrand.h"
|
|
|
5
|
|
|
6 #define FOOSORT_PROFILING 0
|
|
|
7
|
|
|
8 namespace {
|
|
|
9 #if FOOSORT_PROFILING
|
|
|
10 typedef pfc::hires_timer foosort_timer;
|
|
|
11 #endif
|
|
|
12
|
|
|
13 class foosort {
|
|
|
14 public:
|
|
|
15 foosort(pfc::sort_callback & cb, abort_callback & a) : m_abort(a), p_callback(cb) {}
|
|
|
16
|
|
|
17 foosort fork() {
|
|
|
18 foosort ret ( * this );
|
|
|
19 ret.genrand = genrand_service::g_create();
|
|
|
20 return ret;
|
|
|
21 }
|
|
|
22
|
|
|
23 size_t myrand(size_t cnt) {
|
|
|
24 PFC_ASSERT(cnt == (uint32_t)cnt);
|
|
|
25 return genrand->genrand((uint32_t)cnt);
|
|
|
26 }
|
|
|
27
|
|
|
28 void squaresort(t_size const p_base, t_size const p_count) {
|
|
|
29 const t_size max = p_base + p_count;
|
|
|
30 for (t_size walk = p_base + 1; walk < max; ++walk) {
|
|
|
31 for (t_size prev = p_base; prev < walk; ++prev) {
|
|
|
32 p_callback.swap_check(prev, walk);
|
|
|
33 }
|
|
|
34 }
|
|
|
35 }
|
|
|
36
|
|
|
37
|
|
|
38 void _sort_2elem_helper(t_size & p_elem1, t_size & p_elem2) {
|
|
|
39 if (p_callback.compare(p_elem1, p_elem2) > 0) pfc::swap_t(p_elem1, p_elem2);
|
|
|
40 }
|
|
|
41
|
|
|
42 t_size _pivot_helper(t_size const p_base, t_size const p_count) {
|
|
|
43 PFC_ASSERT(p_count > 2);
|
|
|
44
|
|
|
45 //t_size val1 = p_base, val2 = p_base + (p_count / 2), val3 = p_base + (p_count - 1);
|
|
|
46
|
|
|
47 t_size val1 = myrand(p_count), val2 = myrand(p_count - 1), val3 = myrand(p_count - 2);
|
|
|
48 if (val2 >= val1) val2++;
|
|
|
49 if (val3 >= val1) val3++;
|
|
|
50 if (val3 >= val2) val3++;
|
|
|
51
|
|
|
52 val1 += p_base; val2 += p_base; val3 += p_base;
|
|
|
53
|
|
|
54 _sort_2elem_helper(val1, val2);
|
|
|
55 _sort_2elem_helper(val1, val3);
|
|
|
56 _sort_2elem_helper(val2, val3);
|
|
|
57
|
|
|
58 return val2;
|
|
|
59 }
|
|
|
60
|
|
|
61 void newsort(t_size const p_base, t_size const p_count, size_t concurrency) {
|
|
|
62 if (p_count <= 4) {
|
|
|
63 squaresort(p_base, p_count);
|
|
|
64 return;
|
|
|
65 }
|
|
|
66
|
|
|
67 this->m_abort.check();
|
|
|
68 #if FOOSORT_PROFILING
|
|
|
69 foosort_timer t;
|
|
|
70 if ( concurrency > 1 ) t.start();
|
|
|
71 #endif
|
|
|
72
|
|
|
73 t_size pivot = _pivot_helper(p_base, p_count);
|
|
|
74
|
|
|
75 {
|
|
|
76 const t_size target = p_base + p_count - 1;
|
|
|
77 if (pivot != target) {
|
|
|
78 p_callback.swap(pivot, target); pivot = target;
|
|
|
79 }
|
|
|
80 }
|
|
|
81
|
|
|
82
|
|
|
83 t_size partition = p_base;
|
|
|
84 {
|
|
|
85 bool asdf = false;
|
|
|
86 for (t_size walk = p_base; walk < pivot; ++walk) {
|
|
|
87 const int comp = p_callback.compare(walk, pivot);
|
|
|
88 bool trigger = false;
|
|
|
89 if (comp == 0) {
|
|
|
90 trigger = asdf;
|
|
|
91 asdf = !asdf;
|
|
|
92 } else if (comp < 0) {
|
|
|
93 trigger = true;
|
|
|
94 }
|
|
|
95 if (trigger) {
|
|
|
96 if (partition != walk) p_callback.swap(partition, walk);
|
|
|
97 partition++;
|
|
|
98 }
|
|
|
99 }
|
|
|
100 }
|
|
|
101 if (pivot != partition) {
|
|
|
102 p_callback.swap(pivot, partition); pivot = partition;
|
|
|
103 }
|
|
|
104
|
|
|
105 const auto base1 = p_base, count1 = pivot - p_base;
|
|
|
106 const auto base2 = pivot + 1, count2 = p_count - (pivot + 1 - p_base);
|
|
|
107
|
|
|
108 if (concurrency > 1) {
|
|
|
109
|
|
|
110 size_t total = count1 + count2;
|
|
|
111 size_t con1 = (size_t)((uint64_t)count1 * (uint64_t)concurrency / (uint64_t)total);
|
|
|
112 if (con1 < 1) con1 = 1;
|
|
|
113 if (con1 > concurrency - 1) con1 = concurrency - 1;
|
|
|
114 size_t con2 = concurrency - con1;
|
|
|
115
|
|
|
116 #if FOOSORT_PROFILING
|
|
|
117 FB2K_console_formatter() << "foosort pass: " << p_base << "+" << p_count << "(" << concurrency << ") took " << t.queryString();
|
|
|
118 FB2K_console_formatter() << "foosort forking: " << base1 << "+" << count1 << "(" << con1 << ") + " << base2 << "+" << count2 << "(" << con2 << ")";
|
|
|
119 #endif
|
|
|
120 pfc::counter cnt;
|
|
|
121 fb2k::cpuThreadPool::runMultiHelper([&] {
|
|
|
122 try {
|
|
|
123 switch (cnt++) {
|
|
|
124 case 0:
|
|
|
125 { foosort subsort = fork(); subsort.newsort(base1, count1, con1); }
|
|
|
126 break;
|
|
|
127 case 1:
|
|
|
128 newsort(base2, count2, con2);
|
|
|
129 break;
|
|
|
130 }
|
|
|
131 } catch (exception_aborted const &) {}
|
|
|
132 }, 2);
|
|
|
133 m_abort.check();
|
|
|
134 } else {
|
|
|
135 newsort(base1, count1, 1);
|
|
|
136 newsort(base2, count2, 1);
|
|
|
137 }
|
|
|
138 }
|
|
|
139 private:
|
|
|
140 abort_callback & m_abort;
|
|
|
141 pfc::sort_callback & p_callback;
|
|
|
142 genrand_service::ptr genrand = genrand_service::g_create();
|
|
|
143 };
|
|
|
144
|
|
|
145
|
|
|
146
|
|
|
147 }
|
|
|
148 namespace fb2k {
|
|
|
149 void sort(pfc::sort_callback & cb, size_t count, size_t concurrency, abort_callback & aborter) {
|
|
|
150 #ifdef FOOSORT_LIMIT_THREADS
|
|
|
151 if (concurrency > FOOSORT_LIMIT_THREADS) concurrency = FOOSORT_LIMIT_THREADS;
|
|
|
152 #endif
|
|
|
153 #if FOOSORT_PROFILING
|
|
|
154 foosort_timer t; t.start();
|
|
|
155 #endif
|
|
|
156 foosort theFooSort(cb, aborter);
|
|
|
157 theFooSort.newsort(0, count, concurrency);
|
|
|
158 #if FOOSORT_PROFILING
|
|
|
159 FB2K_console_formatter() << "foosort took: " << t.queryString();
|
|
|
160 #endif
|
|
|
161 }
|
|
|
162 }
|
