5 ms·
What's really interesting is the section on linked-lists: author seems to suggest that yeah, arrays of pointers have much better performance. I'm curious what
by angersock 13y ago
What's really interesting is the section on linked-lists: author seems to suggest that yeah, arrays of pointers have much better performance.
I'm curious what sort of performance they run into in MT environments--lockless applications are handy with linked-lists.
- simias 13y agoIf your resource is read-mostly you'll probably still get better performances out of an array and clever/partial locking. That being said you can get correct performances out of linked lists using explicit prefetching while iterating.
- angersock 13y agoAh, interesting. Do you know of any good examples showing prefetching for linked lists?
- simias 13y agoThe classic: http://www.akkadia.org/drepper/cpumemory.pdf http://www.akkadia.org/drepper/cpumemory.pdf Look at 6.3.2 for software prefetching. Like the rest of the paper it's very x86 centric but most of the concepts apply to other architectures.
- eliasmacpherson 13y agoI only clicked to see the comments because it said Doom 3. Thanks for posting the article and thanks for pointing out the section on linked lists. I agree that that section is really interesting. In what sense do you mean lockless applications - applications built around compare and swap primitives or something else? I can't really follow what: "byte otherMembers[64]" is used for. What useful data is stored in there? If pointers are 32bit and cache lines are 64bit, the comment: "// over a cache line worth of other members" doesn't really make sense because you can only fit two full addresses per cache line. It's a shame that the idList type he is suggesting in favour of the other types, a resizeable heap array, is not declared in the body of the pdf. Might be worth looking it up. The distinction between non-intrusive and intrusive linked lists is new to me, I didn't know there was a word for that! This is the best "link" I've found on them: http://www.altdevblogaday.com/2011/12/06/intrusive-lists/ http://www.altdevblogaday.com/2011/12/06/intrusive-lists/
- hrydgard 13y agoCache lines on modern architectures are usually 64 or sometimes even 128 bytes, not bits.
- eliasmacpherson 13y agoThank you, I misread this from the article as saying 64 bit cache lines: "(assuming 32 bit pointers and 64 byte cache lines)" So: byte otherMembers[64]; is 512bits of addresses to other members, that will hold 16 32bit addresses. From the article: "In the case of an array with pointers there may still be a cache miss when reading the ‘valid’ flag but there will be at most one additional cache miss every 16 pointers" so idList must use operator[] to sensibly iterate over otherMembers. class idMyClass { bool valid; byte otherMembers[64]; // over a cache line worth of other members }; idList< idMyClass * > myObjects; for ( int i = 0; i < myObjects.Num(); i++ ) { if (myObjects[i]>valid ) { } }
- NAFV_P 13y agoThis class is also confusing because it is used both for a "link" and the "head" of the list. IMO this class is politically incorrect, there is no mention of the "tail".