Generic type parameters to choose generation and index sizes

[mikwielgus]

Currently, both the generation and index types are u32. Hence, keys (indexes) are always 8 bytes.

In some applications, it may be beneficial to have smaller keys (indexes), e.g. u16 generation and u16 true index summing up to 4 bytes. This not only reduces used memory, but can also considerably improve iteration speed (since iteration is often memory-bound).

To make it possible to choose sizes, thunderdome::Arena could take generation and index types as generic parameters, e.g. thunderdome::Arena<G, I>, or even thunderdome::Arena<K: Key> and provide some default types that implement Key.

[LPGhatguy]

This is a very interesting idea! Smaller keys are attractive. We should be able to isolate any of the complexity to Generation and Index and leave Arena mostly unchanged ideally.

I think we would want to do this with an optional named type parameter, similar to the choice of hasher and allocator in std. Something like thunderdome::Arena<T, Primitive = u32>.

I'm not sure it makes sense to ever have a u32 generation and u16 slot or vice-versa because the size of a struct containing (u32, u16) and a struct containing (u32, u16)` are the same.

[mikwielgus]

I'm not sure it makes sense to ever have a u32 generation and u16 slot or vice-versa because the size of a struct containing (u32, u16) and a struct containing (u32, u16)` are the same.

In thunderdome, values are stored in entries along with generations, so it does make sense to use a smaller generation type than of true index (slot) if you want to decrease memory use or speed up memory-bound iteration.