4 ms·
I’m not sure what I am wrong about, I’m simply pointing out that worse average case performance is sometimes desirable over better average case worse worst case
by dcow 5y ago
I’m not sure what I am wrong about, I’m simply pointing out that worse average case performance is sometimes desirable over better average case worse worst case performance. Context is everything.
Also some things to note: a) game logic tends not to parallelize very well for various reasons, but even so it depends on the domain of the problem whether or not you can run a parallel algorithm on a linked list, b) if you already have a reference to the insertion point you can avoid the walk, c) cache coherence is only important of you are actually iterating over the list, etc.
- whatshisface 5y agoI have never ever seen a linked list in a game, anywhere, serving any purpose.
- dcow 5y agoHere’s one: https://github.com/assaultcube/AC/blob/40a29b51ee48c427cc20cb4902f2dc53a0c20a96/source/enet/include/enet/list.h https://github.com/assaultcube/AC/blob/40a29b51ee48c427cc20c...
- areyousure 5y agoLook at all the instances of "next" in this file: https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb10315479fc00086f08e25d968b4b43c49/q3map/qbsp.h#L92 https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb1...