说不定是因为在家太无聊才简单摸了一个虚幻引擎里的 ...

路过的土

放心吧，有橘子神保佑着我呢。
——平泽唯

序

之前写的Vulkan渲染器里用了大量的std::string来匹配，用的很爽，搞个map按名访问就很舒服。但实际上每次访问时都会遍历字符串，其实没太大必要，如果可以像C#里一样，相同字符串指向同一个地址，每次比较地址就可以知道是否相同，就可以节约一点计算量了。
C++标准库里是没有这种东西的，所以虚幻引擎就搞了一个FName的类，内部只存储一个映射计算得到的键，将实际的字符串映射存储在一些内存块中，加速字符串之间的比较。我也说不太清楚，粘一段虚幻的介绍算了：

在 内容浏览器 中为新资源命名时，变更动态材质实例中的参数或访问骨骼网格体中的一块骨骼时需要使用 FNames。 FName 通过一个轻型系统使用字符串。在此系统中，特定字符串即使会被重复使用，在数据表中也只存储一次。FNames 不区分大小写。它们为不可变，无法被操作。FNames 的存储系统和静态特性决定了通过键进行 FNames 的查找和访问速度较快。 FName 子系统的另一个功能是使用散列表为 FName 转换提供快速字符串。FNames 不区分大小写，作为索引组合存储在唯一字符串和实例编号的表格中。

这几天把虚幻5的源代码又拉了回来，简单研究了一下FName，简化了一些功能，写了一个自己的InternedString类，和std::string对比了一下性能，只能说小有提升，查表大概能快3~4倍的样子，哈希表能到6~7倍，虚幻的应该会更快：


库在这里，用了xmake构建，有些地方写的还优待改进，也说不定有隐藏的bug：
FName简单分析

其实我之前在知乎上看过一两篇介绍FName原理的，但实际上只是模模糊糊知道好像是个什么样子，具体实现上还是很懵逼，所以才拉了虚幻的源码，版本是5.1.0release，看完后感觉和之前看的文章不是特别一致，所以这里简单梳理一下FName的工作原理。
看的文章是这两篇：
主要的文件是Source\Runtime\Core\Private\UObject\UnrealNames.cpp和Source\Runtime\Core\Public\UObject\NameTypes.h，首先把NameTypes.h里的WITH_CASE_PRESERVING_NAME宏定义改成0，去除编辑器模式下的数据，这里只关心实际运行中的情况。



去除WITH_CASE_PRESERVING_NAME

初始化




FNamePool的内部结构

FNamePool在初始化的时候会先初始化一个FNameEntryAllocator，作为FName的内存管理器。其有8192个内存块的指针，通过CurrentBlock确定当前使用的内存块，通过CurrentByteCursor确定当前内存块内部的已使用的量。实际使用时会不断地向堆申请内存块，在块内分配出实际字符串存储的空间，8192个都爆了的话就结束。初始时就先申请一个内存块，把CurrentBlock和CurrentByteCursor设置为0就可以了。



CurrentBlock和CurrentByteCursor设置为0



申请0号内存块

接着在初始化FNamePoolShared[256]，作为映射查找以存储字符串的记录表。其有256个FNamePoolShared，每个FNamePoolShared中有一个slot数组头指针，指向一块堆内存，记录已分配的字符串的散列信息和映射至FNameEntryAllocator中内存块位置的信息。使用时FNamePoolShared可以无限增长，基本上FNameEntryAllocator会先爆。初始时对每个FNamePoolShared申请一块256slot长度的内存块。



初始化每个FNamePoolShared



申请一块256slot长度的内存块

映射过程

首先，将数字部分分离。其中需要注意的是数字部分最多10位，且最后都+1返回，用0代表纯字符串，没有数字，还有就是要对0079这种数字做特殊处理。


接着，将分离剩下的字符串使用CityHash，并填充FNameHash以便之后使用。这里，32~39位用来确定这个字符串处于256个FNamePoolShared中的哪一个，8位刚好够；0~31位用来确定这个字符串映射到这个FNamePoolShared中的哪一个Slot，冲突了就用线性再探测；61~63位用来作为字符串和Slot绑定的标志位，可以加快比较过程；40~44位用来作为这个字符串的标志位，在Slot绑定的标志位相同的情况下并不能说明已存储的字符串和待存储的字符串是相同的，在比较这个字符串标志位，如果不同就不用了使用strcmp检查两个字符串是否相同了，减少一点计算用的。


