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

发表于2017-06-25

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

先奉上代码：

自定义的List

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 类

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接口是这样：

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

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

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实现：

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 : IEnumerator, IDisposable
    {
        T Current
        {
            get;
        }
    }
}

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

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函数。

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

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，看官可以尝试一哈。

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

标签：

游戏开发 Unity GC List Array 接口

首页

出海助力

开发者社区

大奖赛

同行

合作案例

关于我们