Allocator traits and std::heap

[nikomatsakis]

📢 This feature has a dedicated working group, please direct comments and concerns to the working group's repo.

The remainder of this post is no longer an accurate summary of the current state; see that dedicated working group instead.

Old content

Original Post:

---

FCP proposal: #32838 (comment)
FCP checkboxes: #32838 (comment)

---

Tracking issue for rust-lang/rfcs#1398 and the std::heap module.

• land struct Layout, trait Allocator, and default implementations in alloc crate (Allocator integration #42313)
• decide where parts should live (e.g. default impls has dependency on alloc crate, but Layout/Allocator could be in libcore...) (Allocator integration #42313)
• fixme from source code: audit default implementations (in Layout for overflow errors, (potentially switching to overflowing_add and overflowing_mul as necessary).
• decide if realloc_in_place should be replaced with grow_in_place and shrink_in_place (comment) (Allocator integration #42313)
• review arguments for/against associated error type (see subthread here)
• determine what the requirements are on the alignment provided to fn dealloc. (See discussion on allocator rfc and global allocator rfc and trait Alloc PR.)
  • Is it required to deallocate with the exact align that you allocate with? Concerns have been raised that allocators like jemalloc don't require this, and it's difficult to envision an allocator that does require this. (more discussion). @ruuda and @rkruppe look like they've got the most thoughts so far on this.
• should AllocErr be Error instead? (comment)
• Is it required to deallocate with the exact size that you allocate with? With the usable_size business we may wish to allow, for example, that you if you allocate with (size, align) you must deallocate with a size somewhere in the range of size...usable_size(size, align). It appears that jemalloc is totally ok with this (doesn't require you to deallocate with a precise size you allocate with) and this would also allow Vec to naturally take advantage of the excess capacity jemalloc gives it when it does an allocation. (although actually doing this is also somewhat orthogonal to this decision, we're just empowering Vec). So far @gankro has most of the thoughts on this. (@alexcrichton believes this was settled in Allocator integration #42313 due to the definition of "fits")
• similar to previous question: Is it required to deallocate with the exact alignment that you allocated with? (See comment from 5 June 2017)
• OSX/alloc_system is buggy on huge alignments (e.g. an align of 1 << 32) if huge requested align, alloc_system heap::allocate on OS X returns unaligned values #30170 Add precondition to Layout that the align fit in a u32. #43217
• should Layout provide a fn stride(&self) method? (See also Separate size and stride for types rfcs#1397, Collapse trailing padding #17027 )
• Allocator::owns as a method? Alloc: Add owns method #44302

State of std::heap after #42313:

pub struct Layout { /* ... */ }

impl Layout {
    pub fn new<T>() -> Self;
    pub fn for_value<T: ?Sized>(t: &T) -> Self;
    pub fn array<T>(n: usize) -> Option<Self>;
    pub fn from_size_align(size: usize, align: usize) -> Option<Layout>;
    pub unsafe fn from_size_align_unchecked(size: usize, align: usize) -> Layout;

    pub fn size(&self) -> usize;
    pub fn align(&self) -> usize;
    pub fn align_to(&self, align: usize) -> Self;
    pub fn padding_needed_for(&self, align: usize) -> usize;
    pub fn repeat(&self, n: usize) -> Option<(Self, usize)>;
    pub fn extend(&self, next: Self) -> Option<(Self, usize)>;
    pub fn repeat_packed(&self, n: usize) -> Option<Self>;
    pub fn extend_packed(&self, next: Self) -> Option<(Self, usize)>;
}

pub enum AllocErr {
    Exhausted { request: Layout },
    Unsupported { details: &'static str },
}

impl AllocErr {
    pub fn invalid_input(details: &'static str) -> Self;
    pub fn is_memory_exhausted(&self) -> bool;
    pub fn is_request_unsupported(&self) -> bool;
    pub fn description(&self) -> &str;
}

pub struct CannotReallocInPlace;

pub struct Excess(pub *mut u8, pub usize);

pub unsafe trait Alloc {
    // required
    unsafe fn alloc(&mut self, layout: Layout) -> Result<*mut u8, AllocErr>;
    unsafe fn dealloc(&mut self, ptr: *mut u8, layout: Layout);

    // provided
    fn oom(&mut self, _: AllocErr) -> !;
    fn usable_size(&self, layout: &Layout) -> (usize, usize);
    unsafe fn realloc(&mut self,
                      ptr: *mut u8,
                      layout: Layout,
                      new_layout: Layout) -> Result<*mut u8, AllocErr>;
    unsafe fn alloc_zeroed(&mut self, layout: Layout) -> Result<*mut u8, AllocErr>;
    unsafe fn alloc_excess(&mut self, layout: Layout) -> Result<Excess, AllocErr>;
    unsafe fn realloc_excess(&mut self,
                             ptr: *mut u8,
                             layout: Layout,
                             new_layout: Layout) -> Result<Excess, AllocErr>;
    unsafe fn grow_in_place(&mut self,
                            ptr: *mut u8,
                            layout: Layout,
                            new_layout: Layout) -> Result<(), CannotReallocInPlace>;
    unsafe fn shrink_in_place(&mut self,
                              ptr: *mut u8,
                              layout: Layout,
                              new_layout: Layout) -> Result<(), CannotReallocInPlace>;

    // convenience
    fn alloc_one<T>(&mut self) -> Result<Unique<T>, AllocErr>
        where Self: Sized;
    unsafe fn dealloc_one<T>(&mut self, ptr: Unique<T>)
        where Self: Sized;
    fn alloc_array<T>(&mut self, n: usize) -> Result<Unique<T>, AllocErr>
        where Self: Sized;
    unsafe fn realloc_array<T>(&mut self,
                               ptr: Unique<T>,
                               n_old: usize,
                               n_new: usize) -> Result<Unique<T>, AllocErr>
        where Self: Sized;
    unsafe fn dealloc_array<T>(&mut self, ptr: Unique<T>, n: usize) -> Result<(), AllocErr>
        where Self: Sized;
}

/// The global default allocator
pub struct Heap;

impl Alloc for Heap {
    // ...
}

impl<'a> Alloc for &'a Heap {
    // ...
}

/// The "system" allocator
pub struct System;

impl Alloc for System {
    // ...
}

impl<'a> Alloc for &'a System {
    // ...
}

[gereeter]

I unfortunately wasn't paying close enough attention to mention this in the RFC discussion, but I think that realloc_in_place should be replaced by two functions, grow_in_place and shrink_in_place, for two reasons:

• I can't think of a single use case (short of implementing realloc or realloc_in_place) where it is unknown whether the size of the allocation is increasing or decreasing. Using more specialized methods makes it slightly more clear what is going on.
• The code paths for growing and shrinking allocations tend to be radically different - growing involves testing whether adjacent blocks of memory are free and claiming them, while shrinking involves carving off properly sized subblocks and freeing them. While the cost of a branch inside realloc_in_place is quite small, using grow and shrink better captures the distinct tasks that an allocator needs to perform.

Note that these can be added backwards-compatibly next to realloc_in_place, but this would constrain which functions would be by default implemented in terms of which others.

For consistency, realloc would probably also want to be split into grow and split, but the only advantage to having an overloadable realloc function that I know of is to be able to use mmap's remap option, which does not have such a distinction.

[gereeter]

Additionally, I think that the default implementations of realloc and realloc_in_place should be slightly adjusted - instead of checking against the usable_size, realloc should just first try to realloc_in_place. In turn, realloc_in_place should by default check against the usable size and return success in the case of a small change instead of universally returning failure.

This makes it easier to produce a high-performance implementation of realloc: all that is required is improving realloc_in_place. However, the default performance of realloc does not suffer, as the check against the usable_size is still performed.

[pnkfelix]

Another issue: The doc for fn realloc_in_place says that if it returns Ok, then one is assured that ptr now "fits" new_layout.

To me this implies that it must check that the alignment of the given address matches any constraint implied by new_layout.

However, I don't think the spec for the underlying fn reallocate_inplace function implies that it will perform any such check.

• Furthermore, it seems reasonable that any client diving into using fn realloc_in_place will themselves be ensuring that the alignments work (in practice I suspect it means that the same alignment is required everywhere for the given use case...)

So, should the implementation of fn realloc_in_place really be burdened with checking that the alignment of the given ptr is compatible with that of new_layout? It is probably better in this case (of this one method) to push that requirement back to the caller...

[pnkfelix]

@gereeter you make good points; I will add them to the check list I am accumulating in the issue description.

[pnkfelix]

(at this point I am waiting for #[may_dangle] support to ride the train into the beta channel so that I will then be able to use it for std collections as part of allocator integration)

[joshlf]

I'm new to Rust, so forgive me if this has been discussed elsewhere.

Is there any thought on how to support object-specific allocators? Some allocators such as slab allocators and magazine allocators are bound to a particular type, and do the work of constructing new objects, caching constructed objects which have been "freed" (rather than actually dropping them), returning already-constructed cached objects, and dropping objects before freeing the underlying memory to an underlying allocator when required.

Currently, this proposal doesn't include anything along the lines of ObjectAllocator<T>, but it would be very helpful. In particular, I'm working on an implementation of a magazine allocator object-caching layer (link above), and while I can have this only wrap an Allocator and do the work of constructing and dropping objects in the caching layer itself, it'd be great if I could also have this wrap other object allocators (like a slab allocator) and truly be a generic caching layer.

Where would an object allocator type or trait fit into this proposal? Would it be left for a future RFC? Something else?

[Ericson2314]

I don't think this has been discussed yet.

You could write your own ObjectAllocator<T>, and then do impl<T: Allocator, U> ObjectAllocator<U> for T { .. }, so that every regular allocator can serve as an object-specific allocator for all objects.

Future work would be modifying collections to use your trait for their nodes, instead of plain ole' (generic) allocators directly.

[nikomatsakis]

@pnkfelix

(at this point I am waiting for #[may_dangle] support to ride the train into the beta channel so that I will then be able to use it for std collections as part of allocator integration)

I guess this has happened?

[joshlf]

@Ericson2314 Yeah, writing my own is definitely an option for experimental purposes, but I think there'd be much more benefit to it being standardized in terms of interoperability (for example, I plan on also implementing a slab allocator, but it would be nice if a third-party user of my code could use somebody else's slab allocator with my magazine caching layer). My question is simply whether an ObjectAllocator<T> trait or something like it is worth discussing. Although it seems that it might be best for a different RFC? I'm not terribly familiar with the guidelines for how much belongs in a single RFC and when things belong in separate RFCs...

[steveklabnik]

@joshlf

Where would an object allocator type or trait fit into this proposal? Would it be left for a future RFC? Something else?

Yes, it would be another RFC.

I'm not terribly familiar with the guidelines for how much belongs in a single RFC and when things belong in separate RFCs...

that depends on the scope of the RFC itself, which is decided by the person who writes it, and then feedback is given by everyone.

But really, as this is a tracking issue for this already-accepted RFC, thinking about extensions and design changes isn't really for this thread; you should open a new one over on the RFCs repo.

[Ericson2314]

@joshlf Ah, I thought ObjectAllocator<T> was supposed to be a trait. I meant prototype the trait not a specific allocator. Yes that trait would merit its own RFC as @steveklabnik says.

---

@steveklabnik yeah now discussion would be better elsewhere. But @joshlf was also raising the issue lest it expose a hitherto unforeseen flaw in the accepted but unimplemented API design. In that sense it matches the earlier posts in this thread.

[joshlf]

@Ericson2314 Yeah, I thought that was what you meant. I think we're on the same page :)

@steveklabnik Sounds good; I'll poke around with my own implementation and submit an RFC if it ends up seeming like a good idea.

[alexreg]

@joshlf I don't any reason why custom allocators would go into the compiler or standard library. Once this RFC lands, you could easily publish your own crate that does an arbitrary sort of allocation (even a fully-fledged allocator like jemalloc could be custom-implemented!).

[joshlf]

@alexreg This isn't about a particular custom allocator, but rather a trait that specifies the type of all allocators which are parametric on a particular type. So just like RFC 1398 defines a trait (Allocator) that is the type of any low-level allocator, I'm asking about a trait (ObjectAllocator<T>) that is the type of any allocator which can allocate/deallocate and construct/drop objects of type T.

[Ericson2314]

@alexreg See my early point about using standard library collections with custom object-specific allocators.

[alexreg]

Sure, but I’m not sure that would belong in the standard library. Could easily go into another crate, with no loss of functionality or usability.

…

On 4 Jan 2017, at 21:59, Joshua Liebow-Feeser ***@***.***> wrote: @alexreg <https://github.com/alexreg> This isn't about a particular custom allocator, but rather a trait that specifies the type of all allocators which are parametric on a particular type. So just like RFC 1398 defines a trait (Allocator) that is the type of any low-level allocator, I'm asking about a trait (ObjectAllocator<T>) that is the type of any allocator which can allocate/deallocate and construct/drop objects of type T. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#32838 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAEF3IhyyPhFgu1EGHr_GM_Evsr0SRzIks5rPBZGgaJpZM4IDYUN>.

[alexreg]

I think you’d want to use standard-library collections (any heap-allocated value) with an *arbitrary* custom allocator; i.e. not limited to object-specific ones.

…

On 4 Jan 2017, at 22:01, John Ericson ***@***.***> wrote: @alexreg <https://github.com/alexreg> See my early point about using standard library collections with custom object-specific allocators. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#32838 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAEF3CrjYIXqcv8Aqvb4VTyPcajJozICks5rPBbOgaJpZM4IDYUN>.

[joshlf]

Sure, but I’m not sure that would belong in the standard library. Could easily go into another crate, with no loss of functionality or usability.

Yes but you probably want some standard library functionality to rely on it (such as what @Ericson2314 suggested).

I think you’d want to use standard-library collections (any heap-allocated value) with an arbitrary custom allocator; i.e. not limited to object-specific ones.

Ideally you'd want both - to accept either type of allocator. There are very significant benefits to using object-specific caching; for example, both slab allocation and magazine caching give very significant performance benefits - take a look at the papers I linked to above if you're curious.

[alexreg]

But the object allocator trait could simply be a subtrait of the general allocator trait. It’s as simple as that, as far as I’m concerned. Sure, certain types of allocators can be more efficient than general-purpose allocators, but neither the compiler nor the standard really need to (or indeed should) know about this.

…

On 4 Jan 2017, at 22:13, Joshua Liebow-Feeser ***@***.***> wrote: Sure, but I’m not sure that would belong in the standard library. Could easily go into another crate, with no loss of functionality or usability. Yes but you probably want some standard library functionality to rely on it (such as what @Ericson2314 <https://github.com/Ericson2314> suggested). I think you’d want to use standard-library collections (any heap-allocated value) with an arbitrary custom allocator; i.e. not limited to object-specific ones. Ideally you'd want both - to accept either type of allocator. There are very significant benefits to using object-specific caching; for example, both slab allocation and magazine caching give very significant performance benefits - take a look at the papers I linked to above if you're curious. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#32838 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAEF3L9F9r_0T5evOtt7Es92vw6gBxR9ks5rPBl9gaJpZM4IDYUN>.

[joshlf]

But the object allocator trait could simply be a subtrait of the general allocator trait. It’s as simple as that, as far as I’m concerned. Sure, certain types of allocators can be more efficient than general-purpose allocators, but neither the compiler nor the standard really need to (or indeed should) know about this.

Ah, so the problem is that the semantics are different. Allocator allocates and frees raw byte blobs. ObjectAllocator<T>, on the other hand, would allocate already-constructed objects and would also be responsible for dropping these objects (including being able to cache constructed objects which could be handed out later in leu of constructing a newly-allocated object, which is expensive). The trait would look something like this:

trait ObjectAllocator<T> {
    fn alloc() -> T;
    fn free(t T);
}

This is not compatible with Allocator, whose methods deal with raw pointers and have no notion of type. Additionally, with Allocators, it is the caller's responsibility to drop the object being freed first. This is really important - knowing about the type T allows ObjectAllocator<T> to do things like call T's drop method, and since free(t) moves t into free, the caller cannot drop t first - it is instead the ObjectAllocator<T>'s responsibility. Fundamentally, these two traits are incompatible with one another.

[Amanieu]

The wrapper would return NonNull::dangling for all zero-sized allocations and ignore all zero-sized deallocations. Non-zero allocations are passed on to the underlying allocator.

[lilith]

That makes sense; I forgot size was passed to dealloc.

…

On Tue, Jun 27, 2023, 8:40 PM Amanieu ***@***.***> wrote: The wrapper would return NonNull::dangling for all zero-sized allocations and ignore all zero-sized deallocations. Non-zero allocations are passed on to the underlying allocator. — Reply to this email directly, view it on GitHub <#32838 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAA2LH4DZ5YKLOAMLJVIJGLXNOKR5ANCNFSM4CANQUGQ> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[thomcc]

As a side note, all the logic for handling zero-sized allocations could also be implemented as a type that wraps an Allocator and causes zero-sized allocations to become no-ops.

This is true, but you end up with code performing the same checks many times. For example, both sides of the interface end up checking here if your underlying allocator doesn't handle zero-sized allocations well, and most (or at least very many) designs for allocators do not, in my experience.

Given that forbidding it is consistent with the earlier design (GlobalAlloc), I don't really see what we get by allowing it at this point when it clearly causes trouble both for users and implementers of the API.

[RalfJung]

I don't really see what we get by allowing it at this point when it clearly causes trouble both for users and implementers of the API.

It can't possible cause trouble for users -- every user that is correct wrt the more restricted API (that is UB on zero-sized allocs) is also correct wrt the current API.

[Jules-Bertholet]

Another reason to have the collection check for zero size: for e.g. Box<T>, the collection knows statically whether T is a ZST, so the checks can be optimized out.

It can't possible cause trouble for users -- every user that is correct wrt the more restricted API (that is UB on zero-sized allocs) is also correct wrt the current API.

Correctness trouble is the worst kind of trouble, but not the only kind. Users also want performance, which the current API pessimizes.

[thomcc]

I also don't necessarily agree that the current API avoids correctness issues. We clearly had one in the stdlib code, which would have almost certainly been avoided if we made it clear that zero-sized allocations were forbidden (especially if we forbid it by making things take a NonZeroLayout or such).

My experience is that the sort of optimizations that the stdlib does here are quite common, and not a special case. This is likely because of how long we've documented that zero-sized allocations are free and infallible (something which definitely won't be universally true if we delegate this to the underlying allocator).

[RalfJung]

FWIW, if I read 56cbf2f correctly, then RawVec actually did this correctly when the Allocator (AllocRef back then) trait was changed to allow zero-sized allocations. The bug was introduced in 2526acc, a later commit in the same PR (#70362).

I also don't necessarily agree that the current API avoids correctness issues.

I agree that for data structures that have a special zero-size state themselves where they don't own any memory that must be given back to the allocator, the current API does not help at all.

The question is, is that case common enough to justify hurting the alternative case where data structures would be completely fine with always owning some allocated memory, even when the size is 0 -- basically leaving it to allocators to make size 0 efficient, instead of having to implement that optimization for each data structure? Naively it seems much better to do this in the allocator once rather than in every single data structure, but clearly Vec disagrees since it doesn't trust the allocator doing this right. Interesting.

Here is a possible alternative to just making Allocator require non-ZST: we could say that passing the result of NonNull::dangling() to deallocate/grow/shrink with a size-zero layout must always be allowed and not attempt to actually deallocate that pointer. Then Vec::new could still use NonNull::dangling, but all the rest of the Vec code could freely treat the backing buffer as if it was created by the allocator, and drop could unconditionally call deallocate.

That would make the buggy shrink actually legal. It would avoid having to re-implement the "size 0 optimization" in each and every data structure, instead having it implemented once in the allocator. So just from a code structure perspective, it seems to me like that is the API that types like Vec actually want: a const-compatible, zero-cost fn new without having to worry about size 0 anywhere. allocate would be safe without the need for a NonZeroLayout.

What I don't know is whether this API is something allocators can reasonably implement. @thomcc what do you think?

[nbdd0121]

Here is a possible alternative to just making Allocator require non-ZST: we could say that passing the result of NonNull::dangling() to deallocate/grow/shrink with a size-zero layout must always be allowed and not attempt to actually deallocate that pointer.

How would you tell apart dangling() from a valid pointer?

[RalfJung]

Vec does it, so clearly it is possible. It would be up to the allocator to ensure that for size 0, it can never confuse dangling with a valid pointer.

[Jules-Bertholet]

Vec checks for capacity == 0 to determine whether its pointer is dangling.

[thomcc]

a const-compatible, zero-cost fn new without having to worry about size 0 anywhere

I'm not sure how it's const-compatible unless the allocator is a const trait/impl/something (or at least allocation is const), which doesn't seem likely to be the case most of the time (since usually allocation requires a number of operations which are problematic for const). I have to think about the rest of your comment though.

[RalfJung]

NonNull::dangling is a const fn, which is all that is needed for Vec::new. (The function would stay unchanged compared to what the stdlib does right now.)

To be clear, I have no idea if this proposal makes sense. The part where the allocator, in dealloc, has to handle dangling and therefore has to ensure to never actually put a real allocation (that must be freed) of size 0 at that address is certainly somewhat suspicious. I arrived at this purely from the perspective of "what would it take for Vec to not need to special-case capacity 0".

[thomcc]

Oh, I see. I misinterpreted your proposal then.

I think the problem here is that now dealloc can't solely use allocation size to tell the difference between, since it needs to know if the allocation came from a call to alloc with a zero-sized layout, or if it came from NonNull::dangling(), which can return a valid pointer (and in practice often will on 32 bit targets if the alignment is sufficiently high).

[RalfJung]

So sounds like allocators would basically be forced to not have an actual allocation for size 0, so that they can make 'deallocate' always a NOP when the size is 0.

[thomcc]

Yeah. We'd have to document that a zero sized allocation needs to be equivalent to dangling (or at least some kind of no-op), which seems a bit odd to me, but it would work. Basically, instead of telling users of Allocator that they cant' give allocators a zero-sized layout and should allocate a zero-sized layout in a certain way, we're saying they must behave a specific manner when given zero-sized layouts.

The downside here is that the checks couldn't always be removed in cases where Allocator is a trait object. It also plausibly adds a branch into the allocation path that could otherwise be avoided. It also is a bit error-prone if not documented properly, as I go over in #32838 (comment) (although I've softened on this proposal since the issues I hit could possibly be addressed with documentation).

This would make the "handle zero-sized layout by rounding up" approach suggested elsewhere in this thread invalid though (but I don't see a way to keep it without many other downsides).

[thomcc]

I wrote a blog post announcing that I'm intending on working on the Allocator design, and I wrote down (roughly) a set of things I'm thinking about https://shift.click/blog/allocator-trait-talk.

Largely speaking my feeling that Allocator needs more comprehensive rework/consideration is why I haven't filed a PR for the extra parameter for grow, for any changes around zero-sized allocations¹, etc.

Anyway, all of this is tricky because Allocator is trying to serve so many roles, so it's hard to find a design that doesn't end up making a trade-off that negatively impacts something or other, and it takes a lot of experimentation to play around with different implementations of the trait and code using it.

Footnotes

1. I've started to have second thoughts on zero-sized allocations, which is one of the things I'm hoping to work through. I think that perhaps Allocators which use resources for zero-sized allocations is a little analogous to Iterators which return None in the middle -- IOW, could an approach more similar to FusedIterator/Fuse work? I'm not sure, maybe. ↩

[wallgeek]

I'm sorry but isn't both "new_in" and "with_capacity_in" have very minor mistakes in source documentation in example section? Or am I missing something?
https://doc.rust-lang.org/std/collections/struct.VecDeque.html

[udoprog]

@wallgeek No, you're right. They don't exemplify the APIs at all. It should be fixed!

[pravic]

I've checked all new_in methods in https://doc.rust-lang.org/std/index.html?search=new_in&filter-crate=std:

• VecDeque - a blunt copy from new
• BTreeMap

  • Makes a new empty BTreeMap with a reasonable choice for B.

  • what is B exactly?
• BTreeSet - ditto with BTreeMap
• LinkedList

  • Constructs an empty LinkedList<T, A>.

  • the description can be improved

The rest is okay.

[SimonSapin]

• what is B exactly?

Currently in std:

const B: usize = 6;

The struct-level docs explain this and compare a B-tree with a binary tree that would have individual allocations for each item:

https://doc.rust-lang.org/std/collections/struct.BTreeMap.html

A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing this, we reduce the number of allocations by a factor of B, and improve cache efficiency in searches.

It’s probably not relevant for the docs of a constructor to talk about the "choice" of B, since that choice is compile-time constant in the current implementation. (As opposed to something users could influence like Vec::with_capacity)

[vmolsa]

With allocator_api, we now have safe memory allocation methods like try_new() for types like Box and Arc, and some collections (Vec, HashMap) support try_reserve as a workaround. However, collections like BTreeMap lack equivalent allocation-checked methods for operations like insert. To build a more consistent API, could we introduce allocation-checked variants across std::collections::* with a clear prefix like checked_, or safe_, etc.. (e.g., safe_insert, checked_push)? These methods would return Result<T, AllocError> on allocation failure, streamlining safe memory allocation handling.