Adding a const `B` parameter to BTreeMap?

libs
1

Now that rust is getting const generics (and default const generics seem to be behind a feature), any thoughts on adding a const B: usize = 6 const parameter to BTreeMap?

Right now, internal sizes of BTreeMap structures are defined as constants: rust/node.rs at master · rust-lang/rust · GitHub

const B: usize = 6;
pub const CAPACITY: usize = 2 * B - 1;
pub const MIN_LEN_AFTER_SPLIT: usize = B - 1;
const KV_IDX_CENTER: usize = B - 1;
const EDGE_IDX_LEFT_OF_CENTER: usize = B - 1;
const EDGE_IDX_RIGHT_OF_CENTER: usize = B;

Instead, B could be defined in:

pub struct BTreeMap<K, V, const B: usize = 6> {
    ...
}

and then the other constants could be defined internally as const functions of B or similar.

With custom allocators being added to most collections, this would have to turn into:

pub struct BTreeMap<K, V, A: Allocator = Global, const B: usize = 6> {
    ...
}

It's actually impossible to have both type and const parameters with defaults (the compiler complains no matter what), but that looks like a simple oversight.

This might let applications tune the memory consumption and performance of BTreeMap.

10 Likes
2

Do note that after adding a const parameter, adding a defaulted type parameter would be breaking, as <K, V, {6}> wouldn't work anymore.

Other than that, it seems reasonable to do.

2 Likes
3

(note that defaulted const generics are only parsed at the moment: we added this very recently, and as soon as you enable the feature gate it'll ICE everywhere)

4 Likes
4

Yeah, this would have to be added after the allocator parameter.

5

Could that be mitigated by giving the struct a new name when the parameter is added and defining a type alias for the old name that maintains the original parameter list?

pub type BTreeMap<K,V,const B:usize = 6> = BTreeMapWithAlloc<K,V,Global,B>;
pub struct BTreeMapWithAlloc<K,V,A:Allocator,const B:usize {
    /* ... */
}
2 Likes
6

Logistically, the first thing you might want to check is whether a const generic parameter can be marked #[unstable]. If that works then this is more plausible. If not, I'm not sure that this is "obvious" enough to go in insta-stable.

IIRC that was discussed for things like Box's allocator parameter, and it was decided it wasn't a good way forward. I forget exactly why -- maybe because the ___WithAlloc name would show in error messages?

5 Likes
7

What would be the general policy here? I bet there are more tweakables here and there which we can expose this way. For example, we can treat Vec’s growth factor the same.

My gut feeling is that this’ll give needless choice with little benefit. I’d rather have the standard library pick the optimal B automatically, based on the sizeof of key.

7 Likes
8

What algorithm will pick the optimal B? Seems very architecture and situation dependent.

9

One fairly forward-compatible way might be to add a "policy" type parameter à la C++, something like

trait BTreePolicy {
    const B: usize;
    const CAPACITY: usize;
    // etc
}
struct DefaultPolicy<const B: usize>;
impl<const B: usize> BTreePolicy for DefaultPolicy<B> {
    const B: usize = B;
    const CAPACITY: usize = 2 * B - 1;
    // etc
}

struct BTreeMap<K, V, A: Alloc = Global, P: BTreePolicy = DefaultPolicy<6>> {
    // ...
}
6 Likes
10

I like this idea the best; it's like the Context parameter of Future::poll. Since Context leaves open the possibility of adding more fields later on, it allows forward compatibility for when someone decides that more knobs are needed.

11

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.