If you're hoping to be able to service a request in a few hundred (dozen?) cycles, you'll find your choice of data structures severely limited.
That being said, it would be interesting to see how much smarter a CPU could make prefetch. I know there has been a lot of research over the years into prefetch helper threads[1] that would speculatively execute code along both sides of branches to attempt to pull forward as many memory requests as possible. As I understand it, most attempts to implement this in practical systems have been failures.
Well I'm going to try something like a prefetch thread soon with some common request types that just fetch/modify a single object. It will be interesting to see if that makes any difference to throughput. Something less speculative that helps a lot is just hoist the loads in your code as far away from where you use them as possible.
Comments
"Doctor, it hurts when I do this!"
If you're hoping to be able to service a request in a few hundred (dozen?) cycles, you'll find your choice of data structures severely limited.
That being said, it would be interesting to see how much smarter a CPU could make prefetch. I know there has been a lot of research over the years into prefetch helper threads[1] that would speculatively execute code along both sides of branches to attempt to pull forward as many memory requests as possible. As I understand it, most attempts to implement this in practical systems have been failures.
[1] http://cseweb.ucsd.edu/~swanson/papers/ASPLOS2011Prefetching...
Well I'm going to try something like a prefetch thread soon with some common request types that just fetch/modify a single object. It will be interesting to see if that makes any difference to throughput. Something less speculative that helps a lot is just hoist the loads in your code as far away from where you use them as possible.