Early in my game development, I implemented an object pooling method using arrays, like so:
private var reuseStars : GameObject[];
...
...
reuseStars = new GameObject[MAX_STARS];
for (var i : int = 0; i < MAX_STARS; i++) {
reuseStars *= Instantiate(prefabStar, Vector3(-1000, -1000, -1000), Quaternion.identity);*
} Then later, I would loop through my array to find an inactive gameobject to use and just use that array element by reference. Each star gameobject those not “live” for the same time during the game so there was no guarantee which would be active vs inactive so I had to loop through the loop from the top each time. It was the looping that was always a bother for me. For small arrays it was no big deal but I have an object pool of conceivably 25 or more objects. So I thought about using the Stack generic like so: private var stackStars : Stack.; … … stackStars = new Stack.(MAX_STARS);
for (var i : int = 0; i < MAX_STARS; i++) { var newStar : GameObject = Instantiate(prefabStar, Vector3(-1000, -1000, -1000), Quaternion.identity); stackStars.Push(newStar); } Then when I would need a gameobject, I would use the code: var myStar : GameObject = stackStars.Pop(); (do stuff…) And when I no longer needed that gameobject, I would return it to the stack: myStar.SetActive(false); stackStars.Push(myStar); So my questions are: 1. Does the overhead of using a Stack outweigh any savings of not having to loop through an array? 2. When I Pop an item off the Stack, does the GC then clear the memory for that item’s position on the stack such that, when I push it back onto the stack, it causes additional memory allocation? Thanks, Manny
Does the overhead of using a Stack outweigh any savings of not having to loop through an array?
It’s much less expensive to use a Stack in your scenario than it is to use an array for the exact reason you stated. Looping through the array has a worst case of O(n). Pushing and popping from a stack has a worst case of O(1). It’s pretty clear here that the Stack hardly has any overhead in terms of operations compared to the array.
When I Pop an item off the Stack, does the GC then clear the memory for that item’s position on the stack such that, when I push it back onto the stack, it causes additional memory allocation?
This really depends on how the Stack is implemented. If it’s your every day “not very smart” stack, then yes you’ll be allocating and deallocating memory with every push and pop.
BUT if it’s not your every day stack ( and I hope it’s not ), then it would keep extra “nodes” at all times so it doesn’t have to constantly deallocate and reallocate. This is very easy to implement since all you would need is a pointer to the current top most item from the programmer’s perspective.
Advice: Use a stack for now, then if you feel the need to optimize later, google around to find out how the stack is implemented underneath. If it’s not a “smart” stack, then I think you should implement your own array based stack. Then you’d have the best of both worlds
Oh, and if you’re not familiar with big O terminology, O(n) just means that if you have a total of n elements, in the worst case scenario, you’ll have to go through about n elements to get the element you want. So O(1) means in the worst case scenario, you’ll only have to go through about 1 element to get the one you want no matter what the number of elements is. I say “about” because big O is an approximation.
Try as I might, I cant’ seem to find any definitive articles about whether the Stack generic implementation used in Unity javascript is “smart” or not. I’ve also tried looking at articles for MSDN but they never seem to state conclusively either.
Is there an expert or Unity tech who can answer?
I think this is an important thing to know for all developers. Sure I can implement by own… but I think the Stack generics would be even faster.
