add a small vector to the standard library

[thestinger]

It's often useful to have a vector optimized for storing small sequences. LLVM includes a SmallVector templated type which takes the size to store inside the struct as a template parameter, which isn't possible at the moment in Rust. However, it would be fine to just copy what libc++ does for std::string which is to store 3 words in the struct (size, capacity, and the pointer) and reuse that space for the small string optimization.

[catamorphism]

Added the An-interesting-project label.

[abhijeetgaiha]

@catamorphism @thestinger
Just trying to get a feel for what is required here...
This works much like a ~[], except we will allocate space for N elements during initialisation.
How is this different from creating a ~[] and calling reserve()?

[huonw]

@abhijeetgaiha it's more subtle than that, it's effectively:

enum SmallVector<T> {
   Small(uint, [T, .. 8]), // size, data (the 8 shouldn't be hardcoded like this)
   Big(uint, uint, *T) // capacity, size, pointer
}

(But not exactly, a Rust implementation should try to leverage LLVM's support.)

I.e. it is a value with size 3 words, and if there are a small number of elements they are stored directly in the value, not behind a pointer-indirection.

[thestinger]

@huonw: LLVM's type is just a templated C++ container that they use heavily throughout their codebase, it's not really useful to us.

[abhijeetgaiha]

@huonw @thestinger
The bug body makes a little more sense now.

Looks like you are suggesting we have the following struct
SmallVector {
big:bool,
size:uint,
capacity:uint,
ptr: *T
}

For small values, we set big to false and re-use the space reserved for size, capacity and ptr for storage.
If we exceed that, we set big to true and allocate some space to ptr and move the elements there.

Am I following you correctly?

[huonw]

@abhijeetgaiha I think the best-case scenario would be SmallVector { size: uint, capacity: uint, ptr: *T }, and (for example) use the high bit of size to indicate whether the data is stored in the two other words, or if it is behind ptr.

(Note that you still need to indicate the size of the data when on the stack, so size cannot be (entirely) used to store data in that case.)

[abhijeetgaiha]

@huonw Thanks for the input. I'm going to make a initial attempt at this.

[thestinger]

This is still unimplemented and would be very useful, but the lack of integers in the type system makes the concept much less powerful.

[erickt]

I just saw that there is a syntax::util::small_vector that optimizes for 0, 1, or many items cases. It'd be a nice stopgap between now and if/when we add integers to the type system.

[thestinger]

@erickt: It should be doing one branch for a small case (3+ words) and a large case and ideally avoiding the overhead of using an enum. A sane vector type is already not allocating for the 0 element case.

[pnkfelix]

This need not block 1.0. @pcwalton has one in Servo that we could copy over if need be. Assigning P-low.