| Age | Commit message (Collapse) | Author | Lines |
|---|
|
|
|
It's basically just a less capable version of `SmallVec`.
|
|
|
|
|
|
|
|
|
|
This improves SmallVec.extend even more over #52859
Before (as of #52859):
```
test small_vec::tests::fill_small_vec_1_10_with_cap ... bench: 31 ns/iter (+/- 5)
test small_vec::tests::fill_small_vec_1_10_wo_cap ... bench: 70 ns/iter (+/- 4)
test small_vec::tests::fill_small_vec_1_50_with_cap ... bench: 36 ns/iter (+/- 3)
test small_vec::tests::fill_small_vec_1_50_wo_cap ... bench: 256 ns/iter (+/- 17)
test small_vec::tests::fill_small_vec_32_10_with_cap ... bench: 31 ns/iter (+/- 5)
test small_vec::tests::fill_small_vec_32_10_wo_cap ... bench: 26 ns/iter (+/- 1)
test small_vec::tests::fill_small_vec_32_50_with_cap ... bench: 49 ns/iter (+/- 4)
test small_vec::tests::fill_small_vec_32_50_wo_cap ... bench: 219 ns/iter (+/- 11)
test small_vec::tests::fill_small_vec_8_10_with_cap ... bench: 32 ns/iter (+/- 2)
test small_vec::tests::fill_small_vec_8_10_wo_cap ... bench: 61 ns/iter (+/- 12)
test small_vec::tests::fill_small_vec_8_50_with_cap ... bench: 37 ns/iter (+/- 3)
test small_vec::tests::fill_small_vec_8_50_wo_cap ... bench: 210 ns/iter (+/- 10)
```
After:
```
test small_vec::tests::fill_small_vec_1_10_wo_cap ... bench: 31 ns/iter (+/- 3)
test small_vec::tests::fill_small_vec_1_50_with_cap ... bench: 39 ns/iter (+/- 4)
test small_vec::tests::fill_small_vec_1_50_wo_cap ... bench: 35 ns/iter (+/- 4)
test small_vec::tests::fill_small_vec_32_10_with_cap ... bench: 37 ns/iter (+/- 3)
test small_vec::tests::fill_small_vec_32_10_wo_cap ... bench: 32 ns/iter (+/- 2)
test small_vec::tests::fill_small_vec_32_50_with_cap ... bench: 52 ns/iter (+/- 4)
test small_vec::tests::fill_small_vec_32_50_wo_cap ... bench: 46 ns/iter (+/- 0)
test small_vec::tests::fill_small_vec_8_10_with_cap ... bench: 35 ns/iter (+/- 4)
test small_vec::tests::fill_small_vec_8_10_wo_cap ... bench: 31 ns/iter (+/- 0)
test small_vec::tests::fill_small_vec_8_50_with_cap ... bench: 40 ns/iter (+/- 15)
test small_vec::tests::fill_small_vec_8_50_wo_cap ... bench: 36 ns/iter (+/- 2)
```
|
|
Use Vec::extend in SmallVec::extend when applicable
As calculated in #52738, `Vec::extend` is much faster than `push`ing to it in a loop. We can take advantage of this method in `SmallVec` too - at least in cases when its underlying object is an `AccumulateVec::Heap`.
~~This approach also accidentally improves the `push` loop of the `AccumulateVec::Array` variant, because it doesn't utilize `SmallVec::push` which performs `self.reserve(1)` with every iteration; this is unnecessary, because we're already reserving the whole space we will be needing by performing `self.reserve(iter.size_hint().0)` at the beginning.~~
|
|
|
|
|
|
|
|
Extra allocations are a significant cost of NLL, and the most common
ones come from within `Canonicalizer`. In particular, `canonical_var()`
contains this code:
indices
.entry(kind)
.or_insert_with(|| {
let cvar1 = variables.push(info);
let cvar2 = var_values.push(kind);
assert_eq!(cvar1, cvar2);
cvar1
})
.clone()
`variables` and `var_values` are `Vec`s. `indices` is a `HashMap` used
to track what elements have been inserted into `var_values`. If `kind`
hasn't been seen before, `indices`, `variables` and `var_values` all get
a new element. (The number of elements in each container is always the
same.) This results in lots of allocations.
In practice, most of the time these containers only end up holding a few
elements. This PR changes them to avoid heap allocations in the common
case, by changing the `Vec`s to `SmallVec`s and only using `indices`
once enough elements are present. (When the number of elements is small,
a direct linear search of `var_values` is as good or better than a
hashmap lookup.)
The changes to `variables` are straightforward and contained within
`Canonicalizer`. The changes to `indices` are more complex but also
contained within `Canonicalizer`. The changes to `var_values` are more
intrusive because they require defining a new type
`SmallCanonicalVarValues` -- which is to `CanonicalVarValues` as
`SmallVec` is to `Vec -- and passing stack-allocated values of that type
in from outside.
All this speeds up a number of NLL "check" builds, the best by 2%.
|
|
|
|
The change also adds the missing `SmallVec::truncate` method.
|
|
data_structures::SmallVec.
|
