64 Bits ought to be enough for anybody!

六十四（不止）是一个神奇的数字

为什么要尝试猜测一个64位数字？现代处理器处理64位数量，因此64位是神奇数字、头部和其他标记的自然大小。在模糊测试中，经常会遇到与这种“神奇”64位值的比较，但猜测这些值被视为典型的不可能问题。幸运的是，在这种情况下，没有人必须使用暴力方法，因为有更好的方法，如移除比较、使用预制输入种子、字典、符号执行和编译时转换。

但暴力猜测问题易于理解和并行化，展示了并行化在艰巨任务中的有效性。研究这个问题还表明，随着硬件变得更快，新的计算问题变得可能。想象一下，使用现代计算能力的全部武器库我们能实现什么！

尽管如此，我们必须考虑通过简单尝试所有可能性来猜测64位数字是多么棘手。需要多长时间？成本是多少？

64位数字有多大？

一个64位数字可以容纳2^64（即18,446,744,073,709,551,616）个不同的值——比地球上的沙粒和人体细胞还多（图1）。

图1：通过与其他大数字比较，直观感受2^64的大小。

现代CPU每秒可以执行约2700亿条指令，因此穷举2^64搜索空间需要776天——略多于两年。幸运的是，暴力比较是一个令人尴尬的并行问题，工作可以均匀分布在许多处理器之间。那么，如果我们能 coax 每个处理器同时进行多个比较呢？也许有某种服务可以让我们在短时间内获得大量处理器。

突然之间，这开始看起来可行了！

数字计算

免责声明：在讨论数字之前，我想强调这是一个有趣的实验，而不是基准测试。没有尝试确保不同处理器或机器的公平比较。此外：

• 用于生成性能数字的代码是用C编写的，缺乏测试。
• 它可能不是最快的版本。
• 它肯定有多个错误。
• 事实上，在审查过程中发现的一个严重的时间测量错误使这篇文章推迟了几周。
• 欢迎在Github上提交修复和建议。

所有测量反映了10次试验的平均值。测试的两台机器分别是Digital Ocean和Google Cloud的云实例。Digital Ocean（DO）高CPU实例自报告为“Intel(R) Xeon(R) Platinum 8168 CPU”，运行频率为2.70 GHz。Google Cloud（GCP）高CPU实例自报告为“Intel(R) Xeon(R) CPU”，运行频率为3.10 GHz。这些自报告标识符都不可信：虚拟化平台可以且通常会对底层CPU撒谎。云机器也是共享的，其他租户在您的机器上做的事情可能会影响您的CPU吞吐量。

在测试的物理机器中，我的2018 MacBook Pro配备了Intel Core i7 8559U处理器。Xeon E5-2640 v4是一台2.40 GHz的40核共享服务器。这两台机器在测量时同时运行其他软件。运行在2.93 GHz的Core i3 530是一台旧机器，在复活用于这个项目之前，它 literally 用作脚凳和猫抓板，多亏了它的GPU。

拉取请求欢迎： 您会注意到这些都是x86 CPU。非常需要ARM系统测量。我没有包括这些，因为这个项目已经花费了太长时间，而且我必须从头开始学习ARM的SIMD指令。

朴素的for循环

有人说过早优化是万恶之源。因此，让我们测量一个通用for循环比较所有2^64值需要多长时间。下面的图2列出了在完整64位范围的子集上执行的每毫秒操作数（10次运行的平均值），以及尝试所有2^64值所需时间的估计。

图2：所有2^64值的通用for循环比较。

最朴素的方法需要133年。显然，这等待时间太长，需要进行一些优化。

向量化for循环

现代处理器可以通过SIMD或向量指令同时操作多个64位数量。目前，Intel以AVX-512领先，顾名思义，它操作512位向量。这让我们每次迭代可以比较八个64位数量。对于那些想了解更多关于向量指令的人，Cornell有一套很好的入门材料。

向量化是将一次运行一个数量（标量）的代码转换为同时操作多个数量（向量）的过程。向量化是我的第一个优化，因为我认为clang会自动为我向量化代码。不幸的是，我错了——clang的自动向量化旨在向量化不依赖于循环变量的代码，如矩阵乘法。我没有依赖编译器，而是使用 artisanally 手工制作的向量化比较（sse、avx2和avx512）和手工展开的循环，以充分利用多个向量执行单元。

