编写和优化Go代码

image

本文档概述了编写高性能Go代码的最佳实践。

虽然有些讨论会提高单个服务的速度（通过缓存等），但设计高性能的分布式系统已经超出了这项工作的范围。在监控和分布式系统设计方面已经有很好的文章，它包含了一套完全不同的研究和设计权衡理论。

所有内容将根据CC-BY-SA进行许可。

本书分为不同的部分:

1) 编写高性能软件的基本技巧
  * CS 101-level的东西
2) 编写快速软件的技巧
  * 关于如何从Go获得最佳效果的Go-specific章节
3) 编写*真正*快速软件的高级技巧
  * 当你优化的代码不够快时

我们可以总结这三个部分:

• “合理的”
• “慎重的”
• “危险的”

何时何地做优化

我先把这个放在第一位，是因为这真的是最重要的一步。你曾经也应该这样做吗？

每个优化都有成本。通常，这个成本是用代码复杂度或认知负载来表示的 - 优化后的代码很少比未优化的版本简单。

但另一方面，我将称之为“优化经济学”。作为程序员，你的时间是宝贵的。你可以为你的项目工作的机会成本，哪些错误需要修复，以及需要添加哪些功能。优化的工作是很有趣的，但并不总是正确的选择。性能是一项功能，但代价和正确性也是如此。

选择最重要的工作。有时它不是一个实际的CPU优化，而是一个用户体验。就像添加进度条一样简单，或者通过在渲染页面后在后台执行计算来提高页面的响应速度。

有时这是显而易见的:在三小时内完成的报告在一小时完成可能不太有用。

仅仅因为容易优化并不意味着它是值得优化的。忽略low-hang的效果是一种有效的发展战略。

把这看作是优化你的时间。

选择要优化的内容以及何时优化，你可以在“软件质量”和“开发速度”之间移动滑块。

人们无意识地重复说名言——“过早的优化是万恶之源”，但他们错过了它的主要内容。

“程序员浪费了大量的时间来思考或者担心程序中非关键部分的速度，而这些效率的尝试实际上在考虑调试和维护时会产生很大的负面影响。我们应该忘记为了小的性能使用的97％的时间：过早的优化是万恶之源，但我们不应该在这个关键的3％中放弃我们的优化机会。“ - Knuth

附：https : //www.youtube.com/watch?time_continue=429&v=RT46MpK39rQ

• 不要忽视简单的优化
• 更多的算法和数据结构知识使得更多的优化变得“容易”或“明显”

“你应该优化吗？”是的，但是只有当问题很重要时，程序真的太慢了，并且能够在保证正确性，稳健性和清晰度的同时变得更快。“ - 编程实践，Kernighan and Pike

BitFunnel性能评估 有一些数字可以使这种权衡更加明确。想象一下假设搜索引擎需要跨越多个数据中心的30,000台机器，这些机器每年的成本约为1,000美元。如果你可以将软件的速度提高一倍，这可以为公司节省每年1500万美元。即使只有一个开发人员花费整整一年时间才能将性能提高也只会付出1％的代价。

在绝大多数情况下，程序的大小和速度不是问题。最简单的优化不必这样做。第二个最简单的优化就是购买更快的硬件。

如果你决定要改变你的程序，请继续阅读。

如何优化

优化工作流程

在介绍具体细节之前，我们先谈谈优化的一般过程。

优化是一种重构形式。但是，每一步不是改进源代码的某些方面（代码重复，清晰度等），而是可以提高性能的某些方面：降低CPU，内存使用率，延迟等。这种改进通常以可读性为代价。这意味着除了一套全面的单元测试（以确保你的更改没有破坏任何内容）之外，你还需要一套很好的基准测试，以确保您的更改对性能产生预期的影响。你必须能够验证您的更改是否真的在降低CPU。有时候你认为会改善性能的变化实际上会变成零或负变化。在这些情况下，务必确保撤消修改的程序。

<cite>源代码中遇到过的最好的评论是什么？- Stack Overflow</cite>

//
//亲爱的维护者:
//
//当你完成试图“优化”这个程序，
//并且已经意识到了什么可怕的错误，这是，
//请增加以下计数器作为警告
//下一个:
//
//total_hours_wasted_here = 42
//

你使用的基准测试必须正确，并为代表性工作负载提供可重复的数字。如果单个的运行差异太大，则会使得小的改进更难以发现。你将需要使用benchstat或等效的统计测试，而不能只是用眼睛去看(请注意，使用统计测试无论如何都是一个好主意)。应该记录运行基准测试的步骤，并且应该向存储库提交任何自定义脚本和工具，并提供如何运行它们的说明。要注意需要很长时间才能运行的大型基准测试套件:它会使开发迭代变慢。

还要注意，任何可以测量的东西都可以优化。确保你正在衡量正确的事情。

下一步是决定你正在优化什么。如果目标是改进CPU，那么什么是可接受的速度。你想要将当前的性能提高2倍吗？10倍？你能否说它是“小于时间T的大小为N的问题”？你想减少内存使用量吗？多少钱？对于内存使用情况的变化，可以接受的速度有多慢？你愿意放弃什么来换取较低的空间需求？

