本文档概述了编写高性能Go代码的最佳实践。
目前，这是一个视频，幻灯片和博客文章(“awesome-golang-performance”)的链接集合，但我希望它发展成一个更长的书籍格式，其内容是在这里，而不是外部。链接应该被分类到不同的类别中。
虽然有些讨论会针对单个服务进行会更快(高速缓存等)，但设计高性能的分布式系统已经超出了这项工作的范围。在监控和分布式系统设计方面已经有很好的文章。它包含一套完全不同的研究和设计权衡。
所有内容将根据CC-BY-SA进行许可。
本书分为不同的部分:
1) 编写高性能软件的基本技巧
* CS 101-level的东西
2) 编写快速软件的技巧
* 关于如何从Go获得最佳效果的Go-specific章节
3) 编写*真正*快速软件的高级技巧
* 当你优化的代码不够快时
我们可以总结这三个部分:
- “不要糊涂”
- “放聪明点”
- “有危险”
何时何地做优化
我先把这个放在第一位，是因为这真的是最重要的一步。你曾经也应该这样做吗？
每个优化都有成本。通常，这个成本是用代码复杂度或认知负载来表示的 - 优化后的代码很少比未优化的版本简单。
但另一方面，我将称之为“优化经济学”。作为程序员，你的时间是宝贵的。你可以为你的项目工作的机会成本，哪些错误需要修复，以及需要添加哪些功能。优化的工作是很有趣的，但并不总是正确的选择。性能是一项功能，但代价和正确性也是如此。
选择最重要的工作。有时它不是一个实际的CPU优化，而是一个用户体验。就像添加进度条一样简单，或者通过在渲染页面后在后台执行计算来提高页面的响应速度。
有时这是显而易见的:在三小时内完成的报告在一小时完成可能不太有用。
仅仅因为容易优化并不意味着它是值得优化的。忽略low-hang的效果是一种有效的发展战略。
把这看作是优化 你的 时间。
选择要优化的内容，选择何时优化。
澄清“不成熟的优化”报价。97％的时间。把精力放在那些重要的3％的工作。
TPOP:你应该优化吗？“是的，但只有当问题很重要时，程序真的太慢了，并且有一些期望能够在保持正确性，稳健性和清晰度的同时加快速度。”
快速的软件或快速部署。
bitfunnel.org/strangeloop 数字显示，假想搜索引擎需要30k机器 @ 1k美元/年，加倍软件的速度可以节省1500万美元/年，即花费整整一年的时间削减1％的开发人员也可以抵消。
在绝大多数情况下，程序的大小和速度不是问题。最简单的优化不必这样做。第二个最简单的优化就是购买更快的硬件。
如果你决定要改变你的程序，请继续阅读。
如何优化
优化工作流程
在介绍具体细节之前，我们先谈谈优化的一般过程。
优化是一种重构的形式。但是，每一步都会提高性能的某些方面:降低CPU，内存使用率和延迟等，而不是改进源代码的某些方面(代码重复，清晰度等)。这种改进通常是以可读性为代价的。这意味着除了一套全面的单元测试(以确保你的更改没有破坏任何内容)之外，你还需要一套很好的基准测试，以确保你的更改对性能产生预期的影响。你必须能够验证你的更改是否真的在降低CPU。有时你认为会改善的变化实际上会变成零或负变化。在这些情况下，务必确保你撤销修复的程序代码。
stackoverflow.com/questions/1…
//
//亲爱的维护者:
//
//当你完成试图“优化”这个程序，
//并且已经意识到了什么可怕的错误，这是，
//请增加以下计数器作为警告
//下一guy:
//
//total_hours_wasted_here = 42
//你使用的基准测试必须正确，并为代表性工作负载提供可重复的数字。如果单个的运行差异太大，则会使得小的改进更难以发现。你将需要使用benchstat或等效的统计测试，而不能只是用眼睛去看(请注意，使用统计测试无论如何都是一个好主意)。应该记录运行基准测试的步骤，并且应该向存储库提交任何自定义脚本和工具，并提供如何运行它们的说明。要注意需要很长时间才能运行的大型基准测试套件:它会使开发迭代变慢。
还要注意，任何可以测量的东西都可以优化。确保你正在衡量正确的事情。
下一步是决定你正在优化什么。如果目标是改进CPU，那么什么是可接受的速度。你想要将当前的性能提高2倍吗？10倍？你能否说它是“小于时间T的大小为N的问题”？你想减少内存使用量吗？多少钱？对于内存使用情况的变化，可以接受的速度有多慢？你愿意放弃什么来换取较低的空间需求？
优化服务延迟是一个棘手的问题。整本书都是关于如何对Web服务器进行性能测试的。主要问题是对于单线程代码，对于给定的问题大小，性能相当一致。对于webservices，你不会得到一个单一的数字。一个适当的Web服务基准套件将为给定的需求/秒级别提供延迟分布。...(链接到Gil Tene的Talk)
绩效目标必须具体。你会(几乎)总是能够更快地做出一些事情。优化往往是一个收益递减的游戏。你需要知道何时停止。你要付出多少努力才能完成最后一点工作。你愿意做出这样的代码是多么难以维护？
Dan Luu的演讲还指出了粗略计算的优势，以确定你的目标表现数据是否合理。
对于绿地开发，你不应该把所有的基准和性能数字都留到最后。很容易说“我们稍后会修复”，但如果性能非常重要，那么从一开始就将是一个设计考虑因素。在解决性能问题时所需的任何重大体系结构更改在截止日期前将过于冒险。请注意，在开发过程中，重点应放在合理的程序设计，算法和数据结构上。在更低层次的堆栈优化应该等到开发周期晚些时候才能获得更完整的系统性能视图。你在系统不完整时执行的任何完整系统配置文件都会对完成系统中瓶颈的位置给出偏斜视图。
死亡减1000。
编写你可以测试的代码。你可以在较大的系统上执行分析。你可以通过基准测试测试孤立的部分。你需要能够提取并设置足够的环境上下文，以便基准测试足够并具有代表性。
你的目标是什么和目前的表现之间的差异也会让你知道从哪里开始。如果你只需要10％-20％的性能改进，那么可以通过一些实施调整和较小的修复来实现。如果你需要一个10倍或更多的因子，那么用一个左移代替一个乘法不会削减它。这可能会要求你的堆栈上下进行更改。
良好的性能工作需要从系统设计，网络，硬件(CPU，缓存，存储)，算法，调整和调试等多个不同层面的知识。在时间和资源有限的情况下，考虑哪个级别能够提供最大的改进:它并不总是算法或程序调优。
一般而言，优化应该从上到下进行。系统级别的优化将比表达级别的影响更大。确保你在适当的水平上解决问题。
本书主要讨论如何减少CPU使用率，减少内存使用量并减少延迟。很高兴指出你很少能做到这三点。也许CPU时间更快，但现在你的程序使用更多的内存。也许你需要减少内存空间，但现在该程序需要更长的时间。
阿姆达尔定律告诉我们要关注瓶颈。如果你将运行时间仅占5％的例程速度提高一倍，那么整个挂钟的速度只有2.5％。另一方面，将80％的时间加速10％的例程将使运行时间提高近8％。配置文件将有助于确定实际花费的时间。
优化时，你想减少CPU必须完成的工作量。Quicksort比气泡排序更快，因为它能以更少的步骤解决相同的问题(排序)。这是一个更高效的算法。你已经减少了CPU完成相同任务所需完成的工作。
像编译器优化一样，程序调优通常只会在整个运行时间中造成一点小小的负担。大的胜利几乎总是来自算法改变或数据结构的改变，这是你的程序组织方式的根本转变。编译器技术有所改进，但速度很慢。Proebsting定律表明，编译器每18 年的性能翻倍，这与摩尔定律(稍微误解了解释)形成鲜明对比，该定律使处理器性能每18 个月翻一番。算法改进在更大的范围内工作。从1991年到2008年，混合器整数规划算法提高了30,000倍 举一个更具体的例子，考虑将Uber博客文章中描述的蛮力地理空间算法替换为更适合所呈现任务的更专门的算法:https: //medium.com/@buckhx/unwinding-uber- S-最高效的服务，406413c5871d
分析器可能会告诉你，大量的时间都花在了特定的例程上。这可能是一个昂贵的例程，或者它可能是一个便宜的例程，只是被称为许多次。而不是立即加快这一过程，看看你是否可以减少被调用的次数或完全消除它。我们将在下一节讨论更具体的优化策略。
三个优化问题:
- 我们必须这样做吗？最快的代码是永远不会运行的代码。
- 如果是的话，这是最好的算法。
- 如果是的话，这是这个算法的最佳实现。
具体的优化技巧
Jon Bentley在1982年的作品“编写高效程序”将程序优化视为一个工程问题:基准。分析。提高。校验。迭代。他的一些技巧现在由编译器自动完成。程序员的工作是使用编译器无法做到的转换。
本书的摘要如下:
和程序调整规则: web.archive.org/web/2008051…
在考虑对程序进行更改时，有两个基本选项:你可以更改数据，也可以更改代码。
数据的更改
改变你的数据意味着增加或改变你正在处理的数据的表示(其中一些依赖于改变与数据结构的不同方面相关的O())。
增加数据结构的想法:
-
额外字段:例如，存储链接列表的大小，而不是在询问时迭代。或者将经常需要的其他节点的指针存储到多个搜索中(例如，双向链接列表中的“向后”链接以进行删除O(1))。当你需要的数据便于存储并保持最新时，这些更改很有用。
-
额外的搜索索引:大多数数据结构都是为单一类型的查询而设计的。如果你需要两种不同的查询类型，对数据进行额外的“查看”可能会有很大的改进。例如，[] struct，由ID引用，但有时是string - > map [string] id(或* struct)
-
有关元素的额外信息:例如布隆过滤器。这些数据结构必须小而快，以免压倒其余的数据结构。
-
如果查询很昂贵，请添加一个缓存。我们都熟悉memcache，但还有进程内缓存。
- 通过网络，网络+序列化成本将会受到影响
- 进程内缓存，但现在你需要担心到期
- 即使是单个项目也可以帮助(日志文件时间解析示例)
TODO:“缓存”可能不是键值对，只是指向你工作的地方。这可以像“搜索手指”一样简单
这些都是数据结构层面“做更少工作”的明确例子。他们都花费空间。大多数情况下，如果你针对CPU进行优化，程序将使用更多的内存。这是经典的时空交易: en.wikipedia.org/wiki/Space%…
如果你的程序使用太多的内存，也可以换个方式。减少空间使用量以换取更多计算。而不是存储的东西，每次计算它们。你还可以压缩内存中的数据，并在需要时随时对其进行解压缩。
有一本关于减少程序使用空间的在线覆盖技术书。虽然它最初是针对嵌入式开发人员编写的，但这些想法适用于处理大量数据的现代硬件程序。 www.smallmemory.com/
重新排列你的数据:消除填充。删除额外的字段。更改为较慢的数据结构。跳过指针式树状结构，改用切片和线性搜索。为你的数据定制压缩格式:浮点(go-tsz)，整数(delta，xor + huffman)
我们稍后会详细讨论数据布局。
现代计算机和存储器层次结构使空间/时间的权衡不太明确。查找表很容易在内存中“远离”(因此访问成本很高)，使得每次需要时重新计算一次值都会更快。
这也意味着基准测试通常会显示由于缓存争用而导致生产系统无法实现的改进(例如，查找表在基准测试期间位于处理器缓存中，但在真实系统中使用时总是会被“真实数据”冲刷。哈希表实际上直接解决了这个问题，比较了满足和无约束的处理器缓存上的性能。参见Jump Hash论文中的图4和图5:https ://arxiv.org/pdf/1406.2294.pdf )
TODO:如何模拟满足的缓存，显示增量成本
另一个要考虑的方面是数据传输时间。通常，网络和磁盘访问非常缓慢，因此能够加载压缩块的速度将比获取数据后解压缩数据所需的额外CPU时间快得多。一如既往，基准。二进制格式通常比文本格式更小且更快解析，但代价是不再是人类可读的格式。
算法的更改
如果你不更改数据，另一个主要选项是更改代码。
最大的改进很可能来自算法变化。这与使用快速排序将气泡排序替换为从O(n ^ 2)排序到O(n log n)或使用映射查找替换通过过去是小O(n)的数组的线性扫描等效(O (1))。
这就是软件如何变慢。最初设计用于一种用途的结构被重新用于未设计的东西。这是逐渐发生的。
直观地掌握不同的大O级别是很重要的。为你的问题选择正确的数据结构。你不必一直刮刮胡须，但是这样做可以防止很久以后才会发现的愚蠢的性能问题。
基本的复杂类别是:
- O(1):字段访问，数组或地图查找
- O(log n)):二进制搜索
- O(n):简单循环
- O(n*m):嵌套循环
- O(nlogn):分而治之
- combinatoric - 小心！
链接:bigocheatsheet.com
假设你需要搜索未分类的数据集。“我应该用二进制搜索”，你知道一个二进制搜索O(log n)比O(n)线性扫描快。但是，二分查找需要对数据进行排序，这意味着你需要先对它进行排序，这将花费O(n log n)时间。如果你正在进行大量搜索，那么分类的前期成本将会得到回报。另一方面，如果你主要做查询，也许有一个数组是错误的选择，你最好支付O(1)查找地图的代价。
选择最简单的合理数据结构并继续。CS 101，编写“不慢的软件”。别傻了。这应该是你的默认开发模式。如果你知道需要随机访问，请不要选择链接列表。如果你知道需要按顺序遍历，请不要使用地图。需求变化，你不能总是猜测未来。对工作量做出合理的猜测。
daslab.seas.harvard.edu/rum-conject…
类似问题的数据结构在做一件工作时会有所不同。随着插入的发生，二叉树每次排序一次。未排序的数组插入速度更快但未排序:最后，“敲定”你需要一次完成排序。
当编写一个供其他人使用的包时，避免每个用例都要优先考虑的诱惑。这将导致代码不可读。按设计的数据结构实际上是单一用途的。你既不能读懂头脑，也不能预测未来。如果用户说“你的软件包对于这个用例太慢”，一个合理的答案可能是“然后在这里使用这个软件包”。一揽子计划应该“做得很好”。
有时混合数据结构将提供你需要的性能改进。例如，通过分段数据，你可以将搜索范围限制在一个存储桶中。这仍然支付O(n)的理论成本，但常数会更小。当我们进行编程调整时，我们将重新审视这些调整。
在讨论大O符号时，人们忘记了两件事
一:涉及一个恒定的因素。具有相同算法复杂度的两种算法可以具有不同的常数因子。想象一下，在一个列表上循环100次而不是循环一次即使两者都是O(n)，也有一个常数因子高出100倍。
这些常数因素是为什么即使合并排序，快速排序和排列所有O(n log n)，每个人都使用快速排序，因为它是最快的。它具有最小的常数因子。
第二件事是大O只说“随着n增长到无穷大”。它没有提到小n。“随着数字的增长，这是主导运行时间的增长因素。”
经常有一个分界点，在这个分界点以下，木材算法更快。Go标准库sort包的一个很好的例子。大多数时候它使用快速排序，但是当分区大小降到12个元素以下时，它会进行shell排序传递，然后进行插入排序。
现代计算机中的存储器层次结构将问题混淆了一点，因为高速缓存更喜欢将片段扫描到追踪指针的有效随机访问的可预测访问。不过，最好从一个好的算法开始。我们将在硬件特定部分讨论这个问题。
“这场斗争可能并不总是最强，也不是最快的比赛，但这是打赌的方式。” - 吉卜林。
有时，针对特定问题的最佳算法不是单一算法，而是专门针对稍微不同的输入类的算法集合。这个“polyalgorithm”可以快速检测出需要处理的输入类型，然后发送到相应的代码路径。这就是上面提到的排序包所做的:确定问题的大小并选择不同的算法。在string与bytes包做类似的事情，检测和专门针对不同的情况。与数据压缩一样，你对输入内容的了解越多，定制解决方案就越好。即使优化并不总是适用，通过确定使用和执行不同的逻辑是安全的，使代码复杂化可能是值得的。
sort上面提到的包是多算法的另一个例子。除了结合quicksort，shell排序和插入排序之外，它还会跟踪快速排序的递归深度并在必要时调用堆排序。
基准输入
了解你的每种输入尺寸可能在生产中有多大。
你的基准测试必须使用适当大小的输入。正如我们所看到的，不同的算法在不同的输入大小下都有意义。如果你的预期输入范围<100，那么你的基准应该反映这一点。否则，选择最适合n = 10 ^ 6的算法可能不是最快的。
能够生成有代表性的测试数据。不同的数据分布会在你的算法中引发不同的行为:想想经典的“数据排序时快速排序为O(n ^ 2)”示例。类似地，对于均匀的随机数据，插值搜索是O(log log n)，但是O(n)最差的情况。知道你的输入是什么样子是代表性基准和选择最佳算法的关键。如果你用来测试的数据不能代表实际工作负载，那么你可以轻松完成针对某个特定数据集的优化，“过度配置”你的代码以便使用一组特定的输入进行最佳工作。
