Benchmarks

[Lokathor]

It seems like in some cases LLVM is able to make this crate just as fast as using arrayvec and smallvec, but I sure bet that's not always the case.

I'd like someone who is passionate about doing lots of benchmarks to do some comparisons. Maybe there's areas we can improve, maybe there's areas we should just report as being a slower path for our crate.

Also currently there's a very high number of inline and inline(always) attribute usage. Since these types are generic we probably don't need as much of that. Benchmarks comparing an inline vs no-inline version are helpful here as well.

Things of interest:

• no inline hint / inline / inline(always)
• debug performance vs release performance. Good debug performance is important for a good development experience, and if something can help debug perf without hurting release perf we should do that thing.
• Comparing various tasks with tinyvec types compared to arrayvec and smallvec types.

[mbrubeck]

I took the smallvec benchmarks and added comparisons to tinyvec on this branch: https://github.com/mbrubeck/rust-smallvec/tree/bench-tinyvec

These benchmarks compare SmallVec<[u64; 16]> to TinyVec<[u64; 16]> and Vec<u64>. Most benchmarks have one variant that uses 100 elements and a "small" variant with 16 elements. Results from my laptop are below.

test bench_extend_from_slice            ... bench:          74 ns/iter (+/- 18)
test bench_extend_from_slice_small      ... bench:          10 ns/iter (+/- 0)
test bench_extend_from_slice_tiny       ... bench:         622 ns/iter (+/- 17)
test bench_extend_from_slice_tiny_small ... bench:          28 ns/iter (+/- 1)
test bench_extend_from_slice_vec        ... bench:         196 ns/iter (+/- 21)
test bench_extend_from_slice_vec_small  ... bench:          59 ns/iter (+/- 1)
test bench_extend                       ... bench:         100 ns/iter (+/- 5)
test bench_extend_small                 ... bench:          11 ns/iter (+/- 0)
test bench_extend_tiny                  ... bench:         525 ns/iter (+/- 17)
test bench_extend_tiny_small            ... bench:          36 ns/iter (+/- 2)
test bench_extend_vec                   ... bench:         157 ns/iter (+/- 4)
test bench_extend_vec_small             ... bench:          58 ns/iter (+/- 0)
test bench_from_iter                    ... bench:         101 ns/iter (+/- 1)
test bench_from_iter_small              ... bench:          11 ns/iter (+/- 0)
test bench_from_iter_tiny               ... bench:         566 ns/iter (+/- 6)
test bench_from_iter_tiny_small         ... bench:          37 ns/iter (+/- 3)
test bench_from_iter_vec                ... bench:         111 ns/iter (+/- 5)
test bench_from_iter_vec_small          ... bench:          59 ns/iter (+/- 6)
test bench_from_slice                   ... bench:         117 ns/iter (+/- 0)
test bench_from_slice_small             ... bench:          21 ns/iter (+/- 0)
test bench_from_slice_tiny              ... bench:         553 ns/iter (+/- 12)
test bench_from_slice_tiny_small        ... bench:          44 ns/iter (+/- 9)
test bench_from_slice_vec               ... bench:         107 ns/iter (+/- 0)
test bench_from_slice_vec_small         ... bench:          59 ns/iter (+/- 7)
test bench_insert                       ... bench:         762 ns/iter (+/- 342)
test bench_insert_small                 ... bench:         188 ns/iter (+/- 13)
test bench_insert_tiny                  ... bench:       1,014 ns/iter (+/- 85)
test bench_insert_tiny_small            ... bench:         385 ns/iter (+/- 16)
test bench_insert_vec                   ... bench:         788 ns/iter (+/- 9)
test bench_insert_vec_small             ... bench:         234 ns/iter (+/- 15)
test bench_macro_from_elem              ... bench:         124 ns/iter (+/- 8)
test bench_macro_from_elem_small        ... bench:          21 ns/iter (+/- 1)
test bench_macro_from_elem_tiny         ... bench:         671 ns/iter (+/- 55)
test bench_macro_from_elem_tiny_small   ... bench:         115 ns/iter (+/- 33)
test bench_macro_from_elem_vec          ... bench:         114 ns/iter (+/- 8)
test bench_macro_from_elem_vec_small    ... bench:          60 ns/iter (+/- 1)
test bench_macro_from_list              ... bench:         110 ns/iter (+/- 13)
test bench_macro_from_list_tiny         ... bench:         391 ns/iter (+/- 2)
test bench_macro_from_list_vec          ... bench:          99 ns/iter (+/- 0)
test bench_push                         ... bench:         512 ns/iter (+/- 14)
test bench_push_small                   ... bench:          41 ns/iter (+/- 3)
test bench_push_tiny                    ... bench:         802 ns/iter (+/- 57)
test bench_push_tiny_small              ... bench:          53 ns/iter (+/- 0)
test bench_push_vec                     ... bench:         600 ns/iter (+/- 34)
test bench_push_vec_small               ... bench:          86 ns/iter (+/- 12)
test bench_pushpop                      ... bench:         394 ns/iter (+/- 17)
test bench_pushpop_tiny                 ... bench:         426 ns/iter (+/- 40)
test bench_pushpop_vec                  ... bench:         304 ns/iter (+/- 20)
test bench_remove                       ... bench:         495 ns/iter (+/- 0)
test bench_remove_small                 ... bench:          77 ns/iter (+/- 4)
test bench_remove_tiny                  ... bench:       1,192 ns/iter (+/- 85)
test bench_remove_tiny_small            ... bench:         175 ns/iter (+/- 15)
test bench_remove_vec                   ... bench:         506 ns/iter (+/- 39)
test bench_remove_vec_small             ... bench:         124 ns/iter (+/- 7)

