search

vcombey / fallible_collections

impl fallible collections in rust, quite as describe in RFC 2116
Apache License 2.0
31 stars 14 forks source link

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

Closed saethlin closed 2 years ago

saethlin commented 3 years ago

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]
Putnam3145 commented 2 years ago

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.