1 //----------------------------------------------------------------------------
2 /// @file test_block_indirect_sort.cpp
3 /// @brief Test program of the block_indirect_sort algorithm
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 #include <algorithm>
14 #include <random>
15 #include <stdio.h>
16 #include <stdlib.h>
17 #include <time.h>
18 #include <vector>
19 #include <ciso646>
20 #include <boost/test/included/test_exec_monitor.hpp>
21 #include <boost/test/test_tools.hpp>
22 #include <boost/sort/sort.hpp>
23
24
25 namespace bsc = boost::sort::common;
26 namespace bsp = boost::sort;
27 using boost::sort::block_indirect_sort;
28 using bsc::range;
29
30 // ------------------- vector with 64 bits random numbers --------------------
31 std::vector< uint64_t > Vrandom;
32 const uint64_t NELEM = 2000000;
33
test1(void)34 void test1 (void)
35 {
36 const uint32_t NElem = 500000;
37 std::vector< uint64_t > V1;
38 V1.reserve (NElem);
39
40 //------------------ sorted elements 4 threads --------------------------
41 V1.clear ( );
42 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (i);
43
44 block_indirect_sort ( V1.begin ( ), V1.end ( ), 4);
45 for (unsigned i = 1; i < NElem; i++)
46 { BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]);
47 };
48
49 //-------------------- reverse sorted elements 4 threads ------------------
50 V1.clear ( );
51 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (NElem - i);
52
53 block_indirect_sort ( V1.begin ( ), V1.end ( ), 4);
54 for (unsigned i = 1; i < NElem; i++)
55 { BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]);
56 };
57
58 //-------------------- equal elements 4 threads ---------------------------
59 V1.clear ( );
60 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (1000);
61
62 block_indirect_sort (V1.begin ( ), V1.end ( ), 4);
63 for (unsigned i = 1; i < NElem; i++)
64 { BOOST_CHECK (V1[ i - 1 ] == V1[ i ]);
65 };
66
67 //------------------ sorted elements 8 threads --------------------------
68 V1.clear ( );
69 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (i);
70
71 block_indirect_sort ( V1.begin ( ), V1.end ( ), 8);
72 for (unsigned i = 1; i < NElem; i++)
73 { BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]);
74 };
75
76 //-------------------- reverse sorted elements 8 threads ------------------
77 V1.clear ( );
78 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (NElem - i);
79
80 block_indirect_sort ( V1.begin ( ), V1.end ( ), 8);
81 for (unsigned i = 1; i < NElem; i++)
82 { BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]);
83 };
84
85 //-------------------- equal elements 8 threads ---------------------------
86 V1.clear ( );
87 for (uint32_t i = 0; i < NElem; ++i) V1.push_back (1000);
88
89 block_indirect_sort (V1.begin ( ), V1.end ( ), 8);
90 for (unsigned i = 1; i < NElem; i++)
91 { BOOST_CHECK (V1[ i - 1 ] == V1[ i ]);
92 };
93 };
94
test2(void)95 void test2 (void)
96 {
97 typedef std::less<uint64_t> compare;
98 std::vector< uint64_t > V1, V2;
99 V1.reserve ( NELEM ) ;
100
101 V2 = Vrandom;
102 std::sort (V2.begin ( ), V2.end ( ));
103
104 //------------------- random elements 0 threads ---------------------------
105 V1 = Vrandom;
106 block_indirect_sort (V1.begin ( ), V1.end ( ), compare(), 0);
107 for (unsigned i = 0; i < V1.size(); i++)
108 { BOOST_CHECK (V1[i] == V2[i]);
109 };
110
111 //------------------- random elements 4 threads ---------------------------
112 V1 = Vrandom;
113 block_indirect_sort (V1.begin ( ), V1.end ( ), compare(), 4);
114 for (unsigned i = 0; i < V1.size(); i++)
115 { BOOST_CHECK (V1[i] == V2[i]);
116 };
117
118 //------------------- random elements 8 threads ---------------------------
119 V1 = Vrandom;
120 block_indirect_sort (V1.begin ( ), V1.end ( ), compare(), 8);
121 for (unsigned i = 0; i < V1.size(); i++)
122 { BOOST_CHECK (V1[i] == V2[i]);
123 };
124
125 //------------------- random elements 16 threads ---------------------------
126 V1 = Vrandom;
127 block_indirect_sort ( V1.begin ( ), V1.end ( ), compare(), 16);
128 for (unsigned i = 0; i < V1.size(); i++)
129 { BOOST_CHECK (V1[i] == V2[i]);
130 };
131
132 //------------------- random elements 100 threads ---------------------------
133 V1 = Vrandom;
134 block_indirect_sort ( V1.begin ( ), V1.end ( ), compare(), 100);
135 for (unsigned i = 1; i < V1.size(); i++)
136 { BOOST_CHECK (V1[i] == V2[i]);
137 };
138 };
139
140 template<uint32_t NN>
141 struct int_array
142 {
143 uint64_t M[NN];
144
int_arrayint_array145 int_array(uint64_t number = 0)
146 { for (uint32_t i = 0; i < NN; ++i) M[i] = number;
147 };
148
operator <int_array149 bool operator<(const int_array<NN> &A) const
150 { return M[0] < A.M[0];
151 };
152 };
153
154 template<class IA>
test_int_array(uint32_t NELEM)155 void test_int_array(uint32_t NELEM)
156 {
157 std::vector<IA> V1;
158 V1.reserve(NELEM);
159
160 for (uint32_t i = 0; i < NELEM; ++i)
161 V1.emplace_back(Vrandom[i]);
162
163 bsp::block_indirect_sort(V1.begin(), V1.end());
164 for (unsigned i = 1; i < NELEM; i++)
165 { BOOST_CHECK(not (V1[i] < V1[i-1]));
166 };
167 };
test3(void)168 void test3 (void)
169 {
170 test_int_array<int_array<1> >(1u << 20);
171 test_int_array<int_array<2> >(1u << 19);
172 test_int_array<int_array<8> >(1u << 17);
173 }
174
test_main(int,char * [])175 int test_main (int, char *[])
176 {
177 std::mt19937 my_rand (0);
178 Vrandom.reserve (NELEM);
179 for (uint32_t i = 0; i < NELEM; ++i) Vrandom.push_back (my_rand ( ));
180
181 test1 ( );
182 test2 ( );
183 test3 ( );
184
185 return 0;
186 };
187