优化服务延迟是一个棘手的问题。整本书都是关于如何对Web服务器进行性能测试的。主要问题是：对于单个函数，对于给定的问题规模，性能相当一致。对于webservices，你没有一个单一的性能数字。一个适当的Web服务基准套件将为给定的需求/秒级别提供延迟分布。这篇演讲很好地概述了Gil Tene的一些问题："如何不去测量延迟" by Gil Tene

TODO：请参阅后面的关于优化Web服务的部分

绩效目标必须具体。你会（几乎）总是能够更快地做出一些事情。优化往往是一个收益递减的游戏。你需要知道何时停止。你要付出多少努力才能完成最后一点工作。你愿意做出这样的代码是多么难以维护？

Dan Luu之前提到的BitFunnel性能评估的演讲显示了一个使用粗略计算来确定目标性能数据是否合理的例子。

TODO：编程珠玑有“Fermi Problems”。从Jeff Dean's 幻灯片可以了解

对于绿地开发，你不应该把所有的基准和性能数字都留到最后。很容易说“我们稍后会修复”，但如果性能非常重要，那么从一开始就将是一个设计考虑因素。在解决性能问题时所需的任何重大体系结构更改在截止日期前将过于冒险。请注意，在开发过程中，重点应放在合理的程序设计，算法和数据结构上。在更低层次的堆栈优化应该等到开发周期晚些时候才能获得更完整的系统性能视图。你在系统不完整时执行的任何完整系统配置文件都会对完成系统中瓶颈的位置给出偏斜视图。

TODO：如何避免/发现软件写得不好的情况下的“凌迟”。

作为CI的一部分，基准测试是很难的，因为嘈杂的因素，甚至不同的CI盒子，那么很难获取性能指标。一个好的基础是让开发人员运行基准测试（在适当的硬件上）并将其包含在提交消息中，专门用于处理性能问题。对于那些只是提普通补丁的人来说，尽量在代码审查中捕捉性能下降。

TODO：如何跟踪一段时间的性能表现？

编写你可以测试的代码。你可以在较大的系统上执行分析。你可以通过基准测试测试孤立的部分。你需要能够提取并设置足够的环境上下文，以便基准测试足够并具有代表性。

你的目标是什么和目前的表现之间的差异也会让你知道从哪里开始。如果你只需要10％-20％的性能改进，那么可以通过一些实施调整和较小的修复来实现。如果你需要一个10倍或更多的因子，那么用一个左移代替一个乘法不会削减它。这可能会要求你的堆栈上下进行更改。

良好的性能工作需要从系统设计，网络，硬件(CPU，缓存，存储)，算法，调整和调试等多个不同层面的知识。在时间和资源有限的情况下，考虑哪个级别能够提供最大的改进:它并不总是算法或程序调优。

一般而言，优化应该从上到下进行。系统级别的优化将比表达级别的影响更大。确保你在适当的水平上解决问题。

本书主要讨论如何减少CPU使用率，减少内存使用量并减少延迟。很高兴指出你很少能做到这三点。也许CPU时间更快，但现在你的程序使用更多的内存。也许你需要减少内存空间，但现在该程序需要更长的时间。

阿姆达尔定律告诉我们要关注瓶颈。如果你将运行时间仅占5％的例程速度提高一倍，那么整个挂钟的速度只有2.5％。另一方面，将80％的时间加速10％的例程将使运行时间提高近8％。配置文件将有助于确定实际花费的时间。

优化时，你想减少CPU必须完成的工作量。Quicksort比气泡排序更快，因为它能以更少的步骤解决相同的问题(排序)。这是一个更高效的算法。你已经减少了CPU完成相同任务所需完成的工作。

像编译器优化一样，程序调优通常只会在整个运行时间中造成一点小小的负担。大的胜利几乎总是来自算法改变或数据结构的改变，这是你的程序组织方式的根本转变。编译器技术有所改进，但速度很慢。Proebsting定律表明，编译器每18 年的性能翻倍，这与摩尔定律(稍微误解了解释)形成鲜明对比，该定律使处理器性能每18 个月翻一番。算法改进在更大的范围内工作。从1991年到2008年，混合器整数规划算法提高了30,000倍 有关更具体的示例，请考虑此故障取代优步博客文章中描述的蛮力地理空间算法，使用更适合于所提交任务的更专业的算法。没有编译器开关可以提供相同的性能提升。

TODO：在gttse07.pdf中优化浮点FFT和MMM算法的差异

分析器可能会告诉你，大量的时间都花在了特定的例程上。这可能是一个昂贵的例程，或者它可能是一个便宜的例程，只是被称为许多次。而不是立即加快这一过程，看看你是否可以减少被调用的次数或完全消除它。我们将在下一节讨论更具体的优化策略。

三个优化问题:

• 我们必须这样做吗？最快的代码是永远不会运行的代码。
• 如果是的话，这是最好的算法。
• 如果是的话，这是这个算法的最佳实现。

具体的优化技巧

Jon Bentley在1982年的作品“编写高效程序”将程序优化视为一个工程问题:基准。分析。提高。校验。迭代。他的一些技巧现在由编译器自动完成。程序员的工作是使用编译器无法做到的转换。

本书的摘要如下:

• http://www.crowl.org/lawrence/programming/Bentley82.html
• http://www.geoffprewett.com/BookReviews/WritingEfficientPrograms.html

和程序调整规则:
https://web.archive.org/web/20080513070949/http://www.cs.bell-labs.com/cm/cs/pearls/apprules.html

