赌钱赚钱app

2024 年的第一天，Decodable 高档软件工程师 Gunnar Morling 曾向 Java 社区发起了一个十亿行挑战（1BRC），即条目在最快技艺内处理 10 亿行数据。针对这个挑战，本文作家 ŠIMON TÓTH 尝试用 C++ 来完成，从领先结束到经过一系列优化后，最终运行速率提高了 87 倍。

原文汇集：https://simontoth.substack.com/p/daily-bite-of-c-optimizing-code-to

作家 | ŠIMON TÓTH

翻译 | 郑丽媛

“十亿行挑战”是对 Java 开发者的一项挑战，预计是要在最快技艺内处理 10 亿行数据。诚然领先这个挑战是针对 Java 的，但本次挑战是展示 C++ 代码优化和关系性能用具的绝佳契机。（本文波及的竣工源代码地址：https://github.com/HappyCerberus/1brc。）

挑战内容

咱们的输入是一个名为 measurements.txt 的文献，其中包含来自不同测量站的温度测量数据。该文献包含十亿行数据，局势如下：

station name;value\nstation name;value

测量站称号是一个最多 100 字节的 UTF-8 字符串，包含任何 1 字节或 2 字节的字符（但不成包含‘;’或‘\\n’），测量值介于 -99.9 到 99.9 之间，均保留一位极少。另外，惟一键的总和最多为 10,000 个。

输出是一个按字母限定排序的测量站列表，每个站点都有测得的最低温度、平均温度和最高温度。

{Abha=-23.0/18.0/59.2, Abidjan=-16.2/26.0/67.3, Abéché=-10.0/29.4/69.0, ...}

领先结束

天然，咱们开始要从基准结束启动。咱们的范例将分为两个阶段：处理输入和局势化输出。关于输入部分，咱们领会测量站称号和测量值，并将它们存储在一个 std::unordered_map 中。

为了生成输出收尾，咱们整理了惟一称号并按字母限定对其进行排序，然后打印出最低、平均和最高测量值。

只剩下一个下里巴人的主函数，将这两个部分勾通在整个。

这个结束特别粗拙，但它有两个主要问题：一是不正确（暂时先岂论），二是速率特别慢。为此，咱们在以下三台设备上追踪性能：

● Fedora 39 上的 Intel 9700K

● Windows Subsystem for Linux（WSL）上的 Intel 14900K

● Mac Mini M1（8 核）

在 9700K 上用 clang 17 编译二进制文献，在 14900K 上用 clang 18 编译二进制文献，在 Mac Mini 上用 Apple clang 15 编译二进制文献。这三台设备都用了探讨的编译象征：

-O3 -march=native -g0 -DNDEBUG -fomit-frame-pointer

由于咱们主要善良的是相对性能的提高，因此测量收尾仅为相应设备上的最快运行技艺。

● 9700K（Fedora 39）：132 秒

● 14900K（WSL Ubuntu）：67 秒

● Mac Mini M1：113 秒

遗弃拷贝

关于第一步优化，咱们并不需要特殊用具：高性能代码最伏击的原则便是幸免过多拷贝，而咱们却意外间进行了广博拷贝。

当咱们处理一瞥数据时（记取，共有 10 亿行数据），会将测量站称号和测量值读入 std::string 中。这骨子上就产生了数据拷贝，因为当咱们从文献中读取数据时，文献内容依然在内存中的缓冲区了。

为了遗弃这个问题，咱们有几个选拔：改用非缓冲读取，手动处理 istream 的缓冲区；用更系统级的边幅，举例对文献进行内存映射——在本文中，咱们将采纳后者。

当咱们将文献进行内存映射时，操作系统会为文献内容分派地址空间，而数据仅在需要时才会读入内存。这么作念的克己是，咱们可以将整个文献视为一个数组；流毒是，咱们无法戒指刻下内存汉文献的哪些部分是可用的。

既然咱们用的是 C++，那么就用 RAII 对象来封装底层系统逻辑吧。

因为咱们将内存映射文献封装在 std::span 中，因此只需将 std::ifstream 换成 std::ispanstream 就能考证一切是否平素。

不外，诚然这可以确保一切平素，但并不成遗弃任何过多的拷贝。为此，咱们必须将输入处理从在 istream 上操作切换为将输入视为一个大 C 格调字符串。

咱们需要调整哈希映射以复旧异构查找，因为咫尺用 std::string_view 查找测量站，这会波及改革比较器和添加自界说哈希函数。

