了解你的算法

停止使用硬件来解决软件问题。

尊敬的 KV，

我的团队和我正在为我们的项目选择新的服务器平台，并试图决定我们需要更多的核心还是更高频率的 CPU，这似乎是当前服务器系统上的主要权衡。我们的系统部署在最高端的系统上，也就是我们两年前可以购买的最高频率的系统。我们始终以 100% 的 CPU 利用率运行这些系统。我们的部署不消耗大量内存，只是大量的 CPU 周期，因此我们再次倾向于从我们的供应商那里购买最新的、顶级的服务器。我们已经考虑过重构一些我们的软件，但从成本的角度来看，昂贵的服务器比昂贵的程序员时间更便宜，程序员时间正被用来添加新功能，而不是重做旧代码。在您看来，在现代系统中，频率还是核心数更重要？

服务周到的

尊敬的 Served，

我真希望我知道您的供应商是谁，这样我就可以分一杯羹了。由于最高端的服务器目前享有巨大的加价，您的销售人员每次接到您的电话都可能乐得合不拢嘴。

关于频率与核心数的简短回答是，“您告诉我”。似乎您几乎没有花时间去了解您自己的工作负载，而只是陷入了“更新就会更好”的现代谬论。即使抛开频率缩放的结束不谈，仅仅为系统增加更多动力也很少是提高性能的最佳方法。提高性能的真正关键是测量和对算法的理解。

知道您的 CPU 使用率始终为 100% 并不能告诉您关于整个系统的太多信息，除了它很忙，但是忙于什么？也许它正处于一个死循环中，或者某个小丑在测试期间添加了一堆不再需要的延迟循环。在您分析您的系统之前，您不知道 CPU 为什么忙。所有系统都提供某种形式的分析，以便您可以追踪瓶颈所在，并且在您花钱购买全新硬件之前，应用这些工具是您的责任——尤其考虑到过去五年中新硬件有多么古怪，特别是由于 NUMA（非统一内存访问）以及所有疯狂的安全缓解措施，这些措施吸走了现代系统的生命力，以应对 Spectre 等漏洞。有时 KV 会渴望缓慢的八位微处理器的简单性，人们可以通过查看飞逝的汇编指令流来理解它。但那些日子已经过去了，而且，说实话，没有人想在 Commodore 64 上看猫，所以它根本不是现代互联网的可行解决方案。

既然我之前谈到过测量，现在让我们谈谈算法的重要性。算法是我们软件工程师工作的核心，尽管这个事实现在更多地被库和成熟的 API 所掩盖。似乎理论认为，向程序员隐藏算法复杂性可以使他们更有效率。如果我可以像搭乐高积木一样将盒子堆叠在盒子之上来完成我的工作，那么我不需要了解盒子里面是什么，只需要了解如何将它们连接在一起。当其中一个或多个盒子变成您的瓶颈时，盒子堆叠模型就会崩溃。然后您将不得不打开盒子并了解里面的东西，希望它看起来不像有毒的黑色粘液。

对算法的细致理解需要多年的时间，但有一些好的参考资料，例如 Donald Knuth 的系列丛书《计算机程序设计艺术》，可以帮助您入门。开始思考您的算法的最简单方法是每单位输入所需的操作数。在本科计算机科学中，这通常通过比较搜索和排序算法来教授。想象一下，您想在数组中查找一段数据。您知道您要查找的值，但不知道在哪里找到它。一种朴素的初步方法是从元素 0 开始，然后将您的目标值与每个元素依次进行比较。在最佳情况下，您的目标值存在于元素 0 处，在这种情况下，您执行了非常少的指令，可能只有一两个。最坏的情况是您的目标元素根本不存在于数组中，您将执行许多指令——对数组的每个元素进行一次比较——只是为了发现您的搜索答案是空的。这称为线性搜索。

对于许多数据结构和算法，我们想知道实现我们的目标所需的最佳、最坏和平均操作数。对于搜索数组，最佳情况是 1，最坏情况是 N（数组的大小），平均情况介于两者之间。如果您存储和搜索的数据非常小——几千字节——那么数组很可能是您的最佳选择。这是因为即使是最坏情况下的搜索时间也只有几千次操作，而在任何现代处理器上，这都不会花费很长时间。此外，数组非常易于使用和理解。只有当数据集的大小增长到兆字节或更大时，选择一种虽然可能更复杂，但能够提供更好的平均操作数的算法才有意义。

