<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/208299>208299</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [libc++] Optimize the is_heap algorithm
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            libc++,
            performance
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
            philnik777
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          ldionne
      </td>
    </tr>
</table>

<pre>
    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.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJy8VMFupDgQ_Rr3pZQWmAa6DxwICdqWdifRZA65IQNFUzvGZm2TTO_Xrwx0ujOz2uNKlgBT9d6rsusJa-mkEDMW3zPOx56kou9pmjLOWfywEZPrtclkS1op3NS6PWe5BfwxSkEKWyAFricLtdQnGLV1jBdADiziYMH1wsE7QiMUoLAkz0DDKHFA5YAlAdmqRzGyJIBBGwTsOmoIlZNnn6vm3MmYZafVLMqhd260LMoZLxkv_5qmH6OcrFa4PZHrp3pLmvHS62G85AFPGC-DmPEyDBkvyd7NjEHOgvzoGE8tKO3AoJDyDAK6SbXC65u_W-o69PQg5Ekbcv3gC6wnBwManDMMvhtyCJ3RA5BqqUELToNo34RqSJ2AHBrhtLEgSaEw8ryFZ2EcCXnth3Ck1QLierxpaJQvalkSLKth_N6vIHc4jFI4BBYVjRTWQlXoYRQGvcp1p9TmXZj2uIq4-fOCypFCyaJHFuTV78f74vm5-u348FiVX5_-qPL7I1x2i6cvL98eX5-_Vi_HL8VjVby-8uBX8CCvqvVUq0k5kozvfw6CqurILFflQwNUlRTr3kcNCeMJVFWjh5HxA7DUFw2_sPqQnmQLLHr4AI-WWOrAS7gGLDEL1xUSwKCbjLpAXdJZ-jA_33uS6JGcmfBz4nIaP-X9JzGwtGBp8VHZnvH8pifz14LGD34tgAC1QfF9ZfhfWG8Jbyr91OBLh_6tf8u_j4u73ONvPc4XGwyO2jgL3oKoo0Z4U-D7uzBgPPYTdLfzb77bdkRsp9F6oVYDLYP7ro3rgdQbWkcn4UidfADaERua59eSavASbrU3ofN202ZRe4gOYoNZmO6jODrwiG_6LI32O86TNOy6pI52XZTgPmx2XR3HbS0SvqHMG0qQBvvwEEUx36aHMKlFjRiFYRzwiO0CHATJrZRvw1ab04asnTDjwZ4fDhspapR2NVtJ9WWSOWe88P6LptNmEKrB1YBN5pHu6ulk2S6QZJ29YjtycrbuG6j4AZ5GRwP9jbOPrMN49a_NZGT22URX42z0wHjp0dfH3Wj0n9i42TfthHZ21LmSt4z_EwAA__-_Z_Xh">