My qp trie code &lt;<a href="http:&#x2F;&#x2F;dotat.at&#x2F;prog&#x2F;qp&#x2F;&gt;" rel="nofollow">http:&#x2F;&#x2F;dotat.at&#x2F;prog&#x2F;qp&#x2F;&gt;</a> got a performance boost of about 20% by adding prefetch hints in the obvious places. The inner loop is fetch &#x2F; compute &#x2F; fetch &#x2F; compute, chaining down into the true. The next fetch will (usually) be some small offset from a pointer we can get immediately after its preceding fetch, so prefetch the base pointer, then compute to work out the exact offset.