3 ms·
The prefetcher works only if it can predict what you're going to access next. Chasing pointers means essentially jumping to random addresses in a given memory r
by tux3 11y ago
The prefetcher works only if it can predict what you're going to access next. Chasing pointers means essentially jumping to random addresses in a given memory region.
That's pretty much the worst situation from a caching point of view, what the prefetcher loves is linear traversal.
Of course things become more complicated when you start having larger amounts of data, and you want to skip over most of it, but still keep the cache happy.
- Someone 11y agoIn theory, an advanced prefetcher can detect that you are stepping through an array of pointers, dereferencing each of them, and start prefecting. Even that would have its problems, though. Typically, every one of these dereferences brings in a new cache line. Unless the data that the pointers point to fills an integral number of cache lines, you are bringing data into the cache that you will not need.
- eloff 11y agoThere are costs to this, because you may dereference things that are not valid pointers either. The kernel used to have software prefetch code for linked list traversal. On each access it would prefetch the subsequent access. Which sounds like a huge win. However, in practice the most common list size was just a few elements and there was a huge penalty for fetching the final, invalid null pointer. They ended up taking out the prefetching recently (and I think they saw a small speedup as a result!) Now maybe someone could invent a hardware prefetcher that does this in a way that's a net gain, but the fact that Intel hasn't done it yet suggests that it maybe it doesn't help much or that the situation isn't all that common.