在考虑对程序进行更改时，有两个基本选项:你可以更改数据，也可以更改代码。

数据的更改

改变你的数据意味着增加或改变你正在处理的数据的表示。从性能角度来看，其中一些最终会改变与数据结构的不同方面相关的O()。

增加数据结构的想法:

• 额外字段:例如，存储链接列表的大小，而不是在询问时迭代。或者将经常需要的其他节点的指针存储到多个搜索中(例如，双向链接列表中的“向后”链接以进行删除O(1))。当你需要的数据便于存储并保持最新时，这些更改很有用。
• 额外的搜索索引:大多数数据结构都是为单一类型的查询而设计的。如果你需要两种不同的查询类型，对数据进行额外的“查看”可能会有很大的改进。例如，[] struct，由ID引用，但有时是string - > map [string] id(或* struct)
• 有关元素的额外信息:例如布隆过滤器。这些数据结构必须小而快，以免压倒其余的数据结构。
• 如果查询很昂贵，请添加一个缓存。我们都熟悉memcache，但还有进程内缓存。

• 通过网络，网络+序列化成本将会受到影响
• 进程内缓存，但现在你需要担心到期
• 即使是单个项目也可以帮助(日志文件时间解析示例)

TODO:“缓存”可能不是键值对，只是指向你工作的地方。这可以像“搜索手指”一样简单

这些都是数据结构层面“做更少工作”的明确例子。他们都花费空间。大多数情况下，如果你针对CPU进行优化，程序将使用更多的内存。这是经典的时空交易

如果你的程序使用太多的内存，也可以换个方式。减少空间使用量以换取更多计算。而不是存储的东西，每次计算它们。你还可以压缩内存中的数据，并在需要时随时对其进行解压缩。

小内存软件是一本网上可获取的书籍，涵盖了减少程序使用内存空间的技术。虽然它最初是针对嵌入式开发人员编写的，但这些想法适用于处理大量数据的现代硬件的程序。

• 重新排列你的数据
  消除结构填充。删除额外的字段。使用较小的数据类型
• 更改为较慢的数据结构
  较简单的数据结构通常具有较低的内存要求。例如，从一个指针重的树结构转向使用切片和线性搜索。
• 为你的数据定制压缩格式
  []字节（snappy，gzip，lz4），浮点数（go-tsz），整数（delta，xor + huffman）大量的压缩资源。你需要检查数据还是可以保持压缩？你需要随机访问还是只有流媒体？压缩具有额外索引的块。如果不是在进程中，而是写入磁盘，那么迁移或添加/删除字段呢？你现在正在处理raw []字节而不是很好的结构化Go类型。

我们稍后会详细讨论数据布局。

现代计算机和存储器层次结构使空间/时间的权衡不太明确。查找表很容易在内存中“远离”(因此访问成本很高)，使得每次需要时重新计算一次值都会更快。

