chapter six

6 Common data structures: List, Stack, and Queue

 

This chapter covers

  • How built-in data structures like List, Stack, and Queue can hurt performance.
  • Implementing common data structures like List, Stack, and Queue using data-oriented design.
  • Using stack-allocated arrays to pass data from Logic back to the Board.

So far, we have been using arrays of primitive types to store our data. We use arrays for two main reasons. First, they are allocated in a contiguous chunk of memory, which helps us practice data locality and maximizes the chance that our data will be in the L1 cache. Second, we can treat them like object pools, avoiding memory fragmentation and garbage-collector triggers.

If you haven’t caught on yet, data-oriented design is all about using arrays, preferably arrays of primitive types. Arrays work well when you have a fixed amount of data, like a set number of enemies. But what happens when we want to add and remove enemies from an array dynamically? Languages like C# offer built-in data structures, for example, List, that make it easy to add and remove elements.

Unfortunately, popular data structures, including built-in ones like List, Stack, and Queue, don’t align well with data-oriented design. Using them can cause significant performance penalties and hurt memory management.

6.1 C# List

6.1.1 C# List vs Linked List

6.1.2 List and dynamic resizing

6.1.3 List and built-in functions

6.1.4 List and performance

6.1.5 Replacing List with an array

6.2 DOD List Implementation

6.2.1 DOD Implementation of List.Add()

6.2.2 DOD implementation of List Remove()

6.2.3 DOD List helper functions, or lack of

6.2.4 Array.Copy()

6.2.5 Using the AliveEnemyIndices array

6.3 DOD stack implementation

6.4 Queue

6.5 Putting it all together

6.5.1 Adding the alive and dead indices arrays to GameData

6.5.2 Allocating the alive and dead indices arrays

6.5.3 Initializing the alive and dead indices arrays

6.5.4 Spawning and positioning enemies

6.6 Visualizing enemy changes on the board

6.6.1 Allocating temporary arrays in the Board

6.6.2 Populating the addedEnemyIndices array

6.6.3 Populating the removedEnemyIndices array

6.7 Conclusion

6.8 Summary