1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
/** Copyright (C) 2021 Ultimaker - Released under terms of the AGPLv3 License */
#ifndef UTILS_ALGORITHM_H
#define UTILS_ALGORITHM_H
#include <algorithm>
#include <atomic>
#include <functional>
#include <future>
#include <numeric>
#include <vector>
// extensions to algorithm.h from the standard library
namespace cura
{
/*!
* Get the order of a vector: the sorted indices of a vector
*
* {1.6, 1.8, 1.7} returns {1, 3, 2} meaning {in[1], in[3], in[2]} is a sorted
* vector
*
* Thanks to Lukasz Wiklendt
*
* \param in The vector for which to get the order
* \return An ordered vector of indices into \p in
*/
template<typename T>
std::vector<size_t> order(const std::vector<T> &in)
{
// initialize original index locations
std::vector<size_t> order(in.size());
std::iota(order.begin(), order.end(), 0); // fill vector with 1, 2, 3,.. etc
// sort indexes based on comparing values in v
std::sort(order.begin(), order.end(),
[&in](size_t i1, size_t i2)
{
return in[i1] < in[i2];
}
);
return order;
}
/* An implementation of parallel for.
* There are still a lot of compilers that claim to be fully C++17 compatible, but don't implement the Parallel Execution TS of the accompanying standard lybrary.
* This means that we moslty have to fall back to the things that C++11/14 provide when it comes to threading/parallelism/etc.
*
* \param from The index starts here (inclusive).
* \param to The index ends here (not inclusive).
* \param increment Add this to the index each time.
* \param body The loop-body, as a closure. Receives the index on invocation.
*/
template<typename T>
void parallel_for(T from, T to, T increment, const std::function<void(const T)>& body)
{
// Sanity tests.
assert(increment > 0);
assert(from <= to);
// Set the values so that 'to' is a whole integer multiple apart from 'from' (& early out if needed).
to = from + increment * (((to - from) + (increment - static_cast<T>(1))) / increment);
if (to == from)
{
return;
}
// Set an atomic countdown variable to how many tasks need to be completed.
std::atomic<T> tasks_pending((to - from) / increment);
// Wrap the loop-body, so that the outer scope can be notified by 'all_tasks_done'.
std::promise<void> all_tasks_done;
const auto func =
[&body, &tasks_pending, &all_tasks_done](const T index)
{
body(index);
if (--tasks_pending == 0)
{
all_tasks_done.set_value();
}
};
// Run all tasks.
for (size_t index = from; index != to; index += increment)
{
std::async(std::launch::async, func, index);
}
// Wait for the end-result before return.
all_tasks_done.get_future().wait();
}
} // namespace cura
#endif // UTILS_ALGORITHM_H
|
