Steal SmallVec from Servo

[Gankra]

SmallVec is a cool collection (family) that attempts to keep some small constant-sized number of elements in-stack before failing over to heap-allocated Slices.

@aturon has indicated interest in including this, in some form, in libcollections.

[Gankra]

@pcwalton you seem to be the primary author of SmallVec. I'm willing to do the bulk of the migration work, but would appreciate any insights you have on the matter. Is there anything you would change about the impl if you could?

One thing that comes to mind is that SmallVec would probably be simpler to implement as a tagged union between a Vec and Slice that does Vecish things but can fail (Result-wise) to insert. Might be possible to bring much of Vec's impl under some common interface to reduce duplication?

[pcwalton]

Yeah, it would be slightly less efficient as an enum but much easier to understand. Sounds like a good idea to me.

Note that you should extensively unit test it; IIRC the current implementation has some major safety bugs (in iteration I believe).

[Gankra]

So I think my basic idea for this is:

• Write some trait, let's call it AbstractVec
• Move almost all of Vec's logic to AbstractVec as default impls
• Have impls rely heavily on a two unimplemented methods: get_internal_slice and get_internal_slice_mut, which would return the implementers entire allocated space [0, capacity)
• Probably also need a get_len and set_len
• Provide a family of structs FixedVec* that look like: struct FixedVec4<T> { slice: [T, ..4], length: uint }
• Provide Vec as it is now, but with almost all its implementation details now in AbstractVec, being fed by it giving the desired slice to AbstractVec
• Provide a SmallVec* family that's basically enum SmallVec4 { FixedVec(FixedVec4<T>), Vec(Vec<T>) } that defaults using FixedVec until it's full, and then copies everything into a Vec afterwards.

Any thoughts? My largest concern is that this might have performance consequences for Vec itself, which is obviously a big deal.

[Gankra]

Might be worth waiting for something like #15748 to make this less hacky.

[aturon]

I wonder whether it would make sense to start by moving SmallVec into its own crate and working on improvements? Then Servo and others could use this crate, and if we found that it was common enough (and we were happy with the API) we could eventually move to libcollections.

That said, the Vec refactoring is an interesting idea that could be useful for other cases as well, and could be usefully done even if SmallVec lives in its own crate. Would you be interested in experimenting with this and measuring the performance impact? I'd like to see the design in more detail.

[thestinger]

Closing as a duplicate of #4991. The Servo implementation has issues like depending on the drop flag and the design isn't necessarily what Rust wants for the standard library.