Skip to content

libstd: Store capacity of std::vec::Vec on the heap? #67024

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
michaelwoerister opened this issue Dec 4, 2019 · 7 comments
Closed

libstd: Store capacity of std::vec::Vec on the heap? #67024

michaelwoerister opened this issue Dec 4, 2019 · 7 comments
Labels
A-collections Area: `std::collections` C-enhancement Category: An issue proposing an enhancement or a PR with one. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.

Comments

@michaelwoerister
Copy link
Member

This has probably been discussed before but in case it hasn't: It should be possible to store a vec's capacity as part of its heap allocation and thus shrink Vec from three to two words. It would make a difference for code that contains many empty Vecs and code that moves them around a lot. The downside is that the implementation is a bit more complicated and that the capacity can only be accessed after following a pointer. It might still be a worthwhile trade off.

cc @rust-lang/libs (and @nnethercote who likes this kind of thing :))

@jonas-schievink jonas-schievink added A-collections Area: `std::collections` C-enhancement Category: An issue proposing an enhancement or a PR with one. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. labels Dec 4, 2019
@SimonSapin
Copy link
Contributor

Why just the capacity and not also the length? https://crates.io/crates/thin-vec does that.

Either way, this may not be possible or desirable for std::vec::Vec<T> since we have existing APIs like From<Box<T>> or from_raw_parts.

It would make a difference for code that contains many empty Vecs and code that moves them around a lot.

If you have specific pieces of code in mind, try changing it to use ThinVec or something like it?

@Amanieu
Copy link
Member

Amanieu commented Dec 4, 2019

This was attempted with HashMap but the results seemed to be in the noise:

@michaelwoerister
Copy link
Member Author

Why just the capacity and not also the length?

I would expect that the length needs to be accessed more often than the capacity, so it would be less good of a trade-off. Hard to tell without a set of reference benchmarks though.

Thanks for the links, @Amanieu!

Feel free to close this issue if you have reason to believe that it won't improve performance/memory consumption or just isn't worth the trouble.

@SimonSapin
Copy link
Contributor

this may not be possible […] for std::vec::Vec<T>

I think this is the first concern for this proposal as is. But that doesn’t mean that having some container like that isn’t worth investigating.

@michaelwoerister
Copy link
Member Author

The docs for from_raw_parts says

  • ptr needs to have been previously allocated via String/Vec (at least, it's highly likely to be incorrect if it wasn't).

So it's possible to make this work, probably, but would also probably break lots of code in the wild.

@RustyYato
Copy link
Contributor

RustyYato commented Dec 6, 2019

Given that we guarantee

Most fundamentally, Vec is and always will be a (pointer, capacity, length) triplet. No more, no less. The order of these fields is completely unspecified, and you should use the appropriate methods to modify these. The pointer will never be null, so this type is null-pointer-optimized.

https://doc.rust-lang.org/std/vec/struct.Vec.html#guarantees

This is not possible

@michaelwoerister
Copy link
Member Author

Well, that decides it :) Great find, @KrishnaSannasi!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-collections Area: `std::collections` C-enhancement Category: An issue proposing an enhancement or a PR with one. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.
Projects
None yet
Development

No branches or pull requests

5 participants