4 ms·

I 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

I 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 ago
Cache lines on modern architectures are usually 64 or sometimes even 128 bytes, not bits.
- eliasmacpherson 13y ago
  Thank 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 ) { } }

hrydgard 13y ago

Cache lines on modern architectures are usually 64 or sometimes even 128 bytes, not bits.

eliasmacpherson 13y ago
Thank 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 ) { } }