第107章 三十二个证人（1/2）
江临原来的计划是，是把这些长远问题全部封存，留待即將到来的废土时间去解决。
但是回到家里，夜深人静，整个人一空閒下来，就还是忍不住把陈启明给的压缩包拖进电脑的工作目录里。
icrokernel_rank_sort_basele.zip。
右键，解压。
文件夹在屏幕的树状图里一层层铺开，其內部结构的整洁程度，比江临原本想像的要乾净得多。
根目录下躺著三个子文件夹。
江临点开/basele
里面赫然是三套经典的微內核基础算法的基准实现：rank5（五元素求秩）、sort5（五元素完全排序）、3_of_8（八元素选前三）。
每一套算法，陈启明都严谨地给出了两份截然不同的代码。
一份是没有任何底层优化的纯c语言可读版本，用来锚定逻辑正確性。
另一份，则是陈启明团队经过多年打磨的手写极限优化版。
江临扫了一眼，后者的代码里充斥著晦涩的编译器內联提示，强制循环展开，以及少量依赖特定cpu令集的平台相关写法。
江临退出来，点开/verify。
里面是几十个详尽的验证脚本，涵盖了各种极端的边界测试用例。
最后是那个最让系统工程师头皮发麻的/bench（性能测试）文件夹。
里面只有一份原始的.csv格式的性能计数统计表。
这张表是在三台底层微架构完全不同的企业级伺服器上，经过漫长的马拉松式压测跑出来的。
江临將表格放大。
行末密密麻麻地標註著测试环境的绝对变量：cpu型號，微码更新版本號，l1/l2缓存的命中率，分支预测失败率，以及频率是否强制锁定。
频率强制锁定这一项让江临颇为讚许。
现代商用cpu都会狡猾地根据温度和负载，动態调整时钟频率。
在进行这种纳米秒级別的內核代码测试时，哪怕cpu的频率发生了一次轻微的抖动，都会导致测试出的时钟周期出现巨大的噪声，从而彻底掩盖掉代码优化带来的那一两纳秒的真实提升。
陈启明那帮人不仅清楚这一点，还暴力地在bios层面锁死了频率。
光这一张数据表就无声地证明了，陈启明这帮人，是真正懂行的老手。
他们已经把人类能够手动控制的变量，极致地推到了物理的极限。
这就有意思了。
江临决定先从看起来最最基础的sort5开始解剖。
题面很简单：给定五个隨机的整数，將它们按从小到大的顺序排列好。
任何一个学会写for循环和if语句的新手，都能在短暂的三分钟內，交出一段基於两层嵌套循环的冒泡排序或者插入排序代码。
当然，这仅仅只是能跑通的玩具。
陈启明这种长期和底层性能打交道的人，要的当然不是这种充满分支跳转，在现现代cpu流水线里到处添堵的低效正確。
而在去追求那个极致的快之前，江临的数学直觉告诉他，必须先解决一个哲学问题。
【怎么用严谨的数学逻辑，去证明一段晦涩的排序代码，对全宇宙所有可能出现的输入组合，都百分之百地正確】
最直观也是最笨的办法，是暴力地把这五个数的全部大小关係组合，挨个枚举一遍。
那么五个数到底有多少种不同的全排列
简单的组合数学。
5!
一百二十种。
这个数字小到机器一瞬间就能跑完並验证。
这让江临难免就想起了那块砖。
做江氏砖的时候，刻进他骨头里的数学动作，就是把一个庞大到趋於无穷的边界状態空间，精妙地压缩成机器能穷举人能覆核的有限状態形式。
一百二十確实不大。
可如果是频繁出现在高级资料库索引中的，排八个数，排十六个数呢
8!
四万种，机器依然能够轻鬆秒杀。
但是到了十六个数。
16!
二十万亿级別。
对普通程序来说，这已经不是多跑一会儿的问题，而是足以把最笨的全排列验证拖进泥潭。
如果ps框架建立在这种愚蠢的全排列穷举上，它將迅速死在起跑线上。
江临转了一下手中的原子笔，大脑的记忆宫殿开始高速检索。
很快，他放下了笔，在键盘上敲下了一行学术检索词。
zero-oneprcipleswork
（排序网络：零一原理）
他其实早在废土时间里，在啃噬那些浩如烟海的计算机科学巨著时，就已经做了相关的知识储备。
只是在这之前，它仅仅只是停留在离散数学课本里一条定理这样的程度上，並没有迫切的用武之地。
而现在，江临认为这条优美的定理可以成为ps-kernel的第一块地基。
在理论计算机科学中，零一原理可以高傲地宣称——
一个由比较—交换操作固定地构成的比较网络，它是一个绝对正確的排序网络，若且唯若，它能够极其正確地將所有仅仅由数字0和数字1构成的有限输入序列，完全排好序。
这条定理的杀伤力在於，它无情地斩断了无限与有限的边界。
不会要求你去检验全部的120种排列，也不要求你往这段排序代码里餵进任何一个带有具体数值的实际输入。
它只要求你检验那些由0和1拼凑出来的二进位序列。
对於sort5（五个位置），根据零一原理，可以看做每个独立的位置上，要么是绝对的0，要么是绝对的1（非0即1）。
於是，它的验证空间一下子就被不可思议地坍缩成了2?=32。
只要你写出的这段代码网络，能够正確无误地把这三十二个全由0和1构成的序列排成单调递增的形状
那么，神奇且绝对的是，这段比较网络，对任何来自同一全序类型的五个输入都正確。
原本的微小的120，被再次降维压成了32。
如果是十六个数，原本极其恐怖的二十万亿，也能压缩成六万五千个。
一个微处理器闭著眼睛都能跑完的数字。
更重要的是，这三十二个简陋的0-1序列，还不是软体工程里充满玄学的抽样测试，也绝对不是测试工程师绞尽脑汁想出来的边界测试用例。
它在数学意义上，是不留死角的完备检查。
只要顺利地跑通这三十二个简单的序列，这段代码底层的绝对正確性，就被焊死在了真理的铁板上。
这种利用抽象的数学定理斩杀无限状態空间的快感，简直太美妙。
江临立刻在ps-kernel根目录下新建了一个python脚本文件。
verify_sort5_zero_one.py
引入itertools.product，暴力地生成全部確定的三十二个0-1序列。
对每一个独立的序列，机械地跑一遍外部掛载的候选排序网络代码。
严格地检查输出序列是否满足单调不减。
三十二个严苛的证人，只要全部通过，程序就会返回绿色的【provenvalid】（证明有效）。
而只要有任何一个微小的序列无法通过，程序就会將那个反例直接吐出来，无情地枪毙这段代码。
三十二个全过，返回已证明。
任何一个不过，把那个反例吐出来。
江临敲下回车键，拿陈启明团队提供的那份原始的/basele/sort5_pure.c暴力地跑了一遍夹具。
绿色。
三十二个0-1证人，在严密的数学法庭上，没有一个翻供。
正確性的地基，有了。
接下来的是神仙打架的活：在所有正確的排序网络里，找出最好的那一个。
江临开始把他在铺砌几何中经过千锤百炼的ps搜索骨架，巧妙地往这个代码问题上套。
做砖时，状態是一块局部铺砌，动作是放下一块新砖，胜利条件是排除所有拓扑逃逸。
现在呢
状態是一段已经写下的比较器序列。
动作是往后追加一个比较器，比较两个位置，把小的甩前，大的甩后。
胜利条件，是这段序列让三十二个证人全部点头。
结构一模一样。
只是把几何换成了指令。
他写了一版搜索：从空网络出发，逐个追加比较器，每加一个就用零一原理剪枝，留下还有希望的分支，砍掉已经走死的。
搜索先跑长度八以內的全部候选。
ps没找到任何一个能让三十二个0-1证人全部点头的网络。
然后长度放到九。
第一组通过的网络出现了。
江临把结果和knuth里那行s=9对上。
这才意味著：五个元素排序，九个比较器不只是能做到，而是最低限度。
教科书上写了几十年的那个数字，被他这套从一块砖上长出来的框架，从头独立搜了出来。
本章未完，点击下一页继续阅读。