Systems, methods, and apparatus for prefetching node data for linked data structure traversal

摘要

Systems, methods, and apparatus are herein disclosed for prefetching node data of a linked data structure into a processor's cache so as to decrease linked data structure traversal latency. In particular, as the linked data structure is created or modified, forward and reverse prefetch nodes are identified and links identifying locations of these nodes are written to nodes that will be traversed N nodes prior to the prefetch nodes. Once the linked data structure has been created, traversals of the structure use the prefetch links to prefetch node data into the processor cache, so that when traversal reaches a node, that node's data is read from processor cache rather than from memory.