7

Most modern languages make a heavy use of pointers / references: a typical OOP language uses VMT lookups, a typical functional language builds key data structures out of pointers, etc. Even typical C code often sports things like foo->bar->baz.

It is well-known that dereferencing a pointer is cache-unfriendly, unless the pointer happens to point very near some just-accessed location and hits the same cache line.

Is there, or has there been, hardware that tries to address this problem? It's not currently widely deployed; why?

Hitting L1 or even L2 cache is so much faster than hitting RAM on current hardware that the goal of making pointer dereferencing reap some of the caching benefits seems worthy.

Improve this question
14
  • 2
    remember that foo->bar->baz is *(*(foo+barOff)+bazOff) this is 2 derefs that can be anywhere in memory, there is no real way to predict what needs to be prefetched
    – ratchet freak
    Commented Jul 8, 2013 at 14:08
  • @ratchetfreak: Control flow jumps are not easy to predict, too, but dedicated branch prediction logic, coupled with prefetching and speculative execution, is said to have a major effect in modern CPUs. Why branch prediction is practical but "pointer prediction" is not?
    – 9000
    Commented Jul 8, 2013 at 14:16
  • 1
    With branch prediction, there are only ever two outcomes to weigh--branch or not. The processor can guess which of two options is more likely and pipeline it. Dereferencing has as many possibilities as there are memory addresses--far too many to make an intelligent guess.
    – mgw854
    Commented Jul 8, 2013 at 14:22
  • This is already done extensively. By far the most common pattern of memory access is *ptr++ or similar and caches already optimize for sequential access.
    – JohnB
    Commented Jul 8, 2013 at 14:35
  • 1
    @JimmyHoffa: while I'm all for immutability and advantages it offers, I can't help but notice that many purely functional immutable structures (like those from the Okasaki book) use pointers heavily to achieve economical immutability. OTOH the only structure with cache-friendly access currently seems to be a traditional contiguous array.
    – 9000
    Commented Jul 8, 2013 at 15:29

1 Answer 1

Reset to default
3

  • there are cache pre-filling strategies. Those I'm aware of are trying to detect (some subset of) linear patterns of memory accesses and when they are successful, they are quite effective (for instance I remember having measured a difference between forward and backward sequential accesses on a processor, difference which was no more present on later generations). I'm not aware of tentative to use the memory or register content to do that pre-filling, but I'm not following that closely enough to be sure that nothing has been done in that area, it could have been proved useless in practice or less useful than some other things.

  • there is the whole set of efforts done around the principle of "if you have to wait, try to do something else and hope it will be useful". OoO execution is the application for single thread (finding some instructions in the thread which don't have to wait for memory or for the result of not-finished-yet instructions, branch prediction being there to help to find more candidates). And there is a bunch of variants in ways to make the processor thread aware and try to use the processor resources to advance the other threads while one is stuck on a slow memory access, hyperthreading being just one of them.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.