这也意味着基准测试通常会显示由于缓存争用而导致生产系统无法实现的改进(例如，查找表在基准测试期间位于处理器缓存中，但在真实系统中使用时总是会被“真实数据”冲刷。哈希表实际上直接解决了这个问题，比较了满足和无约束的处理器缓存上的性能。参见Jump Hash paper论文中的图4和图5。

TODO:如何模拟满足的缓存，显示增量成本

另一个要考虑的方面是数据传输时间。通常，网络和磁盘访问非常缓慢，因此能够加载压缩块的速度将比获取数据后解压缩数据所需的额外CPU时间快得多。一如既往，基准。二进制格式通常比文本格式更小且更快解析，但代价是不再是人类可读的格式。

对于数据传输，转移到一个不那么有趣的协议，或者增加API以允许部分查询。例如，增量查询而不是每次都被迫获取整个数据集。

算法的更改

如果你不更改数据，另一个主要选项是更改代码。

最大的改进很可能来自算法变化。这与使用快速排序将气泡排序替换为从O(n ^ 2)排序到O(n log n)或使用映射查找替换通过过去是小O(n)的数组的线性扫描等效(O (1))。

最大的改进可能来自算法变化。这相当于用quicksort（O(nlogn)）替换O(n^2)的冒泡排序或者通过哈希查找（O(1)）替换数组（O(n)）的线性扫描。

这就是软件如何变慢。最初设计用于一种用途的结构被重新用于未设计的东西。这是逐渐发生的。

直观地掌握不同的大O级别是很重要的。为你的问题选择正确的数据结构。你不必一直刮刮胡须，但是这样做可以防止很久以后才会发现的愚蠢的性能问题。

基本的复杂类别是:

• O（1）：字段访问，数组或地图查找
  建议：不要担心
• O（log n）：二进制搜索
  建议：如果处于循环状态，则只是一个问题
• O（n）：简单循环
  建议：你一直在这样做
• O（n log n）：分而治之，排序
  建议：还是相当快的
• O（n * m）：嵌套循环/二次方
  建议：小心并限制你的大小
• 二次和次指数之间的任何其他内容
  建议：不要在一百万行上运行
• O（b ^ n），O（n！）：指数上升
  建议：如果你有十几个或两个数据点，祝您好运

链接:http://bigocheatsheet.com

假设你需要搜索未分类的数据集。“我应该用二分搜索”，你知道一个二分搜索O(log n)比O(n)线性扫描快。但是，二分查找需要对数据进行排序，这意味着你需要先对它进行排序，这将花费O(n log n)时间。如果你正在进行大量搜索，那么分类的前期成本将会得到回报。另一方面，如果你主要做查询，也许有一个数组是错误的选择，你最好支付O(1)查找地图的代价。

选择最简单的合理数据结构并继续。这是用于编写“非慢速软件”的CS 101。这应该是您的默认开发模式。如果您知道需要随机访问，请不要选择链接列表。如果您知道需要按顺序遍历，请不要使用地图。需求变化，你不能总是猜测未来。对工作量做出合理的猜测。

http://daslab.seas.harvard.edu/rum-conjecture/

类似问题的数据结构在做一件工作时会有所不同。随着插入的发生，二叉树每次排序一次。未排序的数组插入速度更快但未排序:最后，“敲定”你需要一次完成排序。

当编写一个供其他人使用的包时，避免每个用例都要优先考虑的诱惑。这将导致代码不可读。按设计的数据结构实际上是单一用途的。你既不能读懂头脑，也不能预测未来。如果用户说“你的软件包对于这个用例太慢”，一个合理的答案可能是“然后在这里使用这个软件包”。一揽子计划应该“做得很好”。

有时混合数据结构将提供你需要的性能改进。例如，通过分段数据，你可以将搜索范围限制在一个存储桶中。这仍然支付O(n)的理论成本，但常数会更小。当我们进行编程调整时，我们将重新审视这些调整。

在讨论大O符号时，人们忘记了两件事

其一，涉及到一个不变的因素。具有相同算法复杂度的两种算法可以具有不同的常数因子。想象一下，循环遍历一个列表100次，而仅循环一次。即使两者都是O（n），也有一个恒定的因子是100倍。

这些常数因素是为什么即使合并排序，快速排序和排列所有O(n log n)，每个人都使用快速排序，因为它是最快的。它具有最小的常数因子。

第二件事是大O只说“随着n增长到无穷大”。它谈到了增长趋势，“随着数字变大，这是主导运行时间的增长因素。” 它没有提到实际的表现，也没有说明它如何表现小n。

经常有一个分界点，在这个分界点以下，木材算法更快。Go标准库sort包的一个很好的例子。大多数时候它使用快速排序，但是当分区大小降到12个元素以下时，它会进行shell排序传递，然后进行插入排序。

对于某些算法，常数因子可能非常大，以致此截点可能比所有合理的输入都大。也就是说，O（n ^ 2）算法对于所有可能处理的输入都比O（n）算法快。

这也是另一种方式：例如，即使小输入的基准变慢，选择使用更复杂的数据结构来给出O（n）缩放而不是O（n ^ 2）。这也适用于大多数无锁数据结构。它们通常在单线程情况下较慢，但在多线程使用它时更具可扩展性。

现代计算机中的存储器层次结构将问题混淆了一点，因为高速缓存更喜欢将片段扫描到追踪指针的有效随机访问的可预测访问。不过，最好从一个好的算法开始。我们将在硬件特定部分讨论这个问题。

“这场斗争可能并不总是最强，也不是最快的比赛，但这是打赌的方式。” - 吉卜林。

有时，针对特定问题的最佳算法不是单一的算法，而是专门针对稍微不同的输入类的算法集合。这个“polyalgorithm”可以快速检测出需要处理的输入类型，然后发送到相应的代码路径。这就是上面提到的排序包所做的：确定问题的大小并选择不同的算法。除了结合quicksort，shell排序和插入排序之外，它还会跟踪快速排序的递归深度并在必要时调用堆排序。在string与bytes包做类似的事情，检测和专门处理不同的情况。与数据压缩一样，您对输入内容的了解越多，定制解决方案就越好。即使优化并不总是适用，通过确定使用和执行不同的逻辑是安全的，使代码复杂化可能是值得的。

这也适用于你的算法需要解决的子问题。例如，能够使用基数排序可以对性能产生重大影响，如果只需要部分排序，则可以使用快速选择。

有时候，而不是专门针对您的特定任务，最好的方法是将其抽象为研究人员已经充分研究的更一般的问题空间。然后，您可以将更一般的解决方案应用于您的特定问题。将你的问题映射到已经有很好研究实现的领域可能是一个重大的胜利。

基准输入

了解你的每种输入尺寸可能在生产中有多大。

你的基准测试必须使用适当大小的输入。正如我们所看到的，不同的算法在不同的输入大小下都有意义。如果你的预期输入范围<100，那么你的基准应该反映这一点。否则，选择最适合n = 10 ^ 6的算法可能不是最快的。

能够生成有代表性的测试数据。不同的数据分布会在你的算法中引发不同的行为:想想经典的“数据排序时快速排序为O(n ^ 2)”示例。类似地，对于均匀的随机数据，插值搜索是O(log log n)，但是O(n)最差的情况。知道你的输入是什么样子是代表性基准和选择最佳算法的关键。如果你用来测试的数据不能代表实际工作负载，那么你可以轻松完成针对某个特定数据集的优化，“过度配置”你的代码以便使用一组特定的输入进行最佳工作。

这也意味着你的基准数据需要代表真实世界。如果重复的请求非常少见，保留它们比重新计算它们更昂贵。如果你的基准数据仅包含相同的重复请求，则缓存将提供不准确的性能视图。

另请注意，一旦部署到生产环境并且在40核心服务器上达到25万次/秒，笔记本电脑上可能看不到的一些问题就可以看到。

编写好的基准测试可能很困难。
TODO：microbenchmarks显示速度减慢但宏观（现实世界）性能提高的情况。

• https://timharris.uk/misc/five-ways.pdf

程序调整

程序调优曾经是一种艺术形式，但编译器变得更好。所以现在事实证明，编译器可以比复杂的代码更好地直接优化代码。Go编译器在匹配gcc和clang方面还有很长的路要走，但这确实意味着在调整时需要小心，特别是在升级Go版本时不要变得更糟。一旦编译器得到改进，肯定会出现一些针对缺少特定编译器优化工作的调整。

TODO：https : //github.com/golang/go/commit/9eb219480e8de08d380ee052b7bff293856955f8）

如果你正在解决特定的运行时或编译器代码生成问题，请始终使用指向上游问题的链接记录你的更改。这可以让你在bug修复后快速重新访问你的优化。

打击基于民间传说的崇拜“性能提示”的诱惑，甚至是从你自己的经验中过度概括。每个性能缺陷都需要根据自身的优点加以处理。即使之前已经有效，确保配置文件确保修复仍然适用。你以前的工作可以指导你，但不要盲目应用以前的优化。

程序调优是一个迭代过程。继续重新访问你的代码并查看可以进行哪些更改。确保你在每一步都取得进展。经常有一项改进可以使其他人获得成功。(现在我没有做A，我可以通过做C来简化B)。这意味着你需要继续观察整个图片，而不是沉迷于一小组线。

一旦你确定了正确的算法，程序调优就是改进算法实现的过程。在Big-O表示法中，这是减少与程序相关的常量的过程。

所有的节目调整都要么让速度变慢，要么减慢速度。算法变化也属于这些类别，但我们将看到较小的变化。你的具体做法随技术变化而变化。

做一个缓慢的事情可能会用更快的散列函数替换SHA1或者hash/fnv1。少做一次缓慢的事情可能会节省一个大文件的哈希计算结果，因此你不必多次执行该操作。

保留意见。如果不需要做什么，请解释原因。通常，在优化算法时，你会发现在某些情况下不需要执行的步骤。记录它们。其他人可能会认为这是一个错误，需要放回去。

空程序立刻给出了错误的答案。
如果你不必是正确的，那么很快就会很快。

“正确性”可以取决于问题。启发式算法大多数情况下是正确的，大部分时间都可以很快，而且猜测和改进的算法可以让您在达到可接受的限制时停下来。

缓存常见情况：

• 你的缓存甚至不需要很大。
• 参见下面的 time.Parse（）例子; 只有一个价值观产生了影响
• 但要注意缓存失效，线程问题等。
• 随机缓存驱逐是快速且足够有效的。
• 随机缓存插入可以用最少的逻辑将缓存限制为流行的项目。
• 将缓存逻辑的成本与重新获取数据的成本进行比较。
• 大容量缓存可能会增加GC压力并不断吹动处理器缓存。
• 在极端情况下（很少或没有驱逐，将所有请求缓存到一个昂贵的函数），这可以变成记忆

我已经完成了一个网络跟踪实验，表明即使是最佳的缓存也不值得。你的预期命中率很重要。你需要将比率导出到你的监控堆栈。不断变化的比例将显示流量的变化。然后是重新访问缓存大小或过期策略的时候了。

程序调优：

程序调优是以小步骤迭代改进程序的艺术。Egon Elbre列出了他的程序：

• 提出一个假设，为什么你的程序很慢。
• 拿出N个解决方案来解决它
• 尝试一切，并保持最快。
• 以防万一。
• 重复。

调整可以采取多种形式。

• 如果可能，请保留旧的实现以进行测试。
• 如果不可能，则生成足够的黄金测试用例来比较输出。
  “足够”意味着包括边缘案例，因为这些可能会受到调优的影响，因为您旨在提高一般情况下的性能。
• 利用数学身份：https://github.com/golang/go/commit/ed6c6c9c11496ed8e458f6e0731103126ce60223 https://gist.github.com/dgryski/67e6a7ff94c3a1add30eb26ec0ad8b0f
  • 与加法相乘
  • 使用WolframAlpha，Maxima，sympy和类似工具来专门化，优化或创建查找表
    （另外，https://users.ece.cmu.edu/~franzf/papers/gttse07.pdf）
  • “只为你使用的东西付费，而不是你可以使用的东西”
  • 零只是数组的一部分，而不是整个事物
  • 最好以微小的步骤完成，一次只做几个陈述
  • 从浮点数学到整数数学
  • 或者mandelbrot删除sqrt，或者lttb删除abs， a < b/c=>a * c < b
  • 在更昂贵的支票前进行廉价支票
  • 例如，在正则表达式之前的strcmp，（qv，在查询之前的布隆过滤器）“少花费更多时间”
  • 在罕见情况之前的常见情况，即避免总是失败的额外测试
  • 展开仍然有效：https：//play.golang.org/p/6tnySwNxG6O
  • 代码大小。vs分支测试开销
  • 使用偏移而不是切片分配可以帮助进行边界检查，数据依赖性和代码生成（少于在内部循环中复制）。
  • 这就是Hacker's Delight的一部分
  • 考虑不同的数字表示法：定点，浮点，（小）整数，
  • 爱好者：带误差累加器的整数（如Bresenham的线和圆），多基数/冗余数字系统

许多针对调优的民间传说性能提示依赖于对编译器的优化不足，并鼓励程序员手动完成这些转换。编译器一直在使用更新，而不是用15年的时间乘以或除以2的幂 - 现在没有人应该亲自去做。类似地，提升循环中的不变计算，基本循环展开，常见子表达式消除等等都是由gcc和clang等自动完成的。Go的编译器完成了其中的许多工作，并继续改进。一如往常，在提交新版本之前进行基准测试。

编译器无法做到的转换依赖于你了解有关算法，输入数据，系统中的不变量以及可以做出的其他假设等事情，并将该隐式知识分解为删除或更改数据结构中的步骤。

每个优化都会对你的数据进行假设。这些必须记录下来，甚至更好地进行测试。这些假设将会在你的程序崩溃，放慢速度，或随着系统发展而开始返回错误数据的地方。

程序调整改进是累积的。5倍3％的改善是15％的改善。进行优化时，值得考虑预期的性能改进。用更快的替换哈希函数是一个不断改进的因素。

了解你的要求和可以改变的地方可以提高性能。在#performance Gophers Slack频道中呈现的一个问题是用于为字符串键/值对映射创建唯一标识的花的数量。最初的解决方案是提取键，对它们进行排序，并将结果字符串传递给散列函数。我们提出的改进解决方案是在键/值添加到地图时对其进行单独散列处理，然后将所有这些散列在一起以创建标识符。

这是一个专业化的例子。

假设我们正在处理一天中的大量日志文件，并且每行都以时间戳开始。

Sun 4 Mar 2018 14:35:09 PST <...........................>
对于每行，我们调用time.Parse()把它变成一个格式。如果性能分析显示我们time.Parse()是瓶颈，那么我们有几种方法可以加快速度。

最简单的方法是保留先前看到的时间戳和相关历元的单项缓存。只要我们的日志文件在一秒钟内有多行，这将是一场胜利。对于1000万行日志文件的情况，这种策略将昂贵的呼叫数量time.Parse()从10,000,000减少到86400 - 每个独立的秒钟一个。

TODO：单项缓存的代码示例

我们可以做更多吗？因为我们确切知道时间戳的格式， 并且它们都在一天内完成，所以我们可以编写自定义时间解析逻辑，将其考虑在内。我们可以计算午夜的时代，然后从时间戳字符串中提取小时，分钟和秒 - 它们都将在字符串中处于固定偏移量 - 并执行一些整数运算。

TODO：字符串偏移版本的代码示例

在我的基准测试中，这将解析时间从275ns / op减少到5ns / op。（当然，即使在275 ns / op下，你也更有可能在I / O上被阻塞，而不是在时间解析上被CPU阻塞。）

一般算法很慢，因为它必须处理更多的案例。你的算法可以更快，因为你更了解你的问题。但是代码与您需要的密切关系更紧密。如果时间格式发生变化，更新更加困难。

优化是专业化的，专用代码比通用代码更易于改变。

对于大多数情况，标准库实现需要“足够快”。如果你有更高的性能需求，你可能需要专门的实现。

定期进行配置文件以确保跟踪系统的性能特征，并准备随着流量变化重新优化。了解你的系统的极限，并有好的指标，让你预测什么时候你会达到这些限制。

当你的应用程序的使用发生更改时，不同的部分可能会成为热点。重温先前的优化并决定它们是否仍然值得，并在可能的情况下恢复为更易读的代码。我有一个系统，我使用一组复杂的mmap优化了启动时间，反映了不安全性。一旦我们改变了系统的部署方式，这个代码就不再需要了，我用更可读的常规文件操作取代了它。

优化工作流程摘要
所有优化都应遵循以下步骤：

1. 确定你的表现目标，并确认你没有达到他们的目标
2. 配置文件来识别要改进的区域。
3. 这可以是CPU，堆分配或goroutine阻塞。
4. 基准来确定您的解决方案使用内置基准测试框架提供的加速http://golang.org/pkg/testing/
5. 确保您在目标操作系统和体系结构上进行正确的基准测试。
6. 之后再次进行配置以验证问题已消失
7. 使用https://godoc.org/golang.org/x/perf/benchstat或https://github.com/codahale/tinystat来验证一组时间“充分”不同，以便优化值得添加代码复杂性。
8. 使用https://github.com/tsenart/vegeta负载测试http服务（+其他花哨的：k6，fortio，...）
9. 确保你的延迟数字是有意义的
10. 第一步很重要。它会告诉您何时何地开始优化。更重要的是，它还会告诉你何时停止。几乎所有优化都会增加代码的复杂性以换取速度。而且你总是可以更快地编写代码。这是一个平衡的行为。

工具

介绍性分析

一般适用于源代码的技术

1. 介绍pprof
   • Go工具pprof(https://github.com/google/pprof)
2. 编写和运行(微)基准
   • 简介，将hot code提取到基准，优化基准，配置文件。
   • -cpuprofile/-memprofile/-benchmem
   • 0.5 ns/op意味着它被优化了 ->如何避免
   • 编写好的基准测试的技巧(删除不必要的工作，但增加基准)
3. 如何读取它的pprof输出
4. 显示的运行系统有哪些不同的部分
5. 宏观基准(生产剖析)
   • net/HTTP/pprof
6. 使用-base查看差异
7. 内存选项：-inuse_space，-inuse_objects，-alloc_space，-alloc_objects
8. 生产分析; localhost + ssh隧道，auth头文件，使用curl。

追踪

• 一些更有趣的/先进的工具
• /x/perf中的其他工具
• perf（perf2pprof）
• 英特尔vtune/amd codexl/instruments
  https://godoc.org/github.com/aclements/go-perf

垃圾收集

你不止一次支付内存分配。第一个显然是你分配它的时候。但是，每次垃圾收集运行时，你也要付出代价。

减少回收再利用。 - @bboreham

• 堆栈与堆分配
• 什么导致堆分配？
• 了解逃逸分析(和当前的限制)
• /debug/pprof/heap和-base
• API设计限制分配:允许传入缓冲区，因此调用者可以重用而不是强制分配
• 你甚至可以在扫描时仔细修改切片
• 减少指针以减少gc扫描时间
• 无指针的map键
• GOGC
• 缓冲区重用(sync.Pool vs或通过go-slab等自定义)
• 切片与偏移量：当GC运行时指针写入需要writebarrier：https : //github.com/golang/go/commit/b85433975aedc2be2971093b6bbb0a7dc264c8fd
• 使用错误变量而不是errors.New（）/ fmt.Errorf（）在呼叫站点（性能或风格？接口需要指针，所以它转义为堆）
• 使用结构化的错误来减少分配（传递结构值），在错误打印时创建字符串
• 大小端

运行时和编译器

• 通过接口调用的成本(在CPU级别上的间接调用)
• runtime.convT2E/runtime.convT2I
• 类型断言与类型切换
• 延缓
• 用于整数，字符串的特殊映射实现
  • byte/uint16的映射未优化; 改用切片。
  • 你可以使用math.Float{32,64}{from,}bits优化float64-optimized ，但要注意浮动平等问题
  • https://github.com/dgryski/go-gk/blob/master/exact.go 据说快100倍; 需要基准测试
• 边界检查消除
• []字节<->字符串副本，Map优化
• 双值的range将复制一个数组，使用sclice替代：
  • https://play.golang.org/p/4b181zkB1O
  • https://github.com/mdempsky/rangerdanger
• 尽可能使用字符串连接而不是fmt.Sprintf; 运行时为它已经优化了例程

Unsafe

• 它所有的危险项
• unsafe的常见用途
• mmap数据文件
  • 结构填充
  • 但并不总是足够快以证明复杂性/安全成本
  • 但是“off-heap”，所以被gc忽略（但是没有指针的slice）
• 快速反序列化
• string <-> slice 转换，[]byte <-> []uint32，...
• int到bool是不安全的hack (但 != 0是可以的)
• 填充：
  • https://dave.cheney.net/2015/10/09/padding-is-hard
  • http://www.catb.org/esr/structure-packing/#_go_and_rust
  • https://golang.org/ref/spec#Size_and_alignment_guarantees
  • https://github.com/dominikh/go-tools 结构布局，结构布局优化
  • 通过Offsetof对结构布局进行编码以发现unsafe和asm破损

与标准库共同陷阱

• time.After()泄漏，直到它被触发
• 重用HTTP连接...
• rand.Int()和朋友是1)互斥体保护和2)创建昂贵
• 考虑交替随机数生成(go-pcgr，xorshift)
• binary.Read和binary.Write使用反射并且很慢; 手动做
• 如果可能，请使用strconv而不是fmt
• ....

