4 ms·
> for example in games, where an ECS design using IDs is generally preferable to direct references In scripting/gameplay parts of games maybe. In rendering or
by Const-me 8y ago
> for example in games, where an ECS design using IDs is generally preferable to direct references
In scripting/gameplay parts of games maybe.
In rendering or other performance-critical components, pointers are just faster. They are single RAM reference, IDs are 2 RAM references (and in case of languages like C# or Rust, plus bounds checking).
- kibwen 8y agoSure, and fortunately ECSes are usually for managing world state, leaving one free to use references for graphics, physics, AI, etc. An ECS-esque design for one component of the system does not preclude using pointers elsewhere.
- Const-me 8y ago> An ECS-esque design for one component of the system does not preclude using pointers elsewhere. I know how ECS work, but GP was advocating Rust's way i.e. not using pointers at all.
- eddyb 8y agoNot 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 agoIf 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 agoCould 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 ago1. 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.
- kibwen 8y ago> advocating Rust's way i.e. not using pointers at all I'm not sure where anyone could have gotten this impression, because 99.99999% of Rust code uses pointers (via references, which are statically verified and compile down to raw pointers). Even the people making graphs out of indices will be using references in some capacity.
- pcwalton 8y agoIn hot code, base will be cached in a register.
- Const-me 8y agoI don’t think so. It can be cached by very small chance. Or it can be cached if the developer did profile-guided optimization. Otherwise it’ll be evicted from these registers pretty often. There’re not that many general purpose registers, so unless the processing code is trivially simple like CRC32, the compiler will reuse these registers for something else.