6 ms·

What's the point of using linked lists ? Low memory ? I'll never understand why the usage of linked lists is so common. I mean you don't have fast random acces

by jokoon 12y ago

What's the point of using linked lists ? Low memory ? I'll never understand why the usage of linked lists is so common. I mean you don't have fast random access with linked list, aren't hash maps just better for fast insertion/deletion ? Object pools are also pretty great too. I'll never forget the day a classmate in some game programming school argued that linked list were like vectors (std::vector). Linked lists only seems viable for insertions, they're not viable for fast deletion since you need to search for the pointer first. Maybe you need to index linked lists instead, but since the heap already allows itself to be fragmented like a linked list can, wouldn't it be better to just use vectors as often as possible so it can be more cache friendly ?

maxerickson 12y ago
In a game, I would think most deletions would start from the node being deleted.
flohofwoe 12y ago
(Intrusive) lists were useful when the cost of a memory access didn't matter relative to CPU speed, so that cache thrashing wasn't an issue, and you had a scenario where list nodes had to be inserted and removed frequently, but you don't need random access. In C such intrusive lists are also easier to manage since you don't need to care about dynamic memory management since the list nodes are embedded in some other existing data structure. Today where avoiding cache misses is the most important optimization, traditional lists have indeed become quite useless, especially the non-intrusive type like std::list.
- flohofwoe 12y ago
  ...but I think linked list were not the main problem, but (1) use of inheritance instead of composition to implement unit behaviour (but we all walked into that trap, and these were the 90's when OOP was still hip and universally seen as a silver bullet), and (2) it looks like objects have been linked to each other quite ad-hoc, instead of providing some sort of 'object relationship system' which encapsulates object linkage and querying for objects. But as I said, these were the 90's and game developers have learned from these mistakes. There's a lot of good whitepapers around about entity component systems, composition, high-level architecture of games and so on. Today it's more about asset creation pipelines and production tools, at least for 'big' game projects.
corysama 12y ago
Remember that this code was written a long time ago. It is seriously only recently that I have seen widespread discussion about how poorly linked lists perform in practice despite how theoretically nice they are. Back in the olden days at least a few things were different compared to today: 1) your only point of reference and authority was academic writing that stressed theory over practice. Blogs weren't around yet. So, you didn't have any random blogs with hard measurements showing that in practice brute force often wins over elegance. 2) Back then, the memory/ALU gap wasn't quite as drastic as it is today. 3) Available memory was drastically smaller than it is today. Therefore, if you had a list with a length that was highly variable, the obvious go-to container was a linked list. The idea of using an dynamic array of objects or pointers seemed highly wasteful from a memory fragmentation and copying point of view. Today processors spend most of their time stalling on memory and only dreaming of the opportunity to copy a large, linear chunk of data. It's only now that the performance penalty for random access has exceeded 50:1 for over 10 years that general programming public has started to take the problem seriously.
- Retric 12y ago
  Until recently main memory was close to CPU speeds and RAM cache was pointless. The issue is the speed of light means the distance between RAM chips and the CPU limits you to MHz* speeds which is not an issue for a 286, but CPU's kept getting faster even if the Speed of light is fixed. *At 1GHz light can do a six inch round trip, electricity is significantly slower than that. SDRAM is fairly high latency but cheaper and as the best case is not all that fast it's considered a good tradeoff. Adding cache increases latency even further, but tends to make CPU's faster on average.
  - hengheng 12y ago
    > electricity is significantly slower As a rule of thumb, most signals travel at half the vacuum speed (√ε_r for FR4 is 2.15), with a slight variation due to the copper trace shape. So, 150 mm/ns or 6 inch/ns one-way. I love how we can say nowadays "That's not all that much, is it."
    - 12y ago
