Not using pointers at all for graphs.
I suspect a lot of the data where you want to use pointers for efficiency, is already in stricter shapes than graphs.
I suspect a lot of the data where you want to use pointers for efficiency, is already in stricter shapes than graphs.
And trees.
> I suspect a lot of the data where you want to use pointers for efficiency, is already in stricter shapes than graphs.
In games, graphs are used for pathfinding and other AI, for skeletal animation incl. IK.
Trees are everywhere: scene graph, bounding volumes, space partitioning, many others.
Because caches hierarchy, I usually want tree nodes to be located in nearby areas of RAM, i.e. a small arena allocator per tree/graph. This creates cycles, nodes are owned by arena and yet they need to have pointers between them.
I know about custom allocators in rust, but still, such data structure is much simpler to express in C++ with unsafe pointers. Games often know maximum sizes at compile time (e.g. in GTA5 there’s a hard limit of 255 skeletal bones) so that thing becomes a trivially simple wrapper around std::array.
Another problem with rust references for trees, sometimes nodes need to have pointers to parents. That again creates cycles.
2. MMUs in modern CPUs have prefetcher silicon in it. If the CPU detects you’re doing something resembling sequential access, it will prefetch more cache lines after that.
3. Modern CPUs also have TLBs https://en.wikipedia.org/wiki/Translation_lookaside_buffer Accessing data within the same page (platform-specific, on Windows often 4kb) is faster that accessing random locations because the virtual address->physical address mapping for that page will be in the cache.
4. Last but not least, with small arenas per tree/graph memory allocations and deallocations will be faster than even jemalloc, from the point of view of C runtime you’ll only call malloc/free once per graph, not once per item.
Look at the data in my repository: https://github.com/Const-me/CollectionMicrobench As you see, adding my custom allocator to these standard C++ collections improved performance substantially.
Update: also, with 1 arena per tree, it becomes orders of magnitude faster to copy the tree. You just memcpy and then sequentially walk through the arena adjusting the pointers. Or combine both in a single step.