得物 iOS 启动优化之 Building Closure
得物一直重视用户体验，尤其是启动时长这一重要指标。在近期的启动时长跟进中，我们发现了在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 分别运行新老版本的可执行文件对比打印的日志），发现：
-
老版本循环了 31 次成功生成 HashTable
-
新版本循环了 92 次成功生成 HashTable
至此，我们距离成功已经非常接近了，于是进一步研读 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 碰撞 ，才引发循环次数大幅增加，进而导致启动时长增加。
往期回顾
2.从对话到自主行动：AI应用如何从 Chat 进化为 Agent？开源项目源码深度揭秘｜得物技术
文 / 道隐
关注得物技术，每周一、三更新技术干货
要是觉得文章对你有帮助的话，欢迎评论转发点赞～
未经得物技术许可严禁转载，否则依法追究法律责任。
