Make Vec and String be slices

libs
1

IMHO Vecs and Strings are wasteful in storing the capacity along with the pointer and length. On 64bit systems this makes them to big to fit into u128 registers, where available. And on every move there is an extra usize to push around.

If we moved the capacity to the heap, we’d save that memory for unallocated Vecs and Strings. And it would not be on the stack again in each frame through which it gets passed down (unless they are optimised to overlap.)

I propose putting the capacity at the beginning, but letting the pointer go to the payload. That way the local part is indistinguishable from a slice or fat reference. I.e. as_ref()/as_str() are nops. Only operations that need the capacity, would need to calculate the negative offset.

         ╭─────┬─────╮
         │ ptr │ len │
         ╰─┬───┴─┬───╯
           ▼     ▼
╭──────────┬──────────╮
│ capacity │██████░░░░│
╰─┬────────┴──────────╯
  │                   ▲
  ╰───────────────────╯

N.b. not pretending the latter two are pointers, just illustrating what they refer to.

1 Like
2

Vec has some documented guarantees that make this hard to change:

Most fundamentally, Vec is and always will be a (pointer, capacity, length) triplet. No more, no less.

Right up front, we'd be stretching this guarantee by moving the capacity inward.

If len==capacity, then a Vec<T> can be converted to and from a Box<[T]> without reallocating or moving the elements.

That means we would have to store a hidden capacity in Box<[T]> too, but this wouldn't play well with unsizing coercion from Box<[T; N]>.

Vec::from_raw_parts also makes it hard to change any of this, because that pointer doesn't have to come from a Vec originally.

6 Likes
3

This isn't going to change.

That said, if you want this, check out thin_vec - Rust

4

If you don't like that ThinVec has to dereference its length, you could use ThinBox, something like:

struct MyVec {
    data: ThinBox<[MaybeUninit<T>]>,
    len: usize,
}
1 Like
5

That guarantee strikes me as weird. If you read it narrowly, it would indeed be a breaking change. On its own it feels like needlessly overpromising an implementation detail.

OTOH I never thought about downcasting a String to a Box. Those relying on that would of course be bitten if it becomes impossible. Plus it would be a memory leak if one forces it anyway and the capacity gets forgotten. Upcasting the other way round would become impossible without reallocation. Even if that use case is maybe only a tiny fraction of as_ref()/as_str().

6

One awkwardness about this is that Rust often uses memory allocators that were designed for C. C's free() function, which deallocates memory, does not take a capacity argument, so the allocator has to store it itself, and a lot of allocators store it just before the allocation.

As such, the current Rust Vec layout, when using such an allocator, looks like this: length, pointer, capacity in the Vec; and capacity, elements in the memory provided by the allocator. This is of course storing the capacity twice, which is overhead caused by an abstraction (specifically, that Rust doesn't try to look at or care about the implementation details of allocators).

It would be possible to design an allocator that doesn't store the capacity (and relies entirely on the capacity reported by the Vec to deallocate correctly), but there is actually not a lot of use for these: they wouldn't work with C (so such allocators wouldn't be very backwards-compatible), and most high-performance allocators work by doing things like packing allocations with the same size into the same memory page, and thus naturally end up knowing the capacity anyway (because they can check their metadata for the page on which the memory is allocated to see what size of allocations are allocated there).

There are other allocator changes that would make Rust more efficient, too. For example, on systems with no memory management unit, any address that has ever been allocated will always be readable; and on systems that do have a memory management unit, it can be configured to cause a given range of memory addresses to read as all-zeroes without actually needing to allocate physical memory backing them, so if the allocator needs to free memory, it can just make it read as all-zeroes (while freeing the backing memory) rather than actually freeing the addresses. This means that it would generally be cheap to make an allocator give a guarantee of "any address that has ever been allocated will be readable for the rest of the program's execution, as long as you discard any value you read from non-allocated memory", and such a guarantee can lead to better optimizations because it allows the compiler to speculatively read from potentially deallocated memory without needing to worry about the potential for segfaults.

2 Likes
7

The docs explain why we make those guarantees (that indeed make this change impossible): Vec is an extremely fundamental type. A lot of unsafe code relies on it, and without those guarantees would have to reimplement it (or parts of it), likely with a worse (or even unsound) implementation.

2 Likes
8

Also, and again due to its fundamental nature, you are almost guaranteed to not be able to improve on its basic layout. Any change you will make can be a gain for some use-cases but will be a regression for others, and due to how widely used it is, such regression isn't acceptable. If some specific layout is better for you, you can use a crate that implements it, there are many for many layouts.

Some possible layouts for example: storing the length & capacity as u32 (on a 64-bit system), storing both inside the allocation (ThinVec), storing the capacity only inside the allocation like you suggest, or others.

Some specific downsides to your proposal:

  • LLVM will face more difficulties removing redundant capacity loads, and therefore branches;
  • Small vectors (e.g. one byte, relevant mostly to custom allocators) will occupy more memory;
  • Vec<T> when T has a large alignment will occupy more memory;
  • And probably more.
2 Likes
9

It wouldn't be a leak, it would be UB as the Box would later pass the pointer where the elements begin to free, which is not the actual beginning of the allocation.

4 Likes
10

I usually have cases where either the size of the Vec doesn't matter much (local variables, structs that have few instances) or cases where size of the Vec matters so much (millions of objects) that I want it as small as possible, and then a single-pointer ThinVec is even better. This being half-way in between, neither simplest, nor smallest, seems niche to me. There's Box<[T]> that's already a slice if you don't need it growable.

6 Likes