rust/library/alloc/src/collections/binary_heap, branch tryhttps://github.com/rust-lang/rust
http://git.dreamy.place/mirrors/rust/atom?h=try2025-03-12T07:06:46+00:00Rollup merge of #138161 - HeroicKatora:heap-peek-mut-refresh, r=dtolnay2025-03-12T07:06:46+00:00Matthias Krüger476013+matthiaskrgr@users.noreply.github.com2025-03-12T07:06:46+00:00urn:sha1:4198902e9a7648e4445ab73fdc129231afc33b40
Add PeekMut::refresh
I'm not sure if this should go through ACP or not. BinaryHeap is not the most critical data structure in the standard library and it would be understandable if maintainer throughput is thus too limited to accept this PR without a proper design phase that ensures the required understanding of consequence over a longer time period.
This aims to improve the useability of heaps for priority-based work queues. In certain scenarios, modifications on the most relevant or critical items are performed until a condition that determines the work items have been sufficiently addressed. For instance the criticality could be a deadline that is relaxed whenever some part of a work item is completed. Such a loop will repeatedly access the most critical item and put it back in a sorted position when it is complete. Crucially, due to the ordering invariant we know that all necessary work was performed when the completed item remains the most critical. Getting this information from the heap position avoids a (potentially more costly) check on the item state itself.
A customized `drop` with boolean result would avoid up to two more comparisons performed in both the last no-op refresh and Drop code but this occurs once in each execution of the above scenario whereas refresh occurs any number of times. Also note that the comparison overhead of Drop is only taken if the element is mutably inspected to determine the end condition, i.e. not when refresh itself is the break condition.
Add PeekMut::refresh2025-03-11T14:58:00+00:00Aurelia Molzer5550310+HeroicKatora@users.noreply.github.com2025-03-07T13:38:08+00:00urn:sha1:436959e3f710d3161093bfa183e3c5deceff7ccf
This improves the useability of heaps for priority-based work queues. In
certain scenarios, modifications on the most relevant or critical items are
performed until a condition that determines the work items have been
sufficiently addressed. The loop will repeatedly access the most critical
item and put it back in a sorted position when it is complete. Crucially,
due to the ordering invariant we know that all work was performed when the
completed item remains the most critical. Getting this information from the
heap position avoids a (potentially more costly) check on the item state
itself.
A customized `drop` with boolean result would avoid up to two more
comparisons performed in both the last no-op refresh and Drop code but this
occurs once in each execution of the above scenario whereas refresh occurs
any number of times. Also note that the comparison overhead of Drop is only
taken if the element is mutably inspected to determine the end condition,
i.e. not when refresh itself is the break condition.
Fully test the alloc crate through alloctests2025-03-07T19:11:13+00:00bjorn317426603+bjorn3@users.noreply.github.com2025-02-06T12:46:33+00:00urn:sha1:ae5687e4b0a375d3307856fb81810f6cc9019be5
For the tests that make use of internal implementation details, we
include the module to test using #[path] in alloctests now.
Less unwrap() in documentation2024-12-21T01:26:47+00:00Kornelkornel@geekhood.net2024-12-20T17:02:46+00:00urn:sha1:7b42bc0c7935e9f5fefd017249041d64f27bb583Move some alloc tests to the alloctests crate2024-12-04T14:32:04+00:00bjorn317426603+bjorn3@users.noreply.github.com2024-12-04T14:26:18+00:00urn:sha1:b440ef8cdf029476d84e6ce8841f1e549d60998f
Unit tests directly inside of standard library crates require a very
fragile way of building that is hard to reproduce outside of bootstrap.
get rid of a bunch of unnecessary rustc_const_unstable2024-11-30T10:55:58+00:00Ralf Jungpost@ralfj.de2024-11-30T09:33:09+00:00urn:sha1:4ce2116aef0677c6f59890d9bd3acea890fa5cbbAlso use zero when referencing to capacity or length2024-11-28T08:47:11+00:00timviseetim@visee.me2024-11-28T08:46:26+00:00urn:sha1:89b20e95fd6cb6e976692505ca4ee74e2df3f028library: consistently use American spelling for 'behavior'2024-10-25T10:02:47+00:00Ralf Jungpost@ralfj.de2024-10-25T10:01:08+00:00urn:sha1:854e3c43e005c992542a80bea9bbe16230470362Avoid emptiness check in `PeekMut::pop`2024-10-03T14:15:52+00:00EFanZhefanzh@gmail.com2024-10-03T14:15:52+00:00urn:sha1:d47e388843f682f57262f020edd9909c850a0c49Reformat using the new identifier sorting from rustfmt2024-09-22T23:11:29+00:00Michael Gouletmichael@errs.io2024-09-22T23:05:04+00:00urn:sha1:c682aa162b0d41e21cc6748f4fecfe01efb69d1f