这一优化使咱们的处置决策运行速率大幅提高（暂时跳过 M1，因为 clang 15 不复旧浮点类型的std::from_chars）。

● 9700K（Fedora 39）：47.6 秒（2.8 倍）

● 14900K（WSL Ubuntu）：29.4 秒（2.3 倍）

分析情况

为了进一步优化处置决策，咱们必须分析哪些部分是主要瓶颈，这就需要一个性能分析用具。

至于分析用具的选拔，咱们必须在精度和低支出之间作念出均衡。在本文中，咱们将使用 perf：这是一个 Linux 性能分析用具，支出极低的同期能提供合理精度。

要记载性能分析，咱们必须在二进制文献中注入一些调试信息：

-fno-omit-frame-pointer # do not omit the frame pointer\n-ggdb3 # detailed debugging information

接着在 perf 用具下运行二进制文献：

perf record --call-graph dwarf -F999 ./binary

callgraph 选项允许 perf 期骗二进制文献中存储的调试信息，将初级函数包摄于正确的调用者。第二个选项会镌汰 perf 捕捉样本的频率；如若频率过高，可能会丢失一些样本。

然后，咱们就可以巡视性能分析了：

perf report -g 'graph,caller'

不外，如若咱们在刻下实施决策中运行 perf，只可得到一个信息量较为有限的性能分析。

可以揣度出，运行技艺的最大部分都奢华在 std::unordered_map 中，而其余操作都在初级函数中被合并了。举例，你可能会得出这么的论断：领会测量值只占 3%（std::from_chars 函数）——但这其实是错的。

由于咱们将悉数逻辑都放在了一个细巧的轮回中，这么的性能分析就很差。诚然这对性能来说有克己，但却十足失去了正在践诺的逻辑操作的兴致：

● 领会测量站称号；

● 领会测量值；

● 将数据存储到数据库中。

如若咱们将这些逻辑操作封装成单独的函数，性能分析的了了度将大幅提高。

可以看到，咱们奢华了 62% 的技艺将数据插入数据库，26% 的技艺领会测量值，以及 5% 的技艺领会测量站称号。

接下来应该处理哈希映射，但在此之前，咱们先处理一下数值领会问题，这也将开导咱们代码中一个历久存在的失实（四舍五入失实）。

虚伪的整数

输入包含 -99.9 到 99.9 领域内的测量值，并永久保留一位极少——这意味着，咱们开始处理的不是浮点数，因为测量值是定点数。

暗示定点数值的正确边幅，是将其暗示为整数，咱们可以手动领会（先用成功领会）：

这种变化也会影响到记载的结构：

数据库插入可以保抓原样，但咱们可借此契机略微优化一下代码。

终末，咱们需要修改输出局势的代码。由于咫尺用的是定点数，是以咱们必须将存储的整数值诊治并四舍五入成浮点数。

这一优化开导了前边提到的四舍五入失实，并提高了运行时遵守（浮点运算速率较慢），且该结束也与 M1 Mac 兼容。

● 9700K (Fedora 39)：35.5 秒（3.7 倍）

● 14900K（WSL Ubuntu）：23.7 秒（2.8 倍）

● Mac Mini M1：55.7 秒（2.0 倍）

自界说哈希映射

范例库中的 std::unordered_map 以速率慢而著明，这是因为它使用了节点结构（施行上是节点链表数组）。按理说，咱们可以改用平面映射（来自 Abseil 或 Boost），但这会不服 1brc 挑战赛的端正——即不容使用外部库。

更伏击的是，咱们的输入也特别有限。关于 10 亿札记载，咱们唯有 1 万个惟一键，因此射中率会极高。

由于咱们只可用 1 万个惟一键，因此可用基于 16 位哈希的线性探伤哈希映射，成功索引静态数组。当碰到碰撞时（两个不同站点映射到探讨的哈希/索引）时，咱们将使用下一个可用的槽位。

这就意味着，在最坏的情况下（悉数站点都映射到探讨的哈希/索引），咱们最终会进行线性复杂度查找。然则，这种情况极少发生，关于使用 std::hash 的输入示例，咱们最终会碰到 500 万次碰撞，即 0.5%。

这一变动，带来了相配大的速率提高：

● 9700K（Fedora 39）：25.6 秒（5.1 倍）

● 14900K（WSL Ubuntu）：18.4 秒（3.6 倍）

● Mac Mini M1：49.4 秒（2.3 倍）

微调代码

