#856

Committed 28 Dec 2022 02:00AM UTC coverage: 86.602% (+0.05%) from 86.55%

Build # #856

Build Type

push

Committed by StellarBot

Commit Message

Merge #6119

6119: Update CMakeLists.txt r=hkaiser a=khuck

updating the default APEX version


Co-authored-by: Kevin Huck <khuck@cs.uoregon.edu>

Run Details

174566 of 201573 relevant lines covered (86.6%)

1876093.78 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

85.71

/libs/core/algorithms/tests/unit/algorithms/sort_by_key.cpp

//  Copyright (c) 2015-2016 John Biddiscombe
//
//  SPDX-License-Identifier: BSL-1.0
//  Distributed under the Boost Software License, Version 1.0. (See accompanying
//  file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#include <hpx/local/init.hpp>
#include <hpx/modules/testing.hpp>
#include <hpx/parallel/algorithm.hpp>
#include <hpx/parallel/algorithms/generate.hpp>
#include <hpx/parallel/algorithms/sort_by_key.hpp>
#include <hpx/type_support/unused.hpp>
//
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <utility>
#include <vector>
//
#if defined(HPX_DEBUG)
#define HPX_SORT_BY_KEY_TEST_SIZE (1 << 8)
#else
#define HPX_SORT_BY_KEY_TEST_SIZE (1 << 18)
#endif
//
#include "sort_tests.hpp"
//
#define EXTRA_DEBUG
//
namespace debug {
    template <typename T>
    void output(const std::string& name, const std::vector<T>& v)
    {
#ifdef EXTRA_DEBUG7
        std::cout << name.c_str() << "\t : {" << v.size() << "} : ";
        std::copy(std::begin(v), std::end(v),
            std::ostream_iterator<T>(std::cout, ", "));
        std::cout << "\n";
#else
        HPX_UNUSED(name);
        HPX_UNUSED(v);
#endif
    }

    template <typename Iter>
    void output(const std::string& name, Iter begin, Iter end)
    {
#ifdef EXTRA_DEBUG
        std::cout << name.c_str() << "\t : {" << std::distance(begin, end)
                  << "} : ";
        std::copy(begin, end,
            std::ostream_iterator<
                typename std::iterator_traits<Iter>::value_type>(
                std::cout, ", "));
        std::cout << "\n";
#else
        HPX_UNUSED(name);
        HPX_UNUSED(begin);
        HPX_UNUSED(end);
#endif
    }

#if defined(EXTRA_DEBUG)
#define debug_msg(a) std::cout << a
#else
#define debug_msg(a)
#endif
}    // namespace debug

#undef msg
#define msg(a, b, c, d)                                                        \
    std::cout << std::setw(60) << a << std::setw(12) << b << std::setw(40)     \
              << c << std::setw(30) << std::setw(8) << #d << "\t";

////////////////////////////////////////////////////////////////////////////////
void sort_by_key_benchmark()
{
    try
    {
        const int bench_size = HPX_SORT_BY_KEY_TEST_SIZE * 256;
        // vector of values, and keys
        std::vector<double> values, o_values;
        std::vector<int64_t> keys, o_keys;
        //
        values.assign(bench_size, 0);
        keys.assign(bench_size, 0);

        // generate a sequence as the values
        std::iota(values.begin(), values.end(), 0);
        // generate a sequence as the keys
        std::iota(keys.begin(), keys.end(), 0);

        // shuffle the keys up,
        std::random_device rd;
        std::mt19937 g(rd());
        std::shuffle(keys.begin(), keys.end(), g);

        // make copies of initial states
        o_keys = keys;
        o_values = values;

        hpx::chrono::high_resolution_timer t;
        hpx::experimental::sort_by_key(
            hpx::execution::par, keys.begin(), keys.end(), values.begin());
        auto elapsed = static_cast<std::uint64_t>(t.elapsed_nanoseconds());

        // after sorting by key, the values should be equal to the original keys
        bool is_equal = std::equal(keys.begin(), keys.end(), o_values.begin());
        HPX_TEST(is_equal);
        if (is_equal)
        {
            // CDash graph plotting
            hpx::util::print_cdash_timing("SortByKeyTime", elapsed);
        }
    }
    catch (...)
    {
        HPX_TEST(false);
    }
}

