【Unity优化】构建一个拒绝GC的List

上篇文章《【Unity优化】Unity中究竟能不能使用foreach？》发表之后，曾经有网友说，在他的不同的Unity版本上，发现了泛型List无论使用foreach还是GetEnumerator均会产生GC的情况，这就有点尴尬了。由于它本身就是Mono编译器和相应.net库才能决定的原因，这就使得在使用系统提供的List时，又能最终摆脱GC的纠缠变得很困难。于是抓耳挠腮，翻出差不多六七年为Java代码写的动态数组，然后大肆修改一番。最终好像终于逃离GC的魔咒。

先奉上代码：

自定义的List

using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;


namespace AndrewBox.Math
{
    /// <summary>
    ///  动态数组
    ///  @author AndrewFan
    /// </summary>
    /// <typeparam name="T">任意类型</typeparam>
    public class AB_List<T> :IEnumerable<T>
    {
        protected int m_capacity=10;  // 容量
        protected T[] m_items;// 内部数组
        protected int m_length;// 存放的单元个数

        protected IEnumerator<T>[] m_enumerators; //枚举器组
        protected bool[] m_enumStates;//枚举器组当前占用状态
        public AB_List()
        {
            init(5);
        }
        public AB_List(int capacity,int enumCount=5)
        {
            init(enumCount);
        }
        protected void init(int enumCount)
        {
            m_capacity = m_capacity<10?10:m_capacity;
            enumCount = enumCount < 5 ? 5 : enumCount;
            m_items = new T[m_capacity];
            if (m_enumerators == null)
            {
                m_enumerators = new IEnumerator<T>[enumCount];
                m_enumStates = new bool[enumCount];
                for (int i = 0; i < m_enumerators.Length; i++)
                {
                    m_enumerators[i] = new ABEnumerator<T>(this,i);
                }
            }
        }
        /// <summary>
        /// 增加单元
        /// </summary>
        /// <param name="element">添加的单元</param>
        public virtual void Add(T element)
        {
            increaseCapacity();
            // 赋值
            m_items[m_length] = element;
            m_length++;
        }

        /// <summary>
        /// 插入单元
        /// </summary>
        /// <param name="index">插入位置</param>
        /// <param name="element">单元</param>
        /// <returns>操作是否成功</returns>
        public virtual bool Insert(int index, T element)
        {
            if (index < 0)
            {
                return false;
            }
            if (index >= m_length)
            {
                Add(element);
                return true;
            }
            increaseCapacity();
            // 向后拷贝
            // for(int i=length;i>index;i--)
            // {
            // datas[i]=datas[i-1];
            // }
            System.Array.Copy(m_items, index, m_items, index + 1, m_length - index);

            m_items[index] = element;

            m_length++;
            return true;
        }

        public virtual T this[int index]
        {
            get
            {
                //取位于某个位置的单元
                if (index < 0 || index >= m_length)
                {
                    throw new InvalidOperationException();
                }
                return m_items[index];
            }
            set
            {
                //设置位于某个位置的单元
                if (index < 0 || index >= m_length)
                {
                    throw new InvalidOperationException();
                }
                m_items[index] = value;
            }
        }

        /// <summary>
        /// 增长容量
        /// </summary>
        protected void increaseCapacity()
        {
            if (m_length >= m_capacity)
            {
                int newCapacity = m_capacity;
                if(newCapacity == 0)
                {
                    newCapacity++;
                }
                newCapacity *= 2;
                T[] datasNew = new T[newCapacity];
                System.Array.Copy(m_items, 0, datasNew, 0, m_length);
                m_items = datasNew;
                m_capacity = newCapacity;
            }
        }
        /// <summary>
        /// 清空单元数组
        /// </summary>
        public virtual void Clear()
        {
            for (int i = 0; i < m_length; i++)
            {
                m_items[i] = default(T);
            }
            m_length = 0;
        }


        /// <summary>
        /// 是否包含某个单元
        /// </summary>
        /// <param name="element">单元</param>
        /// <returns>是否包含</returns>
        public bool Contains(T element)
        {
            for (int i = 0; i < m_length; i++)
            {
                if (m_items[i].Equals(element))
                {
                    return true;
                }
            }
            return false;
        }


