4 ms·
> 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 ot
by 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