////////////////////////////////////////////////////////////////////////////////
template <typename ExPolicy, typename Tkey, typename Tval, typename Op,
    typename HelperOp>
void test_sort_by_key1(
    ExPolicy&& policy, Tkey, Tval, const Op&, const HelperOp&)
{
    static_assert(hpx::is_execution_policy<ExPolicy>::value,
        "hpx::is_execution_policy<ExPolicy>::value");
    msg(typeid(ExPolicy).name(), typeid(Tval).name(), typeid(Op).name(), sync);
    std::cout << "\n";

    // vector of values, and keys
    std::vector<Tval> values, o_values;
    std::vector<Tkey> keys, o_keys;
    //
    values.assign(HPX_SORT_BY_KEY_TEST_SIZE, 0);
    keys.assign(HPX_SORT_BY_KEY_TEST_SIZE, 0);

    // generate a sequence as the values
    std::iota(values.begin(), values.end(), 0);
    // generate a sequence as the keys
    std::iota(keys.begin(), keys.end(), 0);

    // shuffle the keys up,
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(keys.begin(), keys.end(), g);

    // make copies of initial states
    o_keys = keys;
    o_values = values;

    // sort_by_key, blocking when seq, par, par_vec
    hpx::experimental::sort_by_key(std::forward<ExPolicy>(policy), keys.begin(),
        keys.end(), values.begin());

    // after sorting by key, the values should be equal to the original keys
    bool is_equal = std::equal(keys.begin(), keys.end(), o_values.begin());
    if (is_equal)
    {
        //std::cout << "Test Passed\n";
    }
    else
    {
        debug::output("keys     ", o_keys);
        debug::output("values   ", o_values);
        debug::output("key range", keys);
        debug::output("val range", values);
        throw std::string("Problem");
    }
    HPX_TEST(is_equal);
}

////////////////////////////////////////////////////////////////////////////////
template <typename ExPolicy, typename Tkey, typename Tval, typename Op,
    typename HelperOp>
void test_sort_by_key_async(
    ExPolicy&& policy, Tkey, Tval, const Op&, const HelperOp&)
{
    static_assert(hpx::is_execution_policy<ExPolicy>::value,
        "hpx::is_execution_policy<ExPolicy>::value");
    msg(typeid(ExPolicy).name(), typeid(Tval).name(), typeid(Op).name(), async);
    std::cout << "\n";

    // vector of values, and keys
    std::vector<Tval> values, o_values;
    std::vector<Tkey> keys, o_keys;
    //
    values.assign(HPX_SORT_BY_KEY_TEST_SIZE, 0);
    keys.assign(HPX_SORT_BY_KEY_TEST_SIZE, 0);

    // generate a sequence as the values
    std::iota(values.begin(), values.end(), 0);
    // generate a sequence as the keys
    std::iota(keys.begin(), keys.end(), 0);

    // shuffle the keys up,
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(keys.begin(), keys.end(), g);

    // make copies of initial states
    o_keys = keys;
    o_values = values;

    // sort_by_key, blocking when seq, par, par_vec
    auto fresult =
        hpx::experimental::sort_by_key(std::forward<ExPolicy>(policy),
            keys.begin(), keys.end(), values.begin());
    fresult.get();

    // after sorting by key, the values should be equal to the original keys
    bool is_equal = std::equal(keys.begin(), keys.end(), o_values.begin());
    if (is_equal)
    {
        //std::cout << "Test Passed\n";
    }
    else
    {
        debug::output("keys     ", o_keys);
        debug::output("values   ", o_values);
        debug::output("key range", keys);
        debug::output("val range", values);
        throw std::string("Problem");
    }
    HPX_TEST(is_equal);
}