[mbrubeck]

In general, for vectors that fit on the stack, TinyVec is faster than Vec but slower than SmallVec, which I think is a reasonable expectation. Two cases where it's slower than both are insert and remove, which is again reasonable, but might be worth warning about in documentation.

For vectors that require a heap allocation, TinyVec is sometimes much slower than both Vec and SmallVec, which is a little surprising to me, and can perhaps be improved.

[Lokathor]

I am also surprised.

Still, it's very pleasant to see that there is a performance niche for TinyVec as well as simply a safety based case.

[Soveu]

I used this benchmark, but slightly modified to compare performance from 0.3 and branch from #82
There are some huge wins, but also some regressions, I'll try to work on them after the PR gets merged

TEST NAME                                       NEW                          OLD
test bench_extend_from_slice_tiny          58 ns/iter (+/- 2)         558 ns/iter (+/- 173)
test bench_extend_from_slice_tiny_small    23 ns/iter (+/- 0)          40 ns/iter (+/- 0)
test bench_extend_tiny                    262 ns/iter (+/- 10)        543 ns/iter (+/- 180)
test bench_from_slice_tiny                 63 ns/iter (+/- 5)         548 ns/iter (+/- 186)
test bench_from_slice_tiny_small           23 ns/iter (+/- 0)          68 ns/iter (+/- 1)
test bench_from_iter_tiny_small            38 ns/iter (+/- 0)          65 ns/iter (+/- 0)
test bench_macro_from_elem_tiny           100 ns/iter (+/- 6)         587 ns/iter (+/- 127)
test bench_macro_from_elem_tiny_small      39 ns/iter (+/- 0)          69 ns/iter (+/- 2)
                                                                                            
test bench_extend_tiny_small               38 ns/iter (+/- 0)          40 ns/iter (+/- 3)
test bench_insert_tiny                    806 ns/iter (+/- 19)        762 ns/iter (+/- 14)
test bench_insert_tiny_small              217 ns/iter (+/- 5)         190 ns/iter (+/- 3)
test bench_macro_from_list_tiny            27 ns/iter (+/- 0)          30 ns/iter (+/- 1)
test bench_push_tiny                      464 ns/iter (+/- 14)        453 ns/iter (+/- 22)
test bench_push_tiny_small                 58 ns/iter (+/- 1)          59 ns/iter (+/- 4)
                                                                                            
