3 ms·
Using indices is a (slight) improvement over pointers, since in Rust you will benefit from bounds checking (restricting you to the memory allocated for that tre
by agalunar 3y ago
Using indices is a (slight) improvement over pointers, since in Rust you will benefit from bounds checking (restricting you to the memory allocated for that tree).
(If you use u32 for the indices, you also save some space.)
- taeric 3y agoIt is hilarious how much space you can save by using smaller indexes than a pointer. Especially on modern architectures.
- burntsushi 3y agoYes! The regex crate does this and it saves quite a bit of memory.
- taeric 3y agoIt is the kind of low hanging optimization that I used to think was greatly oversold. And, to be fair, for many programs I would still wager it probably is. If you are chasing a ton of pointers, though, it is definitely worth considering how many more you can hold in memory with smaller sizes. I think I remember a discussion a while back lamenting that we just tacitly accepted wide pointers. If anyone has a link going over that, I'd be delighted to read it again. I'm 90% sure I did not understand it when I first saw it. :D
- eclark 3y agoI am currently writing a CFR Tree that has nodes that can be self-referential. https://github.com/elliottneilclark/rs-poker/pull/92 https://github.com/elliottneilclark/rs-poker/pull/92 The idea is that every game of poker is a walk through a tree. Keeping track of probabilities and outcomes allows for exploration of the correct way to play. Using indices made building the tree easier (though I am still one bug away from it all working).
- deleted 3y ago[deleted]