Sign in to follow this  
Quak

using prefetch correctly

Recommended Posts

hi, I want to traverse a linked list to set some bit flags. To speed up the traversal I'd like to use the _mm_prefetch intrinsic function so I always have the next node in the cache. Howerver, if I prefetch the next node into L1 and L2 cache the traversal gets even slower. The code looks like this:
while( node )
{
_mm_prefetch( node->next, 2 );
node->flags |= bits;
//more operations
node = node->next;
}

the linked list node structure is 40 bytes on my amd64 cpu in 32bit mode. How would I use the prefetch command most efficiently in such a list traversal loop ? And why does it get slower if I use it like above ? I am not sure how many bytes are prefetched, maybe flags doesn't get prefetches at all as it is the last 4 bytes of the node struct. thanks for your opinions, quak

Share this post


Link to post
Share on other sites
all the prefetch instruction does is get the memory address, the same thing the cpu would have to do if it was doing it manually. Prefetch is in my experience, only a win when your getting a large portion of data.

In your senario your not going to help the cpu as your only getting the next node, which the cpu would have to do anyway. And considering most cpu's now have out of order execution the prefetch at that point may cause the cpu to stall while waiting for the data, or worse, flush out data from the cache it needs.

I remember talking to some AMD guys at a winhec conference and they mentioned that prefetch is only a win for getting array like data. ie many consecutive bytes that will be used in consecutive order, and linked lists don't really fit that bill to well:)

If you want to experiment with prefetch try using it for things like reading the bytes of a bitmap.
Cheers
Chris

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this