Does bulk memmove speed up std:remove_if? (No.)
The article discusses the performance implications of using bulk memmove in the std::remove_if algorithm. It argues that while chunking writes may seem beneficial, it can actually lead to worse performance due to increased bookkeeping and overhead. Benchmark results indicate that the traditional smooth_remove_if implementation outperforms the chunky_remove_if in various scenarios.
- ▪The proposed chunky_remove_if algorithm aims to optimize the removal of elements by using memmove for contiguous writes.
- ▪Benchmarking shows that chunky_remove_if performs worse than the traditional smooth_remove_if, even when designed to favor its strengths.
- ▪The performance penalty of chunky_remove_if increases as fewer elements are removed, suggesting inefficiencies in its design.
Opening excerpt (first ~120 words) tap to expand
Does bulk memmove speed up std::remove_if? (No.) This morning I was reading the umpteenth std-proposals thread proposing some variety of unstable_remove and it occurred to me that one odd thing about a swap-and-pop-based unstable_remove is that it tends to replace large swaths of contiguous removals by reversing the elements that are kept. For example (Godbolt): template<class BidirIt, class Pred> BidirIt unstable_remove_if(BidirIt first, BidirIt last, Pred pred) { while (true) { first = std::find_if(first, last, pred); if (first == last) return first; while (true) { --last; if (first == last) return first; if (!pred(*last)) break; } *first++ = std::move(*last); } } int main() { auto in234 = [](int x) { return 2 <= x && x <= 4; }; std::vector<int> v = {1,2,3,4,5,6,7,8,9};…
Excerpt limited to ~120 words for fair-use compliance. The full article is at Arthur O’Dwyer.
Discussion
0 commentsMore from Arthur O’Dwyer
