《Unity主程手记》摘要记录(1)

作者：陆泽西-《Unity3D高级编程：主程手记》

第一章

1.1架构的意义

1、承载力；2、可扩展性；3、易用性；4、可伸缩性；5、容错

1.2设计

分层（spring web应用、Linux系统架构、TCP/IP分层架构）

分治（分治抽象）

1.3构建

网络->数据->资源管理->核心逻辑框架->框架。GF、ET。

第二章

2.1底层原理和机制

c#源码地址

c#的运行机制：C#代码->编译器->IL（DLL文件）->CLR（加载DLL然后翻译）->10000101（机器语言）

IL2CPP：将IL翻译成C++代码，发布到不同平台时，调用对应平台的C++编译器，AOT，无法热更。

Mono：.Net的跨平台项目，性能底下，C#版本更新慢，无法使用新版本的特性。

三种编译模式：

JIT:Just-In-Time，程序运行时将CIL编译为机器码

AOT:Ahead-Of-Time，将IL编译成机器码并存储在文件中，提前编译。

完全静态编译：该模式只支持少数平台，基于AOT更进一步产生所有的机器码，这可以让程序在运行期间完全不需要JIT，适用于IOS，PS,Xbox等主机系统。

2.2List底层源码

构造部分：

    [DebuggerTypeProxy(typeof(Mscorlib_CollectionDebugView<>))]
    [DebuggerDisplay("Count = {Count}")]
    [Serializable]
    public class List<T> : IList<T>, System.Collections.IList, IReadOnlyList<T>
    {
        private const int _defaultCapacity = 4;
 
        private T[] _items;
        [ContractPublicPropertyName("Count")]
        private int _size;
        private int _version;
        [NonSerialized]
        private Object _syncRoot;
        
        static readonly T[]  _emptyArray = new T[0];        
            
        // Constructs a List. The list is initially empty and has a capacity
        // of zero. Upon adding the first element to the list the capacity is
        // increased to 16, and then increased in multiples of two as required.
        public List() {
            _items = _emptyArray;
        }
    
        // Constructs a List with a given initial capacity. The list is
        // initially empty, but will have room for the given number of elements
        // before any reallocations are required.
        // 
        public List(int capacity) {
            if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
            Contract.EndContractBlock();
 
            if (capacity == 0)
                _items = _emptyArray;
            else
                _items = new T[capacity];
        }

List内部是用数组实现，而非链表，并且没有指定指定capacity时，数组大小为0。

接下来看Add方法

		//将给定对象添加到列表末尾，列表大小+1
		//如果需要，在添加新元素前，列表容量增加一倍
        public void Add(T item) {
            if (_size == _items.Length) EnsureCapacity(_size + 1);
            _items[_size++] = item;
            _version++;
        }

EnsureCapacity：

		//如果列表当前容量小于min，则容量将增加到当前容量的两倍或min，以较大者为准
        private void EnsureCapacity(int min) {
            if (_items.Length < min) {
                int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
                //在遇到溢出前，允许列表增长到最大可能的容量（大约2GB）
                //请注意，即使_items.Length由于Uint强制转换而溢出，此检查仍然有效
                if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
                if (newCapacity < min) newCapacity = min;
                Capacity = newCapacity;
            }
        }

每次增加一个元素，先检查容量是否还够，不够就调用EnsureCapacity增加容量。

在EnsureCapacity()中，每次容量不够，都会扩容一倍，_defaultCapacity表示容量的默认值为4，扩充容量默认为4->8->16->32……..

List使用数组作为底层数据结构，优点是索引快，缺点是扩容时性能堪忧，每次针对数组的new操作都会造成内存垃圾，这会给GC带来负担

然后是Remove方法：

		//删除给定索引处的元素，列表大小-1
        public bool Remove(T item) {
            int index = IndexOf(item);
            if (index >= 0) {
                RemoveAt(index);
                return true;
            }
 
            return false;
        }
 
		//返回列表范围内给定值首次出现的索引
		//该列表从头到尾向前搜索
		//使用Object.Equles方法将列表中的元素与给定值进行比较
		//此方法使用Array.IndexOf方法执行搜索
        public int IndexOf(T item) {
            Contract.Ensures(Contract.Result<int>() >= -1);
            Contract.Ensures(Contract.Result<int>() < Count);
            return Array.IndexOf(_items, item, 0, _size);
        }

        //删除给定索引处的元素，列表大小-1
        public void RemoveAt(int index) {
            if ((uint)index >= (uint)_size) {
                ThrowHelper.ThrowArgumentOutOfRangeException();
            }
            Contract.EndContractBlock();
            _size--;
            if (index < _size) {
                Array.Copy(_items, index + 1, _items, index, _size - index);
            }
            _items[_size] = default(T);
            _version++;
        }

Remove的调用包含IndexOf和RemoveAt两个方法，前者是为了找到元素的索引位置，后者删除指定位置的元素。

原理就是使用Array.Copy对数组进行覆盖，IndexOf的实现是Array.IndexOf，它本身内部的实现就是按索引顺序从0到n对每个位置进行比较，复杂度为先行迭代O(n)。

其他的就不贴源码了。

然后是Insert，和Add一样，先检查容量，不够就扩容，Insert插入元素时，使用的是复制数组的形式，将数组里指定元素后面的所有元素向后移动一个位置。

Add、Remove、Insert、IndexOf等接口都是没有做优化的，使用的都是线性迭代的方式。如果频繁使用，效率就会降低，也会造成不少的内存冗余，使得GC承担更多压力

其他接口也是一样比如AddRange、RemoveRange等

其他：

索引器直接使用数组索引实现

Clear方法调用时并不删除数组，而是将数组中的所有元素置为默认值（0或者null）然后设置_size为0，用于虚拟地表示当前容量。清零会将对象的引用标记从此集合中移除，从这个角度看，调用Clear清零是必要的。

Contains方法使用线性查找遍历比较元素，如果一致就返回true，否则返回false。

ToArray重新创建一个指定大小的数组，将数组本身的内容复制（Array.Copy()）到新数组上再返回，过多使用会造成大量的内存分配

Find和Contains一样是线性查找

Enumerator注意每次获取迭代器时，Enumerator都会被创建（foreach的坑，.Net4.0后已经修复，但仍然不建议大量使用）

Sort调用了Array.Sort()，排序方式为快速排序，效率为O(nlgn)。

List的效率其实并不高，大部分算法都是线性复杂度，遇到规模较大的计算时会导致性能问题
此外List的内存分配方式也不合理，当其中元素不断增加会多次重新分配数组，抛弃原有数组。调用GC时候会造成压力。最好在List初始化的时候就声明Capacity。
List不是线程安全的，并发情况下无法检查_size++的执行顺序，在多线程情况下使用List时应该注意安全
**真实情况是，List并不高效，但是足够通用

2.3Dictionary源码

使用哈希函数做KV映射。

冲突处理方法：开放定址法，再Hash法，拉链法，公共溢出区等，Dictionary使用的是拉链法。

成员字段：

    [DebuggerTypeProxy(typeof(Mscorlib_DictionaryDebugView<,>))]
    [DebuggerDisplay("Count = {Count}")]
    [Serializable]
    [System.Runtime.InteropServices.ComVisible(false)]
    public class Dictionary<TKey,TValue>: IDictionary<TKey,TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue>, ISerializable, IDeserializationCallback  {
    
        private struct Entry {
            public int hashCode;    // Lower 31 bits of hash code, -1 if unused
            public int next;        // Index of next entry, -1 if last
            public TKey key;           // Key of entry
            public TValue value;         // Value of entry
        }
        
        private int[] buckets;
        private Entry[] entries;
        private int count;
        private int version;
        private int freeList;
        private int freeCount;
        private IEqualityComparer<TKey> comparer;
        private KeyCollection keys;
        private ValueCollection values;
        private Object _syncRoot;

底层数据结构为数组，实例化后内部内部数组是0个数组.

Add

        public void Add(TKey key, TValue value) {
            Insert(key, value, true);
        }

        private void Initialize(int capacity) {
            int size = HashHelpers.GetPrime(capacity);
            buckets = new int[size];
            for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;
            entries = new Entry[size];
            freeList = -1;
        }

        private void Insert(TKey key, TValue value, bool add) {
        
            if( key == null ) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }
 
            if (buckets == null) Initialize(0);
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
            int targetBucket = hashCode % buckets.Length;
 
#if FEATURE_RANDOMIZED_STRING_HASHING
            int collisionCount = 0;
#endif
 
            for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
                    if (add) { 
                        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
                    }
                    entries[i].value = value;
                    version++;
                    return;
                } 
 
#if FEATURE_RANDOMIZED_STRING_HASHING
                collisionCount++;
#endif
            }
            int index;
            if (freeCount > 0) {
                index = freeList;
                freeList = entries[index].next;
                freeCount--;
            }
            else {
                if (count == entries.Length)
                {
                    Resize();
                    targetBucket = hashCode % buckets.Length;
                }
                index = count;
                count++;
            }
 
            entries[index].hashCode = hashCode;
            entries[index].next = buckets[targetBucket];
            entries[index].key = key;
            entries[index].value = value;
            buckets[targetBucket] = index;
            version++;
 