替代实现

• 标准库软件包的普遍替代品:
  • encoding/json -> ffjson
  • net/http -> fasthttp(但不兼容的API)
  • regexp -> ragel(或其他正则表达式包)
• 系列化
  • encoding/gob - > https://github.com/alecthomas/go_serialization_benchmarks
  • protobuf - > https://github.com/gogo/protobuf
  • 所有格式都有权衡:选择一种符合你需要的编码空间，解码速度，语言/工具兼容性......
• database/sql - > jackx/pgx，...
• gccgo
• container/list：使用切片（几乎总是）

CGO

• cgo调用的性能特征
• 降低成本的技巧:配料
• Go和C之间传递指针的规则
• syso文件

高级技术

特定于运行代码的体系结构的技术

• CPU缓存介绍

  • 性能的悬崖
  • 围绕缓存行构建直觉:大小，填充，对齐
  • 共享假
  • 真正的共享 ->分片
  • OS工具来查看缓存未命中
  • Mao与切片
  • SOA vs AOS布局
  • 减少指针追逐

• 分支预测
  从内部循环中删除分支：
  if a { for { } } else { for { } }
  代替
  for { if a { } else { } }

  避免

  if i % 2 == 0 {
  evens++
  } else {
  odds++
  }

  counts[i & 1] ++并不总是更快，但通常更难以阅读
  TODO：ASCII类计数示例和基准