一个例子可能是选择一个哈希表，它的平均搜索时间为一次操作，最坏搜索时间为 N——同样是表中的元素数量。哈希表比数组更复杂，但如果搜索确实是您的系统最常做的事情，那么这种复杂性可能值得更短的搜索时间。在过去的 30 年中，已经开发了具有不同性能特征的数据结构和搜索算法，该列表太长、乏味且无聊，无法在此处深入探讨。主要考虑因素是，在最佳、最坏和平均情况下，需要多长时间才能

1. 向数据结构添加元素（插入时间）。

2. 删除元素。

3. 查找元素。

就我个人而言，我从不费心考虑最佳情况，因为我总是期望平均而言，一切都会是最坏情况。如果您幸运的话，您现在使用的盒子之外的另一个盒子里已经有一个您需要的数据结构和算法的良好实现，并且您不必打开盒子并看到粘液，您可以选择更好的盒子并继续处理下一个瓶颈。无论您在优化代码时做什么，更好地选择算法几乎总是胜过更高的频率或核心数。

最终，这又回到了测量驱动算法选择，然后是更多测量，然后是更多优化。或者您可以直接打开您的钱包，继续为所谓的更快硬件付费，而这些硬件永远无法交付您认为您支付的价值。如果您选择后一种路线，请联系 KV，以便我们可以建立供应商关系，这将直接用于支付我的酒吧账单。

大嘴巴 KV
购买还是构建，这是一个问题。
https://queue.org.cn/detail.cfm?id=1255426

线性搜索的 10 个优化
故事的操作方面
Thomas A. Limoncelli
https://queue.org.cn/detail.cfm?id=2984631

无处理器计算
异构系统使我们能够将我们的编程目标对准适当的环境。
Satnam Singh
https://queue.org.cn/detail.cfm?id=2000516

Kode Vicious，凡人称之为 George V. Neville-Neil，为乐趣和利润从事网络和操作系统代码工作。他还教授各种与编程相关的课程。他的兴趣领域是代码探险、操作系统和重写您的糟糕代码（好吧，也许不是最后一个）。他获得了马萨诸塞州波士顿东北大学计算机科学学士学位，并且是、Usenix 协会和 IEEE 的成员。 Neville-Neil 与 Marshall Kirk McKusick 和 Robert N. M. Watson 合着了《FreeBSD 操作系统设计与实现》（第二版）。他是一位狂热的自行车爱好者和旅行家，目前居住在纽约市。

最初发表于 Queue 第 16 卷，第 6 期——
在数字图书馆中评论本文

更多相关文章

Catherine Hayes, David Malone - 质疑评估非密码哈希函数的标准
尽管密码哈希函数和非密码哈希函数无处不在，但在它们的设计方式上似乎存在差距。存在许多由各种安全要求驱动的密码哈希标准，但在非密码方面，存在一定的民间传说，尽管哈希函数历史悠久，但尚未得到充分探索。虽然针对真实世界数据集的均匀分布非常有意义，但在面对具有特定模式的数据集时，这可能是一个挑战。

Nicole Forsgren, Eirini Kalliamvakou, Abi Noda, Michaela Greiler, Brian Houck, Margaret-Anne Storey - DevEx 在行动
随着领导者寻求在财政紧缩和人工智能等变革性技术的背景下优化软件交付，DevEx（开发者体验）在许多软件组织中越来越受到关注。直觉上，技术领导者普遍认为良好的开发者体验能够实现更有效的软件交付和开发者幸福感。然而，在许多组织中，旨在改进 DevEx 的拟议倡议和投资难以获得支持，因为业务利益相关者质疑改进的价值主张。

João Varajão, António Trigo, Miguel Almeida - 低代码开发生产力
本文旨在通过展示使用基于代码、低代码和极限低代码技术进行的实验室实验结果，以研究生产力差异，从而为该主题提供新的见解。低代码技术已清晰地显示出更高的生产力水平，为低代码在短期/中期内主导软件开发主流提供了有力的论据。本文报告了程序和协议、结果、局限性和未来研究的机会。

Ivar Jacobson, Alistair Cockburn - 用例至关重要
虽然软件行业是一个快节奏且令人兴奋的世界，其中不断开发新的工具、技术和技巧来服务于商业和社会，但它也很健忘。在其快速前进的过程中，它容易受到时尚潮流的影响，并且可能会忘记或忽略针对其面临的一些永恒问题的成熟解决方案。用例于 1986 年首次引入，后来普及，是这些成熟的解决方案之一。