4 ms·
How about rearrange the graph to take advantage of the CPU's existing prefetch logic? The problem is that even with pointer chasing prefetch logic there are ot
by jhallenworld 10y ago
How about rearrange the graph to take advantage of the CPU's existing prefetch logic? The problem is that even with pointer chasing prefetch logic there are other device limitations: for example DRAM will deliver higher performance with sequential access.
- akkartik 10y agoI spent a while exploring this during grad school, but it seemed like a non-starter for two reasons: a) It requires the graph to only be accessed in one way. For example anything data-driven like binary tree search is out. b) At least in languages without copying collectors (my focus was C programs) it requires the graph to be immutable or mostly immutable.
- richdougherty 10y agoHere's a paper from Facebook about how they rearrange their data to improve locality. The paper is about distributed systems, but it's interesting and maybe relevant to graph locality on a single machine… https://blog.acolyer.org/2016/05/25/socialhash-an-assignment-framework-for-optimizing-distributed-systems-operations-on-social-networks/ https://blog.acolyer.org/2016/05/25/socialhash-an-assignment...