跳至主要內容

1BRC 挑战 - 第一阶段

lament-z大约 16 分钟

1BRC 挑战 - 第一阶段

最近闲的发慌，想起来年前 Java Weekly, Issue 525 中推送的 Java 的 10亿行数据挑战（1BRCopen in new window），简单的说就是给你一个名叫 measurements.txt 的文件，里面存储了 10 亿条(1 Billion Row)数据，每条数据的格式均为：地名;温度，比如 hamburg;12.0，然后你写一个应用来处理这 10 亿行数据，处理方式也很简单，就是计算每个地点的最低气温、最高气温、平均气温，需要按字母顺序打印。

挑战要求：

  1. 必须用 Java
  2. 必须是 SDKMan 提供的 JVM
  3. 不用外部依赖

准备工作

  • 本系列代码仓库

    My solutions - githubopen in new window

  • Java 21

    sdk install java 21.0.3-oracle

    或者换成你喜欢的任意版本，最多就是去修改 pom 文件。

  • clone 1BRC

    git clone https://github.com/gunnarmorling/1brc.git

    其中 dev.morling.onebrc.CreateMeasurements 用来创建 measurements.txt。

    dev.morling.onebrc.CalculateAverage 是 baseline。

  • build project

    ./mvnw clean verify

  • create measurements.txt

    ./create_measurements.sh 1000000000

    文件大小：13795377085 measurements.txt，约 13G。

    整个过程需要几分钟时间，我的机器大概花了9分钟左右，可怜的老 mac 已经变成铁板烧了，手都快烤熟了，风扇呼呼吹。

    可以使用 head/tail 命令查看数据格式，比如：tail -n 5 measurements.txt。

  • run baseline

    运行基线程序，并把返回结果直接重定向到 result 文件中，之后我们就可以通过 md5 来快速验证结果。

    ./calculate_average_baseline.sh > result 2>&1 &

  • 其他

    profiling 工具什么的，自行决定。

    我这里主要使用的是 idea 自带的 profiler (其实就是 async-profileropen in new window) 和 jmh。

    VisualVM 和 arthas 备用。

挑战开始

  • 自定义规则

    先做单线程方案，单线程方案无法更进一步后转化为多线程方案。在我彻底没有进一步优化思路之前不去看“答案”，毕竟主要目的是为了消磨时间，真的无聊爆了。

    整个过程会记录下来并发布，包括代码和看“答案”的学习记录。当然更新可能会慢一点，最近整理文档整理的想吐，写草稿可爽了，发出来可太闹心了。

基线方案：MyBaseline

先来最“土”的方案，从前面的准备工作中我们可以知道，目标文件都是一行一行的，而且每一行的格式均为 locationName;temperature，那么我们只要从文件中分别读取每一行，然后使用 ; 作为分隔符获取地点名称和温度。之后就对数据进行处理并存入 Map，打印 Map 即可得到结果。

lineStream -> OriginRowStream -> groupBy -> map -> print(map)

HOW HARD CAN IT BE ? （猩猩脸）

emmmmm，结果居然不对，仔细一对比发现忘记题目要求排序了。

对比一下 1brc 提供的 baseline (CalculateAverage_baseline)，几乎一模一样，区别在于它用了 record 类型，我用的是内部类。鉴于 OriginRow 确实属于用完即弃的不变数据，确实用 record 更合适，换！

  • JVM

    21.0.3-oracle

  • 运行时间：约 7 分半

    该换电脑了，好慢 =，=

  • 分析

    这里我们的优化目标是运行时间，所以火焰图就是不二选择，它可以非常直观的展示方法的运行时间。

    从火焰图里可以看到，IO (BufferedReader::readline) 占比约 33%，字符串切分 (String::split) 占比约 32%，生成温度时的 parseDouble 占比约 13%，groupBy 那部分占比约 17%。

    根据火焰图就可以轻松罗列出可优化的点：

    生成字符串流时使用的 Files::lines，它就是利用 BufferedReader::readline 从文件中读取行，而这方法的内部逻辑大致就是一次读一个 char，并缓存到内部的 buff （这里是个 char 数组）中，攒够一个 "line" 后返回。

    字符串切分。

    Double.parseDouble。

    Collectors.groupingBy 合并数据的过程，这个取决于前面的逻辑暂时不需要考虑。

    Baseline 方案肉眼可见的产生了海量垃圾（比如 Files::lines 就 new 了 10 亿个字符串，后面接着就是字符串分割），但是 GC 耗时占比其实并不高，一方面是流式处理的优势，垃圾虽多但产生速度不会太夸张，另一方面是 G1 或者说现代 GC 的强大性能。