有了hash数据后，就可以确定用哪一个FNamePoolShared了，对这个FNamePoolShared做插入操作：



FNameComparisonValue里面有FNameHash和string view

然后就需要在这个FNamePoolShared里找到能用的一个FNameSlot：



线性再探测，优先找未用的，否则先比较Slot标志位



再检查字符串头，包括长度和字符串标志位



最后strcmp检查字符串是否相同

简单观察可知，在探测时是直接将前面得到的hash数据的0~31位对当前FNamePoolShared的容量做一个映射，不断线性再探测，优先找未被使用的Slot，否则就先检查Slot标志位、再检查字符串标志位与字符串长度，最后完全比较两个字符串是否相同，通过3级比较，避免直接比较字符串，减少比较的计算量。
找到Slot后，可以进行下一步了，如果是已使用的Slot，那说明Slot映射的字符串和待存的字符串是一样的，那么直接返回这个Slot中的数据就好了，如果是空的，就说明这个字符串是一个新串，需要保存在映射表和内存块中：



一样的就返回，空的就继续存

首先要把字符串头和字符串合并起来存在内存块中：



存字符串头并拷贝字符串

至于怎样从内存块分配的，就是用上面提到的CurrentBlock与CurrentByteCursor得到当前内存指针，先检查这个内存块还够不够分，够分就增加CurrentByteCursor表示分出去一块内存，否则就先申请一个内存块再分配，注意这里是2字节对齐的：


申请新块很简单，跳进去就是UE自己的Malloc，申请完修改当前块索引并重置当前游标就好了


接着就用存储在内存块后获得的句柄把映射信息存储在Slot中，这里还会检查一下Slot的使用率，超过90%就扩容一倍：



映射信息已经被写入NewValue中了



扩容一倍

申请一块新内存，然后把旧的Slot数据倒腾过去：


扩容后显然需要重新映射一遍，因为容量变了，映射的Slot位置也会变化。这个重映射还是比较简单的，就是先通过旧Slot或得到原始的字符串，然后重新计算Hash信息，再在锌块中通过HAsh信息进行映射，这里因为旧Slot数组中本来每个都是独一无二的，所以这里就只需要听过线性再探测找未使用的Slot就可以了，最后把就Slot内的映射数据直接复制过去就好了，因为字符串头和字符串在内存块上并没有动，只是Slot变了。


这样就完成了字符串在内存块上的存储和映射信息在Slot上的存储了：



先存字符串头与字符串，再存映射信息

最后根据返回的映射信息和之前分离出的数字构造一个FName就好了，完成新字符串的存储。


大概的流程图是这样的：


可以说还是很清晰的，至少在干嘛是清楚了的。而至于如何通过FName访问到字符串，显然Number部分可以直接拼在字符串后面，字符串的获取是通过内部的一个成员变量通过FNameEntryAllocator访问的。具体内容后面再说。


映射细节




用到的数据结构

可以看到，其中用到的这些数据结构名字有点像，而且存的位数也都很少，且可以相互转换，看起来令人头大，这里具体分析一下。
首先是通过字符串获得Hash数据这部分：


这部分前面写的很清楚了，这里的FNameEntryHeader一共就16位，是可以打包在一个uint16_t中的，因为支持的最长的字符串长度为1024（其实是1023，因为10位最大只能表示0~1023），所以10位就够了。
关于探测Slot的步骤中，在探测时会一次比较下图中的三个量，很显然FNameSlot是知道在比较的是哪一个的，因为本身就在一个SlotPool中进行探测，根据UnmaskedSlotIndex依次探测就好了。


但是如何通过一个已使用的FNameSlot找到对应的那个FNameEntry就是另一个问题了。首先FNameSlot和FNameEntryId是可以相互转换的，因为FNameSlot内的IdAndHash的低29位就是FNameEntryId中Value的低29位。


而其实FNameEntryId中Value的低29位就是FNameEntryHandle中的Block和Offset打包得到的：



FNameEntryId转FNameEntryHandle

虽然FNameEntryHandle的Block和Offset是两个uint32_t，但是由于FNameEntryAllocator中的块最多只有8192个，这需要13位，而一个块的偏移量可以是0~65535，且是2字节对齐的，一共需要17位，但已经2字节对齐了，所以需要16位就好了，这两个加起来刚刚好29位。



8192个块