向量指令不断改进，但并非每个x86 CPU都支持AVX-512。有些只支持AVX2（256位向量），而其他只支持SSE4.1（128位向量），有些甚至不支持。在下面的图3（表格）和图4（图表）中，我们可以比较我们硬件集合中可用的不同向量化方法。

图3：向量化和朴素版本的64位比较操作性能。并非所有硬件平台支持相同的向量化方法。

上表为完整性而包含；下面相同数据的图表提供了更直观的比较。

图4：图3的图形表示；在单核上比较64位数字的不同方法性能。

这些数据中突出几点：

• 向量化总是有帮助的。每次迭代比较更多值总是更快，即使考虑了将值移入和移出向量寄存器的设置时间。
• AVX2（一次四个比较）比SSE4.1（一次两个比较）有重大改进。正如预期，AVX2比SSE4.1快约两倍。
• 相反，AVX-512（一次八个比较）比AVX2（一次四个比较）只有小幅改进。怎么会这样？我怀疑这是由于使用AVX-512指令的一个鲜为人知的副作用：它们会使处理器速度降低多达40%。处理器的功率预算不允许它既全速运行又大量使用AVX-512。

即使有这些改进，在单核上检查所有64位仍然需要39年。使用多核我们能走多快？

并行化和向量化

在64位干草堆中找针的问题恰好是极其可并行化的，因此多核应该提供线性的吞吐量增加。下面的数据（图5）显示这是真的——除非不是！有时性能 plateau 即使添加更多核心。怎么会这样？

这种效果是由于超线程。超线程处理器将物理核心呈现为两个或更多虚拟核心给操作系统。虽然每个超线程看起来独立，但底层执行单元是共享的。对于计算密集型应用程序，超线程可能对性能产生显著和令人惊讶的影响。在超线程环境和CPU密集型工作负载中，使用哪些核心可能与核心数量几乎一样重要。这对于基于云的工作负载尤其重要，其中每个vCPU是物理核心上的一个超线程。

图5：每台测试机器的每小时操作数与核心数的关系，按不同核心分配方法分开。MacBook Pro和Core i3 530结果省略。

图5显示了使用两种方法将工作线程分配给超线程的多核性能。Split cores 分配给单独的物理核心，而 share cores 分配给相同的物理核心。

40超线程核心的Xeon E5-2640机器代表了这种差异：使用 split core 分配，性能在20核心——物理核心数量——达到峰值，然后趋于平稳。使用 shared core 分配，吞吐量遵循阶梯函数，随着每个新物理核心增加。我们还可以使用这些数据推断云硬件：高CPU GCP实例的16 vCPU可能代表8个物理和16个超线程核心 dedicated 给我们的工作负载。

DO高CPU机器 presents a puzzle：没有观察到相同的效果。假设vCPU来自真实且单一的Xeon Platinum 8168，在利用24个核心后应该有差异。这没有发生，有几种可能的解释。首先，vCPU不是来自同一个物理处理器：Xeon 8168可以在8路多处理配置中操作。其次，处理器不是Xeon 8168，而是另一个芯片。最后，我的线程亲和性或时间测量代码可能有问题。

无论如何，扩展结果展示了一个宝贵的教训：使用更多核心并不总是更好，而且使用哪些核心（或vCPU）很重要。对于这个工作负载，当分配比机器中物理核心更多的工作线程时，几乎没有增益。当性能重要时，总是测量。

为完整性，图6列出了利用多核时的每毫秒操作数和估计完成年数，每个核心使用支持的最快单核方法。对于云机器，每个核心是一个“vCPU”，大致相当于一个超线程核心。对于物理机器，每个核心是一个超线程核心。

图6：观察到的最佳多处理时间，以及在多少核心时。

图6中唯一的异常值是Xeon E5-2640，它在39/40超线程核心时表现最佳，和Core i3 530，它在2/4超线程核心时表现最佳。为什么是39核心？机器是共享的并处理其他工作负载；在39核心时，所有工作负载可以放在一个核心上。在利用40核心时，工作负载 spread 到更多核心，并从CPU密集型整数比较中占用调度时间。

正如预期，使用多个CPU drastically 减少了计算时间。然而，它仍然太慢。我们不能期望等待超过两年来猜测一个数字。

进入图形