方案1： SmallBlocksDemo

Files::lines 很慢原因主要是 BufferedReader::readline 比较慢，他内部的缓冲区用的是 char 数组，这就意味着读进来 byte 后 decoder 还要把它解码为 char，之后还要把 char 数组 new 成 String。

对于 1BRC 这个场景而言，这些其实都不需要，完全可以直接用 byte 数组作为缓冲区，以 ';' 和 '\n' 作为标记并直接对读进来的文件数据进行处理，不光避免了为每行数据生成一个字符串，还避免了字符串切分，处理后的数据可以直接存入 HashMap。

另外 BufferedReader::readline 是逐行读取文件中的数据，当文件较大时这种方式本身就比较慢，更何况 measurements.txt 文件大小有 13GB+，采用分块读取方式可以大幅提升效率，哪怕是单线程。

然后看 Double.parseDouble，温度数据的格式除了正负数之外，只有 ab.c 和 a.b 这两种格式，并且在打印结果之前都可以用 int 来存储，打印结果的时候再按要求处理即可。

综上所述，我们得到了方案1 SmallBlocksDemo。其基本思路就是把目标文件切分成 n 个数据块，通过自定义的 byte类型数组把数据块读进来并进行处理，将结果存入 Map，然后合并 Map 并排序，最后打印结果。

由于代码中我没有写详细注释，这里挑几个点简单说明一下：

  • 文件分块 | SmallBlocksDemo#divide

    这部分逻辑很简单，核心就是 blockSize = file.length() / blockNum，只不过存在一个“数据行会被截断”的问题。解决这个“截断”问题我能想到的就是两种思路，一种是我在 demo 中采用的非完全平均切分，说人话就是每个块的结尾一定是 '\n'，实现方式就是对每个 Block 的尾部的若干个 byte 进行遍历，找到 '\n' 并记录其位置作为 Block 真正的结尾，这样在处理 block 中的数据时就不需要再去考虑数据截断的问题了；另一种方式就是分块时不处理截断问题，将该问题向后推移到处理块时解决，比如将碎片部分单独拼接并积累到一个独立的 buffer 中最后处理等等。

  • 自定义的 byteBuffer ｜ BlockReader

    这个也很简单，就是个包装在类里的 byte 类型的数组，顺便添加了简单的功能方法作为 buffer 来使用，唯一需要注意的就是数组的初始化和数据载入都延迟到了首次使用时。

  • 数据块处理 ｜ parseMap

    就是遍历每个 block，找出 name 和 data，并存入 hashMap。 初始化大小为 1024 是因为一共只有 413 个不同的 name，虽然看着 512 就够了，但是 hashMap 有个 0.75 的扩容因子，依然会触发扩容(grow())，而从火焰图上看这个 grow() 耗时还不低，1024 可以直接避免。

    后续该方法名会进行变更，格式就是 parse{XX}，XX 代表处理后的行数据会存入什么数据结构。

    最后来看性能分析：

  • JVM

    same

  • time cost

    2m

  • profiling

    运行时间从 7m30s 降低到了 2m，GC 次数从 2100 多次降低到了 168 次，整个运行期间 heap 的占用整体较低，在 90m ~ 330m 之间，不算很平稳不过能接受。

    火焰图上看，processData 耗时占比约 31%，这个方法只是积累温度数据，之所以耗时这么多主要原因是 HashMap::get，processData 方法耗时中 95% 以上都在执行 get 方法。

    生成 name 时的创建字符串占比约 20%。

    HashMap::put 占比约 15%。

    BlockReader::hasRemaining 占比约 10% ，不过其中一半的耗时是 BlockReader 初始化逻辑。

    BlockReader::get 占比约 6%。

    parseDouble 仅占 约 2.5%，也就不到 3 秒，Baseline 中光这部分就差不多 1 分钟。

    现在耗时的大头就是 new String （20%） 和 HashMap 的操作（30%+15%）。

    接下来的优化思路就是，如何尽量避免创建字符串的操作，HashMap 的问题后面再说。

