A symbol lookup walks a chained hash table and spends 60 percent of its time on the load of the first node. The keys for the next 8 lookups are already in hand. Describe how software prefetching helps, the distance you would choose, and two cases where it makes things worse.

A symbol lookup walks a chained hash table and spends 60 percent of its time on the load of the first node. The keys for the next 8 lookups are already in hand. Describe how software prefetching helps, the distance you would choose, and two cases where it makes things worse.

Approach: Separate the address computation from the dependent load, then work out how far ahead a prefetch must issue to cover the latency it is hiding.

Issue a prefetch for the bucket of lookup i plus k while processing lookup i, choosing k so the prefetch has 200 to 300 cycles to complete, which is 4 to 8 iterations for a loop of this weight, and the effect is to overlap what was a serial chain of main memory latency of about 80 nanoseconds each. The bucket address depends only on the hash of a key already in hand, so the prefetch can issue long before the node is needed, which is what makes the pattern work at all. Prefetching the chained node itself does not help, because its address is known only after the bucket load returns, and that is pointer chasing, which is the argument for open addressing here. It gets worse when the distance is so long that the line is evicted before use, and when the extra instructions saturate the load ports on a loop that was already bandwidth bound.

Follow-up: What do you do instead when the eight keys arrive one at a time from the wire rather than being known in advance?

Key concepts: software prefetch, prefetch distance, memory latency, pointer chasing.