GPU采用与CPU不同的计算方法。CPU擅长多个并发任务；GPU擅长在大量数据上执行简单操作。这体现在主要架构差异中：高端CPU可能配备24个非常复杂的核心，而高端GPU配备5,120个简单核心（图7）。

图7：这是NVIDIA的Tesla V100 GPU。它配备5,120个CUDA核心，是测试中最强大的GPU。图形取自NVIDIA Volta架构白皮书。

无意中，我选择了一个为GPU优化量身定制的问题。暴力比较易于并行化，不涉及复杂决策，且完全受计算限制。由于GPU在机器学习中的作用，每个大型云提供商都提供廉价的非高峰GPU容量。

弄清楚如何使用GPU计算花了一些工作，但绝对值得。只需看图8中的吞吐量！即使我刚开始时对GPU编程和CUDA的知识约为零，且我的CUDA代码大约具有我的第一个CUDA教程级别的优化，也有一个数量级的性能增益。

图8：GPU上的64位比较吞吐量，以及搜索所有64位的估计年数。

如图8所示，使用GPU instead of CPU 将所需时间从年缩短到天。合适的平台 makes a difference！一个85美元的旧显卡（GeForce GT 1030）与40核Xeon机器性能相当。使用4x NVIDIA Tesla V100 GPU，我们可以在0.06年或约22天内暴力破解64位比较。

CPU和GPU计算对于这个问题的差异如此 dramatic（一个单独的V100比16个高CPU核心快约18.5倍），以至于使用CPU没有意义。添加另一个GPU将总是比依赖CPU计算更好地利用资源。为了显示CPU在这个问题上的糟糕程度，我制作了这个方便的图表：

图9：在选定CPU和GPU上比较64位数字时的吞吐量。这个特定问题在GPU上可以做得如此之快，以至于使用CPU完全没有意义。

现在我们已经从130年（朴素的for循环）到22天（在多个GPU上），我们能达到小时或分钟吗？需要多少硬件……成本是多少？

给我看钱

我们确定GPU比CPU快得多，但GPU时间也更昂贵。而且哪个GPU最好？不同的GPU系列价格相当不同。

使用当前定价（截至2019年11月），我们可以看到GPU的价格/性能比CPU好约5倍。虽然更昂贵，但V100提供了比其GPU前辈更好的每美元性能（图10）。

图10：比较一个值与2^64数字所需的CPU和GPU时间价格，以计算年衡量。成本是Google Cloud上可抢占时间的。

对于一开始看起来如此不可逾越的事情，最终成本 well within reach：比较一个数字与2^64值将花费约1,700美元的可抢占GPU计算时间。

因为问题可以如此高效地并行化，总计算时间几乎可以直接与硬件成本和可用性互换。例如，4x V100 GPU将在大约22天内查看所有2^64数字，但2,259x V100 GPU将在大约一小时内查看2^64数字，总体成本相同。

结论

这个愚蠢的实验展示了理解您的问题、您的硬件以及普通开发人员可用的计算资源类型的重要性。

一个看起来完全疯狂的想法结果只是 mildly insane。尝试2^64比较将花费约1,700美元的计算时间，并且可以在几小时或几天内完成。

我们沿途还学到了一些更多东西：

• 并行化并不总是容易，但可以 remarkably effective。学习一些CUDA使这个 originally insurmountable 问题从 impractical 到“可容忍但昂贵”。
• 使用更多核心并不总是更好，而且使用哪些核心很重要。
• 底层硬件可以在云的抽象下泄漏。
• 云计算提供对 nearly limitless 按需硬件的访问；只需要加以利用。
• 肯定有许多问题看起来疯狂且完全 out of reach，但可以通过可并行化算法、云计算和公司信用卡的组合解决。

我们一直在开发更快更智能的工作方式。需要帮助您的下一个项目吗？联系我们！

如果您喜欢这篇文章，分享它： Twitter LinkedIn GitHub Mastodon Hacker News

页面内容 六十四（不止）是一个神奇的数字 64位数字有多大？ 数字计算 朴素的for循环 向量化for循环 并行化和向量化 进入图形 给我看钱 结论 最近帖子 非传统创新者奖学金 劫持您的PajaMAS中的多代理系统 我们构建了MCP一直需要的安全层 利用废弃硬件中的零日漏洞 Inside EthCC[8]：成为智能合约审计员 © 2025 Trail of Bits. 使用Hugo和Mainroad主题生成。