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

发表于2017-06-25
评论0 2k浏览

上篇文章《【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 :IEnumerable
    {
        protected int m_capacity=10;  // 容量
        protected T[] m_items;// 内部数组
        protected int m_length;// 存放的单元个数
        protected int m_mayIdleID;// 可能空闲的单元下标
 
        protected IEnumerator[] 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[enumCount];
                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;
        }
        ///
        /// 从指定位置开始(包括当前),移除后续单元,如果单元归属权属于当前列表,则会将其卸载
        ///
        /// 要移除的位置
        /// 是否是内部移动
        /// 被移除的个数,如果index越界,则返回-1
        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 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 : IDisposable, IEnumerator
        {
            private AB_List 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.Current
            {
                get
                {
                    return this.m_current;
                }
            }
 
            internal ABEnumerator(AB_List 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;
            }
        }
    }
 
 
 
}
下面是修改后的ForeachTest 类
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 : IEnumerator, IDisposable
    {
        T Current
        {
            get;
        }
    }
}

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

1
2
3
4
5
6
7
8
9
using System.Collections;
 
namespace System.Collections.Generic
{
    public interface IEnumerable : IEnumerable
    {
        IEnumerator GetEnumerator();
    }
}

如果我们实现泛型的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 : IDisposable, IEnumerator
 {
         private AB_List 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.Current
          {
              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,看官可以尝试一哈。

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引