方案2： PrefixTreeDemo

前一个方案由于需要用地名作 key，10亿行数据那就是10亿次 new String，也就是10亿个待回收的对象，实际上地名只有 400 多个，为了避免这个环节我首先想到了 Trie 这个数据结构，这也是为什么方案1中不分析 HashMap，反正要换数据结构。

所谓 Trieopen in new window，就是字典树，也叫前缀树（PrefixTree）。 Trie 是该数据结构的发明者起的名字，具体可以点击链接查看 wiki。

简单说一下它的特点，前缀树特别适合存储单词，并且天然有序，跟其他常见树不同的一点是，它的值通常不存储在节点，而是存储于分支。

我这里用了最简单的实现方式部分实现了 Trie，也就是数组作为节点，数组下标作为分支（指针、路径）。好处是实现简单，缺点是空间浪费略多，不过一共就 400 + 地名我这里就不纠结那点空间浪费了。没有实现 insert 和 print 之外的其他方法，1brc 场景下其他方法都用不到。

然后来看实现，整体逻辑跟方案1没啥区别，无非就是存储数据的数据结构从 HashMap 换成了自己实现的 Trie，从 buffer 中读取并分离出代表 name 的 byte[]，并 insert 到 Trie 中，而温度则积累到该 name 在树中对应的 EndNode 中。

PrefixTreeDemo 第一个版本遇到了一些问题，运行耗时来到了 3 分钟左右，其中insert 方法耗时占比77%，将近两分多钟，而insert 中耗时最多的是下面这段代码：

if (node.child[childIndex] == null) { // cost a lot
		node.child[childIndex] = new TrieNode();
}
    node = node.child[childIndex]; // cost a lot

虽然我大概能猜到为什么它会慢，估计是因为在我这个 Trie 的实现需要在不同的数组之间跳来跳去，没办法利用 cpu 的 cacheline，但是这也太慢了，抓耳挠腮半天，又不想直接放弃，最终采用了一个非常规的办法让该方案的耗时来到了2分钟以内。

这个办法就是牺牲可读性，直接连 insert 方法都不要了，把里面的逻辑直接提到 parseTrie 里来，直接带来了1分钟的提升，不过耗时最多的还是前面那段代码。

原因也很简单，虽然看似毫无意义（实际上就是毫无意义），但其实减少了方法嵌套的层数/调用栈深度，让 HotSpot 去优化代码，比如 inline 等等。

DO NOT DO THIS，我只是为了消遣和偷懒，正常应该通过 -XX:+PrintCompilation -XX:+UnlockDiagnosticVMOptions -XX:+PrintInlining 找到需要优化的代码，然后对这部分代码进行拆分，拆成更细的粒度，比如拆 if/else、switch、循环等等，剩下的交给 JVM 自行决定如何内联，或者你足够自信的话也可以根据日志去调整 JVM 参数，比如修改可内联的调用栈深度、方法大小等等，而不是我这样的反向操作，我这基本上是实践中最差的选择。

  • time cost

    2m

  • profiling

    这个方案就不详细分析了，虽然成功的避开了 10 亿字符串的消耗，但是那段代码如何优化目前一点儿思路没有，虽然 HotSpot 的强大把运行时间控制在了两分钟，但是核心问题没有解决，不得不感慨数量级一上去，哪怕最简单的判空和赋值都会出乎意料。

    前缀树方案暂且搁置。

方案3：BasicMapDemo

继续回到避免创建字符串上来，之所以要创建那么多字符串是因为我们需要 Key，而 Java 的 HashMap 的 Key 必须是个对象，所以不能直接用 byte数组 来作为 Key，为了可以直接用 byte 数组作为 key，干脆就让劳苦功高的java.util.HashMap休息一下，毕竟它老人家连 DDOS 攻击都要考虑进去，里面功能太多了，我们自己实现一个最简单的哈希表（我叫他 BasicMap）来存储数据。

