1BRC 挑战 - 第二阶段
1BRC 挑战 - 第二阶段
嗒哒～ 看“答案”的环节来啦～～
我干的第一件事情就是先把最快的方案在本地跑了几遍，咱就想直观的感受一下差距。
1brc 排名第一的方案在我关掉大部分后台程序的情况下上最快一次大概 14 s，大部分时候也得 20+ s，而我的方案也能跑 20+ s，从结果看差距貌似不大。默默的想起了思旺的台词：“铁皮壳儿再好，里面的驾驶员不行也没辙啊”。你看，只要铁皮壳够差，里面的驾驶员行不行就看不太出来了:)
what amazing things they do ?
不得不说，在浏览了 1brc 中部分解决方案的代码、BLOG 以及各种资料之后，真的惊了，虽然好多人前期的解题思路都跟我的差不多，但是到了后期就开始变态了。
这里我把排名靠前的解决方案统称为“顶级方案”，后文虽然是以第一名的代码为例，但本身第一名的代码就是集众家之长。
下面的列表中我列出了这些顶级方案中比较共通的且很有意思的优化技巧，注意其中一部分优化技巧之间有交叉或者是重叠：
- mmap ｜ IO 部分
虽然在我机器上 mmap 方案的表现不佳(我才不承认是因为我用的方式有点蠢)，但 1brc 中收录的绝大部分方案都使用了该技术，只是在具体细节上略有差异，简单的可以分为 unsafe、MemorySegment、MappedByteBuffer 三种。
在我的所有方案中（Baseline 除外），IO 部分都比较“传统”，理论上缺点很明显：涉及内存拷贝（kernel space -> user space(JVM Heap)）；由于数据保存在 Heap 中，必然涉及 GC 等等。 而 mmap 方案的核心思路其实就把读文件转化为 Java 中如何直接访问 native memory，那自然就是上面所提到的三种方式。
unsafe基于其优秀的寻址模型可以提供高效的性能优势，虽然 unsafe api 从来都是不推荐使用，但是很多特殊场景 Java 开发人员还是喜欢用它，也就是 1BRC 禁了 JNI，不然解决方案可能会更加魔幻。
MemorySegment 和 MappedByteBuffer 差不多，不熟悉的小伙伴可以简单的理解为 MemorySegment 就是使用 long 作为索引的 MappedByteBuffer，并且比 MappedByteBuffer 更好用。 它解决了 MappedByteBuffer 中的很多痛点，比如 MappedByteBuffer 最常遇到的两个问题：使用 int 作为索引导致映射大小不能超过 int.max，差不多 2GB 多点，以及 MappedByteBuffer 的释放非常麻烦。未来完全可以使用 MemorySegment 来替代 MappedByteBuffer，关于 MemorySegment 的细节见JEP 454: Foreign Function & Memory API。
- 使用自定义的 HashMap ｜ HashMap
几乎都是最简单的实现，数组+链表或者基于数组的开放寻址现实。 在简单浏览了其中一部分方案的代码后我发现，虽然最初大家的目的都是为了消除创建 String，但是背后的原因，或者说改进时的思考方式差异极大。
顶级方案大多直接用 name 在文件中的位置（地址）作为 HashMap 的 key，这个方案不仅仅是避免了创建 String，它没有为生成 key 这个步骤在堆中分配任何额外内存。
我的方案就差多了，顶级方案中 HashMap 的 Key 存的是地名的地址，我存的是 byte[]；后续处理中我依然要创建数组用于 hash/equals；我只是减少了 GC 次数，顶级方案压根就没有在堆中额外分配内存，因此完全避免了这部分的 GC，后面我的模仿版本CopySolution中可以看到，整个方案运行完毕后 GC 次数仅为1次。
- 数据处理 ｜ SWAR - SIMD Within A Register | 地名查找 | 分号搜索 | 温度查找和解析
文件仅做映射，使用 unsafe 根据地址访问文件内容。
对文件进行逻辑分块，处理数据块时，将数据块分为三个部分，在同一线程中同时处理着三个部分并将结果累计。
魔法代码重灾区，大量运用了位运算，比如温度解析时直接用位运算取代了分支指令，从而节省了 CPU 在分支预测上的消耗，要知道分支预测错误的平均代价是 1～10 ns 级别（详见下方 Latency Numbers Table），这个阶段时这帮大神都在盯着 cpu cycles 和 branch-misses 琢磨怎么动手了。
这部分属于魔法重灾区，各种位运算。
btw，perf 干这事儿是真的非常方便，MacOS 上用个 dtrace 还得先绕过 SIP（system integrity protection）。
- 根据数据特点提高 CPU 预测的准确率 ｜ 更快的 equals
因为用了 unsafe，判断 name 相等时也是直接根据地址取出原始数据进行比较，因此 equals方法直接化简为了两个 long 值是否相等，并且根据 name 长度的分布对判断条件进行优化，从而大幅提升 CPU 分支预测的准确率。
- 更小的数据块 ｜ 保证线程充分利用
1brc 中有一部分分块方案使用的是：线程数量=核心数，并按照 fileSize/threadNum 进行分块，另一部分则是跟我的方案类似。
顶级方案多数采用了 2MB 的逻辑数据块，看似相似但背后的原因依然不同，我是在几乎没有考虑任何细节的情况下根据 jmh 的测试结果简单的试出了一个可接受的方案，而且我的方案是物理分块，数据块要载入到堆中；而他们是在观察到分大块的话，某些线程会“更快”完成任务，因此计算末期 cpu 利用率不足，所以他们把文件从逻辑上切分成更小的块，从而提高线程利用率，并且他们选择的数据块的大小都是 2mb，原因似乎是目标机器的 pagesize 就是 2MB。
- GraalVM
可以尝试一下 GraalVM，很多时候即使代码一行不改只是单纯的更换一下 JVM 就可以获得性能提升。
不过顶级方案切换到 GraalVM 是为了直接把代码编译为可执行文件消除 JVM 启动时间、利用 GraalVM 编译时提供的自动优化等等。
- 丧心病狂级别的优化：消除 JVM 的 start up + clean up 阶段。
在 1brc 的末期，“thomaswue” 这位参赛者（如果没记错的话）发现即使程序已经完成打印，依然还有约 100ms 的时间用于取消 mmap 的文件映射，而这部分耗时也是算在比赛计时中的，因此他专门开了个进程来 clean up，以便主线程打印完结果后立即结束。 为了让这个“技巧”生效，又提前将代码编译为二进制文件以便消除 JVM 的启动时间。
CopySolution
该代码已更新至 My solutions - github。
CopySolution 就是几乎完全照抄了一遍CalculateAverage_thomaswue的方案，前面提到的很多优化手段这里几乎都有。
虽然有一堆魔法，但是单看逻辑还挺简单的。
主逻辑就是先映射文件，然后启动核心数个线程，并行执行 parseLoop() 并分别记录结果，最后整合每个线程的结果排序并打印。
再来看 parseLoop() （三部分版本逻辑一样），数据依然存储在 HashMap 中，只不过这个 HashMap 基于数组+开放寻址实现（在我机器上甚至没有哈希冲突），它的 Key 是地名在内存中的地址，Value 就是 min、max、sum、count 这些。
数据块均为逻辑分块，大小是固定的，nextLine() 可以找到文件中每行行尾的位置，因此也不需要考虑数据碎片的问题。findXXX() 方法可以找到 ";"、温度数字，地名是最简单的，行尾+1就是每行开头的地址，也就是地名的起始地址，用分号的地址减去地名的起始地址就能得到地名的长度。
最后数据的积累啥的都是一样的，排序也是利用 TreeMap。
我的模仿版与原版还是有一丢丢区别：
- 提供了两个版本的
parseLoop
一个是数据块内部不再切分的 ``parseLoop`` ，另一个是数据块内部再分成三个部分然后同时处理 ``parseLoop_3_parts``。
- 替换了少见的标签写法
我都忘记 Java 还有标签这个特性了。
由于并不是直接复制粘贴，而是跟着对方的思路照着实现了一遍，所以命名之类的变化比较大，虽然原版的注释大部分都带过来了，如果看我的版本费劲可以去看原版。
运行方式
类似 1brc 的方式，我提供了一些脚本。
- 可执行文件版 ｜ GraalVM 版
先 build 项目，然后执行 ``sh prepare_copysolution_4_graalVM.sh `` 生成可执行文件，完成后执行 ``sh run-CopySolution-exec.sh`` 即可。
当前 shell 会切换到 java version 21.0.2-graal。
- 常规方式运行
``sh run-CopySolution-JVM.sh``
当前 shell 会切换到 java version 21.0.3-oracle。
结语
经过反复思考和修改后，本篇内容比原计划少了很多，因为我觉得这个阶段最大的乐趣和收获并不是有个人详详细细的告诉你“完美答案”是什么，而是当你遇到瓶颈和盲区后，通过自己的努力更进了一步。这一定是来自于挑战者本身的尝试和努力，用失败、用智慧、用你能想到各种方式尝试过之后才能收获到的东西。这种“收获”不是我可以提供的，但通往“收获”的起点可以，于是我就只提供了一种简单且原始的学习方式，模仿。
CopySolution 就是我照着源码的逻辑一步一步模仿出来的，能看懂的部分就自行实现，并不能看懂的部分就照着敲。从创建文件到终于输出了正确的结果之间我犯了很多错误，其中不乏特别低级的错误，代码的运行结果也是五花八门：unsafe 异常、CPU 拉满的死循环、线程空转的死循环、中断程序后依然有线程不肯退出、输出结果乱码、输出数据混乱、输出数据只有平均值错误、profiler 不能正常监控程序等等。
这个过程花了我不少时间，虽然其中一部分原因是我个人习惯靠阅读代码本身去发现问题而不是借助工具快速定位（old habit die hard），但是当程序输出结果正确时我几乎完全掌握了这段代码一切，我对它的熟悉程度就像我自己写的一样。之后无论是想做一些测试还是要验证一些想法，或者想更改其中某个部分都变得非常容易。
这个办法虽然笨了点，但如果你没有思路的话，它可以一步一步的引导你发现问题、解决问题，是个很有效的办法。
至此 1BRC 的旅程就告一段落啦，这个过程中真的是充满了乐趣和惊喜，至少从我第一次看到这个挑战起，我从来没想过读取一个 13GB 文件的问题最终会演变成就像操作一个在内存中的 13GB 数组的问题。
在这个挑战中，编码技巧、解决问题的思路、测试的思路、优化的思路...每个部分都很有意思，尤其是随着事情的发展，瓶颈不断的在改变，思考问题方式和角度也随之变化，我个人非常享受这种“适应&进化”的感觉，就跟玩游戏一样。
特别是在第二阶段，各路大神在 low level 层面的优化让我大开眼界，比特位魔法也是眼花缭乱，不仅仅学到了很多新的知识，还打开了好多新思路。
总的来说，虽意犹未尽，但完结撒花，thanks for reading。
可能未来某天机缘巧合了说不定还会更新个番外篇什么的
Latency Numbers Table (2020s)
时间单位
1 ns (nanosecond) = 1 *
1 μs (microsecond) = 1 *
1 ms (milisecond) = 1 *
表格
Time Scope Desc 1 ns 访问 CPU 寄存器(L1 Cache 上面那层)，CPU 时钟(CPU clock cycle) 1~10 ns 访问 L1、L2 Cache，某些昂贵的 CPU 操作，比如前文提到的分支预测，每次预测错误大概会浪费几十个 CPU 时钟 10~100 ns L3 Cache 100~1000ns System Call 也就是我们常说的“系统调用”，或者说用户/内核空间切换带来的消耗（调用本身的时间不算在内） 1~10 μs Linux 下多个线程之间的空间切换（不考虑从内存中读取 Page 等情况），64 KB 内存的拷贝也在这个区间 10~100 μs 这个级别开始涉及到高级操作：nginx 处理一个典型的 http 请求大概在 50 μs，从内存顺序读取 1MB 数据差不多也是 50 μs，SSD 读取一个 Page (4k/8k) 基本也在这个范围 100~1000 μs SSD 写延迟大概比读延迟慢10倍，所以 SSD 写一个 Page 差不多就在这个范围; 云服务中内网访问一个来回(Intra-zone network round trip) ；客户端发送一次 redis Get 请求并收到结果的时间接近 1000 μs 1~10 ms 云服务的跨区域访问（also round trip）；机械硬盘寻址/寻道，也就是移动机械臂的时间大概 5ms；好多游戏项目的职业选手对网络延迟的要求也在这个范围 😃 10~100 ms 国内包括附近东南亚、日韩等的平均网络延迟；欧美之间网络延迟；从内存读取 1GB 数据的耗时 100~1000 ms 国内访问美国、欧洲的网络延迟，这个是物理距离决定，欧洲现在比以前快了几百ms，忘记是哪年了电信还是谁跟俄罗斯合作搞了亚欧之间的直达专线，以前要先绕道美国再去到欧洲，特别慢还特别不稳定；一些慢加密算法的运行时长，避免被暴力破解；TLS handshake ；SSD 顺序读 1GB 数据 1 s 云服务跨区域传输 1GB 数据大概 10s，不过这是海外的数据 表格中的内容部分参考Latency Numbers Programmer Should Know: Crash Course System Design #1 - by ByteByteGo，有兴趣可以看一下这个视频，想要中文字幕的 B 站好像也有不知道是不是盗版的搬运。