////////////////////////////////////////////////////////////////////////////////
void test_sort_by_key1()
{
    using namespace hpx::execution;
    //
    // run many tests in a loop for N seconds just to play safe
    //
    const int seconds = 1;
    //
    hpx::chrono::high_resolution_timer t;
    do
    {
        //
        test_sort_by_key1(seq, int(), int(), std::equal_to<int>(),
            [](int key) { return key; });
        test_sort_by_key1(par, int(), int(), std::equal_to<int>(),
            [](int key) { return key; });
        test_sort_by_key1(par_unseq, int(), int(), std::equal_to<int>(),
            [](int key) { return key; });
        //
        test_sort_by_key1(seq, int(), double(), std::equal_to<double>(),
            [](int key) { return key; });
        test_sort_by_key1(par, int(), double(), std::equal_to<double>(),
            [](int key) { return key; });
        test_sort_by_key1(par_unseq, int(), double(), std::equal_to<double>(),
            [](int key) { return key; });
        // custom compare
        test_sort_by_key1(
            seq, double(), double(),
            [](double a, double b) {
                return std::floor(a) == std::floor(b);
            },    //-V550
            [](double a) { return std::floor(a); });
        test_sort_by_key1(
            par, double(), double(),
            [](double a, double b) {
                return std::floor(a) == std::floor(b);
            },    //-V550
            [](double a) { return std::floor(a); });
        test_sort_by_key1(
            par_unseq, double(), double(),
            [](double a, double b) {
                return std::floor(a) == std::floor(b);
            },    //-V550
            [](double a) { return std::floor(a); });
    } while (t.elapsed() < seconds);
    //
    hpx::chrono::high_resolution_timer t2;
    do
    {
        test_sort_by_key_async(seq(task), int(), int(), std::equal_to<int>(),
            [](int key) { return key; });
        test_sort_by_key_async(par(task), int(), int(), std::equal_to<int>(),
            [](int key) { return key; });
        //
        test_sort_by_key_async(seq(task), int(), double(),
            std::equal_to<double>(), [](int key) { return key; });
        test_sort_by_key_async(par(task), int(), double(),
            std::equal_to<double>(), [](int key) { return key; });
    } while (t2.elapsed() < seconds);
}

////////////////////////////////////////////////////////////////////////////////
int hpx_main(hpx::program_options::variables_map& vm)
{
    unsigned int seed = (unsigned int) std::time(nullptr);
    if (vm.count("seed"))
        seed = vm["seed"].as<unsigned int>();

    std::cout << "using seed: " << seed << std::endl;
    std::srand(seed);

    test_sort_by_key1();
    sort_by_key_benchmark();

    return hpx::local::finalize();
}

int main(int argc, char* argv[])
{
    // add command line option which controls the random number generator seed
    using namespace hpx::program_options;
    options_description desc_commandline(
        "Usage: " HPX_APPLICATION_STRING " [options]");

    desc_commandline.add_options()("seed,s", value<unsigned int>(),
        "the random number generator seed to use for this run");

    // By default this test should run on all available cores
    std::vector<std::string> const cfg = {"hpx.os_threads=all"};

    hpx::local::init_params init_args;
    init_args.desc_cmdline = desc_commandline;
    init_args.cfg = cfg;

    HPX_TEST_EQ_MSG(hpx::local::init(hpx_main, argc, argv, init_args), 0,
        "HPX main exited with non-zero status");

    return hpx::util::report_errors();
}

