写点什么

十亿行挑战显示 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:009277

评论 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 · 广东
回复
没有更多了
发现更多内容

多样数字人民币钱包来袭,阻力与动力并存

CECBC

在?进来看看新一季周边到底做点啥?【话题讨论】

气气

话题讨论

模块一作业

小智

架构实战营

华为高级技术专家多年经验分享微服务治理体系、架构及实践文档

公众号_愿天堂没有BUG

Java 编程 程序员 架构 面试

Java NIO在接口自动化中应用

FunTester

Java nio 接口测试 测试开发

打造数字人民币的大运应用场景

CECBC

由阿里三位专家撰写:数据库高效优化:架构、规范SQL技巧文档

公众号_愿天堂没有BUG

Java 编程 程序员 架构 面试

终于有大牛把Spring微服务架构设计第2版文档给整理完毕了

公众号_愿天堂没有BUG

Java 编程 程序员 架构 面试

云小课 | 详解华为云独享型负载均衡如何计费

华为云开发者联盟

负载均衡 华为云 弹性负载均衡 独享型ELB实例 独享型负载均衡

一分钟学会使用ApiPost中的全局参数和目录参数

CodeNongXiaoW

大前端 测试 后端 接口工具

web技术分析| 一篇前端图像处理秘籍

anyRTC开发者

大前端 音视频 WebRTC web技术分享

DEX去中心化交易所自动刷量机器人开发|去中心化做市机器人

量化系统19942438797

去中心化 做市机器人

文件上传绕过思路拓展

网络安全学海

黑客 网络安全 信息安全 渗透测试 安全漏洞

protocol buffer的高效编码方式

程序那些事

Java protobuf 程序那些事

国产接口调试工具ApiPost中的内置变量

Proud lion

大前端 测试 后端 Postman 开发工具

区块链+物联网设备,能产生什么反应?

CECBC

后Kubernetes时代的虚拟机管理技术之kubevirt篇

谐云

虚拟机 #Kubernetes#

GraphQL设计思想

Ryan Zheng

graphql

DEX去中心化交易所自动刷量机器人开发|去中心化做市机器人

Geek_23f0c3

去中心化交易所系统开发 量化交易机器人系统开发 量化机器人 做市机器人 自动刷量机器人

堡垒机和跳板机的三大区别分析-行云管家

行云管家

运维 堡垒机 IT运维 跳板机

来了!《中国移动2021智能硬件质量报告》正式发布

零基础入门:基于开源WebRTC,从0到1实现实时音视频聊天功能

JackJiang

音视频 WebRTC 即时通讯 IM

【虚拟机专栏】智能合约执行引擎的前世今生

趣链科技

20年IT老民工苦心编撰成超大流量分布式系统架构解决方案文档

公众号_愿天堂没有BUG

Java 编程 程序员 架构 面试

立于山巅!他,凭什么抗住万亿级流量冲击!

博文视点Broadview

【等保测评】黑龙江等保测评机构详细信息说明

行云管家

网络安全 等保 等级保护 等保测评

一文带你掌握 OceanBase 社区版部署细节及原理

OceanBase 数据库

数据库 分布式数据库 oceanbase OceanBase 开源 OceanBase 社区版

🏆「作者推荐」Java技术专题-JDK/JVM的新储君—GraalVM和Quarkus

洛神灬殇

Java JVM GraalVM 8月日更

没有7年经验你真学不会这份SpringCloud实战演练文档

公众号_愿天堂没有BUG

Java 编程 程序员 架构 面试

MySQL 不完全入门指南

Java 编程 架构 面试 架构师

摩尔时代如何押注AI算力?英特尔战术大揭秘

科技新消息

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