得物一直重视用户体验，尤其是启动时长这一重要指标。在近期的启动时长跟进中，我们发现了在BuildingClosure 阶段的一个优化方式，成功的帮助我们降低了 1/5 的 BuildingClosure 阶段的启动耗时。Building Closure 并非工程的编译阶段（虽然它有一个building），Building Closure 是应用初次启动时会经历的阶段，因此它会影响应用的启动时长。
单就BuildingClosure阶段而言，我们观察到该阶段其中一个函数从 480ms 暴增到 1200ms 左右（PC 电脑端运行 dyld 调试统计耗时数据），我们通过优化，将耗时从1200ms降低到110ms。即使相比最开始的情况，也相当于从480ms降低到了110ms，由此可见Building Closure 优化是应用进行启动优化必不可少的一个重要手段。因此在这里我们也和各位读者进行分享，期望能够对各自项目有所帮助。
一、神秘的 BuildingClosure
启动优化的技术、实现方案业界有不少的文章可以参考学习，这里不再额外赘述。我们来探索下启动过程中非常神秘的 BuildingClosure。
BuildingClosure 是在 System Interface Initialization 阶段 dyld 生成的，并且我们也无法做任何的干预，另外相关的剖析文章相对较少，所以说 BuildingClosure 较为神秘，也是实至名归。
BuildingClosure 是由 dyld 在应用启动阶段执行的，所以想要了解 BuildingClosure 还是要从 dyld 开始了解。
1.1 dyld && BuildingClosure
Dyld 源码可以在 Apple GitHub 上查阅 https://github.com/apple-oss-distributions/dyld
相信大家都应该了解过，BuildingClosure 是在 iOS 13 引入进来的，对应的 dyld 为 dyld3，目的是为了减少启动环节符号查找、Rebase、Bind 的耗时。
核心技术逻辑是将重复的启动工作只做一次，在 App 首次启动、版本更新、手机重启之后的这次启动过程中，将相关信息缓存到 Library/Caches/com.app.dyld/xx.dyld 文件中，App 在下次启动时直接使用缓存好的信息，进而优化二次启动的速度。
在 iOS 15 Dyld4 中更是引入了 SwiftConformance，进一步解决了运行时 Swift 中的类型、协议检查的耗时。
![图片]()
以上优化，我们都无需做任何工作即可享受 dyld 带来的启动速度的优化，可以感受到 Apple 的开发人员也在关心启动速度并为之做了大量的工作。
1.2 BuildingClosure 非常耗时
我们通过 instrument 观测到 BuildingClosure 的耗时占据了启动耗时将近 1/3 的时间。
虽然说，BuildingClosure 只会在首次启动、版本更新、手机重启的第一次启动生成和耗时，但是对用户的体验影响是非常之大的。
![图片]()
1.3 BuildingClosure 文件解析
我们通过对 dyld 的编译和搭建模拟手机环境，成功模拟器了 dyld 加载可执行文件的过程，也就成功解析了 BuildingClosure 文件。BuildingClosure 文件数据格式如下（数据格式、注释仅供参考，并非全部的数据格式）：
![图片]()
BuildingClosure 文件内部结构（数据格式、注释仅供参考）
其中占用比较大的部分主要为 Loader-selectorReferencesFixupsSize SwiftTypeConformance objcSelector objcClass
二、离奇的启动耗时暴增事件
如上，我们已经对 BuildingClosure 有了基本的了解和对 dyld 的执行过程有了一定的了解。但是这份宁静在某一天突然被打破。
2.1 启动耗时暴增 200ms
在我们一个新版本开发过程中，例行对启动耗时进行跟踪测试，但是发现新版本启动耗时暴增 200ms，可以说是灾难级别的事情。
我们开始对最近的出包做了基本的耗时统计，方式为基于 instrument，统计出来启动各个阶段的耗时数据。经过对比，可以明显观测到，200ms 耗时的增加表现在 BuildingClosure 这个环节。
但是 BuildingClosure 耗时的增加既不是阶梯式增加，也不是线性增加，并且只在新版本有增加。在排除相关因素（动态库、工程配置、打包脚本、编译环境）之后，仍然没有定位明确的原因。
在以上定位工作之后，最终确定耗时确实在 dyld 的 BuildingClosure 阶段耗时，并且怀疑可能是某些代码触发了 Dyld 的隐藏彩蛋。所以我们开始了对 BuildingClosure 更深一步的研究。
2.2 BuildingClosure 耗时异常变化定位
通过使用 Instrument 对 System Interface Initialization 阶段进行堆栈分析，最终发现了耗时最高的函数：dyld4::PrebuiltObjC::generateHashTables(dyld4::RuntimeState&)
在对比了新老版本数据，耗时变化差异的函数也是此函数，我们简称为 generateHashTables。这样使得我们更加确定耗时为 dyld 过程中的 BuildingClosure 阶段。
![图片]()
使用 Instrument 分析 BuildingClosure 阶段耗时
三、启动优化新秘境
在发现 BuildingClosure 生成过程中耗时占比非常大，并且有异常时，起初并没有意识到有什么问题，因为这是 dyld 内的代码，并未感觉会有什么问题。但是一切都指向了该函数，于是开始撸起袖子看代码。
从代码中可以看到，此处是为了生成 BuildingClosure 中 objcSelector objcClass objcProtocol 这三个部分的 HashTable（可以参考上面的 【BuildingClosure 文件解析】部分）。
拿起 dyld 开始对耗时异常版本的可执行文件进行调试，通过对该函数和内部实现的代码逻辑阅读，以及增加耗时信息打印。最终确定，耗时的代码在 make_perfect 这个函数中，这个函数是对【输入的字符串列表】生成一个【完美 Hash 表】。
void PrebuiltObjC::generateHashTables(RuntimeState& state)
{
// Write out the class table
writeObjCDataStructHashTable(state, PrebuiltObjC::ObjCStructKind::classes, objcImages, classesHashTable, duplicateSharedCacheClassMap, classMap);
// Write out the protocol table
writeObjCDataStructHashTable(state, PrebuiltObjC::ObjCStructKind::protocols, objcImages, protocolsHashTable, duplicateSharedCacheClassMap, protocolMap);
// If we have closure selectors, we need to make a hash table for them.
if ( !closureSelectorStrings.empty() ) {
objc::PerfectHash phash;
objc::PerfectHash::make_perfect(closureSelectorStrings, phash);
size_t size = ObjCStringTable::size(phash);
selectorsHashTable.resize(size);
//printf("Selector table size: %lld\n", size);
selectorStringTable = (ObjCStringTable*)selectorsHashTable.begin();
selectorStringTable->write(phash, closureSelectorMap.array());
}
}
继续深入了解 make_perfect 这个函数的实现。
3.1 Perfect Hash
通过对研读代码逻辑和耗时分析，最终定位到耗时代码部分为PerfectHash.cpp 中 findhash 函数，这个函数也是 完美散列函数 的核心逻辑。
这里涉及到了一个概念PerfectHash，PerfectHash 的核心是完美散列函数，我们看下维基百科的解释：
https://zh.wikipedia.org/wiki/%E5%AE%8C%E7%BE%8E%E6%95%A3%E5%88%97
对集合S的完美散列函数是一个将S的每个元素映射到一系列无冲突的整数的哈希函数
简单来讲 完美散列函数 是【对输入的字符串列表】【为每个字符串生成一个唯一整数】。
for (si=1; ; ++si)
{
ub4 rslinit;
/* Try to find distinct (A,B) for all keys */
*salt = si * 0x9e3779b97f4a7c13LL; /* golden ratio (arbitrary value) */
initnorm(keys, *alen, blen, smax, *salt);
rslinit = inittab(tabb, keys, FALSE);
if (rslinit == 0)
{
/* didn't find distinct (a,b) */
if (++bad_initkey >= RETRY_INITKEY)
{
/* Try to put more bits in (A,B) to make distinct (A,B) more likely */
if (*alen < maxalen)
{
*alen *= 2;
}
else if (blen < smax)
{
blen *= 2;
tabb.resize(blen);
tabq.resize(blen+1);
}
bad_initkey = 0;
bad_perfect = 0;
}
continue; /* two keys have same (a,b) pair */
}
/* Given distinct (A,B) for all keys, build a perfect hash */
if (!perfect(tabb, tabh, tabq, smax, scramble, (ub4)keys.count()))
{
if (++bad_perfect >= RETRY_PERFECT)
{
if (blen < smax)
{
blen *= 2;
tabb.resize(blen);
tabq.resize(blen+1);
--si; /* we know this salt got distinct (A,B) */
}
else
{
return false;
}
bad_perfect = 0;
}
continue;
}
break;
}
此时通过对比新老版本的数据（使用 dyld 分别运行新老版本的可执行文件对比打印的日志），发现：
至此，我们距离成功已经非常接近了，于是进一步研读 dyld 源码和增加了更多打印信息代码，最终找到了相互冲突的函数字符串名称。
/*
* put keys in tabb according to key->b_k
* check if the initial hash might work
*/
static int inittab_ts(dyld3::OverflowSafeArray<bstuff>& tabb, dyld3::OverflowSafeArray<key>& keys, int complete, int si)
// bstuff *tabb; /* output, list of keys with b for (a,b) */
// ub4 blen; /* length of tabb */
// key *keys; /* list of keys already hashed */
// int complete; /* TRUE means to complete init despite collisions */
{
int nocollision = TRUE;
ub4 i;
memset((void *)tabb.begin(), 0, (size_t)(sizeof(bstuff)*tabb.maxCount()));
/* Two keys with the same (a,b) guarantees a collision */
for (i = 0; i < keys.count(); i++) {
key *mykey = &keys[i];
key *otherkey;
for (otherkey=tabb[mykey->b_k].list_b;
otherkey;
otherkey=otherkey->nextb_k)
{
if (mykey->a_k == otherkey->a_k)
{
// 打印冲突的字符串
std::cout << mykey->name_k << " and " << otherkey->name_k << " has the same ak " << otherkey->a_k << " si is " << si << std::endl;
nocollision = FALSE;
/* 屏蔽此处代码，有冲突的情况下，继续执行，便于打印所有的冲突
if (!complete)
return FALSE;
*/
}
}
++tabb[mykey->b_k].listlen_b;
mykey->nextb_k = tabb[mykey->b_k].list_b;
tabb[mykey->b_k].list_b = mykey;
}
/* no two keys have the same (a,b) pair */
return nocollision;
}
根据以上信息，我们已经了解到在Building Closure阶段中，可能存在字符串的 Hash 碰撞 引发循环次数大幅增加，进而引发了启动耗时暴增。
在经过 dyld 调试的耗时数据、构建出包后验证的数据验证后，通过避免 Hash 碰撞，我们完成了启动时长的优化。
3.2 向前一步
其实从打印的冲突函数名称来看，历史代码中已经存在了 Hash 碰撞 的现象。
猜想，如果我们解决了所有的字符串的 Hash 碰撞，岂不是不仅可以修复启动耗时异常上升的问题，还可以进一步降低启动耗时，提高启动速度？
于是我们对每个有碰撞的函数名称进行修改，经过出包验证，结果与我们猜测的一致，启动耗时有明显的下降。
![图片]()
数据为 PC 电脑端运行 dyld 生成 BuildingClosure 的耗时数据，非手机端数据
四、总结
我们探索了 BuildingClosure 的生成过程，发现在Building Closure阶段中，可能存在字符串的 Hash 碰撞 引发循环次数大幅增加，进而引发了启动耗时暴增，进而导致启动耗时的大幅增加。
我们也发现，Building Closure Hash碰撞相关的启动耗时，其实与项目配置、编译环境、打包脚本等均无任何关系，就只是存在了字符串的Hash 碰撞 ，才引发循环次数大幅增加，进而导致启动时长增加。
往期回顾
1.分布式数据一致性场景与方案处理分析｜得物技术
2.从对话到自主行动：AI应用如何从 Chat 进化为 Agent？开源项目源码深度揭秘｜得物技术
3.得物技术部算法项目管理实践分享
4.商家域稳定性建设之原理探索｜得物技术
5.得物 Android Crash 治理实践
文 / 道隐
关注得物技术，每周一、三更新技术干货
要是觉得文章对你有帮助的话，欢迎评论转发点赞～
未经得物技术许可严禁转载，否则依法追究法律责任。