#if FEATURE_RANDOMIZED_STRING_HASHING
 
#if FEATURE_CORECLR
            // In case we hit the collision threshold we'll need to switch to the comparer which is using randomized string hashing
            // in this case will be EqualityComparer<string>.Default.
            // Note, randomized string hashing is turned on by default on coreclr so EqualityComparer<string>.Default will 
            // be using randomized string hashing
 
            if (collisionCount > HashHelpers.HashCollisionThreshold && comparer == NonRandomizedStringEqualityComparer.Default) 
            {
                comparer = (IEqualityComparer<TKey>) EqualityComparer<string>.Default;
                Resize(entries.Length, true);
            }
#else
            if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer)) 
            {
                comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer);
                Resize(entries.Length, true);
            }
#endif // FEATURE_CORECLR
 
#endif
        }

主要看Insert，初始化调用HashHelper->GetPrime，他会返回一个size需要的最小质数值，首次定义为3每次扩容两倍-即3->7->17->37（每次都是质数）

对关键字key做hash操作，获得索引地址：

int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;//防止hashCode为负数

int targetBucket = hashCode % buckets.Length;

调用函数获得Hash值后，含需要对Hash地址执行余数操作确保再数组长度方范围内不溢出。

然后找到指定key位置的链表进行遍历，找出空位置将Value插入

            for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
                    if (add) { 
                        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
                    }
                    entries[i].value = value;
                    version++;
                    return;
                } 
