Currently, BTreeMap::new() allocates an empty root node. This is in spite of all of our other collections managing to avoid this. In #50240 it was demonstrated that there's massive wins to be had by avoiding allocating here. In the past we avoided implementing this because it simplified the code of BTreeMap a lot (which is already pretty gnarly code).
I see two ways to do this
- Wrap everything in Options, adding extra branches on accesses to iterators and the map itself.
- Do lots of clever shit, introducing minimal branches on access.
Some examples of clever shit:
-
The core Range iterator primitive can always always be initialized with two NonZero::dangling() pointers and len = 0. The existing branches will then do the correct thing. (this is how empty slices generally work)
-
By changing the layout of LeafNode to have the metadata first, we can statically allocate a LeafNode<u64, u64> (say) for all empty instances of BTreeMap to share. get/remove queries will then naturally work correctly without extra branches. See thin-vec for an example of doing this. An extra branch will probably need to be added to insert to check if we're pointing at the static singleton; not a big deal.
Currently,
BTreeMap::new()allocates an empty root node. This is in spite of all of our other collections managing to avoid this. In #50240 it was demonstrated that there's massive wins to be had by avoiding allocating here. In the past we avoided implementing this because it simplified the code of BTreeMap a lot (which is already pretty gnarly code).I see two ways to do this
Some examples of clever shit:
The core Range iterator primitive can always always be initialized with two
NonZero::dangling()pointers andlen = 0. The existing branches will then do the correct thing. (this is how empty slices generally work)By changing the layout of LeafNode to have the metadata first, we can statically allocate a
LeafNode<u64, u64>(say) for all empty instances of BTreeMap to share. get/remove queries will then naturally work correctly without extra branches. See thin-vec for an example of doing this. An extra branch will probably need to be added toinsertto check if we're pointing at the static singleton; not a big deal.