DATA-ORIENTED DESIGN The hardware will thank you.


Follow Data-oriented Design on Google+

Read articles on CellPerformance

Data-Oriented Design book - online beta

FIRST PREV : PAGE 0 : NEXT LAST

Intrusive Linked Lists 10/09/2012:10:36:09

...again

but this time there's an interesting statement that needs to be investigated. In the section titled Why intrusive lists are better, there is an argument:

When traversing objects stored on an intrusive linked list, it only takes one pointer indirection to get to the object, compared to two pointer indirections for std::list. This causes less memory-cache thrashing so your program runs faster — particularly on modern processors which have huge delays for memory stalls.

Right

Think about it a bit more and you realise that this must in fact be false. Where are the pointers to the elements? They are in the middle of the structures being traversed. They're not somewhere all together, huddled up on cachelines, they're split apart by at least the size of the object they are linking. This means you save one indirection, but potentially at the cost of many loads from separate areas of memory which will cane your memory bandwidth.

Apart from that minor snaffet, the article is sound, but when you come across a false statement like that it does make you question the authenticity of the rest of the article. Foremost in your mind when you do any performance related work must be profiling. If the author had done profiling he might have learned that this was the case and been able to improve on the design further, or at least realise that there was a trade-off and with that knowledge be better armed.

http://www.codeofhonor.com/blog/avoiding-game-crashes-related-to-linked-lists?utm_source=rss&utm_medium=rss&utm_campaign=avoiding-game-crashes-related-to-linked-lists