BlobVec::push is linear

[stepancheg]

    #[test]
    fn test_quadratic() {
        unsafe {
            let mut vec = BlobVec::new(Layout::new::<u64>(), None, 0);
            for i in 0..100_000_000 {
                if i % 1_000_000 == 0 {
                    println!("{i}");
                }
                OwningPtr::make(i, |ptr| {
                    vec.push(ptr);
                });
                hint::black_box(&mut vec);
            }
        }
    }

    #[test]
    fn test_quadratic_vec() {
        let mut vec = Vec::new();
        for i in 0..100_000_000 {
            if i % 1_000_000 == 0 {
                println!("{i}");
            }
            vec.push(i);
            hint::black_box(&mut vec);
        }
    }

Second test finishes in a second.

First test never finishes, and shows it gets slower with each iteration.

It is not noticable in typical application because:

• reserve_exact before push (which is how BlobVec is used) makes effect less visible (yet keeping insertion kind of quadratic)
• on small BlobVec realloc often reallocates in place or reallocates to double size, making push effectively constant even with unnecessary call to realloc. But on larger allocations malloc no longer doubles the size making push very expensive.