Repository navigation
Tracking issue for custom allocators in standard collections #42774
Description
The new Alloc trait defined in RFC 1398 was added in #42313 but the libs teamdecided to hold off on Vec integration just yet to be conservative.
This issue is intended to track the integration of the Alloc trait into standard collections like Vec, BTreeMap, etc. I'm not personally aware of any current blockers, but what we'll probably want to do as part of this issue includes:
- Develop a set of conventions for collections which support custom allocators
- Ensure no regressions with integration of a custom allocator:
- error messages should look as they do today
- no performance regressions at runtime
- ideally minimal compile-time impact
Reacted by Felipe S. S. Schneider, Florian Cäsar and Onur Orkun KADER
Reacted by Felipe S. S. Schneider and Florian Cäsar
Activity
Ericson2314 commentedon Jun 20, 2017
There are some very interesting issues here:
"Flat collections" (Vec, VecDec) can easily store a
&mutto the allocator they were crated with, indirection-heavy ones would be significantly bloated if everyBoxalso had an allocator reference.Ideally all collections would be resilient in the face of allocation failure, but that will take some major algorithms design work. It's better to convert quickly blowing up on OOM as they do today.
I had the idea of doing
trait InfallableAllocator = Allocator<Error=!>to signify an allocator that wouldn't fail (and thus must panick on OOM). If, when we en-mass convert collections, we have them take anInfallableAllocatorparameter, it will be clearer to the end-user that the collections are not oom-resilient, and there would be less panics strune about.Layouts, so I'll need to double-check that!wouldn't instead need to be somestrict Unsupported;. Then again, it isn't like the collections will be able to handle an unsupported layout either...Not sure what the ETA on default parameters is, so we're probably best off reexporting collections in std with the allocator parameter specialized to the global allcoator. This will work today, right?
joshlf commentedon Jun 20, 2017
@Ericson2314
I believe that the current design doesn't allow you to parametrize the error, so it must return the concrete error type with two arms -
UnsupportedandExhausted- and if you want to panic on OOM, it's your (the client's) responsibility to do that by panicking yourself or by calling theoommethod.Ericson2314 commentedon Jun 20, 2017
@joshlf err yes, this is predicated on us adding an associated error type.
joshlf commentedon Jul 14, 2017
@s3bk
So the idea is that, for allocators where all instances of the type refer to the same global singleton, you wouldn't actually need to store a reference? Presumably that wouldn't work for allocators that could actually have multiple distinct instances, right?
This motivates a follow-up: if you were implementing a global singleton, couldn't you just make the actual
Alloctype that you expose to users be a ZST that delegates to some private instance under the hood?hanna-kruppe commentedon Jul 15, 2017
@s3bk How common is the case where you will only ever need to deallocate? All the standard collections and smart pointers have methods that allocate new memory from the same allocator (usually
clone;RcandArchavemake_mut).Hm, now that I think about it, those methods already need to clone the allocator, so that would potentially offer a way out. Although it's unclear to me if we can switch between storing
AandA::DeallocInfoin the collection depending on whetherA: Clone, and it's also not clear to me if that would be a good design (it seems to work out mostly by chance, assuming it works out at all).hanna-kruppe commentedon Jul 15, 2017
@s3bk
make_mut_inmakesHeapAlloca special case for no good reason, granting it better ergonomics than other allocators that can supportmake_mutjust as well.Box::cloneallocates. Do you have examples of such non-std types?joshlf commentedon Jul 19, 2017
@s3bk
Is that a problem? The key property of
DeallocInfois the ability to, given a pointer allocated from the allocator, locate the allocator itself. Thus, you should be able to have any method that takes an already-allocated pointer have a_withvariant -realloc,shrink, etc.joshlf commentedon Jul 21, 2017
@s3bk
There's another angle to consider here: how do we obtain a
DeallocInfo? Presumably we need to guarantee that an object of that type has the same lifetime as theAllocit was obtained from, so how do we ensure that? I'm imagining something likefn dealloc_info(&mut self) -> &mut Self::DeallocInfo, but then the lifetimes get pretty hairy. In particular, once somebody has a&mut DeallocInfo, the allocator can't be used again until the reference goes away because it's a mutable reference. This means you can allocate oneBoxat a time from an allocator...42 remaining items
joshlf commentedon Feb 16, 2019
@passchaos Looks like it; thanks!
lachlansneff commentedon Feb 16, 2019
It'd be useful if we could use the traditional collection apis (
new,with_capacity, etc) if our allocator type parameter implementedDefault.SimonSapin commentedon Feb 17, 2019
As long as #27336 is not implemented, that would make some currently-valid programs ambiguous because type inference doesn’t know what allocator to pick.
lachlansneff commentedon Feb 17, 2019
That's been feature-gated for 3 years. Can it not just be stabilized?
SimonSapin commentedon Feb 17, 2019
Assuming yea mean #27336, it’s better discussed in the relevant tracking issue. I haven’t been following this one, but from a quick glance at the thread its implementation is not complete yet and it’s not "just" a matter of flipping the stabilization switch.
Manishearth commentedon Mar 27, 2019
Is there an RFC or design document talking about what the current plans for allocators in stdlib collections are? The allocators RFC leaves this stuff undecided, and this issue seems to be an implementation tracking issue.
SimonSapin commentedon Mar 27, 2019
At this point I think we need a champion who would summarize what’s still unresolved in the (numerous) discussions so far and see, try to build consensus, and make set of proposals (possibly as a new RFC).
Note that I am not volunteering at this time :]
gnzlbg commentedon Mar 27, 2019
Such a champion might probably want to start a working group, similar to the unsafe-code-guidelines, with its own github repo, where multiple parts of the "Allocators issue" can be explored in parallel, with active meetings to make progress, and where the parts of the issue that achieve consensus get merged slowly into a document with rationale, which is then sliced into suitable RFCs.
Summarizing the discussions effectively and putting them into a single comment would be a lot of work, and it won't IMO help much, because 10 people are going to answer to the summary, asking questions and discussing 10 different aspects of it.
The champion of such a working group would probably need to be a core team or lib team member with the time and will to see this through, and that will probably require somehow fitting allocators in the 2019 roadmap.
SimonSapin commentedon Mar 27, 2019
Regarding the 2019 roadmap, allocators are already the one item specifically mention for the library team in rust-lang/rfcs#2657. Though to some extent this might be wishful thinking as long as no-one steps up to lead this work.
I feel that this is a much smaller topic than unsafe code guidelines, but on further thought you’re probably right that this is a better model to keep sub-discussions organized.
Ericson2314 commentedon Mar 29, 2019
Once
Box<T, A>has landed, I'll finish off https://github.com/QuiltOS/rust/commits/allocator-error / #52420 . I'd be happy to make an RFC at that point describing what I did.alexcrichton commentedon Apr 22, 2019
I've made a post on internals where the libs team is considering spinning up a working group to drive this issue to completion, and if you're interested please feel free to comment there!
TimDiekmann commentedon May 4, 2019
As we now have a dedicated repository for the allocators WG this issue may be closed/locked to keep discussions in one place?
mark-i-m commentedon May 4, 2019
I think this issue still serves to funnel people in the direction of that repo. Nobody will know to go there otherwise.
alexcrichton commentedon May 6, 2019
I agree with @TimDiekmann that centralizing discussion is probably best now, so I'm going to close this in favor of the WG repository.
I'll open an issue on the repository about discoverability.