🔒 Locked

using prefetch correctly

Started by Quak Apr 22, 2006 at 5:35 PM 0 replies 850+ views

Original Post

Apr 22, 2006 at 5:35 PM

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

chollida1

Apr 22, 2006 at 5:44 PM

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

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.