test bench_from_iter_tiny                 536 ns/iter (+/- 8)         385 ns/iter (+/- 161)
test bench_pushpop_tiny                   688 ns/iter (+/- 32)        500 ns/iter (+/- 21)
test bench_remove_tiny                  1,218 ns/iter (+/- 26)      1,068 ns/iter (+/- 46)
test bench_remove_tiny_small              315 ns/iter (+/- 14)        207 ns/iter (+/- 9)

EDIT: the functions that have regressions are the ones, that I did not touch, but still I'm willing to improve them

[Soveu]

This is a good start for 0.4

                                                0.3                        0.4
test bench_extend_from_slice_tiny         354 ns/iter (+/- 28)       60 ns/iter (+/- 1) 
test bench_extend_from_slice_tiny_small    64 ns/iter (+/- 0)        23 ns/iter (+/- 0) 
test bench_extend_tiny                    378 ns/iter (+/- 184)      58 ns/iter (+/- 1) 
test bench_extend_tiny_small               40 ns/iter (+/- 1)        40 ns/iter (+/- 2) 
test bench_from_iter_tiny                 377 ns/iter (+/- 13)       58 ns/iter (+/- 0) 
test bench_from_iter_tiny_small            65 ns/iter (+/- 27)       40 ns/iter (+/- 1) 
test bench_from_slice_tiny                549 ns/iter (+/- 82)       60 ns/iter (+/- 1) 
test bench_from_slice_tiny_small           42 ns/iter (+/- 2)        23 ns/iter (+/- 0) 
test bench_insert_tiny                    801 ns/iter (+/- 89)      770 ns/iter (+/- 18)
test bench_insert_tiny_small              208 ns/iter (+/- 5)       207 ns/iter (+/- 2) 
test bench_macro_from_elem_tiny           593 ns/iter (+/- 252)      90 ns/iter (+/- 1) 
test bench_macro_from_elem_tiny_small      71 ns/iter (+/- 22)       36 ns/iter (+/- 0) 
test bench_macro_from_list_tiny            33 ns/iter (+/- 3)        26 ns/iter (+/- 0) 
test bench_push_tiny                      440 ns/iter (+/- 14)      458 ns/iter (+/- 10)
test bench_push_tiny_small                 58 ns/iter (+/- 0)        53 ns/iter (+/- 0) 
test bench_pushpop_tiny                   488 ns/iter (+/- 8)       647 ns/iter (+/- 37)
test bench_remove_tiny                  1,076 ns/iter (+/- 93)      568 ns/iter (+/- 7) 
test bench_remove_tiny_small              207 ns/iter (+/- 5)       147 ns/iter (+/- 2) 

As I expected, extending from slice or from iterator is now much quicker
Also the macro is faster!
Only bench_pushpop here is worse (may be for the same random reason as bench_remove)
bench_remove result seems to fluctuate between different compilations

[saethlin]

I'm interested in helping out here. As a start, I copied @mbrubeck's benchmarks and massaged them a bit. At the moment I'm only tracking the runtime ratio tinyvec/smallvec because I'm focused on driving the runtime of tinyvec down to justify replacing smallvec. Current status:

bench_extend                   0.48
bench_from_iter                0.49
bench_insert                   1.08
bench_extend_from_slice_small  1.14
bench_pushpop                  1.17
bench_push                     1.42
bench_insert_small             1.55
bench_extend_from_slice        1.57
bench_from_iter_small          1.59
bench_extend_small             1.62
bench_push_small               1.85
bench_remove                   2.21
bench_macro_from_elem_small    2.24
bench_remove_small             2.59
bench_from_slice               2.66
bench_from_slice_small         4.54
bench_macro_from_elem          11.82

It looks like there is a lot of work to do here. I have no idea why extend and from_iter are so favorable. I'm opening a PR which optimized TinyVec::push to bring the list to this:

bench_from_iter                0.59
bench_extend                   0.59
bench_insert                   1.05
bench_push                     1.06
bench_pushpop                  1.07
bench_push_small               1.08
bench_extend_from_slice_small  1.15
bench_from_iter_small          1.33
bench_extend_small             1.34
bench_insert_small             1.47
bench_extend_from_slice        1.73
bench_macro_from_elem_small    1.91
bench_remove                   2.12
bench_remove_small             2.48
bench_from_slice               2.89
bench_from_slice_small         4.41
bench_macro_from_elem          10.71

