ceph/src/boost/libs/compute/test/test_radix_sort_by_key.cpp

   1 //---------------------------------------------------------------------------//
   2 // Copyright (c) 2016 Jakub Szuppe <j.szuppe@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 TestRadixSortByKey
  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 compute = boost::compute;
  26
  27 const bool descending = false;
  28
  29 // radix_sort_by_key should be stable
  30 BOOST_AUTO_TEST_CASE(stable_radix_sort_int_by_int)
  31 {
  32     if(is_apple_cpu_device(device)) {
  33         std::cerr
  34             << "skipping all radix_sort_by_key tests due to Apple platform"
  35             << " behavior when local memory is used on a CPU device"
  36             << std::endl;
  37         return;
  38     }
  39
  40     compute::int_ keys_data[] =   { 10, 9, 2, 7, 6, -1, 4, 2, 2, 10 };
  41     compute::int_ values_data[] = { 1,  2, 3, 4, 5,  6, 7, 8, 9, 10 };
  42
  43     compute::vector<compute::int_> keys(keys_data, keys_data + 10, queue);
  44     compute::vector<compute::int_> values(values_data, values_data + 10, queue);
  45
  46     BOOST_CHECK(!compute::is_sorted(keys.begin(), keys.end(), queue));
  47     compute::detail::radix_sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
  48     BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue));
  49
  50     CHECK_RANGE_EQUAL(
  51         compute::int_, 10, keys,
  52         (-1, 2, 2, 2, 4, 6, 7, 9, 10, 10) // keys
  53      // ( 6, 3, 8, 9, 7, 5, 4, 2,  1, 10) values
  54     );
  55     CHECK_RANGE_EQUAL(
  56         compute::int_, 10, values,
  57      // (-1, 2, 2, 2, 4, 6, 7, 9, 10, 10) keys
  58         ( 6, 3, 8, 9, 7, 5, 4, 2,  1, 10) // values
  59     );
  60 }
  61
  62 // radix_sort_by_key should be stable
  63 BOOST_AUTO_TEST_CASE(stable_radix_sort_int_by_int_desc)
  64 {
  65     if(is_apple_cpu_device(device)) {
  66         return;
  67     }
  68
  69     compute::int_ keys_data[] =   { 10, 9, 2, 7, 6, -1, 4, 2, 2, 10 };
  70     compute::int_ values_data[] = { 1,  2, 3, 4, 5,  6, 7, 8, 9, 10 };
  71
  72     compute::vector<compute::int_> keys(keys_data, keys_data + 10, queue);
  73     compute::vector<compute::int_> values(values_data, values_data + 10, queue);
  74
  75     BOOST_CHECK(
  76         !compute::is_sorted(
  77             keys.begin(), keys.end(), compute::greater<compute::int_>(), queue
  78         )
  79     );
  80     compute::detail::radix_sort_by_key(
  81         keys.begin(), keys.end(), values.begin(), descending, queue
  82     );
  83     BOOST_CHECK(
  84         compute::is_sorted(
  85             keys.begin(), keys.end(), compute::greater<compute::int_>(), queue
  86         )
  87     );
  88
  89     CHECK_RANGE_EQUAL(
  90         compute::int_, 10, keys,
  91         (10, 10, 9, 7, 6, 4, 2, 2, 2, -1) // keys
  92      // ( 1, 10, 2, 4, 5, 7, 3, 8, 9,  6) values
  93     );
  94     CHECK_RANGE_EQUAL(
  95         compute::int_, 10, values,
  96     //  (10, 10, 9, 7, 6, 4, 2, 2, 2, -1) // keys
  97         ( 1, 10, 2, 4, 5, 7, 3, 8, 9,  6) // values
  98     );
  99 }
 100
 101 // radix_sort_by_key should be stable
 102 BOOST_AUTO_TEST_CASE(stable_radix_sort_uint_by_uint)
 103 {
 104     if(is_apple_cpu_device(device)) {
 105         return;
 106     }
 107
 108     compute::uint_ keys_data[] =   { 10, 9, 2, 7, 6, 1, 4, 2, 2, 10 };
 109     compute::uint_ values_data[] = { 1,  2, 3, 4, 5, 6, 7, 8, 9, 10 };
 110
 111     compute::vector<compute::uint_> keys(keys_data, keys_data + 10, queue);
 112     compute::vector<compute::uint_> values(values_data, values_data + 10, queue);
 113
 114     BOOST_CHECK(!compute::is_sorted(keys.begin(), keys.end(), queue));
 115     compute::detail::radix_sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
 116     BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue));
 117
 118     CHECK_RANGE_EQUAL(
 119         compute::uint_, 10, keys,
 120         (1, 2, 2, 2, 4, 6, 7, 9, 10, 10) // keys
 121      // (6, 3, 8, 9, 7, 5, 4, 2,  1, 10) values
 122     );
 123     CHECK_RANGE_EQUAL(
 124         compute::uint_, 10, values,
 125      // (1, 2, 2, 2, 4, 6, 7, 9, 10, 10) keys
 126         (6, 3, 8, 9, 7, 5, 4, 2,  1, 10) // values
 127     );
 128 }
 129
 130 // radix_sort_by_key should be stable
 131 BOOST_AUTO_TEST_CASE(stable_radix_sort_uint_by_uint_desc)
 132 {
 133     if(is_apple_cpu_device(device)) {
 134         return;
 135     }
 136
 137     compute::uint_ keys_data[] =   { 10, 9, 2, 7, 6, 1, 4, 2, 2, 10 };
 138     compute::uint_ values_data[] = { 1,  2, 3, 4, 5, 6, 7, 8, 9, 10 };
 139
 140     compute::vector<compute::uint_> keys(keys_data, keys_data + 10, queue);
 141     compute::vector<compute::uint_> values(values_data, values_data + 10, queue);
 142
 143     BOOST_CHECK(
 144         !compute::is_sorted(
 145             keys.begin(), keys.end(), compute::greater<compute::uint_>(), queue
 146         )
 147     );
 148     compute::detail::radix_sort_by_key(
 149         keys.begin(), keys.end(), values.begin(), descending, queue
 150     );
 151     BOOST_CHECK(
 152         compute::is_sorted(
 153             keys.begin(), keys.end(), compute::greater<compute::uint_>(), queue
 154         )
 155     );
 156
 157     CHECK_RANGE_EQUAL(
 158         compute::uint_, 10, keys,
 159         (10, 10, 9, 7, 6, 4, 2, 2, 2, 1) // keys
 160      // ( 1, 10, 2, 4, 5, 7, 3, 8, 9, 6) values
 161     );
 162     CHECK_RANGE_EQUAL(
 163         compute::uint_, 10, values,
 164     //  (10, 10, 9, 7, 6, 4, 2, 2, 2, 1) // keys
 165         ( 1, 10, 2, 4, 5, 7, 3, 8, 9, 6) // values
 166     );
 167 }
 168
 169
 170 // radix_sort_by_key should be stable
 171 BOOST_AUTO_TEST_CASE(stable_radix_sort_int_by_float)
 172 {
 173     if(is_apple_cpu_device(device)) {
 174         return;
 175     }
 176
 177     compute::float_ keys_data[]   = { 10., 5.5, 10., 7., 5.5};
 178     compute::int_   values_data[] = {   1, 200, -10,  2, 4 };
 179
 180     compute::vector<compute::float_> keys(keys_data, keys_data + 5, queue);
 181     compute::vector<compute::uint_> values(values_data, values_data + 5, queue);
 182
 183     BOOST_CHECK(!compute::is_sorted(keys.begin(), keys.end(), queue));
 184     compute::detail::radix_sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
 185     BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue));
 186
 187     CHECK_RANGE_EQUAL(
 188         compute::float_, 5, keys,
 189         (5.5, 5.5, 7., 10., 10.) // keys
 190      // (200,   4,  2,   1, -10) values
 191     );
 192     CHECK_RANGE_EQUAL(
 193         compute::int_, 5, values,
 194      // (5.5, 5.5, 7., 10., 10.) keys
 195         (200,   4,  2,   1, -10) // values
 196     );
 197 }
 198
 199 // radix_sort_by_key should be stable
 200 BOOST_AUTO_TEST_CASE(stable_radix_sort_int_by_float_desc)
 201 {
 202     if(is_apple_cpu_device(device)) {
 203         return;
 204     }
 205
 206     compute::float_ keys_data[]   = { 10., 5.5, 10., 7., 5.5};
 207     compute::int_   values_data[] = {   1, 200, -10,  2, 4 };
 208
 209     compute::vector<compute::float_> keys(keys_data, keys_data + 5, queue);
 210     compute::vector<compute::uint_> values(values_data, values_data + 5, queue);
 211
 212     BOOST_CHECK(
 213         !compute::is_sorted(
 214             keys.begin(), keys.end(), compute::greater<compute::float_>(), queue
 215         )
 216     );
 217     compute::detail::radix_sort_by_key(
 218         keys.begin(), keys.end(), values.begin(), descending, queue
 219     );
 220     BOOST_CHECK(
 221         compute::is_sorted(
 222             keys.begin(), keys.end(), compute::greater<compute::float_>(), queue
 223         )
 224     );
 225
 226     CHECK_RANGE_EQUAL(
 227         compute::float_, 5, keys,
 228         (10.,  10., 7., 5.5, 5.5) // keys
 229      // (  1, -10,   2, 200, 4) values
 230     );
 231     CHECK_RANGE_EQUAL(
 232         compute::int_, 5, values,
 233      // (10.,  10., 7., 5.5, 5.5) // keys
 234         (  1, -10,   2, 200, 4) // values
 235     );
 236 }
 237
 238
 239 // radix_sort_by_key should be stable
 240 BOOST_AUTO_TEST_CASE(stable_radix_sort_char_by_int)
 241 {
 242     if(is_apple_cpu_device(device)) {
 243         return;
 244     }
 245
 246     compute::int_ keys_data[] = { 6, 1, 1, 3, 4, 7, 5, 1 };
 247     compute::char_ values_data[] = { 'g', 'c', 'b', 'd', 'e', 'h', 'f', 'a' };
 248
 249     compute::vector<compute::int_> keys(keys_data, keys_data + 8, queue);
 250     compute::vector<compute::char_> values(values_data, values_data + 8, queue);
 251
 252     BOOST_CHECK(!compute::is_sorted(keys.begin(), keys.end(), queue));
 253     compute::detail::radix_sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
 254     BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue));
 255
 256     CHECK_RANGE_EQUAL(
 257         compute::int_, 8, keys,
 258         (1, 1, 1, 3, 4, 5, 6, 7)
 259     );
 260     CHECK_RANGE_EQUAL(
 261         compute::char_, 8, values,
 262         ('c', 'b', 'a', 'd', 'e', 'f', 'g', 'h')
 263     );
 264 }
 265
 266 // radix_sort_by_key should be stable
 267 BOOST_AUTO_TEST_CASE(stable_radix_sort_int2_by_int)
 268 {
 269     if(is_apple_cpu_device(device)) {
 270         return;
 271     }
 272
 273     compute::int_ keys_data[] = { 6, 1, 1, 3, 4, 7, 5, 1 };
 274     compute::int2_ values_data[] = {
 275         compute::int2_(1, 1), // 6
 276         compute::int2_(1, 2), // 1
 277         compute::int2_(1, 3), // 1
 278         compute::int2_(1, 4), // 3
 279         compute::int2_(1, 5), // 4
 280         compute::int2_(1, 6), // 7
 281         compute::int2_(1, 7), // 5
 282         compute::int2_(1, 8)  // 1
 283     };
 284
 285     compute::vector<compute::int_> keys(keys_data, keys_data + 8, queue);
 286     compute::vector<compute::int2_> values(values_data, values_data + 8, queue);
 287
 288     BOOST_CHECK(!compute::is_sorted(keys.begin(), keys.end(), queue));
 289     compute::detail::radix_sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
 290     BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue));
 291
 292     CHECK_RANGE_EQUAL(
 293         compute::int_, 8, keys,
 294         (1, 1, 1, 3, 4, 5, 6, 7)
 295     );
 296     CHECK_RANGE_EQUAL(
 297         compute::int2_, 8, values,
 298         (
 299             compute::int2_(1, 2),
 300             compute::int2_(1, 3),
 301             compute::int2_(1, 8),
 302             compute::int2_(1, 4),
 303             compute::int2_(1, 5),
 304             compute::int2_(1, 7),
 305             compute::int2_(1, 1),
 306             compute::int2_(1, 6)
 307         )
 308     );
 309 }
 310
 311 BOOST_AUTO_TEST_SUITE_END()