#if FEATURE_RANDOMIZED_STRING_HASHING
                collisionCount++;
#endif

这就是拉链法的推入操作。如果数组空间不够（freeCount为0），则扩容

Remove

        public bool Remove(TKey key) {
            if(key == null) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }
 
            if (buckets != null) {
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                int bucket = hashCode % buckets.Length;
                int last = -1;
                for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next) {
                    if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
                        if (last < 0) {
                            buckets[bucket] = entries[i].next;
                        }
                        else {
                            entries[last].next = entries[i].next;
                        }
                        entries[i].hashCode = -1;
                        entries[i].next = freeList;
                        entries[i].key = default(TKey);
                        entries[i].value = default(TValue);
                        freeList = i;
                        freeCount++;
                        version++;
                        return true;
                    }
                }
            }
            return false;
        }

和插入类似，对key进行hash操作然后在链表里找匹配元素，Remove并没有对内存进行删减，而是将对应hash位置置为默认值，这是为了减少内存的频繁操作。

ContainsKey

        public bool ContainsKey(TKey key) {
            return FindEntry(key) >= 0;
        }

        private int FindEntry(TKey key) {
            if( key == null) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }
 
            if (buckets != null) {
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
                    if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
                }
            }
            return -1;
        }

FindEntry使用和前面相同的方式查找key的hash位置，然后从链表里匹配元素，成功返回该索引地址。

