Smaller pointers

1

To allocate a pointer-heavy data structure like some kind of tree I could speed up the code significantly using a memory arena, like:
https://crates.io/crates/typed-arena

arena.alloc() returns a reference, that's usable inside the tree nodes.

Is it possible to create a generic arena data structure like typed-arena that returns 32 bit pointers-like structures (in a 64 bit system) that are usable like regular pointers to reduce the memory allocated by the whole tree?

In general is it a good idea to add Rust standard library some tools to use 32 bit pointers on a 64 bit system?

2

What you could do (while not really a reply to your question but may still be useful) is to have u16/u32 indices into a separate Vec<T> of your type.

This something we use in game dev to not store u64 pointers in tight data structures.

3

The problem with indices of course is that you can forget to update them as objects move around (if they do) and then a lot of fun ensues.

4

Sure. You need to keep things in sync but I have rarely found that to be a big problem. This is just something that you have to live with. Also in this case you don't run into explicit lifetime issues (which of course may be both good or bad depending on what you are doing) which you can end up with when tree nodes needs to refer to each other.

5

Oh I agree it’s a viable solution. You have to arrange for moving objects to occur such that you also (somehow) know where all the indices to it are. In a tree that’s typically easy enough.

6

Yeah if you do operations on the array (unless only pushing) they need to be matched in the tree, and as you point out if it's a fairly standard tree structure this isn't usually a big deal but of course depends on the use case.

7

There is also the x32 target.

1 Like
8

Actually you can create a wrapper type for u16 that is lifetime-bound to the vector using a PhantomData field.

1 Like