其实 byte[] 也是当成对象处理的，但是 JVM 不会给它生成 equals 之类的方法，所以不能直接用于 HashMap。

至于为什么不用一个类来包裹 byte[]，自行实现 equals 等方法以便适用于 java.util.HashMap，那是因为我觉得这种思路只是从 new String 变成 new 另一个类，两者没啥本质区别。

方案整体逻辑跟之前一致，唯一算得上区别的就是在进行 map.put 操作时可以直接对数据进行处理，而不是把数据处理好再 put（省掉了 map.get 操作），这里只简单介绍一下 BasicMap 的实现。

BasicMap 我采用了哈希表最经典的实现：数组+链表，Key 的类型为 byte 数组，Value 就用之前的 Data，table size 默认为 2048，希望大一些能降低冲突概率，其他扩容等等一概不考虑。

  • 第一版

    hash 函数使用： Arrays::hashcode，equals 方法是用：Arrays::equals。

    cost：1m30s | hash conflict 45次 | table.size = 2048

    hash：Arrays::hashcode 耗时占比约 18%，大概 17s 左右。

    equals：Arrays::equals 耗时占比约 15%， 大概 15s 左右。

    map.put 包含 hash 和 equals，占比约 43%，大概 40s 左右。 与方案1相比，哈希表操作的整体时间缩短了大概 10s 左右，不过不好直接对比，毕竟方案1中耗时较多的是 map.get，而这里直接省略了 get 操作，不过也因此让 map.put 来到了 40s，远超方案1中的不到 20s。

    有效果但不多，进一步优化哈希函数和 equals 方法。

  • 第二版

    更换哈希算法，顺便探索点儿新东西：vector API，其实也不算新了这东西很早就开始孵化了，只是平时很少用。

    hash 函数：FNV-1a hash（实现简单）

    equals：BasicMap#eq 则尝试使用向量 API 来看看能不能实现一个更快的比较方法。为此对原来的代码进行了一点点改造，将 key 固定为 32 bytes，并在 Entry 中存储每个 key 的真实长度。

    然后有意思的事情就出现了...

    hash 函数依然是 Arrays::hashcode时，测试新 eq 的结果是，hash 耗时不到 1s，而 eq 耗时长达 36s，最后总耗时与第一版基本一致。

    出于好奇，我将 hash 函数更换为：fnv1a32Hash 后再次进行了对比测试，结果如下：

    function nameArrays.equalseq (use vector api)
    total cost79s75s

    fnv1a32Hash方法从 8s 左右的耗时降低到了 3s 左右，eq 似乎出现了加速哈希的效果，不过暂时不去深究。

    不考虑eq的情况下，来看看 fnv1a32Hash 的效果，它比 Arrays::hashcode 快个10秒左右，哈希冲突为50次，略微上升但完全可以接受。

    最终方案为 fnv1a32Hash + eq 的版本。

  • cost

    1m15s

  • JVM option

    需要添加 --add-modules=jdk.incubator.vector，不然会报找不到 module。

  • profiling

    map.put 占比约 40%，耗时约 30s，其中 hash 函数和 equals 方法占了 90%，这也是为什么本方案中我一直在折腾这俩函数。

    IO 照旧。

    其他耗时大头就是 parseMap 方法中处理行数据的逻辑。

方案4：BasicMapMutiThreadDemo

顾名思义，方案3的多线程版本，算是挑战第一阶段的最终版本。

这算是一个偷懒的多线程版本，整体逻辑跟 BasicMapDemo 没有区别，就是应用 MapReduce 思想换成并行流来处理切分好的数据块，好处是实现简单，只有 RandomAccessFile file 是竞争资源，并且只有 load 时才有竞争，只要在load方法中对 file 加锁即可，我这里是直接加 synchronized。

切分200块，每个数据块约 64m | total cost: 35~40s。

切分400块，每个数据块约 32m | total cost: 30s。

