1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
3 //
4 // Distributed under the Boost Software License, Version 1.0
5 // See accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt
7 //
8 // See http://boostorg.github.com/compute for more information.
9 //---------------------------------------------------------------------------//
10
11 #define BOOST_TEST_MODULE TestRadixSort
12 #include <boost/test/unit_test.hpp>
13
14 #include <iostream>
15
16 #include <boost/compute/system.hpp>
17 #include <boost/compute/algorithm/is_sorted.hpp>
18 #include <boost/compute/algorithm/detail/radix_sort.hpp>
19 #include <boost/compute/container/vector.hpp>
20
21 #include "quirks.hpp"
22 #include "check_macros.hpp"
23 #include "context_setup.hpp"
24
25 namespace bc = boost::compute;
26
27 const bool descending = false;
28
BOOST_AUTO_TEST_CASE(sort_char_vector)29 BOOST_AUTO_TEST_CASE(sort_char_vector)
30 {
31 if(is_apple_cpu_device(device)) {
32 std::cerr
33 << "skipping all radix_sort tests due to Apple platform"
34 << " behavior when local memory is used on a CPU device"
35 << std::endl;
36 return;
37 }
38
39 using boost::compute::char_;
40
41 char_ data[] = { 'c', 'a', '0', '7', 'B', 'F', '\0', '$' };
42 boost::compute::vector<char_> vector(data, data + 8, queue);
43 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
44 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
45
46 boost::compute::detail::radix_sort(vector.begin(), vector.end(), queue);
47 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
48 CHECK_RANGE_EQUAL(char_, 8, vector, ('\0', '$', '0', '7', 'B', 'F', 'a', 'c'));
49 }
50
BOOST_AUTO_TEST_CASE(sort_uchar_vector)51 BOOST_AUTO_TEST_CASE(sort_uchar_vector)
52 {
53 if(is_apple_cpu_device(device)) {
54 return;
55 }
56
57 using boost::compute::uchar_;
58
59 uchar_ data[] = { 0x12, 0x00, 0xFF, 0xB4, 0x80, 0x32, 0x64, 0xA2 };
60 boost::compute::vector<uchar_> vector(data, data + 8, queue);
61 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
62 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
63
64 boost::compute::detail::radix_sort(vector.begin(), vector.end(), queue);
65 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
66 CHECK_RANGE_EQUAL(uchar_, 8, vector, (0x00, 0x12, 0x32, 0x64, 0x80, 0xA2, 0xB4, 0xFF));
67 }
68
BOOST_AUTO_TEST_CASE(sort_short_vector)69 BOOST_AUTO_TEST_CASE(sort_short_vector)
70 {
71 if(is_apple_cpu_device(device)) {
72 return;
73 }
74
75 using boost::compute::short_;
76
77 short_ data[] = { -4, 152, -94, 963, 31002, -456, 0, -2113 };
78 boost::compute::vector<short_> vector(data, data + 8, queue);
79 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
80 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
81
82 boost::compute::detail::radix_sort(vector.begin(), vector.end(), queue);
83 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
84 CHECK_RANGE_EQUAL(short_, 8, vector, (-2113, -456, -94, -4, 0, 152, 963, 31002));
85 }
86
BOOST_AUTO_TEST_CASE(sort_ushort_vector)87 BOOST_AUTO_TEST_CASE(sort_ushort_vector)
88 {
89 if(is_apple_cpu_device(device)) {
90 return;
91 }
92
93 using boost::compute::ushort_;
94
95 ushort_ data[] = { 4, 152, 94, 963, 63202, 34560, 0, 2113 };
96 boost::compute::vector<ushort_> vector(data, data + 8, queue);
97 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
98 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
99
100 boost::compute::detail::radix_sort(vector.begin(), vector.end(), queue);
101 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
102 CHECK_RANGE_EQUAL(ushort_, 8, vector, (0, 4, 94, 152, 963, 2113, 34560, 63202));
103 }
104
BOOST_AUTO_TEST_CASE(sort_int_vector)105 BOOST_AUTO_TEST_CASE(sort_int_vector)
106 {
107 if(is_apple_cpu_device(device)) {
108 return;
109 }
110
111 int data[] = { -4, 152, -5000, 963, 75321, -456, 0, 1112 };
112 boost::compute::vector<int> vector(data, data + 8, queue);
113 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
114 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
115
116 boost::compute::detail::radix_sort(vector.begin(), vector.end(), queue);
117 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
118 CHECK_RANGE_EQUAL(int, 8, vector, (-5000, -456, -4, 0, 152, 963, 1112, 75321));
119 }
120
BOOST_AUTO_TEST_CASE(sort_uint_vector)121 BOOST_AUTO_TEST_CASE(sort_uint_vector)
122 {
123 if(is_apple_cpu_device(device)) {
124 return;
125 }
126
127 using boost::compute::uint_;
128
129 uint_ data[] = { 500, 1988, 123456, 562, 0, 4000000, 9852, 102030 };
130 boost::compute::vector<uint_> vector(data, data + 8, queue);
131 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
132 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
133
134 boost::compute::detail::radix_sort(vector.begin(), vector.end(), queue);
135 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
136 CHECK_RANGE_EQUAL(uint_, 8, vector, (0, 500, 562, 1988, 9852, 102030, 123456, 4000000));
137 }
138
BOOST_AUTO_TEST_CASE(sort_long_vector)139 BOOST_AUTO_TEST_CASE(sort_long_vector)
140 {
141 if(is_apple_cpu_device(device)) {
142 return;
143 }
144
145 using boost::compute::long_;
146
147 long_ data[] = { 500, 1988, 123456, 562, 0, 4000000, 9852, 102030 };
148 boost::compute::vector<long_> vector(data, data + 8, queue);
149 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
150 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
151
152 boost::compute::detail::radix_sort(vector.begin(), vector.end(), queue);
153 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
154 CHECK_RANGE_EQUAL(long_, 8, vector, (0, 500, 562, 1988, 9852, 102030, 123456, 4000000));
155 }
156
BOOST_AUTO_TEST_CASE(sort_ulong_vector)157 BOOST_AUTO_TEST_CASE(sort_ulong_vector)
158 {
159 if(is_apple_cpu_device(device)) {
160 return;
161 }
162
163 using boost::compute::ulong_;
164
165 ulong_ data[] = { 500, 1988, 123456, 562, 0, 4000000, 9852, 102030 };
166 boost::compute::vector<ulong_> vector(data, data + 8, queue);
167 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
168 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
169
170 boost::compute::detail::radix_sort(vector.begin(), vector.end(), queue);
171 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
172 CHECK_RANGE_EQUAL(ulong_, 8, vector, (0, 500, 562, 1988, 9852, 102030, 123456, 4000000));
173 }
174
BOOST_AUTO_TEST_CASE(sort_float_vector)175 BOOST_AUTO_TEST_CASE(sort_float_vector)
176 {
177 if(is_apple_cpu_device(device)) {
178 return;
179 }
180
181 float data[] = { -6023.0f, 152.5f, -63.0f, 1234567.0f, 11.2f,
182 -5000.1f, 0.0f, 14.0f, -8.25f, -0.0f };
183 boost::compute::vector<float> vector(data, data + 10, queue);
184 BOOST_CHECK_EQUAL(vector.size(), size_t(10));
185 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
186
187 boost::compute::detail::radix_sort(vector.begin(), vector.end(), queue);
188 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
189 CHECK_RANGE_EQUAL(
190 float, 10, vector,
191 (-6023.0f, -5000.1f, -63.0f, -8.25f, -0.0f, 0.0f, 11.2f, 14.0f, 152.5f, 1234567.0f)
192 );
193
194 // copy data, sort, and check again (to check program caching)
195 boost::compute::copy(data, data + 10, vector.begin(), queue);
196 boost::compute::detail::radix_sort(vector.begin(), vector.end(), queue);
197 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
198 CHECK_RANGE_EQUAL(
199 float, 10, vector,
200 (-6023.0f, -5000.1f, -63.0f, -8.25f, -0.0f, 0.0f, 11.2f, 14.0f, 152.5f, 1234567.0f)
201 );
202 }
203
BOOST_AUTO_TEST_CASE(sort_double_vector)204 BOOST_AUTO_TEST_CASE(sort_double_vector)
205 {
206 if(is_apple_cpu_device(device)) {
207 return;
208 }
209
210 if(!device.supports_extension("cl_khr_fp64")){
211 std::cout << "skipping test: device does not support double" << std::endl;
212 return;
213 }
214
215 double data[] = { -6023.0, 152.5, -63.0, 1234567.0, 11.2,
216 -5000.1, 0.0, 14.0, -8.25, -0.0 };
217 boost::compute::vector<double> vector(data, data + 10, queue);
218 BOOST_CHECK_EQUAL(vector.size(), size_t(10));
219 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
220
221 boost::compute::detail::radix_sort(vector.begin(), vector.end(), queue);
222 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
223 CHECK_RANGE_EQUAL(
224 double, 10, vector,
225 (-6023.0, -5000.1, -63.0, -8.25, -0.0, 0.0, 11.2, 14.0, 152.5, 1234567.0)
226 );
227 }
228
BOOST_AUTO_TEST_CASE(sort_char_vector_desc)229 BOOST_AUTO_TEST_CASE(sort_char_vector_desc)
230 {
231 if(is_apple_cpu_device(device)) {
232 return;
233 }
234
235 using boost::compute::char_;
236
237 char_ data[] = { 'c', 'a', '0', '7', 'B', 'F', '\0', '$' };
238 boost::compute::vector<char_> vector(data, data + 8, queue);
239 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
240
241 BOOST_CHECK(!boost::compute::is_sorted(
242 vector.begin(), vector.end(), boost::compute::greater<char_>(), queue
243 ));
244 boost::compute::detail::radix_sort(
245 vector.begin(), vector.end(), descending, queue
246 );
247 BOOST_CHECK(boost::compute::is_sorted(
248 vector.begin(), vector.end(), boost::compute::greater<char_>(), queue
249 ));
250
251 CHECK_RANGE_EQUAL(
252 char_, 8, vector,
253 ('c', 'a', 'F', 'B', '7', '0', '$', '\0')
254 );
255 }
256
BOOST_AUTO_TEST_CASE(sort_uchar_vector_desc)257 BOOST_AUTO_TEST_CASE(sort_uchar_vector_desc)
258 {
259 if(is_apple_cpu_device(device)) {
260 return;
261 }
262
263 using boost::compute::uchar_;
264
265 uchar_ data[] = { 0x12, 0x00, 0xFF, 0xB4, 0x80, 0x32, 0x64, 0xA2 };
266 boost::compute::vector<uchar_> vector(data, data + 8, queue);
267 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
268
269 BOOST_CHECK(!boost::compute::is_sorted(
270 vector.begin(), vector.end(), boost::compute::greater<uchar_>(), queue
271 ));
272 boost::compute::detail::radix_sort(
273 vector.begin(), vector.end(), descending, queue
274 );
275 BOOST_CHECK(boost::compute::is_sorted(
276 vector.begin(), vector.end(), boost::compute::greater<uchar_>(), queue
277 ));
278
279 CHECK_RANGE_EQUAL(
280 uchar_, 8, vector,
281 (0xFF, 0xB4, 0xA2, 0x80, 0x64, 0x32, 0x12, 0x00)
282 );
283 }
284
BOOST_AUTO_TEST_CASE(sort_short_vector_desc)285 BOOST_AUTO_TEST_CASE(sort_short_vector_desc)
286 {
287 if(is_apple_cpu_device(device)) {
288 return;
289 }
290
291 using boost::compute::short_;
292
293 short_ data[] = { -4, 152, -94, 963, 31002, -456, 0, -2113 };
294 boost::compute::vector<short_> vector(data, data + 8, queue);
295 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
296
297 BOOST_CHECK(!boost::compute::is_sorted(
298 vector.begin(), vector.end(), boost::compute::greater<short_>(), queue
299 ));
300 boost::compute::detail::radix_sort(
301 vector.begin(), vector.end(), descending, queue
302 );
303 BOOST_CHECK(boost::compute::is_sorted(
304 vector.begin(), vector.end(), boost::compute::greater<short_>(), queue
305 ));
306
307 CHECK_RANGE_EQUAL(
308 short_, 8, vector,
309 (31002, 963, 152, 0, -4, -94, -456, -2113)
310 );
311 }
312
BOOST_AUTO_TEST_CASE(sort_ushort_vector_desc)313 BOOST_AUTO_TEST_CASE(sort_ushort_vector_desc)
314 {
315 if(is_apple_cpu_device(device)) {
316 return;
317 }
318
319 using boost::compute::ushort_;
320
321 ushort_ data[] = { 4, 152, 94, 963, 63202, 34560, 0, 2113 };
322 boost::compute::vector<ushort_> vector(data, data + 8, queue);
323 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
324
325 BOOST_CHECK(!boost::compute::is_sorted(
326 vector.begin(), vector.end(), boost::compute::greater<ushort_>(), queue
327 ));
328 boost::compute::detail::radix_sort(
329 vector.begin(), vector.end(), descending, queue
330 );
331 BOOST_CHECK(boost::compute::is_sorted(
332 vector.begin(), vector.end(), boost::compute::greater<ushort_>(), queue
333 ));
334
335 CHECK_RANGE_EQUAL(
336 ushort_, 8, vector,
337 (63202, 34560, 2113, 963, 152, 94, 4, 0)
338 );
339 }
340
BOOST_AUTO_TEST_CASE(sort_int_vector_desc)341 BOOST_AUTO_TEST_CASE(sort_int_vector_desc)
342 {
343 if(is_apple_cpu_device(device)) {
344 return;
345 }
346
347 using boost::compute::int_;
348
349 int_ data[] = { -4, 152, -5000, 963, 75321, -456, 0, 1112 };
350 boost::compute::vector<int_> vector(data, data + 8, queue);
351 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
352
353 BOOST_CHECK(!boost::compute::is_sorted(
354 vector.begin(), vector.end(), boost::compute::greater<int_>(), queue
355 ));
356 boost::compute::detail::radix_sort(
357 vector.begin(), vector.end(), descending, queue
358 );
359 BOOST_CHECK(boost::compute::is_sorted(
360 vector.begin(), vector.end(), boost::compute::greater<int_>(), queue
361 ));
362
363 CHECK_RANGE_EQUAL(
364 int_, 8, vector,
365 (75321, 1112, 963, 152, 0, -4, -456, -5000)
366 );
367 }
368
BOOST_AUTO_TEST_CASE(sort_uint_vector_desc)369 BOOST_AUTO_TEST_CASE(sort_uint_vector_desc)
370 {
371 if(is_apple_cpu_device(device)) {
372 return;
373 }
374
375 using boost::compute::uint_;
376
377 uint_ data[] = { 500, 1988, 123456, 562, 0, 4000000, 9852, 102030 };
378 boost::compute::vector<uint_> vector(data, data + 8, queue);
379 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
380
381 BOOST_CHECK(!boost::compute::is_sorted(
382 vector.begin(), vector.end(), boost::compute::greater<uint_>(), queue
383 ));
384 boost::compute::detail::radix_sort(
385 vector.begin(), vector.end(), descending, queue
386 );
387 BOOST_CHECK(boost::compute::is_sorted(
388 vector.begin(), vector.end(), boost::compute::greater<uint_>(), queue
389 ));
390
391 CHECK_RANGE_EQUAL(
392 uint_, 8, vector,
393 (4000000, 123456, 102030, 9852, 1988, 562, 500, 0)
394 );
395 }
396
BOOST_AUTO_TEST_CASE(sort_long_vector_desc)397 BOOST_AUTO_TEST_CASE(sort_long_vector_desc)
398 {
399 if(is_apple_cpu_device(device)) {
400 return;
401 }
402
403 using boost::compute::long_;
404
405 long_ data[] = { -500, 1988, 123456, 562, 0, 4000000, 9852, 102030 };
406 boost::compute::vector<long_> vector(data, data + 8, queue);
407 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
408
409 BOOST_CHECK(!boost::compute::is_sorted(
410 vector.begin(), vector.end(), boost::compute::greater<long_>(), queue
411 ));
412 boost::compute::detail::radix_sort(
413 vector.begin(), vector.end(), descending, queue
414 );
415 BOOST_CHECK(boost::compute::is_sorted(
416 vector.begin(), vector.end(), boost::compute::greater<long_>(), queue
417 ));
418
419 CHECK_RANGE_EQUAL(
420 long_, 8, vector,
421 (4000000, 123456, 102030, 9852, 1988, 562, 0, -500)
422 );
423 }
424
BOOST_AUTO_TEST_CASE(sort_ulong_vector_desc)425 BOOST_AUTO_TEST_CASE(sort_ulong_vector_desc)
426 {
427 if(is_apple_cpu_device(device)) {
428 return;
429 }
430
431 using boost::compute::ulong_;
432
433 ulong_ data[] = { 500, 1988, 123456, 562, 0, 4000000, 9852, 102030 };
434 boost::compute::vector<ulong_> vector(data, data + 8, queue);
435 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
436
437 BOOST_CHECK(!boost::compute::is_sorted(
438 vector.begin(), vector.end(), boost::compute::greater<ulong_>(), queue
439 ));
440 boost::compute::detail::radix_sort(
441 vector.begin(), vector.end(), descending, queue
442 );
443 BOOST_CHECK(boost::compute::is_sorted(
444 vector.begin(), vector.end(), boost::compute::greater<ulong_>(), queue
445 ));
446
447 CHECK_RANGE_EQUAL(
448 ulong_, 8, vector,
449 (4000000, 123456, 102030, 9852, 1988, 562, 500, 0)
450 );
451 }
452
BOOST_AUTO_TEST_CASE(sort_float_vector_desc)453 BOOST_AUTO_TEST_CASE(sort_float_vector_desc)
454 {
455 if(is_apple_cpu_device(device)) {
456 return;
457 }
458
459 float data[] = {
460 -6023.0f, 152.5f, -63.0f, 1234567.0f, 11.2f,
461 -5000.1f, 0.0f, 14.0f, -8.25f, -0.0f
462 };
463
464 boost::compute::vector<float> vector(data, data + 10, queue);
465 BOOST_CHECK_EQUAL(vector.size(), size_t(10));
466
467 BOOST_CHECK(!boost::compute::is_sorted(
468 vector.begin(), vector.end(), boost::compute::greater<float>(), queue
469 ));
470 boost::compute::detail::radix_sort(
471 vector.begin(), vector.end(), descending, queue
472 );
473 BOOST_CHECK(boost::compute::is_sorted(
474 vector.begin(), vector.end(), boost::compute::greater<float>(), queue
475 ));
476
477 CHECK_RANGE_EQUAL(
478 float, 10, vector,
479 (1234567.0f, 152.5f, 14.0f, 11.2f, 0.0f, -0.0f, -8.25f, -63.0f, -5000.1f, -6023.0f)
480 );
481
482 // copy data, sort, and check again (to check program caching)
483 boost::compute::copy(data, data + 10, vector.begin(), queue);
484 boost::compute::detail::radix_sort(
485 vector.begin(), vector.end(), descending, queue
486 );
487 BOOST_CHECK(boost::compute::is_sorted(
488 vector.begin(), vector.end(), boost::compute::greater<float>(), queue
489 ));
490 CHECK_RANGE_EQUAL(
491 float, 10, vector,
492 (1234567.0f, 152.5f, 14.0f, 11.2f, 0.0f, -0.0f, -8.25f, -63.0f, -5000.1f, -6023.0f)
493 );
494 }
495
BOOST_AUTO_TEST_CASE(sort_double_vector_desc)496 BOOST_AUTO_TEST_CASE(sort_double_vector_desc)
497 {
498 if(is_apple_cpu_device(device)) {
499 return;
500 }
501
502 if(!device.supports_extension("cl_khr_fp64")){
503 std::cout << "skipping test: device does not support double" << std::endl;
504 return;
505 }
506
507 double data[] = {
508 -6023.0, 152.5, -63.0, 1234567.0, 11.2, -5000.1, 0.0, 14.0, -8.25, -0.0
509 };
510
511 boost::compute::vector<double> vector(data, data + 10, queue);
512 BOOST_CHECK_EQUAL(vector.size(), size_t(10));
513
514 BOOST_CHECK(!boost::compute::is_sorted(
515 vector.begin(), vector.end(), boost::compute::greater<double>(), queue
516 ));
517 boost::compute::detail::radix_sort(
518 vector.begin(), vector.end(), descending, queue
519 );
520 BOOST_CHECK(boost::compute::is_sorted(
521 vector.begin(), vector.end(), boost::compute::greater<double>(), queue
522 ));
523
524 CHECK_RANGE_EQUAL(
525 double, 10, vector,
526 (1234567.0, 152.5, 14.0, 11.2, 0.0, -0.0, -8.25, -63.0, -5000.1, -6023.0)
527 );
528 }
529
BOOST_AUTO_TEST_CASE(sort_partial_vector)530 BOOST_AUTO_TEST_CASE(sort_partial_vector)
531 {
532 if(is_apple_cpu_device(device)) {
533 return;
534 }
535
536 int data[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
537 boost::compute::vector<int> vec(data, data + 10, queue);
538
539 boost::compute::detail::radix_sort(vec.begin() + 2, vec.end() - 2, queue);
540 CHECK_RANGE_EQUAL(int, 10, vec, (9, 8, 2, 3, 4, 5, 6, 7, 1, 0));
541 }
542
543 BOOST_AUTO_TEST_SUITE_END()
544