| Issue |
208299
|
| Summary |
[libc++] Optimize the is_heap algorithm
|
| Labels |
libc++,
performance
|
| Assignees |
philnik777
|
| Reporter |
ldionne
|
As explained in this blog post, it seems that we can easily implement `is_heap` more efficiently than we currently do: https://quuxplusone.github.io/blog/2026/05/11/is-heap
It's not really a fundamentally different algorithm, but merely a rewrite from indices to advancing iterators linearly. Partial implementation from the blog post:
```c++
template <class _Compare, class _ForwardIterator, class _Sentinel>
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator
__is_heap_until(_ForwardIterator __first, _Sentinel __last, _Compare&& __comp) {
_ForwardIterator __child = __first;
if (__child == __last) {
return __child;
}
while (true) {
++__child;
if (__child == __last || __comp(*__first, *__child))
break;
++__child;
if (__child == __last || __comp(*__first, *__child))
break;
++__first;
}
return __child;
}
```
The post reports significant (-10% to -40%) speedups, so it's worth investigating, especially since it's so easy.
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
