【Unity优化】构建一个拒绝GC的List
上篇文章《【Unity优化】Unity中究竟能不能使用foreach?》发表之后,曾经有网友说,在他的不同的Unity版本上,发现了泛型List无论使用foreach还是GetEnumerator均会产生GC的情况,这就有点尴尬了。由于它本身就是Mono编译器和相应.net库才能决定的原因,这就使得在使用系统提供的List时,又能最终摆脱GC的纠缠变得很困难。于是抓耳挠腮,翻出差不多六七年为Java代码写的动态数组,然后大肆修改一番。最终好像终于逃离GC的魔咒。
先奉上代码:
自定义的List
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 | using System; using System.Collections; using System.Collections.Generic; using UnityEngine; namespace AndrewBox.Math { /// /// 动态数组 /// @author AndrewFan /// /// public class AB_List { protected int m_capacity=10; // 容量 protected T[] m_items; // 内部数组 protected int m_length; // 存放的单元个数 protected int m_mayIdleID; // 可能空闲的单元下标 protected IEnumerator //枚举器组 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 m_enumStates = new bool [enumCount]; for ( int i = 0; i < m_enumerators.Length; i++) { m_enumerators[i] = new ABEnumerator this ,i); } } } /// /// 增加单元 /// /// 添加的单元 public virtual void Add(T element) { increaseCapacity(); // 赋值 m_items[m_length] = element; m_length++; } /// /// 插入单元 /// /// 插入位置 /// 单元 /// 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; } } /// /// 增长容量 /// 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; } } /// /// 清空单元数组 /// public virtual void Clear() { for ( int i = 0; i < m_length; i++) { m_items[i] = default (T); } m_length = 0; } /// /// 是否包含某个单元 /// /// 单元 /// public bool Contains(T element) { for ( int i = 0; i < m_length; i++) { if (m_items[i].Equals(element)) { return true ; } } return false ; } /// /// 获取指定单元在当前列表中的位置,从前向后查找 /// /// 单元 /// public int IndexOf(T element) { for ( int i = 0; i < m_length; i++) { if (m_items[i].Equals(element)) { return i; } } return -1; } /// /// 获取指定单元在当前列表中的位置,从后先前查找 /// /// 单元 /// public int LastIndexOf(T element) { for ( int i = m_length-1; i >=0; i--) { if (m_items[i].Equals(element)) { return i; } } return -1; } /// /// 获得长度 /// public virtual int Count { get { return m_length; } } /// /// 移除指定位置的单元,如果单元归属权属于当前列表,则会将其卸载 /// /// 位置索引 /// 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--; } /// /// 移除指定尾部单元 /// /// 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; } /// /// 从指定位置开始(包括当前),移除后续单元,如果单元归属权属于当前列表,则会将其卸载 /// /// 要移除的位置 /// 是否是内部移动 /// 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; } /// /// 移除指定单元,如果单元归属权属于当前列表,则会将其卸载 /// /// 单元 /// public virtual bool Remove(T element) { int index = IndexOf(element); if (index < 0) { return false ; } RemoveAt(index); return true ; } /// /// 获取所有数据,注意这里的数据可能包含了很多冗余空数据,长度>=当前数组长度。 /// /// public T[] GetAllItems() { return m_items; } /// /// 转换成定长数组,伴随着内容拷贝。 /// 如果是值类型数组,将与本动态数组失去关联; /// 如果是引用类型数组,将与本动态数组保存相同的引用。 /// /// 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; } /// /// 显示此数组,每个单元之间以逗号分隔 /// public void Show() { string text = "" ; for ( int i = 0; i < m_length; i++) { T obj = m_items[i]; text += (obj.ToString() + "," ); } Debug.Log(text); } /// /// 显示此数组,每个单元一行 /// 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 { //搜索可用的枚举器 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 { private AB_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 { get { return this .m_current; } } internal ABEnumerator(AB_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 ; 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 ; } } } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 | 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) //{ //} } } } } } } int > int > int > int > |
Foreach调用解析
关键之处作个解释:
首先理清楚IEnumerable、IEnumerator之间的关系。
IEnumerable是指那种可以被枚举的列表类型,如果我们自己自定义一个List,希望它能结合foreach使用的话,必须实现这个接口。
IEnumerator是一个枚举器。
系统库里的IEnumerable接口是这样:
1 2 3 4 5 6 7 8 9 | using System.Runtime.InteropServices; namespace System.Collections { public interface IEnumerable { IEnumerator GetEnumerator(); } } |
在我的ABList类中实现接口的函数是下面这样:
1 2 3 4 5 6 7 8 9 | IEnumerator IEnumerable.GetEnumerator() { if (m_enumerator == null ) { m_enumerator = new ABEnumerator this ); } m_enumerator.Reset(); return m_enumerator; } |
目前的函数实现经过设计的话,它不会产生GC。然而,问题在后面紧紧跟随。实现了IEnumerable接口之后。当我们使用形如foreach(var t in list)的时刻,它就会去调用list中的继承于IEnumerator的Current实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 | namespace System.Collections { public interface IEnumerator { object Current { get ; } bool MoveNext(); void Reset(); } } |
看到这里,它返回的是object,如果我们List中存放的是值类型,那么系统自然就产生了一次box装箱操作,GC于是悄悄地产生了。
也正是因为这个原因,微软后来加入了泛型的IEnumerator。但是,为了兼容以前的设计,这个泛型IEnumerator被设计成实现于之前的IEnumerator,而它的下方增加了同样的Current的Get方法。
1 2 3 4 5 6 7 8 9 10 11 12 13 | using System; using System.Collections; namespace System.Collections.Generic { public interface IEnumerator { T Current { get ; } } } |
同样的设计也被用于泛型的IEnumerable,
1 2 3 4 5 6 7 8 9 | using System.Collections; namespace System.Collections.Generic { public interface IEnumerable { IEnumerator } } |
如果我们实现泛型的IEnumerable和IEnumerator,必须同时泛型和非泛型的GetEnumerator和Current方法。
那么,问题来了。现在有两个GetEnumerator()方法,两个Current的Get方法,究竟该用谁的呢?
首先,在实现的时候就需要加以区分:
public IEnumerator GetEnumerator() IEnumerator IEnumerable.GetEnumerator()
这两个实现,你给其中一个加上public,另外一个就不能加上public;两个函数至少有一个需要增加[接口名称.]这种前缀;那么最终我们在foreach期间调用的就是public的那个方法。
自然,我们这里为了避免使用到非泛型IEnumerator中的Current方法的object返回形式,我们必须使用将唯一的生存权留给泛型的GetEnumerator。
同样,我们也需要在自定义的枚举器中作出选择。保留泛型的Current函数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | struct ABEnumerator { private AB_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 { get { return this .m_current; } } ... |
GC测试
应用于AB_List< int >的foreach
1 2 3 4 5 6 7 8 9 | void testABListForeach() { for ( int i = 0; i < 1000; i++) { foreach (var iNum in m_intABList) { } } } |
没有产生GC
应用于AB_List< int >的GetEnumerator
1 2 3 4 5 6 7 8 9 10 11 | 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中,大概是这样:
1 2 3 | using (var iNum = m_intABList.GetEnumerator()) { } |
这样做的目的是在代码块结束时,调用枚举器的Dispose方法,这样可以让这个枚举器变成可重用状态。
总结
Unity系统的泛型List存在的问题是:它在finally中回收枚举器时执行了Box操作。自定义List时,正确实现泛型格式的IEnumerable、IEnumerator是关键,需要避开枚举单元被Current时,值类型被强制转换成对象类型的Box操作。
总体上来说,这应该是一个高效的,无GC的List,看官可以尝试一哈。