rcxdude 12y ago
Another useful aspect of intrusive linked lists in certain situations (mostly embedded nowadays) is that they work across non-contiguous memory. When you don't have virtual memory or even malloc that can be really important.
falcolas 12y ago
Linked lists have more consistent performance than std::vector. And taking half a second to render one frame when you're averaging 100fps is way worse than consistent 50 FPS. There was recently an article about intrusive linked lists, and this same question came up. I took the unreal linked list library, and wrote a similar std::vector implementation, and tested it. The test was simple, fire 50,000 bullets at a rate of 500 rounds per second, and remove them when they fall 2 meters. They existed in 3 separate lists: physics objects, renderable objects, and all objects. When they hit the ground, they were removed from all lists. Capture the clock ticks to generate each "frame", and do a few calculations on them at the end. The average and median operation times for std::vector were indeed a fair bit faster (at -o3, at no optimizations the ILL implementation was faster). However, the worst case for std::vector was... much worse. More than 1000x worse in some runs. One test run showed the worse case taking over two millisecond for a single frame of just manipulating vectors! $ ./benchmark_ill Minimum: 0.000000 Maximum: 0.000094 Average: 0.000005 Median: 0.000005 Total Frames Rendered: 18968118 Total Run Time: 100.663895 $ ./benchmark_v Minimum: 0.000000 Maximum: 0.004813 Average: 0.000002 Median: 0.000002 Total Frames Rendered: 35859663 Total Run Time: 100.664009
- sillysaurus3 12y ago
  Wait a sec. You can't bust out numbers like that without being clear about a few key points: 1. What was std::vector's removal algorithm like? Are you sure that .remove() wasn't shifting all elements in the vector? The "correct" removal algorithm in that case looks like this: Swap the target element to the end, and then decrease the vector's size by 1. But if I remember correctly, std::vector's remove method doesn't work like that, so of course it will have terrible worst-case performance if it was shifting all elements of the array when you remove the first one. 2. What's causing the worst-case slowdown? Are you sure you weren't simply seeing the effects of the L2 CPU cache being invalidated? A linked list will thrash the CPU cache constantly, whereas vectors thrash the cache much less since the elements are stored in contiguous memory. For a modern game running on a modern CPU, vectors are almost always the better choice for that reason. EDIT: I'm not sure your numbers are trustworthy. For example, there's no way it rendered 35859663 frames in 100 seconds. That would be 358,596 FPS. Assuming your FPS was actually something like 358, not 358,596, that's still an extremely high FPS. When your FPS is so high, it becomes difficult to accurately measure the reasons for worst-case performance. A sudden spike within a single frame could be for any of a dozen reasons, such as CPU cache eviction, a GPU pipeline stall, or some other program on your computer taking CPU resources.
davexunit 12y ago
>What's the point of using linked lists ? The most important quality to me is that singly linked lists are a great simple persistent data structure, whereas the data structures you've mentioned rely on mutation. Linked lists are awesome, seriously.

by jokoon 12y ago

maxerickson 12y ago

In a game, I would think most deletions would start from the node being deleted.

flohofwoe 12y ago

(Intrusive) lists were useful when the cost of a memory access didn't matter relative to CPU speed, so that cache thrashing wasn't an issue, and you had a scenario where list nodes had to be inserted and removed frequently, but you don't need random access. In C such intrusive lists are also easier to manage since you don't need to care about dynamic memory management since the list nodes are embedded in some other existing data structure. Today where avoiding cache misses is the most important optimization, traditional lists have indeed become quite useless, especially the non-intrusive type like std::list.

flohofwoe 12y ago
...but I think linked list were not the main problem, but (1) use of inheritance instead of composition to implement unit behaviour (but we all walked into that trap, and these were the 90's when OOP was still hip and universally seen as a silver bullet), and (2) it looks like objects have been linked to each other quite ad-hoc, instead of providing some sort of 'object relationship system' which encapsulates object linkage and querying for objects. But as I said, these were the 90's and game developers have learned from these mistakes. There's a lot of good whitepapers around about entity component systems, composition, high-level architecture of games and so on. Today it's more about asset creation pipelines and production tools, at least for 'big' game projects.

corysama 12y ago

Remember that this code was written a long time ago. It is seriously only recently that I have seen widespread discussion about how poorly linked lists perform in practice despite how theoretically nice they are. Back in the olden days at least a few things were different compared to today: 1) your only point of reference and authority was academic writing that stressed theory over practice. Blogs weren't around yet. So, you didn't have any random blogs with hard measurements showing that in practice brute force often wins over elegance. 2) Back then, the memory/ALU gap wasn't quite as drastic as it is today. 3) Available memory was drastically smaller than it is today. Therefore, if you had a list with a length that was highly variable, the obvious go-to container was a linked list. The idea of using an dynamic array of objects or pointers seemed highly wasteful from a memory fragmentation and copying point of view. Today processors spend most of their time stalling on memory and only dreaming of the opportunity to copy a large, linear chunk of data. It's only now that the performance penalty for random access has exceeded 50:1 for over 10 years that general programming public has started to take the problem seriously.

