4 ms·

>You're doing some awesome lock-free concurrent thing. I can confirm lists are pretty rarely used. The four times I've used a linked list in 10 years of profes

>You're doing some awesome lock-free concurrent thing. I can confirm lists are pretty rarely used. The four times I've used a linked list in 10 years of professional programming were: -quick&dirty hashmap in C -threadsafe queue -keeping track of a set of objects that can't be copied ( threads) -LRU cache In C++ at least, the nice thing about a list is you can push/pop in the front/back without a reallocattion or invalidating iterators.

chongli 7y ago
Linked lists are used a lot in game programming where the worst-case behaviour of std::vector and similar structures is undesirable. Linked lists may be slow for a variety of reasons but they're simple and predictable which is very nice when you're trying not to miss the 16.67ms per-frame window.
- estebank 7y ago
  I thought it was the other way around: games using arrays, non arbitrarily growable vectors to precisely be able to iterate over everything quickly in a deterministic fashion. Specially because a lot of what games have to deal with is "visit every node".
  - chongli 7y ago
    They use arrays for static vertex, texture, etc. data to send to the GPU. They don't use arrays for things that are being created and destroyed all the time, such as units in a strategy game, they use lists for those things.
    - estebank 7y ago
      But do they use linked lists for them? I would have assumed you would use an arena for something like that, precisely because you already need to iterate over all of them and can represent any graph as keys into a generational index, so that reading stale keys is trivially handled. Again, I'm not a game dev and this is just my understanding after reading up on these topics after watching https://youtu.be/aKLntZcp27M https://youtu.be/aKLntZcp27M.
      - chongli 7y ago
        They certainly used linked lists all over the place in StarCraft, WarCraft, and Diablo [1]. I don't know that many game developers would use complicated data structures like the one you've described here. Linked lists are fantastic for insertion/removal in arbitrary places. Game development is not really about showing off with cutting-edge CS research, it's about getting things done. Maybe your arenas with generational indices would be better, but they could take a long time to figure out and lead to a big mess that doesn't go anywhere. [1] https://www.codeofhonor.com/blog/tough-times-on-the-road-to-starcraft https://www.codeofhonor.com/blog/tough-times-on-the-road-to-...
        ssalazar 7y ago
        Arenas aren't "cutting edge CS research," theyre used widely in latency-sensitive applications like gaming. This article [1] describes how to implement one for a game engine. Basic versions are easy to understand and provide good results. Starcraft/etc. are 20+ year old games and software development patterns as well as gaming hardware have changed in fundamental ways since then. Conventional wisdom nowadays is that cache misses on every list iteration are a lot worse than shuffling a few contiguous bytes around or marking things inactive when removing items. [1] https://www.gamasutra.com/blogs/MichaelKissner/20151104/258271/Writing_a_Game_Engine_from_Scratch__Part_2_Memory.php https://www.gamasutra.com/blogs/MichaelKissner/20151104/2582...
        Narishma 7y ago
        Those are pretty old games written when caches were small and the CPU-memory speed gap wasn't as large as it is today.
        jfkebwjsbx 7y ago
        You are wrong in several fronts: + Linked lists are a thing of the past. + Game engines use complex data structures and algorithms. Some are cutting-edge research implemented from papers, specially in graphics. + A generational index is not complex. Yes, game development (as opposed to game engine development or video/audio rendering) is a mess. That does not mean the actual technical fields involved are simple.
    - jfkebwjsbx 7y ago
      No, they don't. You are talking about the state of affairs 20 years ago.
  - Jasper_ 7y ago
    An array of pointers you call a virtual method on is indistinguishable in "pointer-chase" time (with current caches, at least), to an embedded linked list. Embedded linked lists have better insertion/deletion costs, and are easier to manage, so they're used quite frequently in games.
    - jfkebwjsbx 7y ago
      That model (bag of polymorphic objects) is avoided nowadays in everything from games to simulation software.
- SAI_Peregrinus 7y ago
  Used, yes, butbnot implemented. std::collections::LinkedList is a doubly-linked list suitable for games. It's basically just the no-std crowd that might need to implement their own.