从 7m30s 到 30s，并且没有什么复杂代码，除了 BasicMap#eq 可能有人不太熟悉，那个其实也很简单，逻辑和Arrays#equals没啥区别，总的来说这个结果我还挺满意的。

第一阶段挑战到此结束，撒花🎉。

补充说明

在方案3和4之间，我做了一系列尝试和验证性测试，主要针对 IO 和行数据处理这部分。

  • IO

    关于 IO，准确的说是本地磁盘顺序读，我通过不同方式（磁盘测试工具、dd、JMH自行编写测试等）验证了目前的方式基本就是我本地磁盘读取 13 GB 文件的比较快的一档了，目前是 4s 左右，经过测试我本机理论上最快也就 3.x s，差值也就几百毫秒，我挺满意的。

    其实是十年老本舍不得造了，电池几年前跪了后自行维修的磨难还历历在目，苹果的东西太难拆了

    读取方式除了现有方式外还顺便验证了我关于 MappedByteBuffer 的猜想，对于 1BRC 这个场景，我用 MappedByteBuffer 的话并不一定会快，简单的说它需要先映射再读取，而映射过程不见得就比我现在直接 load 快多少（本机只有16G物理内存），虽然读取很快，可是 1brc 场景下并不需要反复读取，毕竟整整 13GB 数据只需要读取一次。

    关于以上内容的测试代码回头放在 1brc-benchmark 中，测试内容就之后单独开一篇发吧。

    顺便说句题外话，刚看到 1BRC 时我下意识的以为 IO 会是一个优化的重点，然而写完 Baseline 之后就猜测可能固态硬盘 IO 没我想的那么慢，而方案1很快就印证了我的想法，load 总共也只耗时 4s。

  • 行数据处理

    这部分基本就是从 buffer 中逐个 byte 进行读取并处理，反复思考后发现似乎除了使用一些位运算魔法之外就没什么可优化的了，因此暂时到此为止。

数据特征

一共有 413 个不同地点。

温度: ab.c | a.b | -ab.c | -a.b 。

地名： 不止26个英文字母，还有其他语言的字符。

profiler

1BRC 文档中介绍的方式： Jbang + AP loader + async-profiler 来测试。

jbang --javaagent=ap-loader@jvm-profiling-tools/ap-loader=start,event=cpu,file=profile.html src/main/java/../yourDemo.java

命令会生成profile.html，浏览器打开即可看到火焰图。

FNV-1a hash

  • 实现逻辑

    hash = offset_basis
for each octet_of_data to be hashed
  hash = hash xor octet_of_data
  hash = hash * FNV_prime
return hash

  • offset_basis

    32 bit offset_basis = 2166136261

64 bit offset_basis = 14695981039346656037

128 bit offset_basis = 144066263297769815596495629667062367629

256 bit offset_basis =
100029257958052580907070968620625704837092796014241193945225284501741471925557

512 bit offset_basis =
96593031294966694980094354007163104660904187456726378961083743294344626579945829
32197716438449813051892206539805784495328239340083876191928701583869517785

1024 bit offset_basis =
14197795064947621068722070641403218320880622795441933960878474914617582723252296
73230371772215086409652120235554936562817466910857181476047101507614802975596980
40773201576924585630032153049571501574036444603635505054127112859663616102678680
82893823963790439336411086884584107735010676915

  • FNV_prime

    32 bit FNV_prime = 224 + 28 + 0x93 = 16777619

64 bit FNV_prime = 240 + 28 + 0xb3 = 1099511628211

128 bit FNV_prime = 288 + 28 + 0x3b = 309485009821345068724781371

256 bit FNV_prime = 2168 + 28 + 0x63 = 374144419156711147060143317175368453031918731002211

512 bit FNV_prime = 2344 + 28 + 0x57 =
35835915874844867368919076489095108449946327955754392558399825615420669938882575
126094039892345713852759

1024 bit FNV_prime = 2680 + 28 + 0x8d =
50164565101131186554345988110352789550307653454047907443030175238311120551081474
51509157692220295382716162651878526895249385292291816524375083746691371804094271
873160484737966720260389217684476157468082573
上次编辑于:
贡献者: Lament
Made with ❤ by lament ️
Copyright © 2024 lament-z