Software prefetch can be a big win when doing a traversal that lets you predict random reads far enough in advance, which is generally not the case for linked l

Software prefetch can be a big win when doing a traversal that lets you predict random reads far enough in advance, which is generally not the case for linked list or tree traversals. (Since it's microarchitecture as well as data dependent, you'll need to do a lot of profiling) A better trick for hiding memory latency in these cases is to interleave multiple searches (perhaps of different instances of the data structure). For example you can write binary_tree.find_both(key1, key2) that's almost as fast (on large trees) as finding a single key.