Use optimized SmallVec crate

[arthurprs]

Right now there are 3'ish variants of SmallVec in rustc_data_structures.

In the meantime there's some ongoing work on servo/SmallVec. master branch even contains a change that could benefit rustc well servo/rust-smallvec#94 (remove enum tag size overhead).

I don't have time to write a PR right now but I thought I could inspire someone else to do so.

[Mark-Simulacrum]

Note that the variants in data_structures are intended to be progressively more complex, that is they aren't separate code but reuse their "children" -- ArrayVec is purely stack-only, AccumulateVec adds potential growth onto the heap, and I'm not sure why SmallVec exists as a separate structure.

Generally speaking though this is a good idea.

[arthurprs]

Yeah, 3'sih variants is a subpar description but the reasoning is still good.

[gootorov]

I'd like to work on this. I've already made some initial changes.
@rust-highfive assign me

I have a few questions:

1. In other parts of rustc, SmallVec is imported like this

use rustc_data_structures::smallvec::SmallVec;

Would it be better to replace it with

extern crate smallvec;
use smallvec::SmallVec;

or instead, keep imports as is and put in src/librustc_data_structures/small_vec.rs the following?

extern crate smallvec;
pub use smallvec::SmallVec;

2. Servo/SmallVec is missing a few methods that are used within rustc.
   In particular, SmallVec::one(), SmallVec::many() and SmallVec::expect_one().
   Shall I open a PR to servo/SmallVec or just import it and implement these methods locally? They seem useful, so I guess a PR would be better. cc @mbrubeck

Also, I suggest that we rename SmallVec::one() and SmallVec::many() to SmallVec::from_one() and SmallVec::from_many(). It's not used a lot, so it will be easy to fix breakage.

3. There are benchmarks in src/librustc_data_structures/small_vec.rs. What do we do with them? Just keep them there?

[Mark-Simulacrum]

I would replace with crate imports, we should delete SmallVec from data structures entirely if we're to do this.

I'd look at either adding the methods to the crate. I'd rather avoid a mix of both in-tree and out of tree code.

Benchmarks can either be uplifted to smallvec or deleted (perhaps after checking that the imported crate is equivalent performance wise).

[BurntPizza]

I've done a minimal-change version of this (this was before you posted, @gootorov) by making librustc_data_structures/small_vec a wrapper of SmallVec, and a local perf run looks good.

I agree that straight imports are what we want, but how do we want to handle serialization? We could import and impl in libserialize, as we do with std data structures, but it's kind of yucky. It might be possible to just not implement Rustc(De)Serialize, I haven't looked at how much it's actually used with SmallVec and if those cases can be supplied by a Serialization-specific wrapper.

I would also like to test the impact of also subsuming AccumulateVec and ArrayVec as well (perhaps the latter with the arrayvec crate if smallvec isn't appropriate, I saw that it was already in tree somewhere).

I can work on something else, do you want the code, @gootorov?

[Mark-Simulacrum]

Hm, I hadn't considered serialization. It might be best to leave the structure as a newtype wrapper in librustc_data_structures then, and implement the relevant traits there. I think that might be best.

[gootorov]

@BurntPizza This issue looks like a good place for me to start contributing to rustc, so I'm quite interested in completing it. Thanks!
I think I don't need the code, but thanks for helping! I want to do it myself, it will be a good learning experience.

[mbrubeck]

Servo/SmallVec is missing a few methods that are used within rustc. In particular, SmallVec::one(), SmallVec::many() and SmallVec::expect_one(). Shall I open a PR to servo/SmallVec or just import it and implement these methods locally?

SmallVec::one(x) can be replaced by smallvec![x]. (In some cases this may require servo/rust-smallvec#107 which is not included in the latest published release. I can publish a new release if necessary.)

SmallVec::many(iter) can be replaced by SmallVec::from_iter(iter).

SmallVec::expect_one seems fairly specialized, and could be implemented locally in librustc_data_structures.

[Mark-Simulacrum]

I believe the new release will be required, I seem to recall smallvec of box (well, P) being quite common, and it's often constructed with one.

Agreed on many.

Yes, we should probably implement expect_one ourselves. Arguably it's possible it should be removed entirely, depending on use cases, but that is a separate question.

[mbrubeck]

Published smallvec 0.6.4: servo/rust-smallvec#110