写点什么

十亿行挑战显示 Java 可以在两秒钟内处理十亿行的文件

作者:Olimpiu Pop

  • 2024-02-24
    北京
  • 本文字数:2043 字

    阅读完需:约 7 分钟

十亿行挑战显示 Java 可以在两秒钟内处理十亿行的文件

2024 年的第一天,Decodable 高级软件工程师 Gunnar Morling 向 Java 社区发起了 十亿行挑战(1BRC)。这项挑战将持续到 1 月底,目标是找到在最快时间内处理 10 亿行的 Java 代码。到目前为止,最快的算法可以在 2.5 秒内完成处理。



挑战的规则很简单:只能使用 SDK 特性,可以是任何 Java 发行版。因此,解决方案中不能借助外部库或数据存储。为了更好地了解这一挑战,InfoQ 联系了 Morling、GoTo 首席软件工程师 Eliot Barlas、OpenValue Rotterdam 总监 Roy van Rijn 以及 Oracle 软件开发副总裁兼 GraalVM 创始人 Thomas Wuerthinger。


InfoQ:这是一项令人兴奋的挑战。您能描述一下吗?其背后的动机是什么?


Morling:1BRC 是一项编码挑战,它的任务看似简单:解析文本文件中的温度测量值,并确定每个气象站的最小、最大和平均温度。需要注意的是:该文件有 10 亿个条目!


我想创造一个机会来探索高性能编程技术、新引入的 API(比如 Vector API——它利用了 CPU SIMD 指令)、不同 Java 发行版的特性,以及任何能证明 Java 已经变得非常快的东西。


InfoQ:如何参与这项挑战?


Morling: 可以先看下README文件,并克隆存储库。尝试实现自己的解决方案,并看看其他人做了什么尝试——归根结底是为了学习。


InfoQ:您在解决方案中有看到什么出人意料的东西吗?


Morling: 有人采用了黑客的做法:许多解决方案针对特定的键集合(即天气预报站名称)做了优化。这对于这个特定的数据集是有效的。在社区的帮助下,我们澄清了挑战的目的。


有许多解决方案很有趣:使用 SIMD 和新特性 Java 原生内存 API(这是我希望看到的),以及高度优化的解析函数,包括 SWAR(寄存器内 SIMD),这是我没有预料到的。到目前为止,致力于实现最快算法的人们已经深入到原生优化领域,计算 CPU 指令,评估分支预测错误等。


InfoQ:请描述下您的解决方案。有什么技术是您想要尝试的吗?


Eliot Barlas:我的解决方案是按照可用处理器的数量拆分文件。对于每一个部分,都有一个任务在单独的线程上计算每个气象站的统计信息。当这些任务完成后,最终结果将汇总到最终的统计数据表中。


对每一部分中的数据做内存映射,并通过可以覆盖整个分区字节范围的MappedByteBuffer进行访问。任务会使用ByteBuffer遍历分区中的数据,每次一个 byte 或 int。我还使用sun.misc.Unsafe将气象站名称提取并存储为整数序列。


Roy van Rijn: 我的解决方案是一种渐进式的解决方案。一开始,它使用 SDK 提供的普通数据结构和 API(如BufferedInputStreamHashMap)。逐步地,它演变成使用 Unsafe 来直接访问内存。并行性、无分支代码和实现 SWAR(SIMD 作为寄存器)使我的解决方案成为迄今为止最主要的竞争者之一。对于存储,我自己实现了一个“非常简单”的 hashmap,其底层是基于线性探查概念的数组。


Thomas Wuerthinger: 该解决方案的第一部分将工作负载按照目标处理器的可用核数进行划分,以便可以并行处理。它使用 Java 的特性对输入文件做内存映射,从而实现最有效的直接内存访问。解析数据的最内层循环所采用的技术设法避免了分支代码,代之以一些复杂的算术和位操作。对于这个特定的问题,由于输入的随机性,处理器经常会做出错误的分支预测,因此避免分支是最大化性能的关键。


InfoQ:您的解决方案还有可能进一步改进吗?


Barlas: 我一直在关注 Panama 项目,但 1BRC 提供了一个以应用方式探索外部内存能力的机会。[…] 我还未能成功地利用 Panama 项目的 Vector API 实现加速。例如,开始时,我尝试使用 ByteVector API 来快速比较气象站名称。我想使用其他类型的向量或结合 MemorySegment 接口重新实现这个过程。


Wuerthinger: 现在可能的改进在很大程度上取决于目标硬件。具体来说,可以在内存带宽、计算带宽和分支预测依赖方面进行权衡。


Roy van Rijn: 从大的方面来讲,方法是类似的。我目前正在尝试探索的概念是“机械同情(mechanical sympathy)”,我希望改进需要执行的指令,让它们以一种最适合测试机器的方式执行。


InfoQ:您怎么看新年伊始的这项有趣的挑战?


