Search Unity

  1. Unity 6 Preview is now available. To find out what's new, have a look at our Unity 6 Preview blog post.
    Dismiss Notice
  2. Unity is excited to announce that we will be collaborating with TheXPlace for a summer game jam from June 13 - June 19. Learn more.
    Dismiss Notice
  3. Dismiss Notice

Discussion Queues and stacks

Discussion in 'Scripting' started by Ne0mega, May 17, 2024.

  1. Ne0mega

    Ne0mega

    Joined:
    Feb 18, 2018
    Posts:
    768
    I do a lot of different iterations. I have learned all sorts of tricks and patterns. For one, i have found no need for "for each" iterations, as i generally just get the count or length, and use standard i++ iterator.

    I have looked curiously at queues and stacks over the years,but cant really find a need for them. What are some hypothetical uses for them in game dev, that an iterator cant do, or that would be significantly simpler/more readable than an iterator?
     
  2. CodeSmile

    CodeSmile

    Joined:
    Apr 10, 2014
    Posts:
    6,934
    What's the "trick" in this?

    Foreach is rather convenient unless you need the iterator variable itself.
    Never mind the "x is faster" theoretical observations that are marginal at best in real world scenarios.

    Queues are for collections that can grow at a different rate than they are removed. A command queue comes to mind where the user may issue various cloud save calls eg "moved inventory item from slot A to slot B" but behind the scenes these changes are only pushed to the cloud every couple seconds. And these pushes may be limited to at most 20 items. So you send out (remove) 20 items from the queue every couple seconds until the queue is empty. By using a queue you can make sure you're pushing the oldest (longest in cache) commands first.

    Stacks would be quite useful for a card game where you can have stack of cards and you can only add to / remove from the top of the stack.
     
    Bunny83 likes this.
  3. Ne0mega

    Ne0mega

    Joined:
    Feb 18, 2018
    Posts:
    768
    I have just found i usually do, or upon refactoring i often come upon a for each loop that i need to change to an iteration, so as of about a week ago, i just decided no more for each loops. Just dont see the point, all bench tests ive seen show very little performance difference between the two. Its kind of like my "no var" preference. I just feel the iterator is more explicit.
     
  4. spiney199

    spiney199

    Joined:
    Feb 11, 2021
    Posts:
    8,396
    Queues and Stacks don't really have anything to do with iterators, honestly. They're just types of collections that have been designed with a certain idiomatic pattern in mind.

    Naturally you use a queue where you need something work in a first in, first out basis. And a stack where you need something in a last in, first out basis. There's not much else to say about it. Same reason you may use a HashSet (don't want duplicates), or want a Dictionary (fast lookup). They have particular usages in mind.

    Both of which come up a lot less than using a regular array or List<T>. Particularly as neither are natively serializable by Unity.
     
    Last edited: May 17, 2024
    SisusCo and Spy-Master like this.
  5. CodeSmile

    CodeSmile

    Joined:
    Apr 10, 2014
    Posts:
    6,934
    I hope you do make that change with a refactoring, not manually. You can flip between both variants with a single refactoring, at least in good IDEs.

    Well, there is a point in that it makes the code more readable. Consider:
    Code (CSharp):
    1. for (int i = 0; i < transform.ChildCount; i++)
    2.     transform[i].Translate(transform[i].position + moveDir);
    vs
    Code (CSharp):
    1. foreach (Transform child in transform)
    2.     child.Translate(child.position + moveDir);
    Not only does it remove all the various symbols that make for hard reading, it also gives transform a speaking name (provided you care for naming variables, which you should).

    Which means you prefer to duplicate the type even though it is implicit. This goes against the DRY principle. It again makes code harder to read, but on top it makes code harder to WRITE too:
    Code (CSharp):
    1. Dictionary<MyTypeForKeys, Dictionary<string, object>> whatever = new Dictionary<MyTypeForKeys, Dictionary<string, object>>();
    vs
    Code (CSharp):
    1. var whatever = new Dictionary<MyTypeForKeys, Dictionary<string, object>>();
    Note that any good IDE will fine-print the actual type of a "var" variable next to it.

    Also note that I do not consider Microsoft's IDE to adhere to my notion of "good". :D
     
    orionsyndrome and Spy-Master like this.
  6. spiney199

    spiney199

    Joined:
    Feb 11, 2021
    Posts:
    8,396
    Blargh, I honestly always get it backwards. Editing my post...
     
    Spy-Master likes this.
  7. orionsyndrome

    orionsyndrome

    Joined:
    May 4, 2014
    Posts:
    3,214
    First, there is nothing preventing you from using just
    for
    loops. Especially if you want to rely on counts and you need an index.

    foreach
    is a specific feature of C#, belonging to what's known as enumerators, which allows you to loop over a generalized set. It's not really there to replace the other loops, it's more of a convenient, generalized approach of iterating through some elements, which happens all the time in programming. However, with
    foreach
    it's more about the object-oriented approach, encapsulation, and effective use of memory, than it is about iterating through arrays and other index-based solutions. Also, we all need ways to iterate through non-indexable collections such as the dictionary.

    While
    for
    and
    while
    (or
    do
    ) loops are there for legacy and performance reasons, they are much more mathematical and low-level in what they're doing, they are essentially parts of the fundamental language grammar.

    foreach
    is a more modern, high level construct, that can be applied to arrays and lists, but we occasionally don't because in that case it mostly just adds an overhead (there is a link in the end where you can learn more about it). So we tend to avoid it when working with tight-performing low-level code, but not when your code is sufficiently high-level (which is typically the main application logic) or sufficiently complex (in terms of maintenance).

    The whole thing of enumerators boils down to what collections are supposed to be. Basically
    ICollection
    is an interface that defines Count, Add, Remove, Contains, and Clear, the most typical operations. But it also inherits from
    IEnumerable
    , which means the collection must support a simple iteration over its elements. To enable this the interface defines GetEnumerator method that returns
    IEnumerator
    . Implementor of
    IEnumerator
    is a type that implements iteration logic via Current property, MoveNext, and Reset. The way you use this is conveniently hidden by
    foreach
    , it's practically a syntactic sugar feature.

    In other words, there is nothing particularly special about
    foreach
    , it's merely a part of the extended language grammar.

    Here you can see all kinds of experiments which not only push the performance of
    foreach
    (with arrays) to be in line with the classic
    for
    loops, but also illustrates how the
    foreach
    is actually rewritten by Roslyn (and why collections that contain reference types or implement
    IDisposable
    must have a
    try..catch
    block included, which is something we normally avoid in game dev if we can help it).

    All of this knowledge combines into better understanding of
    foreach
    and subsequently you'll learn how to maintain a healthy balance of different iteration techniques for the best outcome (typically a product or a sweet spot between performance and maintainability).
     
    Last edited: May 17, 2024
    Ohilo, SisusCo, Ne0mega and 3 others like this.
  8. Lurking-Ninja

    Lurking-Ninja

    Joined:
    Jan 5, 2024
    Posts:
    552
    It is not that the iterator can't do something, it is mostly signaling what you're doing. For example if you develop an Undo-stack, you will use, you guessed it, a stack. The last command goes in, the last command comes out first.
    If you develop a tactical RPG, you probably familiar with the order of actions like character images on the top of the screen and represent in what order the characters perform their turns... the clue is that in order, so it's usually a queue.
    Or the timeline in "For The King" is also a queue. You add to the end and take the next from the front.
     
  9. LaneFox

    LaneFox

    Joined:
    Jun 29, 2011
    Posts:
    7,598
    For one example, Stack could be useful example for Undo/Redo systems. Queue is useful for deterministic simulations where you have a queue of operations in the order that they arrived (whenever they arrived).

    You can also use a List, an Array, or 20 fixed variables definitions. A lot of what you write is syntatic sugar and convenience for the task at hand. Just use what you want, no one is forcing you to do anything. Technically all math can be solved with only addition - but subtraction, division and multiplication are preferred for many situations to avoid stupid formulas.

    Just remember that it is definitely beneficial to understand different patterns and usages because you can do a variety of things in a variety of ways using a variety of tools. If you don't know, you're just a one trick pony that will eventually be too inflexible to be relevant. Whether you like the option or not is somewhat irrelevant - the value add to the design is what is important.
     
    Ne0mega likes this.
  10. Kurt-Dekker

    Kurt-Dekker

    Joined:
    Mar 16, 2013
    Posts:
    39,371
    Asking questions about what a queue/stack is used for is an EXCELLENT approach... fill your mind with all the tools available to you.

    Questions about basic data types are often used in interview questions because they can reveal a great deal about the candidate's mental model.

    Your mental model actually controls what you can do. If you can't conceive of something, then you simply cannot do it.

    I would advise you not to become "that guy who blindly avoids foreach."

    Every part of every language has a purpose.

    Learn when each tool / feature is appropriate.

    Learn how to reason about the tradeoffs.

    And also, have fun. :)
     
  11. halley

    halley

    Joined:
    Aug 26, 2013
    Posts:
    2,559
    "Orthodoxy is unconsciousness."
     
    Munchy2007 and Kurt-Dekker like this.
  12. Ryiah

    Ryiah

    Joined:
    Oct 11, 2012
    Posts:
    21,691
    You can do it with a
    foreach
    too if you don't mind relying on LINQ.
    Code (csharp):
    1. using System;
    2. using System.Collections.Generic;
    3. using System.Linq;
    4.  
    5. public class Program
    6. {
    7.     public static void Main()
    8.     {
    9.         var items = new List<string> { "apple", "banana", "cherry" };
    10.  
    11.         foreach (var i in Enumerable.Range(0, items.Count))
    12.         {
    13.             Console.WriteLine($"Index: {i}, Item: {items[i]}");
    14.         }
    15.     }
    16. }
    Code (csharp):
    1. Index: 0, Item: apple
    2. Index: 1, Item: banana
    3. Index: 2, Item: cherry
     
    Ohilo and orionsyndrome like this.
  13. orionsyndrome

    orionsyndrome

    Joined:
    May 4, 2014
    Posts:
    3,214
    Very much! Nowadays it's really more of a personal preference, though it used to be that foreach wasn't as optimal as it is now (for that particular use case).
     
    Ryiah likes this.
  14. Ne0mega

    Ne0mega

    Joined:
    Feb 18, 2018
    Posts:
    768
    "Also, we all need ways to iterate through non-indexable collections such as the dictionary."

    Right, and hashsets.

    So, as analogy, when does queue or stack become the best option, or perhaps only option, is what I am getting at. And by best i mean easy to read, and not a lot of shifting around or reordering of lists etc.

    Perhaps they are good for, say an update that catches only some of the data providers that frame, assuring that even with the fickleness of object update, everybody gets their update data change once per frame, be it this frame or the next?

    hmm.

    Asked another way: is there a difference between a stack, and an iterator running backwards? (Count to zero, i- -)...

    There seems to be some kind of "limiter" on sizes of queues and stacks?

    But anyways, in my reading last night i came upon sortedsets, which i did not know existed, and seem pretty fast.. ..and i can see great use for those for what i am doing...

    ..i once read a nuts and bolts on hashsets, and it was way above my head at the time, would like to find that again, as well as a nuts and bolts on how sortedsets are done so fast, harder to find now, i think, than it was six years ago.
     
    Last edited: May 18, 2024
  15. spiney199

    spiney199

    Joined:
    Feb 11, 2021
    Posts:
    8,396
    As has been already mentioned, when you have a situation where their particular idiomatic pattern is the best choice. There have already been examples posted in this thread.

    I feel like you're overthinking this.
     
    Munchy2007, lordofduct and Ryiah like this.
  16. Ryiah

    Ryiah

    Joined:
    Oct 11, 2012
    Posts:
    21,691
    No. Like @spiney199 mentioned you're overcomplicating them in your head. Under the hood they're just arrays with alternative ways of being accessed.

    https://github.com/microsoft/referencesource/blob/master/mscorlib/system/collections/generic/list.cs
    https://github.com/microsoft/refere...m/compmod/system/collections/generic/queue.cs
    https://github.com/microsoft/refere...m/compmod/system/collections/generic/stack.cs
     
    Last edited: May 18, 2024
  17. halley

    halley

    Joined:
    Aug 26, 2013
    Posts:
    2,559
    All of them boil down to Jump and Branch statements reading registers, so the philosophical question is really moot. You are choosing some arbitrary midpoint between "express the problem as succinctly as possible" and "command the hardware as discretely as possible" that happens to have a
    for (int i ...)
    syntax.

    If you want FIFO, you use Queue. The low-level implementation of Queue manages the internal complexity of allocating or reallocating or shifting elements in the underlying arrays for you, so that adding and fetching from opposite ends minimizes the actual copying around of data. Often this is with a ring-consumption scheme. If someone else reads your code and sees the word 'queue', they answered a ton of their own questions before reading anything else.

    If you want LIFO, you use Stack. There's not much internal difference from List, so if you're happier with List, use it. Similar to Queue, it manages the capacity versus the actual growth, minimizing the number of times it has to allocate more without much in the way of hints to go by. A reader immediately understands a 'stack' to have a business end and an uninteresting end.

    There are MANY situations where the set of data is completely unordered or arbitrarily ordered, and treating an iterator as a plain integer is just orthodoxy for the sake of orthodoxy. Almost dogma, as we're down to post #17. Walking a HashSet, for example. The only thing you really want to know is that a single trip through the data will not revisit the same data multiple times accidentally.
     
    Ne0mega and Ryiah like this.
  18. Ryiah

    Ryiah

    Joined:
    Oct 11, 2012
    Posts:
    21,691
    Multithreading too. I remember a past work project that ran heavy calculations on other threads, pushed the results into a
    ConcurrentQueue
    , and then in an
    Update
    method they were pulled out and passed to the appropriate Unity APIs.

    https://learn.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentqueue-1
     
    lordofduct, LaneFox and Ne0mega like this.
  19. Ne0mega

    Ne0mega

    Joined:
    Feb 18, 2018
    Posts:
    768
    Well, thank you. I was asking a question, not quite sure what the question was, but got an answer to that question.
     
    Last edited: May 18, 2024
    orionsyndrome and SisusCo like this.
  20. SisusCo

    SisusCo

    Joined:
    Jan 29, 2019
    Posts:
    1,364
    Just to add a simple practical example:

    Stack:
    Code (CSharp):
    1. class UndoHandler
    2. {
    3.     readonly Stack<IUndoable> history = new();
    4.  
    5.     public void RecordAction(IUndoable undoable) => history.Push(undoable);
    6.  
    7.     public void UndoLastAction()
    8.     {
    9.         if(history.Count > 0)
    10.         {
    11.             history.Pop().Undo();
    12.         }
    13.     }
    14. }
    List:
    Code (CSharp):
    1. class UndoHandler
    2. {
    3.     readonly List<IUndoable> history = new();
    4.  
    5.     public void RecordAction(IUndoable undoable) => history.Add(undoable);
    6.  
    7.     public void UndoLastAction()
    8.     {
    9.         if(history.Count > 0)
    10.         {
    11.             int lastIndex = history.Count - 1;
    12.             var lastAction = history[lastIndex];
    13.             history.RemoveAt(lastIndex);
    14.             lastAction.Undo();
    15.         }
    16.     }
    17. }
    It's not like it's an enormous difference in terms of readability, but it's definitely there.

    And being able to completely get rid of the possibility of off-by-one errors, and other errors that using indexes can quite easily result in, is a big plus in my book.
     
    orionsyndrome and Ryiah like this.
  21. Munchy2007

    Munchy2007

    Joined:
    Jun 16, 2013
    Posts:
    1,747
    I read this and smiled when I think of the many, many posts on here regarding the use of GameObject.Find and it's variants :p

    Commands which I'm totally comfortable using myself, in the right circumstances, I might add!
     
    Bunny83, Ryiah and Kurt-Dekker like this.
  22. Ryiah

    Ryiah

    Joined:
    Oct 11, 2012
    Posts:
    21,691
    Including the ones that we like to pretend don't exist. :p

    https://learn.microsoft.com/en-us/d...statements/jump-statements#the-goto-statement

    They're fine if you know what you're doing, how to minimize the debugging nightmare they can introduce, and most importantly know not to call them every frame in
    Update
    like so many threads recently have been doing.
     
  23. Bunny83

    Bunny83

    Joined:
    Oct 18, 2010
    Posts:
    4,194
    Just to make it more clear what the difference between a Stack, Queue and List are. As it was already mentioned, they all use an ordinary array behind the scenes. As we all (hopefully) know, arrays have a fix size that can not be changed. All those 3 classes create an array with a certain "capacity" / reserve and in addition remember how many and which elements of that array are currently in use. When those classes run out of capacity, so the internal array is full, the class has to create a complete new, larger array and copy all elements over.

    The main difference between those classes is that each is optimised for a different purpose. As it was also already mentioned, a Queue is a FIFO (First In is the First Out), A Stack is a LIFO (the Last In is the First Out) and a List is just a dynamic array.

    Stack

    The stack has two methods, Push and Pop. Push will add an element on top of the stack and Pop will remove and return the "top" element. The push and pop methods are optimised so they are the least expensive and use the given capacity optimally. Instead of a Stack you could also use a List as Adding a new element at the end and removing the last element have equal "cost"

    Queue

    A queue has also two methods: Enqueue and Dequeue. One to "add" an element and one to "remove" / extract an element. Unlike the stack it does not remove the last added but the first added, well, a queue. The main point of the queue is that it is optimised for those operations. Those are O(1) operations, so they have a constant cost, regardless of the number of elements in the queue. Removing the first element in a List is expensive because it has to move all elements in the internal array down one slot. So element 1 becomes the new 0, 2 becomes the new 1, etc... A Queue uses a separate read and write index into the internal array. So the elements are not copied around. Only when a resize is required and a new internal array is allocated which necessarily copies the elements from the old into the new array.

    List

    Unlike the Stack and Queue, the List allows random access to all elements, just like an array. The List is the most versatile collection of the 3 but depending on the operation you want to perform, not necessarily the best choice. A List allows inserting and deleting elements at any position in the list, however that necessarily requires the movement of all following elements. Adding / removing elements at the end of the list is O(1), Inserting or removing at the front (index 0) is an O(n) operation.

    So in the end all 3 collections just wrap an array and provide different methods to add / remove and access elements. Stack and Queue are designed for a particular purpose. They don't provide random access to the elements but are optimised for their specialized operations. I personally almost never used a Stack as you can always use a List instead. However if your requirement is that you should not have access to the intermediate elements, a Stack does encapsulate this well. The Queue really provides a unique mechanic so when you have a high number of elements in a queue, you can enqueue and dequeue elements very fast.

    I once made a RingBuffer class which works pretty much like a normal Queue, but it never resizes. It has a fix capacity and when you queue up another element when the buffer is full, it just overwrites the oldest / first element. Though my buffer provides random access for read and write. However you can not add / remove elements in between. Ring buffers are great when you want to limit the number of elements that can be queued up. This can be done with a normal queue as well by checking the count before you enqueue and simply dequeue an element (and discard it). Though my class also provides random access which can be useful in certain situations. It's great for something like an fps graph or network graph with a certain number of elements. So you just add the latest sample and you can iterate the collection to draw the graph. It's also great for a delay queue when you want to "delay" by a certain amount of frames / elements.
     
  24. orionsyndrome

    orionsyndrome

    Joined:
    May 4, 2014
    Posts:
    3,214
    @Bunny83
    I too wanted to mention specific implementations like the ring buffer.

    @Ne0mega
    I now think I understand what your question regarding Queues and Stacks was all about.

    It's all about semantics. When building a complex Lego sculpture, it makes little sense to describe every part in terms of individual Lego bricks, even though the parts themselves are made out of Lego bricks. It's much better to classify and compartmentalize, this lets you split a much larger work into logical sections, little "factory processes".

    However, in programming, complex logic demands better readability. The ability to "zoom out" from the implementation details, and see the bigger picture lets us map the topology of the problem better and this also helps reduce the editing errors. Thus we tend to hide all operational complexities beneath the mental analogues in order to keep the abstraction flowing.

    This is why it helps to semantically delineate between a queue and an array, both of which are fundamentally made out of (some kind of) Lego bricks. Most of the "advanced" collections are custom-tailored upgrades of the actual array (which is a limited, general-purpose basic memory interface), but which algorithmically and ergonomically serve some specific, but fairly common, service when programming. They are effectively optimized solutions for common patterns of memory access and consumption.

    Typically all collections are data sets that behave in pragmatic ways so that you can analyze their behavior just by glancing over their usage patterns. When you see Stack you can think of Hanoi towers, where instead of having one inlet and one outlet like queues do, there is only one combined port, and you can't write randomly. When you see a dictionary, you can actually imagine a real world dictionary, it's name refers to its interface, and the way it is implemented is not something you should bother with (unless it affects the way it's used).

    But you should absolutely know and understand what all of these collections are for, even if you currently do not need them.
     
    Munchy2007, spiney199 and Ryiah like this.