TryGetValue与ContainsKey类似，以此获取对应的Value，然后对索引器进行重定义。

Hash函数的创建过程

//
        // Note that logic in this method is replicated in vm\compile.cpp to ensure that NGen
        // saves the right instantiations
        //
        [System.Security.SecuritySafeCritical]  // auto-generated
        private static EqualityComparer<T> CreateComparer() {
            Contract.Ensures(Contract.Result<EqualityComparer<T>>() != null);
 
            RuntimeType t = (RuntimeType)typeof(T);
            // Specialize type byte for performance reasons
            if (t == typeof(byte)) {
                return (EqualityComparer<T>)(object)(new ByteEqualityComparer());
            }
            // If T implements IEquatable<T> return a GenericEqualityComparer<T>
            if (typeof(IEquatable<T>).IsAssignableFrom(t)) {
                return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericEqualityComparer<int>), t);
            }
            // If T is a Nullable<U> where U implements IEquatable<U> return a NullableEqualityComparer<U>
            if (t.IsGenericType && t.GetGenericTypeDefinition() == typeof(Nullable<>)) {
                RuntimeType u = (RuntimeType)t.GetGenericArguments()[0];
                if (typeof(IEquatable<>).MakeGenericType(u).IsAssignableFrom(u)) {
                    return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(NullableEqualityComparer<int>), u);
                }
            }
            
            // See the METHOD__JIT_HELPERS__UNSAFE_ENUM_CAST and METHOD__JIT_HELPERS__UNSAFE_ENUM_CAST_LONG cases in getILIntrinsicImplementation
            if (t.IsEnum) {
                TypeCode underlyingTypeCode = Type.GetTypeCode(Enum.GetUnderlyingType(t));
 
                // Depending on the enum type, we need to special case the comparers so that we avoid boxing
                // Note: We have different comparers for Short and SByte because for those types we need to make sure we call GetHashCode on the actual underlying type as the 
                // implementation of GetHashCode is more complex than for the other types.
                switch (underlyingTypeCode) {
                    case TypeCode.Int16: // short
                        return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(ShortEnumEqualityComparer<short>), t);
                    case TypeCode.SByte:
                        return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(SByteEnumEqualityComparer<sbyte>), t);
                    case TypeCode.Int32:
                    case TypeCode.UInt32:
                    case TypeCode.Byte:
                    case TypeCode.UInt16: //ushort
                        return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(EnumEqualityComparer<int>), t);
                    case TypeCode.Int64:
                    case TypeCode.UInt64:
                        return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(LongEnumEqualityComparer<long>), t);
                }
            }
            // Otherwise return an ObjectEqualityComparer<T>
            return new ObjectEqualityComparer<T>();
        }

对于数字类型，他们实现了IEquatable接口，直接使用GenericEqualityComparer获得hash函数。否则如果实现了Nullable接口，则调用NullableEquality-Comparer()，如果不是以上两种情况则调用ObjectEqualityComparer。

和List一样，Dictionary并不是线程安全的

官方源码中有这样的解释：

**Hashtable has Multiple reader/single writer(MR/SW) thread safety built into
**certain methods and properties,-whereas Dictionary doesn't.If you're
**converting to consider whether callers may have taken a dependence on MR/SW
**thread safety.IF a writer lock is available,then that maybe used
**with a Dictionary to et the same thread safety guarantee.

Hashtable在多线程读/写中是线程安全的，而Dictionary不是。如果要在多个线程中共享Dictionary的读/写操作，就要自己写lock，以保证线程安全。