And as I'm making this I'm realizing I really need to propagate criterion's uncertainties to this report, the jitter varies a lot between benchmarks.

[saethlin]

I looked into the remove benchmarks. They use Vector::from_elem to build a container for each benchmark run, which smallvec has a fast implementation for and tinyvec does not. I've switched the benchmark to create a single container outside the loop, then clone it for each run. After that change, the standings are:

bench_extend                   0.59
bench_from_iter                0.59
bench_push                     0.94
bench_pushpop                  1.08
bench_push_small               1.10
bench_remove                   1.11
bench_extend_from_slice_small  1.11
bench_extend_from_slice        1.16
bench_insert_small             1.33
bench_remove_small             1.42
bench_from_iter_small          1.56
bench_extend_small             1.57
bench_insert                   1.89
bench_macro_from_elem_small    2.33
bench_from_slice               2.70
bench_from_slice_small         4.55
bench_macro_from_elem          13.70

Then after the change in #128 we're down to

bench_from_iter                0.52
bench_extend                   0.59
bench_remove_small             0.72
bench_insert                   0.97
bench_push                     1.00
bench_pushpop                  1.06
bench_push_small               1.06
bench_extend_from_slice_small  1.08
bench_remove                   1.11
bench_extend_small             1.37
bench_insert_small             1.37
bench_from_iter_small          1.37
bench_extend_from_slice        1.75
bench_macro_from_elem_small    2.63
bench_from_slice               2.97
bench_from_slice_small         4.51
bench_macro_from_elem          12.21

[saethlin]

After some small tweaks to the benchmarks and the changes in #129 we are now at:

bench_from_iter                0.42
bench_extend                   0.43
bench_extend_from_slice_small  0.59
bench_remove_small             0.64
bench_push_small               0.95
bench_push                     0.97
bench_insert                   0.97
bench_from_slice               0.98
bench_insert_small             1.06
bench_pushpop                  1.07
bench_extend_from_slice        1.36
bench_from_iter_small          1.42
bench_remove                   1.48
bench_extend_small             1.57
bench_from_slice_small         1.83
bench_macro_from_elem_small    3.58
bench_macro_from_elem          8.37

I've looked into the from_slice/from_slice_small benchmarks and I couldn't come up with any easy improvements. Hopefully at some point someone is able to do something about bench_from_slice_small. I think the next thing to do here is to beef up this benchmark suite with various inline arrays and put it up in a PR.

[saethlin]

Update, now with multiple container sizes. Still need some benchmarking with types whose default state is not all zeroes, but even with just this things are now more interesting:

Benchmarks

SmallVec_[u8;16]_
remove_small             0.50
remove                   0.51
extend_from_slice_small  0.59
extend                   0.89
insert_small             0.97
push_small               0.97
from_iter                0.97
insert                   1.00
from_slice               1.00
pushpop                  1.10
pushpop_small            1.18
push                     1.21
extend_from_slice        1.22
extend_small             1.45
from_iter_small          1.45
from_slice_small         1.51
from_elem                4.18
from_elem_small          14.15

SmallVec_[u8;32]_
extend_from_slice_small  0.59
from_iter                0.66
extend                   0.68
remove                   0.70
remove_small             0.73
push                     0.90
insert                   0.99
from_slice               0.99
pushpop                  1.07
pushpop_small            1.08
push_small               1.10
insert_small             1.12
extend_from_slice        1.25
from_slice_small         1.45
from_iter_small          1.82
extend_small             1.89
from_elem                7.39
from_elem_small          20.81

SmallVec_[u8;64]_
extend                   0.39
from_iter                0.39
extend_from_slice_small  0.64
remove                   0.65
remove_small             0.65
push                     0.79
insert                   0.97
from_slice               1.01
insert_small             1.04
pushpop_small            1.07
pushpop                  1.08
extend_from_slice        1.08
push_small               1.09
from_slice_small         1.29
extend_small             2.58
from_iter_small          2.80
from_elem                12.86
from_elem_small          31.79