• 排序数据可以通过缓存局部性和分支预测来帮助提高性能，即使考虑到排序所花费的时间

• 函数调用开销

• 关于Jeff Dean的2002年数字(加上更新)的评论

  • cpus变得更快了，但是内存没有跟上

并发

• 找出哪些部分可以并行完成，哪部分必须是顺序的
• goroutines很便宜，但不免费。
• 优化多线程代码
  • 共享false -> 填充缓存行大小
  • 共享true -> 分片
• 与上一节关于缓存和虚假/真实共享重叠
• 延迟同步; 它很贵，所以复制工作可能会更便宜
• 你可以控制的东西：worker的数量，批量大小

你需要一个互斥体来保护共享的可变状态。如果你有很多的互斥量争用，你需要减少共享，或者减少mutable。减少共享的两种方法是1）分割锁或2）独立处理，然后合并。为了减少mutable：好吧，让你的数据结构是只读的。你还可以通过减少关键部分来缩短数据共享的时间 - 尽可能少地锁定锁定。有时候RWMutex就足够了，但是请注意，它们比较慢，但是它们允许多个读者进入。

如果你正在分解锁，请注意共享缓存行。您需要填充以避免缓存行拥有权在处理器之间弹跳。

var stripe [8]struct{ sync.Mutex; _ [7]uint64 } //互斥量为64位; 填充填充缓存行的其余部分