以上，咱们依然梳理了高头绪的优化道路，接下来是技艺真切挖掘并微调代码中的要害部分了。先让咱们回来一下咫尺的情况。

咱们可以在哈希（17%）和整数领会（21%）方面进行一些初级优化。微调代码的正确用具是基准测试框架，咱们将结束几个预计函数的版块，并把收尾互比较较。在本文中，咱们选拔使用 Google Benchmark。

（1）领会整数

刻下版块的整数领会（专诚）写得很差，有过多的分支。

由于数值可以短至三个字符，咱们无法有用地期骗宽提示（AVX）。在这种情况下，惟一能遗弃分支的边幅便是通过查找表。

当咱们领会数字时，唯有两种可能的情况（忽略象征）：

● 碰到一个数字：累加器乘以 10 并加上数字值。

● 碰到一个非数字：累加器乘以 1 并加上 0。

咱们可以把这个流程编码为一个二维的、在编译时生成的数组，其中包含 char 类型悉数 256 个值的信息。

如若咱们把这两个版块插入到微基准测试中，就会得到一个特别明确的收尾。

但很可惜，咱们并不成把这两个版块成功插入到 Google Benchmark 中。咱们的结束是一个进步 5 个字符的细巧轮回，因此对布局特别敏锐，可以用 LLVM 象征来对皆这些函数。

-mllvm -align-all-functions=5

不外即使这么，收尾也会有很大波动（高达 40%）。

（2）哈希处理

在进行哈希处理时，咱们有两个优化的契机。

咫尺，咱们是先领会站点的称号，然后在 lookup_slot 入网算哈希值，这意味着要对数据进行两次遍历。此外，咱们打算的是 64 位的哈希值，但施行上只需要 16 位的哈希值。

为了减少整数领会时碰到的问题，咱们将把领会合并为一个门径，生成一个站点称号的 string_view、一个 16 位哈希和定点测量值。

咱们可以用一个粗拙公式来打算自界说的 16 位哈希，依赖无象征溢出而不是取模。

这将大幅加速打算速率（同期具有合理的显露性）。

当咱们将这个转换纳入处置决策中后，就会得到举座速率的提高：

● 9700K (Fedora 39)：19.2 秒（6.87 倍）

● 14900K（WSL Ubuntu）：14.1 秒（4.75 倍）

● Mac Mini M1：46.2 秒（2.44 倍速）

开释线程

如若咫尺磋商一下性能分析，就会发现咱们依然达到了可行的极限。

因此，下一步天然是并行化咱们的代码。最粗拙的边幅是将输入分红约略探讨的块，在单独的线程中处理每个块，然后合并收尾。咱们可以扩张 MappedFile 类型，以提供分块考查。

这么，咱们就可以粗拙地在每个线程中按块运行现存代码。

这么的优化恶果相配可以。

以下是最好收尾。请注意，这些仅仅相对比较下的最好运行收尾，而不是严格的基准测试。

● 9700K（Fedora 39）：2.6 秒（50 倍）（在 8 个线程上）

● 14900K（WSL Ubuntu）：0.89 秒（75 倍）（在 32 个线程上）

● Mac Mini M1：10.2 秒（11 倍）（在 24 个线程上）

（1）处理非对称处理速率

9700K 的缩放特别任性，但这是因为这款处理器有 8 个不复旧超线程的探讨内核。一朝咱们升级到 14900K，架构中的性能和遵守内核就会变得复杂得多。

如若咱们粗拙地将输入分红探讨的块，遵守中枢会逾期于主中枢，拖慢举座运行速率。因此，咱们不再将输入分红每个线程一个块，而是让线程按需恳求块。

以及 MappedFile 中相应的 next_chunk 边幅。

这么咱们就可以从 14900K 中挤出终末一点性能：

● 14900K（WSL Ubuntu）：0.77 秒（87 倍）（在 32 个线程上）

论断

对比领先结束的性能，咫尺咱们依然提高了 87 倍——你可能会问：这值得吗？

那要看情况了。写这篇著述我花了很长技艺，也奢华了广博元气心灵，阑珊是用微基准测试时出现的对皆问题是一个很大的贫穷。如若我正在优化一段出产代码，我可能会留步于基本优化这个关节。微调代码的恶果可能可以，但要插足广博技艺，况兼这些优化在当代架构上的显露性很差。

终末，本文中波及的竣工源代码可在这个 GitHub 存储库中赢得：https://github.com/HappyCerberus/1brc。