4 ms·

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.

by eddyb 8y ago

Const-me 8y ago
> Not using pointers at all for 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.
- kibwen 8y ago
  If you have a tree then your data necessarily isn't cyclic or self-referential, in which case you likely won't have any problem using references.
  - Const-me 8y ago
    > then your data necessarily isn't cyclic or self-referential, in which case you likely won't have any problem using references. 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.
    - verdagon 8y ago
      Could you elaborate on the "nearby areas of RAM" part? From what I've been learning, cache lines are only 64 bytes, so if you can't fit things in the same 64 bytes then it's not worth thinking about. What am I missing?
      - Const-me 8y ago
        1. If these structures take 100 bytes, they will span 2-3 cache lines. You access an item, CPU caches these 2-3 lines. If shortly after that you access the neighbor one because your algorithm walked the tree/graph pointers and come to a neighbor item, you save some RAM latency. If these items are 1MB/each the win will be very small, but for small structures the performance difference can be huge. 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 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 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.

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.

by eddyb 8y ago

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.

Const-me 8y ago

> Not using pointers at all for 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.

kibwen 8y ago
If you have a tree then your data necessarily isn't cyclic or self-referential, in which case you likely won't have any problem using references.
- Const-me 8y ago
  > then your data necessarily isn't cyclic or self-referential, in which case you likely won't have any problem using references. 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.
  - verdagon 8y ago
    Could you elaborate on the "nearby areas of RAM" part? From what I've been learning, cache lines are only 64 bytes, so if you can't fit things in the same 64 bytes then it's not worth thinking about. What am I missing?
    - Const-me 8y ago
      1. If these structures take 100 bytes, they will span 2-3 cache lines. You access an item, CPU caches these 2-3 lines. If shortly after that you access the neighbor one because your algorithm walked the tree/graph pointers and come to a neighbor item, you save some RAM latency. If these items are 1MB/each the win will be very small, but for small structures the performance difference can be huge. 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 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 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.