Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

TryVec::try_push is linear, not amortized constant time like Vec::push #22

Closed
saethlin opened this issue Aug 15, 2021 · 1 comment · Fixed by #28
Closed

TryVec::try_push is linear, not amortized constant time like Vec::push #22

saethlin opened this issue Aug 15, 2021 · 1 comment · Fixed by #28

Comments

@saethlin
Copy link

This makes TryVec arbitrarily slower than Vec, unless you reserve for enough space to never exceed capacity. The performance difference was pointed out to me with these benchmarks: https://gist.github.com/meowjesty/c41b24d15c5cba68723e2ab4920ebde0

Here's a demo of the reallocation behavior:

//! ```cargo
//! [dependencies]
//! env_logger = "=0.9.0"
//! logging-allocator = "=0.1.1"
//! ```

use logging_allocator::LoggingAllocator;

#[global_allocator]
static ALLOC: LoggingAllocator = LoggingAllocator::new();

fn main() {
    env_logger::init();
    ALLOC.enable_logging();

    let mut v = Vec::new();
    for i in 0..100 {
        v.push(i as u8);
    }

    let mut v = fallible_collections::vec::TryVec::new();
    for i in 0..100 {
        v.push(i as u8).unwrap();
    }
}
Output

[2021-08-15T04:48:45Z TRACE logging_allocator] alloc [address=0x55e25a92daf0, size=8, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=8, align=1] to [address=0x55e25a92daf0, size=16, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=16, align=1] to [address=0x55e25a92de40, size=32, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92de40, size=32, align=1] to [address=0x55e25a92de40, size=64, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92de40, size=64, align=1] to [address=0x55e25a92de40, size=128, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] alloc [address=0x55e25a92daf0, size=1, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=1, align=1] to [address=0x55e25a92daf0, size=2, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=2, align=1] to [address=0x55e25a92daf0, size=3, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=3, align=1] to [address=0x55e25a92daf0, size=4, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=4, align=1] to [address=0x55e25a92daf0, size=5, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=5, align=1] to [address=0x55e25a92daf0, size=6, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=6, align=1] to [address=0x55e25a92daf0, size=7, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=7, align=1] to [address=0x55e25a92daf0, size=8, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=8, align=1] to [address=0x55e25a92daf0, size=9, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=9, align=1] to [address=0x55e25a92daf0, size=10, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=10, align=1] to [address=0x55e25a92daf0, size=11, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=11, align=1] to [address=0x55e25a92daf0, size=12, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=12, align=1] to [address=0x55e25a92daf0, size=13, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=13, align=1] to [address=0x55e25a92daf0, size=14, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=14, align=1] to [address=0x55e25a92daf0, size=15, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=15, align=1] to [address=0x55e25a92daf0, size=16, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=16, align=1] to [address=0x55e25a92daf0, size=17, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=17, align=1] to [address=0x55e25a92daf0, size=18, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=18, align=1] to [address=0x55e25a92daf0, size=19, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=19, align=1] to [address=0x55e25a92daf0, size=20, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=20, align=1] to [address=0x55e25a92daf0, size=21, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=21, align=1] to [address=0x55e25a92daf0, size=22, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=22, align=1] to [address=0x55e25a92daf0, size=23, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=23, align=1] to [address=0x55e25a92daf0, size=24, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92daf0, size=24, align=1] to [address=0x55e25a92ded0, size=25, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=25, align=1] to [address=0x55e25a92ded0, size=26, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=26, align=1] to [address=0x55e25a92ded0, size=27, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=27, align=1] to [address=0x55e25a92ded0, size=28, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=28, align=1] to [address=0x55e25a92ded0, size=29, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=29, align=1] to [address=0x55e25a92ded0, size=30, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=30, align=1] to [address=0x55e25a92ded0, size=31, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=31, align=1] to [address=0x55e25a92ded0, size=32, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=32, align=1] to [address=0x55e25a92ded0, size=33, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=33, align=1] to [address=0x55e25a92ded0, size=34, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=34, align=1] to [address=0x55e25a92ded0, size=35, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=35, align=1] to [address=0x55e25a92ded0, size=36, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=36, align=1] to [address=0x55e25a92ded0, size=37, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=37, align=1] to [address=0x55e25a92ded0, size=38, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=38, align=1] to [address=0x55e25a92ded0, size=39, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=39, align=1] to [address=0x55e25a92ded0, size=40, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=40, align=1] to [address=0x55e25a92ded0, size=41, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=41, align=1] to [address=0x55e25a92ded0, size=42, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=42, align=1] to [address=0x55e25a92ded0, size=43, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=43, align=1] to [address=0x55e25a92ded0, size=44, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=44, align=1] to [address=0x55e25a92ded0, size=45, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=45, align=1] to [address=0x55e25a92ded0, size=46, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=46, align=1] to [address=0x55e25a92ded0, size=47, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=47, align=1] to [address=0x55e25a92ded0, size=48, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=48, align=1] to [address=0x55e25a92ded0, size=49, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=49, align=1] to [address=0x55e25a92ded0, size=50, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=50, align=1] to [address=0x55e25a92ded0, size=51, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=51, align=1] to [address=0x55e25a92ded0, size=52, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=52, align=1] to [address=0x55e25a92ded0, size=53, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=53, align=1] to [address=0x55e25a92ded0, size=54, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=54, align=1] to [address=0x55e25a92ded0, size=55, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=55, align=1] to [address=0x55e25a92ded0, size=56, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=56, align=1] to [address=0x55e25a92ded0, size=57, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=57, align=1] to [address=0x55e25a92ded0, size=58, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=58, align=1] to [address=0x55e25a92ded0, size=59, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=59, align=1] to [address=0x55e25a92ded0, size=60, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=60, align=1] to [address=0x55e25a92ded0, size=61, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=61, align=1] to [address=0x55e25a92ded0, size=62, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=62, align=1] to [address=0x55e25a92ded0, size=63, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=63, align=1] to [address=0x55e25a92ded0, size=64, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=64, align=1] to [address=0x55e25a92ded0, size=65, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=65, align=1] to [address=0x55e25a92ded0, size=66, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=66, align=1] to [address=0x55e25a92ded0, size=67, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=67, align=1] to [address=0x55e25a92ded0, size=68, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=68, align=1] to [address=0x55e25a92ded0, size=69, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=69, align=1] to [address=0x55e25a92ded0, size=70, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=70, align=1] to [address=0x55e25a92ded0, size=71, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=71, align=1] to [address=0x55e25a92ded0, size=72, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=72, align=1] to [address=0x55e25a92ded0, size=73, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=73, align=1] to [address=0x55e25a92ded0, size=74, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=74, align=1] to [address=0x55e25a92ded0, size=75, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=75, align=1] to [address=0x55e25a92ded0, size=76, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=76, align=1] to [address=0x55e25a92ded0, size=77, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=77, align=1] to [address=0x55e25a92ded0, size=78, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=78, align=1] to [address=0x55e25a92ded0, size=79, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=79, align=1] to [address=0x55e25a92ded0, size=80, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=80, align=1] to [address=0x55e25a92ded0, size=81, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=81, align=1] to [address=0x55e25a92ded0, size=82, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=82, align=1] to [address=0x55e25a92ded0, size=83, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=83, align=1] to [address=0x55e25a92ded0, size=84, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=84, align=1] to [address=0x55e25a92ded0, size=85, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=85, align=1] to [address=0x55e25a92ded0, size=86, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=86, align=1] to [address=0x55e25a92ded0, size=87, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=87, align=1] to [address=0x55e25a92ded0, size=88, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=88, align=1] to [address=0x55e25a92ded0, size=89, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=89, align=1] to [address=0x55e25a92ded0, size=90, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=90, align=1] to [address=0x55e25a92ded0, size=91, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=91, align=1] to [address=0x55e25a92ded0, size=92, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=92, align=1] to [address=0x55e25a92ded0, size=93, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=93, align=1] to [address=0x55e25a92ded0, size=94, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=94, align=1] to [address=0x55e25a92ded0, size=95, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=95, align=1] to [address=0x55e25a92ded0, size=96, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=96, align=1] to [address=0x55e25a92ded0, size=97, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=97, align=1] to [address=0x55e25a92ded0, size=98, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=98, align=1] to [address=0x55e25a92ded0, size=99, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] realloc [address=0x55e25a92ded0, size=99, align=1] to [address=0x55e25a92ded0, size=100, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] dealloc [address=0x55e25a92ded0, size=100, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] dealloc [address=0x55e25a92de40, size=128, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] dealloc [address=0x55e25a92dd30, size=256, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] dealloc [address=0x55e25a92dce0, size=64, align=8]
[2021-08-15T04:48:45Z TRACE logging_allocator] dealloc [address=0x55e25a92da10, size=5, align=1]
[2021-08-15T04:48:45Z TRACE logging_allocator] dealloc [address=0x55e25a92da30, size=48, align=8]
@jgallagher jgallagher mentioned this issue Nov 3, 2021
Open
@Putnam3145
Copy link

Since this is due to the behavior of try_extend, which is used in the implementation of try_reserve, this extends to just about every function in FallibleVec. Should probably have a strong recommendation not to use it in places where performance is important.

@Putnam3145 Putnam3145 mentioned this issue Jun 26, 2022
Closed
kornelski added a commit to kornelski/fallible_collections that referenced this issue Jun 26, 2022
@kornelski
Grow capacity exponentially
d338278 
vcombey#22
@kornelski kornelski mentioned this issue Jun 26, 2022
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Grow capacity exponentially kornelski/fallible_collections
2 participants
@Putnam3145 @saethlin