部件

• 关于为Go编写汇编代码
• 编译器改进; bar很高
• 尽可能少地替换以产生影响
• 很好的理由：SIMD指令或者Go和编译器可以提供的其他东西
• 非常重要的基准:改进可能是巨大的(高速公路的10倍)零(小点)，或甚至更慢(不内联)
• 用新版本重新标记以查看是否可以删除代码
• TODO：链接到1.11补丁删除汇编代码
• 总是有纯粹的Go版本(noasm build tag):测试，arm，gccgo
• 简要介绍语法
• 调用的约定
• 使用不受asm支持的操作码
• 关于为什么内联很难
• 使这更容易工具:asmfmt，peachpy，c2goasm，...

优化整个服务

大多数情况下，你不会看到一个CPU限制的例程。这是一个简单的例子。如果你有优化服务，则需要查看整个系统。监测。指标。随着时间的推移记录很多事情，这样你可以看到它们变得更糟，所以你可以看到你的更改对生产的影响。

tip.golang.org/doc/diagnostics.html

• 系统设计参考:SRE Book，实用的分布式系统设计
• 额外的工具:更多日志记录+分析
• 两条基本规则:加速缓慢的事情或减少频率。
• 分布式跟踪以追踪更高级别的瓶颈
• 用于查询单个服务器而不是批量查询模式
• 你的性能问题可能不是你的代码，但是你仍然需要解决它们

