You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The behaviour of the .reserve_at_least is much better asymptotically, since calling .reserve in a loop will cause quadratic behaviour. We should be using the short method name to encourage the faster behaviour.
.reserve(n) allocates exactly enough capacity to store n elements (if there isn't enough space already), while .reserve_at_least(n) will ensure that there is enough space, but overallocate to ensure that reallocations don't occur too often (i.e. increase the allocation size exponentially).
e.g. imagine a protocol which consists of a sets of messages, where set block as an initial message with the count for that set:
let received = ~[];letmut total_messages = 0;while listener.more_messages(){let next_count = listener.recv();
total_messages += next_count;// we know how many we're going to have total, so// might as well allocate it up-front.
received.reserve(total_messages);for _ inrange(0, next_count){
received.push(listener.recv());}}
using (the current) .reserve causes every single set to do a reallocation and memcpy (i.e. O(n^2) behaviour), while using .reserve_at_least would mean the reallocation and memcpy only happens logarithmically often, preserving O(n) asymptotics.
(For vector specifically the above should really be using .reserve_additional, but other types like ~str and extra::{priority_queue, ring_buf} suffer the same problem.)
The text was updated successfully, but these errors were encountered:
`.reserve_exact` can cause pathological O(n^2) behaviour, so providing a
`.reserve` that ensures that capacity doubles (if you step 1, 2, ..., n)
is more efficient.
cc rust-lang#11949
`.reserve_exact` can cause pathological O(n^2) behaviour, so providing a
`.reserve` that ensures that capacity doubles (if you step 1, 2, ..., n)
is more efficient.
cc rust-lang#11949
flip1995
pushed a commit
to flip1995/rust
that referenced
this issue
Dec 16, 2023
Add `blyxyas` to `users_on_vacation`
I have a surgery this Wednesday, so I won't be able to review anything from that day up to (at least) Dec. 22, I'll open another PR by then.
I'm not sure if `users_on_vacation` will work here, if it doesn't work, I'll just remove myself from the reviewer rotation
changelog:none
The behaviour of the
.reserve_at_least
is much better asymptotically, since calling.reserve
in a loop will cause quadratic behaviour. We should be using the short method name to encourage the faster behaviour..reserve(n)
allocates exactly enough capacity to storen
elements (if there isn't enough space already), while.reserve_at_least(n)
will ensure that there is enough space, but overallocate to ensure that reallocations don't occur too often (i.e. increase the allocation size exponentially).e.g. imagine a protocol which consists of a sets of messages, where set block as an initial message with the count for that set:
using (the current)
.reserve
causes every single set to do a reallocation andmemcpy
(i.e. O(n^2) behaviour), while using.reserve_at_least
would mean the reallocation and memcpy only happens logarithmically often, preserving O(n) asymptotics.(For vector specifically the above should really be using
.reserve_additional
, but other types like~str
andextra::{priority_queue, ring_buf}
suffer the same problem.)The text was updated successfully, but these errors were encountered: