Hi Arthur and std-proposals,
My reply with the updated proposal
version is a bit late. I'm sorry for that, but I needed some time to thoroughly verify my benchmarking.
Unfortunately, careful measurements showed that the
performance does not change noticeably (falling within noise levels for most types), at least on my benchmarking sets. However, there is a consistent
generated code size reduction across all benchmarks which even allows inlining for some complex types. I've reflected these updated findings in the 'Benchmarks' sections. I've also addressed the review comments.
Please find the updated proposal attached. Thank you for your review and any comments in advance.
---
Best regards,
Aleksei Sidorin.
Hi Alexey,
Sorry for the belated reply. :)
(1) I'd like to see the benchmarks sections rearranged so that the
differences between runs are legible. Right now you have them not even on
the same page; it's like
> (page 5)
> uint32_1 3.51 ns 3.51 ns 199491584
> uint32_4 3.73 ns 3.73 ns 187170816
> uint32_16 8.65 ns 8.65 ns 81002496
> (page 6)
> uint32_1 3.61 ns 3.60 ns 193462272
> uint32_4 3.56 ns 3.56 ns 196870144
> uint32_16 8.57 ns 8.57 ns 81788928
What I'd like to see is: Instead of two numbers "Time" and "CPU" in each
row, show me two numbers "CPU before" and "CPU after". And instead of
"Iterations," which I don't care about, show me "Ratio" — i.e. "After"
divided by "Before," so that lower numbers are better.
(2) I'd like the paper to contain a little section on naming. What verbs
were considered, and why were "displace" and "remove" chosen? Why does
"pq.displace_top()" conserve the number of live objects but
"std::displace_heap" leave an extra object in a moved-from state? This
section needn't be long, and it probably *shouldn't* be phrased as a
question to LEWG; it should simply explain the reasons these names were
considered good, and at least one reason why other plausible names were
considered bad.
I know you and I specifically have had the naming discussion already, so I
assume I should like the names you chose. But I'm not sure I remember *why*
I liked them. Remind me, in the paper. ;) I do recall that
"std::remove_heap" leaves the tail in a moved-from state analogously to
"std::remove" and "std::remove_if". I *don't* recall whether we considered
"std::shift_heap", since std::shift_{left,right} are also algorithms that
produce moved-from tails.
(3) The one place you say "unspecified state" I think you should say
"moved-from state." Not only is that clearer, I think we actually intend to
*guarantee* that (for types like unique_ptr whose moved-from state is not
unspecified).
(4) Stylistically, I think "Technical specification" should be called
"Proposed wording" and should come last in the paper (before
"Acknowledgments" but after "Benchmarks"), to make it easy to find and to
scroll to. I'd also rename "Reference implementation" to "Implementation
experience."
(5) I'm sure we've discussed this already, but I'd like to see some
discussion preserved in the paper.— `pq.displace_top()` could be (thought
of / implemented) as either your
T t = std::displace_heap(c.begin(), c.end()); c.pop_back(); return t;
or my own fork's
std::pop_heap(c.begin(), c.end()); return c.displace_back();
The latter works even for "relocate-only types," i.e., it does not require
T to have a moved-from state. But it depends on e.g. `vector` to have a
`displace_back()` method, and just generally is more invasive than your
proposal. Your proposal (the former) requires T to have a moved-from state,
but is much less invasive and thus much more achievable politically. I
believe we also examined the operations involved and decided that the
former was actually more efficient (required fewer operations), but I don't
remember the details. It would be nice to have this analysis preserved in
the paper. The analysis might usefully end with a reassuring assertion such
as "A sufficiently smart implementation might use either algorithm, since
they produce the same results for value-semantic types." In fact, you could
even link to Giuseppe D'Angelo's paper P4102R0 "Container insertion and
erasure should be allowed to relocate"
<https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2026/p4102r0.html> in
the just-released April mailing!
Cheers and HTH,
–Arthur
On Sun, Mar 8, 2026 at 5:26 PM Alexey Sidorin <alexey.v.sidorin_at_[hidden]>
wrote:
> Hello again.
> Sorry for a long delay, but it took me some time to update the document
> and the reference implementation. But finally, there is an update.
> 1. extract_heap_top() renamed to displace_top()
> 2. Added remove_heap function
> 3. Changed pop_heap wording (remove_heap() + pop_back())
> 4. Added benchmark results for `pop_heap() + pop_back()` against
> `remove_heap() + pop_back()`. I wished to recheck my claim about potential
> performance improvements.
> 5. Added motivation for adding freestanding functions
> 6. Different minor improvements.
>
> Thank you in advance.
>
> ---
> Best regards,
> Aleksei Sidorin.