附录:实施研究论文

实施论文的提示:( algorithm另请参阅data structure）

• 别。从明显的解决方案和合理的数据结构开始。
  “现代”算法往往具有较低的理论复杂性，但具有较高的常数因子和很多实施复杂性。其中一个经典例子是斐波那契堆。他们很难得到正确的，并有一个巨大的不变因素。已经发表了多篇论文，比较了不同工作负载下堆的实现方式，总体而言，4或8元的隐含堆总是排在前列。即使在Fibonacci堆应该更快（由于O（1）“减少键”）的情况下，使用Dijkstra的深度优先搜索算法的实验表明，当他们使用直接堆去除和加法时，它的速度更快。

类似地，对比更复杂的红黑或AVL树也可以找到对照或者跳过列表。在现代硬件上，“较慢”的算法可能足够快，甚至更快。

最快的算法经常可以被几乎一样快速且容易理解的算法取代。

道格拉斯W.琼斯，爱荷华大学

增加的复杂性必须足以使得回报实际上值得。另一个例子是缓存驱逐算法。不同的算法可以具有高得多的复杂度，仅命中率的小改进。当然，您可能无法在测试之前进行测试，直到您有一个可行的实施并将其整合到您的程序中。

有时候这篇论文会有图表，但很像只发布正面结果的趋势，但这些倾向往往会偏向于表示新算法的优点。

• 选择正确的纸张。
• 寻找他们的算法声称击败和实施的论文。

通常，早期的论文会更容易理解，并且必须具有更简单的算法。

并非所有的文件都很好。

查看论文写入的上下文。确定有关硬件的假设：磁盘空间，内存使用情况等。一些较旧的论文在70年代或80年代进行了合理的不同折衷，但不一定适用于您的使用案例。例如，他们认为什么是“合理的”内存与磁盘使用的权衡。内存大小现在增加了数量级，并且SSD改变了使用磁盘的延迟惩罚。同样，一些流媒体算法是为路由器硬件而设计的，这可能会使转换成软件变得非常痛苦。

确保算法对数据保持的假设。

这将需要一些挖掘。你可能不想实现你找到的第一篇论文。

• 确保你了解算法。这听起来很明显，但是否则无法进行调试。
  https://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/07/paper-reading.pdf
  一个良好的理解可能会让你从论文中提取关键的想法，并且可能将这个想法应用于你的问题，这可能比重新实现整个事情更简单。
• 数据结构或算法的原始文件并不总是最好的。后来的论文可能会有更好的解释。
• 一些论文发布了可以与之比较的参考源代码，但是
  1. 学术代码几乎普遍可怕
  2. 谨防许可限制（仅限“研究目的”）
  3. 提防错误; 边缘情况，错误检查，性能等。

还要注意GitHub上的其他实现：它们可能与您的bug相同（或不同）。

有关此主题的其他资源：

• https://www.youtube.com/watch?v=8eRx5Wo3xYA
• http://codecapsule.com/2012/01/18/how-to-implement-a-paper/

image