块的偏移量是0~65535（2字节对齐）



2字节对齐

既然已经有了FNameEntryHandle的Block和Offset，那么直接从FNameEntryAllocator中找到对应的块，根据偏移量访问就好了，之后该存储就存储：



2字节对齐强转



通过Slot访问字符串

而FName中也存储了一份FNameEntryId，所以就可以在FNameEntryAllocator的帮助下通过FNameEntryId得到FNameEntry进而得到字符串长度和字符串起始地址了，这样FName的ToString就没有问题了。



FName中的成员变量



FName访问字符串

这样整个的映射细节就非常的清楚了，挺nb的。
其他

在FNamePool的初始化过程中有一个非常有意思的东西，我还是第一次见到还可以这样的，还是我们C++厉害啊：





UnrealNames.inl

（这里将None第一个存，保证了它内存块索引和偏移都是0，也就是说FNameEntryID为0，且没有数字后缀所以Number也是0，就可以通过判断FName中的两个成员变量是否都为0来判断这个字符串是否为空，也是很巧妙的。）
可以看到，这里它使用宏定义和include在初始化中预先存入了一些值，并且在之后讲这些加到的值存在了一个Map中：


而EName似乎也是用到了UnrealNames.inl来初始化一个枚举类型：


这样就可以通过EName来直接创建一些FName，并且几乎无消耗，因为直接查初始化时的EName的表就可以了，完全不用再去算Hash之类的东西了：


还有就是在FNamePoolShared扩容时做重映射的时候，用SSE指令集直接将需要操作的数据的内存直接加载一些到Cache中，反正留下的注释里说可以提高几倍的性能。




InternedString

变化

由于是自己用的，所以能简单就简单一点：首先去掉数字部分，因为我感觉没啥用；然后去掉SSE指令集的部分，因为加起来很麻烦，前段时间写CUDA真实麻了；初始化预存储与EName也暂时去掉，之后感觉有用到的时候再加上吧，因为感觉好像也不是很困难的样子；数据结构也需要精简一点，太多看起来很混乱；宽字符串的支持也要去掉，因为我没用过哈哈哈哈。反正这么一减，就只剩下最主要的映射部分了，这部分才是最核心的东西。
大致的流程是几乎一样的，因为去掉宽字符串的支持，所以FNameEntry中的bIsWide位可以完全去掉，这样字符串标志位就可以变为6位了。


其他部分非常类似：



寻找空或对应Slot



找到Slot就返回，否则从内存块中申请一部分存储并写入空Slot中

不过我把检查单个SlotPool使用率放在找Slot前面了，其实差别不大。SlotPool的Resize和从内存块申请一部分也都和FName很类似，毕竟是学习了之后才写的：



SlotPool的Resize



从内存块申请一部分内存

除此之外，还特化了一个std::hash，这样就可以直接使用std::unordered_map了，反正直接返回内部存储的StringEntryHandle打包的32位变量就好了，必然是独一无二的：


数据结构的部分，我讲一部分成员变量命名修改了一下，更清楚了一点，并且也去掉了StringEntryId，直接用StringEntryHandle来表示：






因为没有预加载字符串，所以也就不能用前面说到的None判断是否使用的魔法了。因为stringEntryHandle只用29位就好了，所以uint32_t还剩下3位，用一位做个标记就好了。



使用标记



判空

使用

用起来到也还行，写了一部分常用的：


但至于为什么测试起来在创建字符串时std::string也会慢，可能是字符串拷贝的原因，不过InternedString内部又是加锁又是算hash的，也有可能是分配堆内存次数比较少的原因。拷贝必然是快的，毕竟只用拷贝4个字节。


由于使用哈希表的时候不用在计算字符串的hash值了，所以肯定会快点，不过普通map快的倒不是特别多。
:||

看文章、查源码、写代码、写文章大概用了一周的时间，我感觉已经算快的了。上周还尝试了Xmake，感觉还算能用，反正Cmake我是拒绝的。放假在家其实也挺无聊的，打会游戏就不想打了，原神也不想玩，不过倒是在B站上看了白色相簿2cc的小春线和麻里线的录播，感觉挺好的，不过总感觉春哥有点渣，一直不喝雪菜分手，也是挺迷的，麻里大姐姐真好啊，不过我是冬马党。



吐了



呜呼

明天大概会再整理一下代码，写写readme就好了，我下周一定开始刷题。。。

阳光下的幸福

好棒