N Different Ways to
Filter Containers in
Modern C++
Raw loops, algorithms, Concepts, Ranges and Parallel
Algorithms
Bartłomiej Filipek, 20th May 2021, cppstories.com
About Me
•
Author of cppstories.com
o
previously bfilipek.com, since ~2011
•
~14y professional coding experience
•
Microsoft MVP, since 2018
•
C++ ISO Member
•
@Xara.com since 2014
o
Mostly text related features for advanced
document editors
•
Somehow addicted to C++
3
The plan
•
The problem
•
Raw loops
•
Adding algorithms
•
C++20
o
Erase if, Concepts, Ranges, Going More Generic
•
Throwing some threads
•
Bonus Slide
4
The problem statement
// pseudocode
Container Filter(const Container& cont, UnaryPredicate p);
const std::vector<std::string> vec{ "Hello", "**txt",
"World", "error",
"warning", "C++", "****" };
auto filtered = Filter(vec, [](auto& elem) {
return !elem.starts_with('*');
});
// filtered should have "Hello", "World", "error", "warning", "C++"
5
Good old raw loops
template <typename T, typename Pred>
auto FilterRaw(const std::vector<T>& vec, Pred p) {
std::vector<T> out;
for (const auto& elem : vec)
if (p(elem))
out.push_back(elem);
return out;
}
template <typename T, typename Pred>
std::vector<T> FilterRawOld(const std::vector<T>& vec, Pred p) {
std::vector<T> out;
for (typename std::vector<T>::const_iterator it = begin(vec); it != end(vec); ++it)
if (p(*it))
out.push_back(*it);
return out;
}
6
Adding some algorithms
template <typename T, typename Pred>
auto FilterCopyIf(const std::vector<T>& vec, Pred p) {
std::vector<T> out;
std::copy_if(begin(vec), end(vec), std::back_inserter(out), p);
return out;
}
template <typename T, typename Pred>
auto FilterCopyIf(const std::vector<T>& vec, Pred p) {
std::vector<T> out;
std::remove_copy_if(begin(vec), end(vec),
std::back_inserter(out), std::not_fn(p));
return out;
}
C++17
7
Remove Erase
template <typename T, typename Pred>
auto FilterRemoveErase(const std::vector<T>& vec, Pred p) {
auto out = vec;
out.erase(std::remove_if(begin(out), end(out), std::not_fn(p)), end(out));
return out;
}
8
C++20 Erase!
template <typename T, typename Pred>
auto FilterEraseIf(const std::vector<T>& vec, Pred p) {
auto out = vec;
std::erase_if(out, std::not_fn(p));
return out;
}
9
Ranges
template <typename T, typename Pred>
auto FilterRangesCopyIf(const std::vector<T>& vec, Pred p) {
std::vector<T> out;
std::ranges::copy_if(vec, std::back_inserter(out), p);
return out;
}
auto FilterWithRanges(const std::vector<T>& vec, Pred p) {
return vec | std::views::filter(p) | ranges::to<std::vector<T>>;
}
10
More Generic
template <typename TCont, typename Pred>
auto FilterEraseIfGen(const TCont& cont, Pred p) {
auto out = cont;
std::erase_if(out, std::not_fn(p));
return out;
}
template <typename TCont, typename Pred>
auto FilterRangesCopyIfGen(const TCont& vec, Pred p) {
TCont out;
std::ranges::copy_if(vec, std::back_inserter(out), p);
return out;
}
11
More Generic v2
template <typename TCont, typename Pred>
auto FilterCopyIfGen(const TCont& cont, Pred p) {
TCont out;
if constexpr(has_push_back<TCont>)
std::copy_if(begin(cont), end(cont), std::back_inserter(out), p);
else
std::copy_if(begin(cont), end(cont), std::inserter(out, out.begin()), p);
return out;
}
12
Adding concepts
template <typename T, typename Pred>
auto FilterCopyIfConcepts(const std::vector<T>& vec, Pred p) {
std::vector<T> out;
std::copy_if(begin(vec), end(vec), std::back_inserter(out), p);
return out;
}
std::predicate<Pred, const T&>
13
Throwing some threads
std::execution::seq
sequential
std::execution::par
parallel, possibly on a system thread pool
std::execution::par_unseq
parallel with also ability to use vector
instructions (like SSE, AVX)
std::execution::unseq
vector instructions (C++20)
14
Naive approach
template <typename T, typename Pred>
auto FilterCopyIfParNaive(const std::vector<T>& vec, Pred p) {
std::vector<T> out;
std::mutex mut;
std::for_each(std::execution::par, begin(vec), end(vec),
[&out, &mut, p](auto&& elem) {
if (p(elem)) {
std::unique_lock lock(mut);
out.push_back(elem);
}
});
return out;
}
15
Naive approach
// 6 cores / 12 threads
benchmark vec size: 100000
transform only seq : 2.223 ms, ret: 100000
transform only par : 0.5507 ms, ret: 100000
FilterCopyIf : 3.851 ms, ret: 50203
FilterCopyIfParNaive : 10.1295 ms, ret: 50203
only 3X slower :)
std::vector<std::pair<double, double>>
testVec(VEC_SIZE);
17
Results
// 6 cores / 12 threads
benchmark vec size: 100000
transform only seq : 2.3379 ms, ret: 100000
transform only par : 0.5979 ms, ret: 100000
FilterCopyIf : 3.675 ms, ret: 50203
FilterCopyIfParNaive : 10.0073 ms, ret: 50203
FilterCopyIfParCompose : 1.2936 ms, ret: 50203
FilterCopyIfParComposeSeq : 1.0754 ms, ret: 50203
FilterCopyIfParTransformPush: 2.0103 ms, ret: 50203
FilterCopyIfParChunks : 2.0974 ms, ret: 50203
FilterCopyIfParChunksFuture : 1.9456 ms, ret: 50203
~2.7x speedup!
even better with
sequential “merge”
divide and work in
chunks
18
Results, bigger size
// 6 cores / 12 threads
benchmark vec size: 1000000
transform only seq : 24.7731 ms, ret: 1000000
transform only par : 2.8692 ms, ret: 1000000
FilterCopyIf : 35.6397 ms, ret: 499950 // base line
FilterCopyIfParNaive : 102.079 ms, ret: 499950
FilterCopyIfParCompose : 9.3953 ms, ret: 499950
FilterCopyIfParComposeSeq : 9.9909 ms, ret: 499950
FilterCopyIfParTransformPush: 13.9003 ms, ret: 499950
FilterCopyIfParChunks : 13.2688 ms, ret: 499950
FilterCopyIfParChunksFuture : 12.6284 ms, ret: 499950
19
Summary
// benchmark vec size: 1000000, VS2019, 4 cores
FilterCopyIfParComposeSeq 21.4029
FilterCopyIfParCompose 24.5993
FilterCopyIfParChunksFuture 30.3935
FilterCopyIfParChunks 30.4579
FilterCopyIfParTransformPush 31.1474
FilterEraseIfGen 48.5937
FilterRemoveErase 48.6897
FilterEraseIf 48.7276
FilterRangesCopyif 55.3421
FilterRemoveCopyIf 55.7044
FilterRangesCopyIfGen 55.8806
FilterCopyIfConcepts 55.9158
FilterCopyIf 56.0549
FilterRaw 57.1189
FilterCopyIfGen 58.2821
FilterRawOld 59.0925
FilterCopyIfParNaive 86.3884
20
Bonus
•
C++20 - published!
•
C++23 ongoing
o
Herb Sutter: Trip report: Winter 2021 ISO C++ standards
meeting (virtual)
o
Five Awesome C++ Papers for the Q1 2021 and C++23 Status
•
Lots of online talks
o
Online C++ User Group Meetings in May 2021
o
Meeting C++ online