1	// Copyright (c) 2015-2016 John Biddiscombe
2	//
3	// SPDX-License-Identifier: BSL-1.0
4	// Distributed under the Boost Software License, Version 1.0. (See accompanying
5	// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6
7	#include <hpx/local/init.hpp>
8	#include <hpx/modules/testing.hpp>
9	#include <hpx/parallel/algorithm.hpp>
10	#include <hpx/parallel/algorithms/generate.hpp>
11	#include <hpx/parallel/algorithms/sort_by_key.hpp>
12	#include <hpx/type_support/unused.hpp>
13	//
14	#include <cstdint>
15	#include <iomanip>
16	#include <iostream>
17	#include <numeric>
18	#include <random>
19	#include <string>
20	#include <utility>
21	#include <vector>
22	//
23	#if defined(HPX_DEBUG)
24	#define HPX_SORT_BY_KEY_TEST_SIZE (1 << 8)
25	#else
26	#define HPX_SORT_BY_KEY_TEST_SIZE (1 << 18)
27	#endif
28	//
29	#include "sort_tests.hpp"
30	//
31	#define EXTRA_DEBUG
32	//
33	namespace debug {
34	template <typename T>
35	void output(const std::string& name, const std::vector<T>& v)	×
36	{
37	#ifdef EXTRA_DEBUG7
38	std::cout << name.c_str() << "\t : {" << v.size() << "} : ";
39	std::copy(std::begin(v), std::end(v),
40	std::ostream_iterator<T>(std::cout, ", "));
41	std::cout << "\n";
42	#else
43	HPX_UNUSED(name);	×
44	HPX_UNUSED(v);	×
45	#endif
46	}	×
47
48	template <typename Iter>
49	void output(const std::string& name, Iter begin, Iter end)
50	{
51	#ifdef EXTRA_DEBUG
52	std::cout << name.c_str() << "\t : {" << std::distance(begin, end)
53	<< "} : ";
54	std::copy(begin, end,
55	std::ostream_iterator<
56	typename std::iterator_traits<Iter>::value_type>(
57	std::cout, ", "));
58	std::cout << "\n";
59	#else
60	HPX_UNUSED(name);
61	HPX_UNUSED(begin);
62	HPX_UNUSED(end);
63	#endif
64	}
65
66	#if defined(EXTRA_DEBUG)
67	#define debug_msg(a) std::cout << a
68	#else
69	#define debug_msg(a)
70	#endif
71	} // namespace debug
72
73	#undef msg
74	#define msg(a, b, c, d) \
75	std::cout << std::setw(60) << a << std::setw(12) << b << std::setw(40) \
76	<< c << std::setw(30) << std::setw(8) << #d << "\t";
77
78	////////////////////////////////////////////////////////////////////////////////
79	void sort_by_key_benchmark()	1✔
80	{
81	try
82	{
83	const int bench_size = HPX_SORT_BY_KEY_TEST_SIZE * 256;	1✔
84	// vector of values, and keys
85	std::vector<double> values, o_values;	1✔
86	std::vector<int64_t> keys, o_keys;	1✔
87	//
88	values.assign(bench_size, 0);	1✔
89	keys.assign(bench_size, 0);	1✔
90
91	// generate a sequence as the values
92	std::iota(values.begin(), values.end(), 0);	1✔
93	// generate a sequence as the keys
94	std::iota(keys.begin(), keys.end(), 0);	1✔
95
96	// shuffle the keys up,
97	std::random_device rd;	1✔
98	std::mt19937 g(rd());	1✔
99	std::shuffle(keys.begin(), keys.end(), g);	1✔
100
101	// make copies of initial states
102	o_keys = keys;	1✔
103	o_values = values;	1✔
104
105	hpx::chrono::high_resolution_timer t;	1✔
106	hpx::experimental::sort_by_key(	1✔
107	hpx::execution::par, keys.begin(), keys.end(), values.begin());	1✔
108	auto elapsed = static_cast<std::uint64_t>(t.elapsed_nanoseconds());	1✔
109
110	// after sorting by key, the values should be equal to the original keys
111	bool is_equal = std::equal(keys.begin(), keys.end(), o_values.begin());	1✔
112	HPX_TEST(is_equal);	1✔
113	if (is_equal)	1✔
114	{
115	// CDash graph plotting
116	hpx::util::print_cdash_timing("SortByKeyTime", elapsed);	1✔
117	}	1✔
118	}	1✔
119	catch (...)
120	{
121	HPX_TEST(false);	×
122	}	×
123	}	1✔
124
125	////////////////////////////////////////////////////////////////////////////////
126	template <typename ExPolicy, typename Tkey, typename Tval, typename Op,
127	typename HelperOp>
128	void test_sort_by_key1(	522✔
129	ExPolicy&& policy, Tkey, Tval, const Op&, const HelperOp&)
130	{
131	static_assert(hpx::is_execution_policy<ExPolicy>::value,
132	"hpx::is_execution_policy<ExPolicy>::value");
133	msg(typeid(ExPolicy).name(), typeid(Tval).name(), typeid(Op).name(), sync);	522✔
134	std::cout << "\n";	522✔
135
136	// vector of values, and keys
137	std::vector<Tval> values, o_values;	522✔
138	std::vector<Tkey> keys, o_keys;	522✔
139	//
140	values.assign(HPX_SORT_BY_KEY_TEST_SIZE, 0);	522✔
141	keys.assign(HPX_SORT_BY_KEY_TEST_SIZE, 0);	522✔
142
143	// generate a sequence as the values
144	std::iota(values.begin(), values.end(), 0);	522✔
145	// generate a sequence as the keys
146	std::iota(keys.begin(), keys.end(), 0);	522✔
147
148	// shuffle the keys up,
149	std::random_device rd;	522✔
150	std::mt19937 g(rd());	522✔
151	std::shuffle(keys.begin(), keys.end(), g);	522✔
152
153	// make copies of initial states
154	o_keys = keys;	522✔
155	o_values = values;	522✔
156
157	// sort_by_key, blocking when seq, par, par_vec
158	hpx::experimental::sort_by_key(std::forward<ExPolicy>(policy), keys.begin(),	1,044✔
159	keys.end(), values.begin());	522✔
160
161	// after sorting by key, the values should be equal to the original keys
162	bool is_equal = std::equal(keys.begin(), keys.end(), o_values.begin());	522✔
163	if (is_equal)	522✔
164	{
165	//std::cout << "Test Passed\n";
166	}	522✔
167	else
168	{
169	debug::output("keys ", o_keys);	×
170	debug::output("values ", o_values);	×
171	debug::output("key range", keys);	×
172	debug::output("val range", values);	×
173	throw std::string("Problem");	×
174	}
175	HPX_TEST(is_equal);	522✔
176	}	522✔
177
178	////////////////////////////////////////////////////////////////////////////////
179	template <typename ExPolicy, typename Tkey, typename Tval, typename Op,
180	typename HelperOp>
181	void test_sort_by_key_async(	496✔
182	ExPolicy&& policy, Tkey, Tval, const Op&, const HelperOp&)
183	{
184	static_assert(hpx::is_execution_policy<ExPolicy>::value,
185	"hpx::is_execution_policy<ExPolicy>::value");
186	msg(typeid(ExPolicy).name(), typeid(Tval).name(), typeid(Op).name(), async);	496✔
187	std::cout << "\n";	496✔
188
189	// vector of values, and keys
190	std::vector<Tval> values, o_values;	496✔
191	std::vector<Tkey> keys, o_keys;	496✔
192	//
193	values.assign(HPX_SORT_BY_KEY_TEST_SIZE, 0);	496✔
194	keys.assign(HPX_SORT_BY_KEY_TEST_SIZE, 0);	496✔
195
196	// generate a sequence as the values
197	std::iota(values.begin(), values.end(), 0);	496✔
198	// generate a sequence as the keys
199	std::iota(keys.begin(), keys.end(), 0);	496✔
200
201	// shuffle the keys up,
202	std::random_device rd;	496✔
203	std::mt19937 g(rd());	496✔
204	std::shuffle(keys.begin(), keys.end(), g);	496✔
205
206	// make copies of initial states
207	o_keys = keys;	496✔
208	o_values = values;	496✔
209
210	// sort_by_key, blocking when seq, par, par_vec
211	auto fresult =
212	hpx::experimental::sort_by_key(std::forward<ExPolicy>(policy),	992✔
213	keys.begin(), keys.end(), values.begin());	496✔
214	fresult.get();	496✔
215
216	// after sorting by key, the values should be equal to the original keys
217	bool is_equal = std::equal(keys.begin(), keys.end(), o_values.begin());	496✔
218	if (is_equal)	496✔
219	{
220	//std::cout << "Test Passed\n";
221	}	496✔
222	else
223	{
224	debug::output("keys ", o_keys);	×
225	debug::output("values ", o_values);	×
226	debug::output("key range", keys);	×
227	debug::output("val range", values);	×
228	throw std::string("Problem");	×
229	}
230	HPX_TEST(is_equal);	496✔
231	}	496✔
232
233	////////////////////////////////////////////////////////////////////////////////
234	void test_sort_by_key1()	1✔
235	{
236	using namespace hpx::execution;
237	//
238	// run many tests in a loop for N seconds just to play safe
239	//
240	const int seconds = 1;	1✔
241	//
242	hpx::chrono::high_resolution_timer t;	1✔
243	do	1✔
244	{
245	//
246	test_sort_by_key1(seq, int(), int(), std::equal_to<int>(),	58✔
247	[](int key) { return key; });
248	test_sort_by_key1(par, int(), int(), std::equal_to<int>(),	58✔
249	[](int key) { return key; });
250	test_sort_by_key1(par_unseq, int(), int(), std::equal_to<int>(),	58✔
251	[](int key) { return key; });
252	//
253	test_sort_by_key1(seq, int(), double(), std::equal_to<double>(),	58✔
254	[](int key) { return key; });
255	test_sort_by_key1(par, int(), double(), std::equal_to<double>(),	58✔
256	[](int key) { return key; });
257	test_sort_by_key1(par_unseq, int(), double(), std::equal_to<double>(),	58✔
258	[](int key) { return key; });
259	// custom compare
260	test_sort_by_key1(	58✔
261	seq, double(), double(),
262	[](double a, double b) {
263	return std::floor(a) == std::floor(b);
264	}, //-V550
265	[](double a) { return std::floor(a); });
266	test_sort_by_key1(	58✔
267	par, double(), double(),
268	[](double a, double b) {
269	return std::floor(a) == std::floor(b);
270	}, //-V550
271	[](double a) { return std::floor(a); });
272	test_sort_by_key1(	58✔
273	par_unseq, double(), double(),
274	[](double a, double b) {
275	return std::floor(a) == std::floor(b);
276	}, //-V550
277	[](double a) { return std::floor(a); });
278	} while (t.elapsed() < seconds);	58✔
279	//
280	hpx::chrono::high_resolution_timer t2;	1✔
281	do	1✔
282	{
283	test_sort_by_key_async(seq(task), int(), int(), std::equal_to<int>(),	124✔
284	[](int key) { return key; });
285	test_sort_by_key_async(par(task), int(), int(), std::equal_to<int>(),	124✔
286	[](int key) { return key; });
287	//
288	test_sort_by_key_async(seq(task), int(), double(),	124✔
289	std::equal_to<double>(), [](int key) { return key; });
290	test_sort_by_key_async(par(task), int(), double(),	124✔
291	std::equal_to<double>(), [](int key) { return key; });
292	} while (t2.elapsed() < seconds);	124✔
293	}	1✔
294
295	////////////////////////////////////////////////////////////////////////////////
296	int hpx_main(hpx::program_options::variables_map& vm)	1✔
297	{
298	unsigned int seed = (unsigned int) std::time(nullptr);	1✔
299	if (vm.count("seed"))	1✔
300	seed = vm["seed"].as<unsigned int>();	×
301
302	std::cout << "using seed: " << seed << std::endl;	1✔
303	std::srand(seed);	1✔
304
305	test_sort_by_key1();	1✔
306	sort_by_key_benchmark();	1✔
307
308	return hpx::local::finalize();	1✔
309	}	×
310
311	int main(int argc, char* argv[])	1✔
312	{
313	// add command line option which controls the random number generator seed
314	using namespace hpx::program_options;
315	options_description desc_commandline(	1✔
316	"Usage: " HPX_APPLICATION_STRING " [options]");	1✔
317
318	desc_commandline.add_options()("seed,s", value<unsigned int>(),	1✔
319	"the random number generator seed to use for this run");
320
321	// By default this test should run on all available cores
322	std::vector<std::string> const cfg = {"hpx.os_threads=all"};	1✔
323
324	hpx::local::init_params init_args;	1✔
325	init_args.desc_cmdline = desc_commandline;	1✔
326	init_args.cfg = cfg;	1✔
327
328	HPX_TEST_EQ_MSG(hpx::local::init(hpx_main, argc, argv, init_args), 0,	1✔
329	"HPX main exited with non-zero status");
330
331	return hpx::util::report_errors();	1✔
332	}	1✔

STEllAR-GROUP / hpx / #856

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous