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

在不同的Unity版本中，我们发现泛型List无论使用foreach还是GetEnumerator都会产生GC（垃圾回收），这给性能优化带来了挑战。由于这一问题是由Mono编译器和相应的.NET库决定的，因此要在使用系统提供的List时避免GC变得十分困难。为此，我翻出了大约六七年前为Java代码编写的动态数组，并对其进行了大量修改，最终成功摆脱了GC的困扰。

自定义List代码实现

以下是自定义的AB_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 int m_mayIdleID; // 可能空闲的单元下标

protected IEnumerator<T>[] m_enumerators; // 枚举器组
protected bool[] m_enumStates; // 枚举器组当前占用状态

public AB_List()
{
init(5);
}

public AB_List(int capacity, int enumCount = 5)
{
m_capacity = capacity;
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();
// 向后拷贝
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++)
{
int tryID = i + m_mayIdleID;
if (!m_enumStates[tryID])
{
idleEnumID = tryID;
break;
}
}
if (idleEnumID < 0)
{
Debug.LogError("use too much enumerators");
}
// 标记为已经使用状态
m_enumStates[idleEnumID] = true;
m_enumerators[idleEnumID].Reset();
// 向前迁移空闲坐标
m_mayIdleID = (m_mayIdleID + 1) % m_enumStates.Length;
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()
{
// 清除使用标记
m_list.m_enumStates[m_id] = false;
m_list.m_mayIdleID = m_id;
}

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和IEnumerator之间的关系。IEnumerable是一个表示可以被枚举的列表类型的接口，如果我们自定义一个List并希望它能与foreach结合使用，就必须实现这个接口。而IEnumerator则是一个枚举器，用于遍历集合中的元素。

系统库中的IEnumerable接口定义如下：

using System.Runtime.InteropServices;

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

在ABList类中，实现该接口的函数如下：

IEnumerator IEnumerable.GetEnumerator()
{
return null;
}

目前的函数实现经过设计，不会产生GC。

泛型与非泛型接口的问题

实现IEnumerable接口后，当我们使用foreach(var t in list)时，会调用list中继承于IEnumerator的Current实现：

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

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

可以看到，Current属性返回的是object类型。如果我们的List中存放的是值类型，系统就会进行一次装箱操作，从而产生GC。

为了解决这个问题，微软后来引入了泛型的IEnumerator和IEnumerable接口：

using System;
using System.Collections;

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

using System.Collections;

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

当我们实现泛型的IEnumerable和IEnumerator时，必须同时实现泛型和非泛型的GetEnumerator和Current方法。那么，在使用时应该选择哪个方法呢？

在实现时，需要进行区分：

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

这两个实现中，一个需要加上public，另一个则不能加。并且至少有一个函数需要增加[接口名称.]前缀，最终foreach会调用public修饰的方法。为了避免使用非泛型IEnumerator中的Current方法返回object类型导致的装箱问题，我们应该使用泛型的GetEnumerator方法。同样，在自定义的枚举器中，也需要保留泛型的Current函数。

GC测试

AB_List的foreach测试

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

经过测试，使用AB_List<int>的foreach不会产生GC。

AB_List的GetEnumerator测试

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

同样，使用AB_List<int>的GetEnumerator也不会产生GC。

局限性

foreach嵌套问题

本List虽然避免了GC，但在使用上存在一定的局限性。最大的问题是foreach嵌套问题。当进行多层嵌套的foreach操作时，需要多个枚举器同时存在。List被设计为存储一定数量的枚举器组，以避免值类型枚举器被当做引用返回时造成的装箱问题。默认情况下，允许同时嵌套5层foreach，如果需要更多层次的嵌套，可以在ABList的构造函数中传入更大的枚举器数量。

使用getEnumerator()的限制

当使用getEnumerator()方法时，需要将其放在using语句中，示例如下：

using (var iNum = m_intABList.GetEnumerator())
{
// 代码逻辑
}

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

总结

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

总体而言，这个自定义的List是一个高效、无GC的实现，大家可以尝试使用。