Unity DOTS中的Entity
在DOTS中entity往往只被看作一个ID，用来查找component，但实际上Unity为了有效地管理entity，在背后还做了一些其他的工作。首先是Entity类本身的定义，它的确跟一个ID差不多，只包含了两个int类型的成员：
public struct Entity : IEquatable<Entity>, IComparable<Entity>
{/// <summary>/// The ID of an entity./// </summary>/// <value>The index into the internal list of entities.</value>/// <remarks>/// Entity indexes are recycled when an entity is destroyed. When an entity is destroyed, the/// EntityManager increments the version identifier. To represent the same entity, both the Index and the/// Version fields of the Entity object must match. If the Index is the same, but the Version is different,/// then the entity has been recycled./// </remarks>public int Index;/// <summary>/// The generational version of the entity./// </summary>/// <remarks>The Version number can, theoretically, overflow and wrap around within the lifetime of an/// application. For this reason, you cannot assume that an Entity instance with a larger Version is a more/// recent incarnation of the entity than one with a smaller Version (and the same Index).</remarks>/// <value>Used to determine whether this Entity object still identifies an existing entity.</value>public int Version;
}
这里的Index，并非是表示entity在chunk中的存储位置，它是一个二级索引，指向管理entity的block。block才真正记录了entity位于哪个chunk，以及在chunk中的具体位置。之所以这样设计，是因为在structural change时（例如AddComponent，RemoveComponent）entity会从一个chunk移动到另一个chunk。使用二级索引，就可以保证在发生移动时，entity的index保持不变，变化的只是block中的内容。
另外，从代码中的注释可知，entity的Index是会循环利用的，当一个entity销毁时，另一个创建的entity可能会复用到之前entity的Index，所以entity还包含一个Version字段。只有当Index和Version同时相等时，两个entity才会被视为相等。Version字段的默认值为0，每当entity创建时都会+1，销毁时也会+1，这意味着只有当Version为奇数时，entity才是存在的。
管理entity的block是全局唯一的，它是一个长度为16K的64位指针数组，其中每个指针指向一个更小的data block，data block最多可记录8K数量的entity状态。所以Unity全局最多可以支持16K * 8K数量的entity。
struct DataBlock
{// 8k entities per DataBlockpublic fixed ulong allocated[k_EntitiesInBlock / 64];public fixed ulong entityInChunk[k_EntitiesInBlock];public fixed int versions[k_EntitiesInBlock];
#if !DOTS_DISABLE_DEBUG_NAMESpublic fixed int nameByEntityIndex[k_EntitiesInBlock];
#endif
}const int k_EntitiesInBlock = 8192;
这里可以看到记录data block当前分配entity使用的是8192 / 64大小的unsigned long数组，这是由于unsigned long本身是64位的，每一个二进制位都可以表示是否被分配，所以数组的大小可以省下来。
来看下创建entity的具体逻辑，看上去比较复杂：
internal void AllocateEntities(Entity* entities, int totalCount, ChunkIndex chunkIndex, int firstEntityInChunkIndex)
{var entityInChunkIndex = firstEntityInChunkIndex;for (int i = 0; i < k_BlockCount; i++){var blockCount = Interlocked.Add(ref m_EntityCount[i], 0);if (blockCount == k_BlockBusy || blockCount == k_EntitiesInBlock){continue;}var blockAvailable = k_EntitiesInBlock - blockCount;var count = math.min(blockAvailable, totalCount);// Set the count to a flag indicating that this block is busy (-1)var before = Interlocked.CompareExchange(ref m_EntityCount[i], k_BlockBusy, blockCount);if (before != blockCount){// Another thread is messing around with this block, it's either busy or was changed// between the time we read the count and now. In both cases, let's keep looking.continue;}DataBlock* block = (DataBlock*)m_DataBlocks[i];// Be careful that the block might exist even if the count is zero, checking the pointer// for null is the only valid way to tell if the block exists or not.if (block == null){block = (DataBlock*)Memory.Unmanaged.Allocate(k_BlockSize, 8, Allocator.Persistent);UnsafeUtility.MemClear(block, k_BlockSize);m_DataBlocks[i] = (ulong)block;}int remainingCount = math.min(blockAvailable, count);var allocated = block->allocated;var versions = block->versions;var entityInChunk = block->entityInChunk;var baseEntityIndex = i * k_EntitiesInBlock;while (remainingCount > 0){for (int maskIndex = 0; maskIndex < k_EntitiesInBlock / 64; maskIndex++){if (allocated[maskIndex] != ~0UL){// There is some space in this onefor (int entity = 0; entity < 64; entity++){var indexInBlock = maskIndex * 64 + entity;var mask = 1UL << (indexInBlock % 64);if ((allocated[maskIndex] & mask) == 0){allocated[maskIndex] |= mask;*entities = new Entity{Index = baseEntityIndex + indexInBlock,Version = versions[indexInBlock] += 1};if (chunkIndex != ChunkIndex.Null){((EntityInChunk*)entityInChunk)[indexInBlock] = new EntityInChunk{Chunk = chunkIndex,IndexInChunk = entityInChunkIndex,};}else{entityInChunk[indexInBlock] = 0;}entities++;entityInChunkIndex++;remainingCount--;if (remainingCount == 0){break;}}}if (remainingCount == 0){break;}}}}Assert.AreEqual(0, remainingCount);var resultCheck = Interlocked.CompareExchange(ref m_EntityCount[i], blockCount + count, k_BlockBusy);Assert.AreEqual(resultCheck, k_BlockBusy);totalCount -= count;if (totalCount == 0){return;}}throw new InvalidOperationException("Could not find a data block for entity allocation.");
}
虽然有一定代码量，但是要做的事情其实是很直观的。具体来说可以分为以下几个步骤：
- 找到第一个可用的data block，如果某个block分配已满（entity数量为8K），或者被其他线程所占用（entity数量被置为busy），则说明不可用；
- 对可用的data block尝试加锁（即将其entity数量置为busy），如果加锁失败，说明被其他线程抢先一步占用，直接放弃尝试下一个data block；
- 加锁成功，查看data block当前的分配状态，如果分配状态为空，创建一个新的内存块并指向它；
- 在分配状态中寻找空闲的二进制位，根据它的位置计算出entity的Index，也就是指向block的二级索引，同时entity的Version自增，表示新建；
- 把entity在chunk中的实际位置信息（位于哪个chunk，以及在chunk中的位置）记录到block中；
- 释放之前加的锁，恢复data block的entity数量为正确的值。
当有了一个entity之后，又如何判断它是否还真实存在呢？这时候Version就派上用场了，data block里存着的永远是最新的Version，直接对比一下就好：
internal bool Exists(Entity entity)
{var blockIndex = entity.Index / k_EntitiesInBlock;var indexInBlock = entity.Index % k_EntitiesInBlock;var block = (DataBlock*)m_DataBlocks[blockIndex];if (block == null) return false;if (((uint)entity.Version & 1) == 0 || block->versions[indexInBlock] != entity.Version) return false;return true;
}
销毁entity的逻辑也是类似的，只不过销毁只处理data block分配状态的二进制位，将其置回为0，Version字段继续自增，表示已销毁。另外，就算block的分配状态为全空，也不会将block的内存回收掉。
for (int j = startIndex, indexInEntitiesArray = rangeStart; j < endIndex; j++, indexInEntitiesArray++)
{var indexInBlock = j % k_EntitiesInBlock;if (versions[indexInBlock] == entities[indexInEntitiesArray].Version){// Matching versions confirm that we are deallocating the intended entityvar mask = 1UL << (indexInBlock % 64);versions[indexInBlock]++;allocated[indexInBlock / 64] &= ~0UL ^ mask;#if !DOTS_DISABLE_DEBUG_NAMESblock->nameByEntityIndex[indexInBlock] = default;
#endifblockCount--;}
}// Do not deallocate the block even if it's empty. Versions should be preserved.{var resultCheck = Interlocked.CompareExchange(ref m_EntityCount[blockIndex], blockCount, k_BlockBusy);Assert.AreEqual(resultCheck, k_BlockBusy);
}
最后我们来看一下chunk的创建与销毁。当出现无处安放的entity时，就需要创建新的chunk。在前一篇文章中我们提到过，chunk不是单独分配的，而是按照64 * 16K大小进行分配的，这块内存成为mega chunk。Unity最多可以创建16384个mega chunk。 那么，Unity最多需要管理16384*64个chunk，为了提高效率，Unity使用了两个查找表，方便快速定位到空闲的chunk。
Ulong16384 m_chunkInUse;
Ulong256 m_megachunkIsFull;
m_megachunkIsFull把所有mega chunk分为256组，每组64个，那么每个mega chunk刚好可以用一个unsigned long表示；同样地，m_chunkInUse可表示16384个mega chunk，而每一个unsigned long，刚好可以表示每一个chunk的状态。
public int AllocateContiguousChunks(out ChunkIndex value, int requestedCount, out int actualCount)
{int gigachunkIndex = 0;for(; gigachunkIndex < m_megachunkIsFull.Length; ++gigachunkIndex)if(m_megachunkIsFull.ElementAt(gigachunkIndex) != ~0L)break;int firstMegachunk = gigachunkIndex << 6;actualCount = math.min(chunksPerMegachunk, requestedCount); // literally can't service requests for morevalue = ChunkIndex.Null;while(actualCount > 0){for(int offset = 0; offset < megachunksInUniverse; ++offset){int megachunkIndex = (firstMegachunk + offset) & (megachunksInUniverse-1); // index of current megachunklong maskAfterAllocation, oldMask, newMask, readMask = m_chunkInUse.ElementAt(megachunkIndex); // read the mask of which chunks are allocatedint chunkInMegachunk; // index of first chunk allocated in current megachunkdo {oldMask = readMask;if(oldMask == ~0L)goto NEXT_MEGACHUNK; // can't find any bits, try the next megachunkif(!ConcurrentMask.foundAtLeastThisManyConsecutiveZeroes(oldMask, actualCount, out chunkInMegachunk, out int _)) // find consecutive 0 bits to allocate intogoto NEXT_MEGACHUNK; // can't find enough bits, try the next megachunknewMask = maskAfterAllocation = oldMask | ConcurrentMask.MakeMask(chunkInMegachunk, actualCount); // mask in the freshly allocated bitsif(oldMask == 0L) // if we're the first to allocate from this megachunk,newMask = ~0L; // mark the whole megachunk as full (busy) until we're done allocating memoryreadMask = Interlocked.CompareExchange(ref m_chunkInUse.ElementAt(megachunkIndex), newMask, oldMask);} while(readMask != oldMask);int firstChunkIndex = (megachunkIndex << log2ChunksPerMegachunk) + chunkInMegachunk;if(oldMask == 0L) // if we are the first allocation in this chunk...{long allocated = (long)Memory.Unmanaged.Allocate(MegachunkSizeInBytes, CollectionHelper.CacheLineSize, Allocator.Persistent); // allocate memoryif (allocated == 0L) // if the allocation failed...return AllocationFailed(firstChunkIndex, actualCount);Interlocked.Exchange(ref m_megachunk.ElementAt(megachunkIndex), allocated); // store the pointer to the freshly allocated memoryInterlocked.Exchange(ref m_chunkInUse.ElementAt(megachunkIndex), maskAfterAllocation); // change the mask from ~0L to the true mask after our allocation (which may be ~0L)}if(maskAfterAllocation == ~0L)ConcurrentMask.AtomicOr(ref m_megachunkIsFull.ElementAt(megachunkIndex>>6), 1L << (megachunkIndex & 63));value = new ChunkIndex(firstChunkIndex);return kErrorNone;NEXT_MEGACHUNK:;}actualCount >>= 1;}return kErrorNoChunksAvailable;
}
这里分配chunk的代码也是比较直观的，从流程上可以分为以下步骤：
- 首先通过
m_megachunkIsFull，找到空闲的mega chunk组gigachunkIndex； - 通过
gigachunkIndex，得到第一个空闲的mega chunk的index，再查找m_chunkInUse，得到此时该mega chunk中64个chunk的空闲情况； - 如果chunk都已分配完毕，或者此时正被其他线程所占用，那么放弃该mega chunk，尝试下一个可用的mega chunk；
- 如果找到空闲的chunk，那么尝试加锁，如果加锁失败则一直等待，除非发生上一步的情况，才会放弃该mega chunk；
- 加锁成功，如果整个mega chunk都是空闲的，说明这个mega chunk压根还没实际分配内存，需要分配完内存后保存地址指针；
- 如果mega chunk不再有空闲的chunk，则需要记录回
m_megachunkIsFull中； - 返回可用的chunk。
销毁chunk的逻辑也是类似的，当chunk中entity数量为0时就会触发。由于chunk是以mega chunk为单位进行分配的，所以只有当整个mega chunk都是空闲时，才会真正地释放整个mega chunk的内存。
Reference
[1] Entity concepts
[2] Unity DOTS中的Archetype与Chunk
[3] Interlocked.CompareExchange Method