Retric 12y ago
Until recently main memory was close to CPU speeds and RAM cache was pointless. The issue is the speed of light means the distance between RAM chips and the CPU limits you to MHz* speeds which is not an issue for a 286, but CPU's kept getting faster even if the Speed of light is fixed. *At 1GHz light can do a six inch round trip, electricity is significantly slower than that. SDRAM is fairly high latency but cheaper and as the best case is not all that fast it's considered a good tradeoff. Adding cache increases latency even further, but tends to make CPU's faster on average.
- hengheng 12y ago
  > electricity is significantly slower As a rule of thumb, most signals travel at half the vacuum speed (√ε_r for FR4 is 2.15), with a slight variation due to the copper trace shape. So, 150 mm/ns or 6 inch/ns one-way. I love how we can say nowadays "That's not all that much, is it."
  - 12y ago

rcxdude 12y ago

Another useful aspect of intrusive linked lists in certain situations (mostly embedded nowadays) is that they work across non-contiguous memory. When you don't have virtual memory or even malloc that can be really important.

falcolas 12y ago

Linked lists have more consistent performance than std::vector. And taking half a second to render one frame when you're averaging 100fps is way worse than consistent 50 FPS. There was recently an article about intrusive linked lists, and this same question came up. I took the unreal linked list library, and wrote a similar std::vector implementation, and tested it. The test was simple, fire 50,000 bullets at a rate of 500 rounds per second, and remove them when they fall 2 meters. They existed in 3 separate lists: physics objects, renderable objects, and all objects. When they hit the ground, they were removed from all lists. Capture the clock ticks to generate each "frame", and do a few calculations on them at the end. The average and median operation times for std::vector were indeed a fair bit faster (at -o3, at no optimizations the ILL implementation was faster). However, the worst case for std::vector was... much worse. More than 1000x worse in some runs. One test run showed the worse case taking over two millisecond for a single frame of just manipulating vectors! $ ./benchmark_ill Minimum: 0.000000 Maximum: 0.000094 Average: 0.000005 Median: 0.000005 Total Frames Rendered: 18968118 Total Run Time: 100.663895 $ ./benchmark_v Minimum: 0.000000 Maximum: 0.004813 Average: 0.000002 Median: 0.000002 Total Frames Rendered: 35859663 Total Run Time: 100.664009

sillysaurus3 12y ago
Wait a sec. You can't bust out numbers like that without being clear about a few key points: 1. What was std::vector's removal algorithm like? Are you sure that .remove() wasn't shifting all elements in the vector? The "correct" removal algorithm in that case looks like this: Swap the target element to the end, and then decrease the vector's size by 1. But if I remember correctly, std::vector's remove method doesn't work like that, so of course it will have terrible worst-case performance if it was shifting all elements of the array when you remove the first one. 2. What's causing the worst-case slowdown? Are you sure you weren't simply seeing the effects of the L2 CPU cache being invalidated? A linked list will thrash the CPU cache constantly, whereas vectors thrash the cache much less since the elements are stored in contiguous memory. For a modern game running on a modern CPU, vectors are almost always the better choice for that reason. EDIT: I'm not sure your numbers are trustworthy. For example, there's no way it rendered 35859663 frames in 100 seconds. That would be 358,596 FPS. Assuming your FPS was actually something like 358, not 358,596, that's still an extremely high FPS. When your FPS is so high, it becomes difficult to accurately measure the reasons for worst-case performance. A sudden spike within a single frame could be for any of a dozen reasons, such as CPU cache eviction, a GPU pipeline stall, or some other program on your computer taking CPU resources.

davexunit 12y ago

>What's the point of using linked lists ? The most important quality to me is that singly linked lists are a great simple persistent data structure, whereas the data structures you've mentioned rely on mutation. Linked lists are awesome, seriously.