Std: Is_heap Could Be Faster
The article discusses potential inefficiencies in the implementation of std::is_heap in C++ standard libraries, noting that it unnecessarily requires random access iterators despite being implementable with forward traversal. A proposed alternative implementation reduces redundant arithmetic and improves performance in benchmarks. The author highlights that major standard library implementations, including libc++, libstdc++, and MS STL, exhibit similar inefficiencies.
- ▪std::is_heap currently requires random_access_range, even though it could work with forward traversal.
- ▪A more efficient implementation using forward iterators reduces redundant arithmetic operations.
- ▪Benchmark results show performance improvements of up to 39% after optimizing the function.
Opening excerpt (first ~120 words) tap to expand
std::is_heap could be faster The other day I was noodling around with some libc++ unit-test code that looked roughly like this (Godbolt): template<class A> auto extract_container(A& a) { struct UnwrapAdaptor : A { A::container_type& cc = A::c; }; return UnwrapAdaptor(a).cc; } template<class Adaptor> void test_push_range(bool is_heapified) { int in1[] = {1,3,7}; int in2[] = {2,4,5,6}; int expected[] = {1,3,7,2,4,5,6}; Adaptor a; a.push_range(in1); a.push_range(in2); if (auto c = extract_container(a); is_heapified) { assert(std::ranges::is_heap(c)); assert(std::ranges::is_permutation(c, expected)); } else { assert(std::ranges::equal(c, expected)); } } int main() { test_push_range<std::stack<int>>(false); test_push_range<std::queue<int>>(false);…
Excerpt limited to ~120 words for fair-use compliance. The full article is at Arthur O’Dwyer.
Discussion
0 commentsMore from Arthur O’Dwyer
