6 ms·
> You could put all of your graph nodes into a linear data structure like an array, and have them point to each other by holding a list of indices instead of a
by dmitrygr 7y ago
> You could put all of your graph nodes into a linear data structure like an array, and have them point to each other by holding a list of indices instead of a list of pointers
Rust practitioners keep proposing this solution. It is like you have never heard of caches or do not understand that modern CPUs have multiple special prefetchers for pointer chasing and no prefetchers for "rust fanatics"
This solution will be SIGNIFICANTLY slower on any modern CPU. By a wide margin! Since you'll keep having to wait for main memory as the cache prefetchers have no idea about this insane scheme and will not prefetch the data for you. They will for actual pointers.
- aw1621107 7y ago> It is like you have never heard of caches But isn’t that part of the point of putting nodes into an array? So the nodes are guaranteed to sit next to each other in memory, and so are quite likely to be in cache? > do not understand that modern CPUs have multiple special prefetchers for pointer chasing and no prefetchers for "rust fanatics" Doesn’t array indexing reduce down to pointer chasing anyways? Or are you saying that the prefetchers can’t see through “nested” array accesses (e.g. nodes[nodes[i].out[0]].data vs node.out[0].data)?
- dmitrygr 7y agoYes that is what I am saying. See Intel manuals for patterns they can detect. Mostly it is strided accesses and use of pointers at fixed offsets of a structure which the previous pointer pointed to.
- aw1621107 7y agoSo I guess it comes down to whether the graph would fit into cache and the particulars of the access patterns? If the graph fits into cache as an array the prefetchers would be more or less unnecessary since everything is already there. Beyond that, I probably don’t have enough experience or knowledge to make a good guess.
- dmitrygr 7y agoYes. If the entire thing fits yes, but then it is small enough that you might as well manage it in Basic or JavaScript. No real programming required
- adito 7y ago> This solution will be SIGNIFICANTLY slower on any modern CPU. By a wide margin! I'm not an expert and would know more. Can you point out on any benchmark demonstrating those claim? Would love to see the actual number.
- fredsanford 7y agoSearch for ArrayOfStructures or StructureOfArrays to see benchmarks similar to what you're asking for
- dodobirdlord 7y agoI don’t do much graph programming, and the few pieces of graph programming I’ve had to work with that needed to be high-performance fit in L1/L2. But for most non-pathological graphs (treelike, few backlinks from nodes deep in the graph to nodes shallow in the graph, nodes are small) you could arrange a statistical locality property that child nodes are usually located at nearby greater indices. Most operations on the graph would sweep left->right in small strides likely to be either within the a cache page or onto a page that has been prefetched by the linear memory access pattern prefetcher. Certainly this is more awkward to write than pointer linking, but approximately the same performance should be achievable for sparse or treelike graphs. If you need to work with dense graphs larger than the size of the cache performance will suffer a lot, but this meets the criteria to justify using unsafe, at which point the implementation would look a lot like a C implementation.