        /// <summary>
        /// 获取指定单元在当前列表中的位置，从前向后查找
        /// </summary>
        /// <param name="element">单元</param>
        /// <returns>位置</returns>
        public int IndexOf(T element)
        {
            for (int i = 0; i < m_length; i++)
            {
                if (m_items[i].Equals(element))
                {
                    return i;
                }
            }
            return -1;
        }
        /// <summary>
        /// 获取指定单元在当前列表中的位置，从后先前查找
        /// </summary>
        /// <param name="element">单元</param>
        /// <returns>位置</returns>
        public int LastIndexOf(T element)
        {
            for (int i = m_length-1; i >=0; i--)
            {
                if (m_items[i].Equals(element))
                {
                    return i;
                }
            }
            return -1;
        }

        /// <summary>
        /// 获得长度
        /// </summary>
        public virtual int Count
        {
            get
            {
                return m_length;
            }
        }
        /// <summary>
        /// 移除指定位置的单元，如果单元归属权属于当前列表，则会将其卸载
        /// </summary>
        /// <param name="index">位置索引</param>
        /// <returns>移除掉的单元</returns>
        public virtual void RemoveAt(int index)
        {
            if (index < 0 || index >= m_length)
            {
                return;
            }
            for (int i = index; i <= m_length - 2; i++)
            {
                m_items[i] = m_items[i + 1];
            }
            m_length--;
        }
        /// <summary>
        /// 移除指定尾部单元
        /// </summary>
        /// <returns>移除掉的单元</returns>
        public virtual T RemoveEnd()
        {
            if (m_length <= 0)
            {
                return default(T);
            }
            T temp = m_items[m_length - 1];
            m_items[m_length - 1] = default(T);
            m_length--;
            return temp;
        }
        /// <summary>
        /// 从指定位置开始(包括当前)，移除后续单元，如果单元归属权属于当前列表，则会将其卸载
        /// </summary>
        /// <param name="index">要移除的位置</param>
        /// <param name="innerMove">是否是内部移动</param>
        /// <returns>被移除的个数，如果index越界，则返回-1</returns>
        public virtual int RemoveAllFrom(int index)
        {
            if (index < 0 || index >= m_length)
            {
                return -1;
            }
            int removedNum = 0;
            for (int i = m_length - 1; i >= index; i--)
            {
                m_items[i] = default(T);
                m_length--;
                removedNum++;
            }
            return removedNum;
        }
        /// <summary>
        /// 移除指定单元，如果单元归属权属于当前列表，则会将其卸载
        /// </summary>
        /// <param name="element">单元</param>
        /// <returns>是否操作成功</returns>
        public virtual bool Remove(T element)
        {
            int index = IndexOf(element);
            if (index < 0)
            {
                return false;
            }
            RemoveAt(index);
            return true;
        }
        /// <summary>
        /// 获取所有数据，注意这里的数据可能包含了很多冗余空数据，长度>=当前数组长度。
        /// </summary>
        /// <returns>所有数据数组</returns>
        public T[] GetAllItems()
        {
            return m_items;
        }
        /// <summary>
        /// 转换成定长数组，伴随着内容拷贝。
        /// 如果是值类型数组，将与本动态数组失去关联；
        /// 如果是引用类型数组，将与本动态数组保存相同的引用。
        /// </summary>
        /// <returns>数组</returns>
        public virtual Array ToArray()
        {
            T[] array = new T[m_length];
            for (int i = 0; i < m_length; i++)
            {
                array[i] = m_items[i];
            }
            return array;
        }
        /// <summary>
        /// 显示此数组，每个单元之间以逗号分隔
        /// </summary>
        public void Show()
        {
            string text = "";
            for (int i = 0; i < m_length; i++)
            {
                T obj = m_items[i];
                text += (obj.ToString() + ",");
            }
            Debug.Log(text);
        }

        /// <summary>
        /// 显示此数组，每个单元一行
        /// </summary>
        public void ShowByLines()
        {
            string text = "";
            for (int i = 0; i < m_length; i++)
            {
                T obj = m_items[i];
                text += (obj.ToString());
            }
            Debug.Log(text);
        }


        public IEnumerator<T> GetEnumerator()
        {
            //搜索可用的枚举器
            int idleEnumID = -1;
            for (int i = 0; i < m_enumStates.Length; i++)
            {
                if (!m_enumStates[i])
                {
                    idleEnumID = i;
                    break;
                }
            }
            if (idleEnumID < 0)
            {
                    Debug.LogError("use too much enumerators");
            }
            //标记为已经使用状态
            m_enumStates[idleEnumID] = true;
            m_enumerators[idleEnumID].Reset();
            return m_enumerators[idleEnumID];
        }
        IEnumerator  IEnumerable.GetEnumerator()
        {
            return null;
        }