Morling: 可以肯定的是,Java 及其生态系统和社区比以往任何时候都更加繁荣!看到这么多人参加挑战,包括一些非常知名的开发者,真是令人鼓舞。每个人都在学习:要么通过编码,要么通过阅读代码。能有这么多人参加这项挑战,实在是离不开社区的帮助。


这一挑战受到了程序员社区的热烈欢迎,Morling 说,“这一切都远远超出了我的预期。”尽管领跑者似乎是在 GraalVM 上运行的解决方案,但也有提交使用了 OpenJDK 构建、Amazon Corretto 或 Eclipse Temurin。Morling 进一步评论说:“Graal 非常适合眼下这项任务,可以额外提供几个百分点的性能提升。”


这个挑战已经不限于 Java 生态系统,已经有使用 Rust、Go、C++ 甚至 SQL 和 Shell 编写的解决方案。


Morling 感谢了社区和 Decodable——他们提供了评估用的机器。


原文链接

https://www.infoq.com/news/2024/01/1brc-fast-java-processing/



欢迎加入 InfoQ 读者技术交流群,与志同道合的朋友一起探讨知识,交流经验。


2024-02-24 08:009375

评论 3 条评论

发布
用户头像
如何使用.NET在2.2秒内处理10亿行数据(1brc挑战)https://www.cnblogs.com/InCerry/p/17964592/7-1brc-in-dotnet-even-faster-than-java-cpp
2024-02-24 20:54 · 广东
回复
.NET比 Java快多了
2024-02-24 20:54 · 广东
回复
Java 的优点是因为快嘛?
2024-02-28 16:30 · 广东
回复
没有更多了
发现更多内容

OneFlow源码解析:Eager模式下Tensor的存储管理

OneFlow

TIME_WAIT累积与端口耗尽

阿泽🧸

TIME_WAIT 三周年连更

关于ChatGPT,我们请小红书技术人和NLP专家聊聊原理和潜力

小红书技术REDtech

自然语言处理 openai ChatGPT

【七千字】教你如何用MySQL分析查询语句Explain

会踢球的程序源

Java MySQL

支持多种数据库管理系统:Valentina Studio Pro Mac激活版

真大的脸盆

软件 Mac 数据库管理 管理数据库

LED显示屏如何做到节能环保?

Dylan

经济 设备 LED显示屏

OSPFv3与OSPFv2的对比

穿过生命散发芬芳

三周年连更 OSPFv3

深入Spring Boot :web.xml去哪了

会踢球的程序源

Java Spring Boot

测试工程师为什么要关注研发效能?

思码逸研发效能

软件工程 研发效能 测试工程师

开屏广告=让用户等?小红书如何兼顾用户体验和广告投放效果

小红书技术REDtech

推荐 广告 小红书

互联网工程师Java面试八股文及答案整理(2023最新版)

会踢球的程序源

Java springboot java面试

【安全运维】小微企业的安全运维工具用哪款好?

行云管家

运维 安全运维

3月寒窗!啃透美团保姆级分布式进阶技术手册,4月终入美团定L8

Java你猿哥

Java 分布式 SSM框架 分布式数据 分布式消息

我在 20 年的软件工程师生涯中学到的 20 件事

宇宙之一粟

翻译 软技能

小红书2024届实习生招聘一直在等着你!

小红书技术REDtech

招聘 实习 小红书

把脉分布式事务的模型、协议和方案

小小怪下士

Java 分布式 分布式事务 后端

如何一招搞定PCB阻焊过孔问题?

华秋PCB

工具 电路 阻抗 PCB PCB设计

《中国企业软件研发管理白皮书》发布会倒计时1天|精彩抢先看

万事ONES

python统计程序耗时 | python小知识

AIWeker

Python python小知识 三周年连更

小红书社区反作弊探索与实践

小红书技术REDtech

防作弊 小红书

从「搭子」文化,看融云如何助力垂类社交应用增长

融云 RongCloud

融云 Z世代 通讯 交友 搭子

Unity 之 月签到累计签到代码实现(ScriptableObject应用 | DoTween入场动画)

陈言必行

Unity 三周年连更

开源正当时,共赢新未来 OpenHarmony开发者大会成功召开

科技汇

SpringBoot2.x系列教程——整合使用JPA

会踢球的程序源

Java

小红书广告智能创意能力构建过程详解

小红书技术REDtech

人工智能 广告 小红书

FastAPI 快速开发 Web API 项目: 连接 MySQL 数据库

宇宙之一粟

Python FastApi 三周年连更

准备2023金三银四的Java程序员注意:40+文档5000+页面试资料来啦

会踢球的程序源

Java java面试 面试资料 Java大厂面试

Oracle 23c 新特性实操体验优质文章汇总

墨天轮

数据库 oracle sql 新版本/特性解读

字节跳动正式开源分布式训练调度框架 Primus

字节跳动开源

开源 算法 流批一体

阿里全新推出:微服务突击手册,把所有操作都写出来了

Java你猿哥

微服务 微服务架构 Spring Cloud SSM框架

十亿行挑战显示 Java 可以在两秒钟内处理十亿行的文件_编程语言_InfoQ精选文章