2.4浮点数的精度问题

数值比较不相等，浮点数在运算时无法准确定位到某个值，比如要么比0.23小，要么比他大，这样就不能使用==来做检查而是使用>、<，如果要用等于，则必须使用一个很小的浮动区间，abs(X-Y) <0.00001，即X -Y >float.Epsilon。
设备不同，不同平台和架构会导致浮点数的精度不一致
计算数值不确定，浮点数由于位数限制无法得到一个精确的数值，而是一个被截断的值，在某些情况期望的结果是1，但算出来可能是0.9999999999。

解决办法：

由一台机器（服务器）决定运算结果，认定这个值为准确值，并将结果传递给其他设备或模块。
改用int或long，把浮点数乘以10幂次得到更准确的整数，即把精度用整型表示，比如约定所有浮点数都乘以10000，1.5x10000=15000，用的时候再转回来。
定点数，即把整数位和小数位分开存
字符串代替浮点数，但缺点是CPU和内存消耗大，只能做少量计算

2.5委托和事件、拆箱和装箱

委托

delegate的实例，从功能上来讲，类似于C++的函数指针。Delegate继承自System.MulticastDelegate，其中有BeginInvoke,EndInvoke,Invoke三个函数，分别代表异步开始，异步结束，直接调用。

MulticastDelegate

该类不允许被继承，父类Delegate也是如此，Delegate类中有一个变量用于存储函数地址，当变量操作=符号时，将直接保存函数地址。他还重写了+=，-=两个操作符它对应了MulticastDelegate的Combine和Remove。当对这些操作符进行操作时，相当于把函数地址退入链表尾部或移出链表。

当委托被调用。委托实例会以此调用调用链中保存的函数并将参数带进去。

官方文档如下：

MulticastDelegate类中有一个已经连接好的delegate列表，被称为调用列表，它由一个或者更多个元素组成。当一个multicast delegate被启动调用时，所有在调用列表里的delegate都会按照它们出现的顺序被调用。如果在执行列表期间遇到一个错误，就会立即抛出异常并停止调用。

Event

在委托上又做一次封装，这样做是出于业务代码的维护考虑。

装箱和拆箱

简单来讲，就是将一个值类型（数字，结构体，bool等）转换为引用类型（class,string等）或反过来。

值类型的数据存储在stack上，直接持有。

引用类型的真实数据存储在heap，持有该地址的指针。

装箱的内部操作：在堆内存分配一个新的内存块，将值类型的值复制到堆内存中，返回指向这个堆内存地址的指针。

拆箱反过来就可以了。

避免方法：

使用struct
使用泛型
通过统一实现的接口提前拆装箱

2.6排序

快排：最坏情况O(n^2)，不消耗额外内存

最大最小堆：二叉树、寻路算法

桶排序、基数排序

2.7搜索算法

二分法：要求列表有序，效率较好。

平衡二叉树、红黑树、B树

四叉树：主要运用在2D平面空间搜索和划分上

八叉树：3D空间

2.8业务逻辑优化技巧

List&Dictionary

List->Contains,insert,Remove都是线性查找。

设置初始大小避免扩容，对于Dictionary来说

注意GetHashCode的算力损耗。
Struct

Struct分配在stack上，stack是连续内存，并且返回外部调用后回收非常快。CPU读取数据对连续内存也是友好的

使用数组时Struct的值是内存连续的，有利于CPU缓存命中。但并非所有结构体都可以这样。如果结构体太大超过了缓存复制的数据块则缓存命中不再起作用。
ObjectPool、ReferencePool
字符串

每次动态创建一个string都会在堆内存中分配一块内存。

c#对string没有缓存机制，每次使用都要重新分配（连接、切割、组合），并且抛弃没有引用的string等待GC回收

自建缓存机制，使用键值对缓存常用或常量string

使用unsafe的方式处理string(fixed，指针)

上篇一篇资源更新流程记录

下篇《Unity主程手记》摘要记录(2)