Entity Pooling

Memory allocation in run time can be pretty heavy depending on how much you do it, getting rid of objects every loop will trigger the garbage collector (at 1 MB in the Xbox) often making you get lag spikes once in a while.

I encountered this issue with my engine, where entities were being created and deleted almost every frame, this made the lag unbearable. I knew from the start I had to pool the entities, so I did using this method:

static List EntityList = new List();

public static void GetEntity(out Entity Returnee)
{
        int Count = EntityList.Count;
        if(Count > 0)
        {
                  Returnee = EntityList[Count - 1];
                  EntityList.Remove(Returnee);
         }
         else
         {
                  Returnee = new Entity();
          }
}

Something I am not showing here is the way to return the entities to the list, that's by simply re adding them to list of entities, trivial.



The main issue with this way of pooling is that you are required to remove things from a list, this could get heavy if the list gets bigger, but for the time this method did improve my overall performance I thought I was happy with the results, until one day one of my class mates said something about how a pool can know what the next available index was instead of taking things out of a list, this made me really curious and I went on that to find a better way of pooling.

What I found is that removing things from the list was just wasteful and not necessarily, if I knew the next available index I could use that instead of removing the ones that were being used, this was possible by creating a base object that represents an item that can be activated when in the pool and "deactivated" or "unavailable" when "not" in the pool ("" because it is always in the pool at all times), the new pool looks like this:

public class Poolean where T: Poolable, new()
    {
        private List Pool;
        int MaxCount;
        int CurrentFreeIndex;
        bool SpecificType;
        Type ElementType;

        public Poolean(int BufferSize)
        {
            SpecificType = false;
            Pool = new List(BufferSize);
            MaxCount = 0;
            CurrentFreeIndex = 0;
            ExpandPool(BufferSize);
            
        }

        public Poolean(int BufferSize, Type typeOfElement)
        {
            ElementType = typeOfElement;
            SpecificType = true;
            Pool = new List(BufferSize);
            MaxCount = 0;
            CurrentFreeIndex = 0;
            ExpandPool(BufferSize);
        }

        private void ExpandPool(int size)
        {
            int start = MaxCount;
            MaxCount += size;

            if (SpecificType)
            {
                for (int i = start; i < MaxCount; i++)
                {
                    T NewPoolElement = (T)Activator.CreateInstance(ElementType);
                    NewPoolElement.Index = i;
                    NewPoolElement.InUse = false;
                    Pool.Add(NewPoolElement);
                }
            }
            else
            {
                
                for (int i = start; i < MaxCount; i++)
                {
                    T NewPoolElement = new T();
                    NewPoolElement.Index = i;
                    NewPoolElement.InUse = false;
                    Pool.Add(NewPoolElement);
                }
            }
        }

        public void ReturnPoolable(Poolable returnee)
        {
            returnee.InUse = false;
        }

        public void GetPoolable(out T vessel)
        {
            vessel = (T)Pool[CurrentFreeIndex];
            vessel.InUse = true;

            //find ther next available item
            int Next = vessel.Index + 1;
            GetNextAvailableElement(Next);
        }

        private void GetNextAvailableElement(int LastPlusOne)
        {
            for (int NextInLine = LastPlusOne; NextInLine < MaxCount; NextInLine++)
            {
                Poolable Current = Pool[NextInLine];
                if (!Current.InUse)
                {
                    CurrentFreeIndex = Current.Index;
                    return;
                }
            }

            //if it gets here then we need to start from the beginning of the list until we reach the last "Next", if this happens, 
            //then all elements are being used in the list, we need to increase the size of the list.

            for (int Start = 0; Start < LastPlusOne - 1; Start++)
            {
                Poolable Current = Pool[Start];
                if (!Current.InUse)
                {
                    CurrentFreeIndex = Current.Index;
                    return;
                }
            }

            //if we still here... then yes all the elements are being use, you need to inscrease the size of the pool.

            ExpandPool(MaxCount);
            GetNextAvailableElement(LastPlusOne);
        }
   
    }

As you can see, the new pool return references to the element in the pool, but it never ever removes that reference from the pool itself, instead it makes its "used" tag true, and looks for the next available from the index that was just taken out, in case the pool ever runs out of elements, it will double its size to continue working properly. A poolable base class looks like this:

public class Poolable
    {
        public int Index;
        public bool InUse;

        public Poolable()
        {

        }
    }

Real simple!


Well that's the cool thing I learned today, now all my entities are created really much much faster.