big_chungus 7y ago
I've used linked lists a little more because I mostly do C rather than C++. Sometimes I end up using it as a quick-and-dirty vector when I don't want to bother writing something or using a library, though I typically use some kind of block/arena allocator vs. just malloc.

chongli 7y ago

Linked lists are used a lot in game programming where the worst-case behaviour of std::vector and similar structures is undesirable. Linked lists may be slow for a variety of reasons but they're simple and predictable which is very nice when you're trying not to miss the 16.67ms per-frame window.

estebank 7y ago
I thought it was the other way around: games using arrays, non arbitrarily growable vectors to precisely be able to iterate over everything quickly in a deterministic fashion. Specially because a lot of what games have to deal with is "visit every node".
- chongli 7y ago
  They use arrays for static vertex, texture, etc. data to send to the GPU. They don't use arrays for things that are being created and destroyed all the time, such as units in a strategy game, they use lists for those things.
  - estebank 7y ago
    But do they use linked lists for them? I would have assumed you would use an arena for something like that, precisely because you already need to iterate over all of them and can represent any graph as keys into a generational index, so that reading stale keys is trivially handled. Again, I'm not a game dev and this is just my understanding after reading up on these topics after watching https://youtu.be/aKLntZcp27M https://youtu.be/aKLntZcp27M.
    - chongli 7y ago
      They certainly used linked lists all over the place in StarCraft, WarCraft, and Diablo [1]. I don't know that many game developers would use complicated data structures like the one you've described here. Linked lists are fantastic for insertion/removal in arbitrary places. Game development is not really about showing off with cutting-edge CS research, it's about getting things done. Maybe your arenas with generational indices would be better, but they could take a long time to figure out and lead to a big mess that doesn't go anywhere. [1] https://www.codeofhonor.com/blog/tough-times-on-the-road-to-starcraft https://www.codeofhonor.com/blog/tough-times-on-the-road-to-...
      - ssalazar 7y ago
        Arenas aren't "cutting edge CS research," theyre used widely in latency-sensitive applications like gaming. This article [1] describes how to implement one for a game engine. Basic versions are easy to understand and provide good results. Starcraft/etc. are 20+ year old games and software development patterns as well as gaming hardware have changed in fundamental ways since then. Conventional wisdom nowadays is that cache misses on every list iteration are a lot worse than shuffling a few contiguous bytes around or marking things inactive when removing items. [1] https://www.gamasutra.com/blogs/MichaelKissner/20151104/258271/Writing_a_Game_Engine_from_Scratch__Part_2_Memory.php https://www.gamasutra.com/blogs/MichaelKissner/20151104/2582...
      - Narishma 7y ago
        Those are pretty old games written when caches were small and the CPU-memory speed gap wasn't as large as it is today.
      - jfkebwjsbx 7y ago
        You are wrong in several fronts: + Linked lists are a thing of the past. + Game engines use complex data structures and algorithms. Some are cutting-edge research implemented from papers, specially in graphics. + A generational index is not complex. Yes, game development (as opposed to game engine development or video/audio rendering) is a mess. That does not mean the actual technical fields involved are simple.
  - jfkebwjsbx 7y ago
    No, they don't. You are talking about the state of affairs 20 years ago.
- Jasper_ 7y ago
  An array of pointers you call a virtual method on is indistinguishable in "pointer-chase" time (with current caches, at least), to an embedded linked list. Embedded linked lists have better insertion/deletion costs, and are easier to manage, so they're used quite frequently in games.
  - jfkebwjsbx 7y ago
    That model (bag of polymorphic objects) is avoided nowadays in everything from games to simulation software.
SAI_Peregrinus 7y ago
Used, yes, butbnot implemented. std::collections::LinkedList is a doubly-linked list suitable for games. It's basically just the no-std crowd that might need to implement their own.

big_chungus 7y ago

I've used linked lists a little more because I mostly do C rather than C++. Sometimes I end up using it as a quick-and-dirty vector when I don't want to bother writing something or using a library, though I typically use some kind of block/arena allocator vs. just malloc.