        struct ABEnumerator<T> : IDisposable, IEnumerator<T>
        {
            private AB_List<T> m_list;
            private int m_idNext;
            private T m_current;
            private int m_id;
           public  object Current
            {
                get
                {
                    if (this.m_idNext <= 0)
                    {
                        throw new InvalidOperationException();
                    }
                    return this.m_current;
                }
            }
            T IEnumerator<T>.Current
            {
                get
                {
                    return this.m_current;
                }
            }

            internal ABEnumerator(AB_List<T> list,int id)
            {
                this.m_list = list;
                this.m_idNext = 0;
                this.m_id=id;
                m_current = default(T);
            }

            void IEnumerator.Reset()
            {
                this.m_idNext = 0;
            }

            public void Dispose()
            {
                //this.m_list = null;
                //清除使用标记
                m_list.m_enumStates[m_id] = false;
            }


            public bool MoveNext()
            {
                if (this.m_list == null)
                {
                    throw new ObjectDisposedException(base.GetType().FullName);
                }
                if (this.m_idNext < 0)
                {
                    return false;
                }
                if (this.m_idNext < this.m_list.Count)
                {
                    this.m_current = this.m_list.m_items[this.m_idNext++];
                    return true;
                }
                this.m_idNext = -1;
                return false;
            }
        }
    }



}

下面是修改后的ForeachTest 类

using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using AndrewBox.Math;

public class ForeachTest : MonoBehaviour {

    int[] m_intArray;
    List<int> m_intList;
    ArrayList m_arryList;
    AB_List<int> m_intABList;
    public void Start () 
    {
        m_intArray = new int[2];
        m_intList = new List<int>();
        m_arryList = new ArrayList();
        m_intABList = new AB_List<int>();
        for (int i = 0; i < m_intArray.Length; i++)
        {
            m_intArray[i] = i;
            m_intList.Add(i);
            m_arryList.Add(i);
            m_intABList.Add(i);
        }
    }

    void Update () 
    {
        testABListEnumLevel();
        //testABListGetEmulator();
        //testABListForeach();
    }

    void testIntListForeach()
    {
        for (int i = 0; i < 1000; i++)
        {
            foreach (var iNum in m_intList)
            {
            }
        }
    }
    void testIntListGetEmulator()
    {
        for (int i = 0; i < 1000; i++)
        {
            var iNum = m_intList.GetEnumerator();
            while (iNum.MoveNext())
            {
            }
        }
    }
    void testIntArrayForeach()
    {
        for (int i = 0; i < 1000; i++)
        {
            foreach (var iNum in m_intArray)
            {
            }
        }
    }
    void testIntArrayGetEmulator()
    {
        for (int i = 0; i < 1000; i++)
        {
            var iNum = m_intArray.GetEnumerator();
            while (iNum.MoveNext())
            {
            }
        }
    }
    void testArrayListForeach()
    {
        for (int i = 0; i < 1000; i++)
        {
            foreach (var iNum in m_arryList)
            {
            }
        }
    }
    void testArrayListGetEmulator()
    {
        for (int i = 0; i < 1000; i++)
        {
            var iNum = m_arryList.GetEnumerator();
            while (iNum.MoveNext())
            {
            }
        }
    }
    void testABListForeach()
    {
        for (int i = 0; i < 1000; i++)
        {
            foreach (var iNum in m_intABList)
            {
            }
        }
    }
    void testABListGetEmulator()
    {
        for (int i = 0; i < 1000; i++)
        {
            using (var iNum = m_intABList.GetEnumerator())
            {
                while (iNum.MoveNext())
                {
                    var t = iNum.Current;
                }
            }
        }
    }
    void testABListEnumLevel()
    {
        foreach (var iNum1 in m_intABList)
        {
            foreach (var iNum2 in m_intABList)
            {
                foreach (var iNum3 in m_intABList)
                {
                    foreach (var iNum4 in m_intABList)
                    {
                        //foreach (var iNum5 in m_intABList)
                        //{
                        //}
                    }
                }
            }
        }
    }
}

Foreach调用解析

关键之处作个解释：
首先理清楚IEnumerable、IEnumerator之间的关系。
IEnumerable是指那种可以被枚举的列表类型，如果我们自己自定义一个List，希望它能结合foreach使用的话，必须实现这个接口。
IEnumerator是一个枚举器。

系统库里的IEnumerable接口是这样：

using System.Runtime.InteropServices;

namespace System.Collections
{
    public interface IEnumerable
    {
        IEnumerator GetEnumerator();
    }
}