SmallVec_[u16;128]_
extend                   0.30
from_iter                0.30
remove                   0.82
remove_small             0.83
push                     0.89
insert                   0.94
from_slice_small         0.98
insert_small             0.98
from_slice               0.99
pushpop                  1.07
pushpop_small            1.08
push_small               1.12
extend_from_slice_small  1.16
extend_from_slice        1.23
from_iter_small          2.61
extend_small             2.81
from_elem                12.55
from_elem_small          15.35

SmallVec_[u64;2]_
remove                   0.42
remove_small             0.43
extend_from_slice_small  0.62
extend                   0.78
from_iter                0.79
extend_small             0.79
from_iter_small          0.81
from_elem                0.83
from_slice               0.98
extend_from_slice        1.00
from_slice_small         1.18
insert                   1.19
insert_small             1.21
pushpop                  1.39
push                     1.54
push_small               2.66
from_elem_small          3.25
pushpop_small            3.75

A few things jump out at me:

1. My insert/remove optimizations that swapped out slice::rotate_right and slice::rotate_left which were a huge win for [u8; 16] don't drop us below SmallVec even at pretty significant inline arrays.

2. extend and from_iter are consistently quite bad. There's definitely something going on there.

3. TinyVec<[u64; 2]>::push_small is shockingly bad. I don't know why. Could be a result of the short inline array or the large element size. In either case, we clearly need to cover parameter space better and this needs some optimization if possible.

4. I should do something about the from_elem benchmark so I can stop looking at those huge numbers.

[saethlin]

It looks like as of my latest work, TinyVec is now at parity with or beating SmallVec in all benchmarks that do not create a new container. Where SmallVec is slower, this is mostly due to failed inlining in the benchmarks. I've looked into a few of the most significant cases, and where SmallVec is ~20x slower this is due to multiple layers of failed inlining. The hot instructions in SmallVec for those benchmarks are mostly push/pop, and there are a lot of huge jumps.

Overall I think we're now in a good spot. The benchmarks now clearly point out places where SmallVec could do with some love, and the code path(s) where the #![forbid(unsafe_code)] policy of this crate imposes overhead. I'm experimenting with some data visualization to present the benchmarks in a way that helps identify systematic problems, and also looking into ways to identify instability/jitter. There are a few benchmarks which look like they are highly unstable over runs. I'm afraid this is because they're sensitive to layout, in which case I fear all we can do with criterion is quantify the jitter.

Benchmarks

SmallVec_[u8;16]_
clone_small              0.19
extend                   0.26
push                     0.38
clone                    0.42
default                  0.50
from_iter_small          0.54
remove_small             0.56
extend_from_slice_small  0.59
extend_small             0.72
from_iter                0.74
remove                   0.81
from_elem                0.81
insert_small             0.88
insert                   0.89
extend_from_slice        0.90
push_small               0.97
from_slice               1.01
from_slice_small         1.01
pushpop_small            1.05
pushpop                  1.08
from_elem_small          1.58
0.82

SmallVec_[u8;32]_
clone_small              0.12
extend                   0.15
clone                    0.28
push                     0.37
remove_small             0.55
from_iter                0.61
extend_from_slice_small  0.64
from_iter_small          0.67
default                  0.67
extend_small             0.68
from_elem                0.84
extend_from_slice        0.84
insert_small             0.85
push_small               0.90
insert                   0.95
from_slice               1.01
pushpop_small            1.06
remove                   1.07
pushpop                  1.08
from_slice_small         1.22
from_elem_small          3.86
1.14

SmallVec_[u8;64]_
clone_small              0.08
extend                   0.09
clone                    0.17
from_iter                0.34
push                     0.36
extend_from_slice_small  0.61
remove_small             0.68
from_iter_small          0.73
extend_small             0.73
remove                   0.83
extend_from_slice        0.83
from_elem                0.92
insert_small             0.95
insert                   0.99
default                  1.00
from_slice               1.00
push_small               1.05
pushpop_small            1.06
pushpop                  1.07
from_slice_small         1.24
from_elem_small          3.07
1.04

