I'm sort of surprised that the gains are so high. I'd tend to expect the cost of a pointer deference in a large data structure to be bigger than the comparison

I'm sort of surprised that the gains are so high. I'd tend to expect the cost of a pointer deference in a large data structure to be bigger than the comparisons even with the attendant branch mispredictions. EDIT: Oh, duh, if the path hints are useful then cache locality means that the data you're looking for is already nearby. If the hint works the cost of the lookup will actually be dominated by the comparisons.