Go 中的十亿行挑战:从 1 分 45 秒到 3.4 秒的九个解决方案

2024 年 3 月,作者看到“十亿行挑战”后用 Go 语言去解决。作者虽迟到该派对(原竞赛在 1 月且用 Java),但一直对优化 Go 代码感兴趣。此挑战简单,处理包含天气站名称和温度的文本文件,输出每个站的最低、平均和最高温度,输入文件有 10 亿行约 13GB 数据,作者已知道磁盘 I/O 不再是瓶颈,而是内存分配和解析。
文章描述 9 个用 Go 写的解决方案,每个比前一个快,第一个简单且惯用的方案在作者机器上运行 1 分 45 秒,最后一个 3.4 秒。更新了自定义哈希表的代码,将时间从 3.9 秒降至 3.4 秒。解决方案从慢到快如下:

  • r1:简单且惯用的 Go 代码,用bufio.Scanner读行等操作,处理 10 亿行需 1 分 45 秒,比 AWK 快。
  • r2:使用指针值的 map,避免重复哈希,将时间从 1 分 45 秒降至 1 分 31 秒。
  • r3:手动解析温度,不用strconv.ParseFloat,时间从 1 分 31 秒降至 55.8 秒。
  • r4:使用定点整数,将时间从 55.8 秒降至 51.0 秒。
  • r5:避免bytes.Cut,时间从 51.0 秒降至 46.0 秒。
  • r6:避免bufio.Scanner,自己扫描文件,时间从 46.0 秒降至 41.3 秒。
  • r7:自定义哈希表,避免处理字节两次和转换为字符串,时间从 41.3 秒降至 22.1 秒。
  • r8:并行处理文件块,将时间从 1 分 45 秒降至 22.6 秒,比优化的非并行版本 r7 稍慢。
  • r9:所有优化加并行,将时间从 22.6 秒降至 3.4 秒,有巨大提升。
    文末给出所有 Go 解决方案及最快的 Go 和 Java 解决方案的时间对比表,作者的方案与最快的 Go 版本相近,最快的 Java 版本在作者机器上运行不到 1 秒,比 Go 版本快很多,作者认为对于日常编程简单惯用代码好,但若构建数据处理管道或类似 GraalVM 运行时,性能很重要,还希望得到 GitHub 赞助。
阅读 8
0 条评论