SmallVec_[u8;128]_
clone_small              0.05
extend                   0.07
clone                    0.09
from_iter                0.27
push                     0.35
remove_small             0.70
extend_from_slice_small  0.75
extend_small             0.76
from_iter_small          0.77
remove                   0.78
extend_from_slice        0.78
from_elem                0.82
insert                   0.95
insert_small             1.00
from_slice               1.02
push_small               1.06
pushpop_small            1.08
pushpop                  1.08
from_slice_small         1.25
default                  1.67
from_elem_small          2.56
1.02

SmallVec_[u8;256]_
extend                   0.05
clone                    0.07
clone_small              0.09
from_iter                0.17
push                     0.35
extend_small             0.79
remove                   0.80
extend_from_slice_small  0.81
from_iter_small          0.82
from_elem                0.88
remove_small             0.88
insert                   0.91
insert_small             0.91
extend_from_slice        0.96
from_slice               1.01
pushpop_small            1.07
push_small               1.08
pushpop                  1.08
from_slice_small         1.16
from_elem_small          1.79
default                  3.69
1.19

SmallVec_[u64;2]_
from_iter_small          0.26
clone_small              0.27
push                     0.35
clone                    0.38
pushpop                  0.41
extend_small             0.41
remove_small             0.46
remove                   0.48
extend_from_slice_small  0.57
extend                   0.69
pushpop_small            0.72
from_iter                0.82
extend_from_slice        0.84
from_elem                0.91
insert_small             0.99
from_slice               1.01
insert                   1.02
push_small               1.06
from_slice_small         1.37
default                  2.40
from_elem_small          2.51
1.04

SmallVec_[u64;4]_
push                     0.31
pushpop                  0.33
pushpop_small            0.38
clone                    0.46
extend_small             0.50
extend                   0.52
remove                   0.64
extend_from_slice_small  0.65
push_small               0.82
extend_from_slice        0.84
from_elem                0.97
insert_small             0.98
insert                   0.99
from_slice               1.03
from_iter                1.11
from_slice_small         1.13
clone_small              1.49
from_iter_small          1.69
remove_small             1.73
from_elem_small          4.12
default                  17.12
3.95

SmallVec_[u64;8]_
push                     0.30
pushpop_small            0.32
extend                   0.47
clone                    0.51
extend_from_slice_small  0.59
extend_small             0.72
push_small               0.76
remove                   0.80
from_elem                0.93
insert                   0.97
from_iter                0.99
extend_from_slice        1.01
from_slice               1.01
pushpop                  1.06
insert_small             1.07
remove_small             1.27
from_slice_small         1.28
clone_small              1.47
from_iter_small          1.63
from_elem_small          3.43
default                  22.84
5.12

SmallVec_[u64;16]_
push                     0.30
clone                    0.44
extend                   0.47
extend_from_slice_small  0.74
remove                   0.77
extend_small             0.85
insert_small             0.86
insert                   0.90
from_elem                0.99
from_slice               1.01
remove_small             1.02
extend_from_slice        1.03
pushpop_small            1.05
pushpop                  1.05
from_elem_small          1.09
from_iter                1.09
push_small               1.17
from_slice_small         1.31
clone_small              1.35
from_iter_small          1.66
default                  34.28
7.54

SmallVec_[u64;32]_
push                     0.30
clone                    0.38
extend_small             0.56
extend                   0.61
push_small               0.61
extend_from_slice_small  0.76
remove                   0.77
insert_small             0.90
insert                   0.90
from_elem                0.91
remove_small             0.95
pushpop_small            1.05
pushpop                  1.06
from_slice               1.06
extend_from_slice        1.07
clone_small              1.14
from_elem_small          1.19
from_iter                1.33
from_slice_small         1.48
from_iter_small          1.61
default                  42.84

[saethlin]

Closed by #150? Or do we want more benchmarks per your original list to close this out?

[Lokathor]

oh right, yeah. we can close this.