在我的ABList类中实现接口的函数是下面这样:

        IEnumerator  IEnumerable.GetEnumerator()
        {
            if (m_enumerator == null)
            {
                m_enumerator = new ABEnumerator<T>(this);
            }
            m_enumerator.Reset();
            return m_enumerator;
        }

目前的函数实现经过设计的话，它不会产生GC。然而，问题在后面紧紧跟随。实现了IEnumerable接口之后。当我们使用形如foreach(var t in list)的时刻，它就会去调用list中的继承于IEnumerator的Current实现：

namespace System.Collections
{
    public interface IEnumerator
    {
        object Current
        {
            get;
        }

        bool MoveNext();
        void Reset();
    }
}

看到这里，它返回的是object，如果我们List中存放的是值类型，那么系统自然就产生了一次box装箱操作，GC于是悄悄地产生了。
也正是因为这个原因，微软后来加入了泛型的IEnumerator。但是，为了兼容以前的设计，这个泛型IEnumerator被设计成实现于之前的IEnumerator，而它的下方增加了同样的Current的Get方法。

using System;
using System.Collections;

namespace System.Collections.Generic
{
    public interface IEnumerator<T> : IEnumerator, IDisposable
    {
        T Current
        {
            get;
        }
    }
}

同样的设计也被用于泛型的IEnumerable，

using System.Collections;

namespace System.Collections.Generic
{
    public interface IEnumerable<T> : IEnumerable
    {
        IEnumerator<T> GetEnumerator();
    }
}

如果我们实现泛型的IEnumerable和IEnumerator，必须同时泛型和非泛型的GetEnumerator和Current方法。
那么，问题来了。现在有两个GetEnumerator()方法，两个Current的Get方法，究竟该用谁的呢？
首先，在实现的时候就需要加以区分：

        public IEnumerator<T> GetEnumerator()
        IEnumerator  IEnumerable.GetEnumerator()

这两个实现，你给其中一个加上public，另外一个就不能加上public；两个函数至少有一个需要增加[接口名称.]这种前缀；那么最终我们在foreach期间调用的就是public的那个方法。
自然，我们这里为了避免使用到非泛型IEnumerator中的Current方法的object返回形式，我们必须使用将唯一的生存权留给泛型的GetEnumerator。
同样，我们也需要在自定义的枚举器中作出选择。保留泛型的Current函数。

 struct ABEnumerator<T> : IDisposable, IEnumerator<T>
 {
         private AB_List<T> m_list;
          private int m_idNext;
          private T m_current;

         public  object Current
          {
              get
              {
                  if (this.m_idNext <= 0)
                  {
                      throw new InvalidOperationException();
                  }
                  return this.m_current;
              }
          }
          T IEnumerator<T>.Current
          {
              get
              {
                  return this.m_current;
              }
          }
          ...

GC测试

应用于AB_List< int >的foreach

    void testABListForeach()
    {
        for (int i = 0; i < 1000; i++)
        {
            foreach (var iNum in m_intABList)
            {
            }
        }
    }

没有产生GC

应用于AB_List< int >的GetEnumerator

    void testABListGetEmulator()
    {
        for (int i = 0; i < 1000; i++)
        {
            var iNum = m_intABList.GetEnumerator();
            while (iNum.MoveNext())
            {
               var t=  iNum.Current;
            }
        }
    }

也没有产生GC

局限性

本list虽然没有GC，但是其使用也有一定的局限性。

最大的局限性是foreach嵌套的问题。当我们在很多重嵌套中同时foreach这个list时，相当于需要多个枚举器同时存在。List被设计为存储一定数目的枚举器组，以便于多次调用。(这样设计是为了避免值类型枚举器被当做引用返回时造成的装箱问题)

不过，一般而言，你应该不需要那么多层的foreach嵌套，默认允许同时嵌套5层，如果你需要超过5层的嵌套，则在ABList的构造函数中传入更多测层次就可以。
另外一个小小的限制就是，当你使用getEnumerator()时，需要把它们放在using中，大概是这样：

            using (var iNum = m_intABList.GetEnumerator())
            {
            }

这样做的目的是在代码块结束时，调用枚举器的Dispose方法，这样可以让这个枚举器变成可重用状态。

总结

Unity系统的泛型List存在的问题是：它在finally中回收枚举器时执行了Box操作。自定义List时，正确实现泛型格式的IEnumerable、IEnumerator是关键，需要避开枚举单元被Current时，值类型被强制转换成对象类型的Box操作。

总体上来说，这应该是一个高效的，无GC的List，看官可以尝试一哈。