如何更好地优化？

Question

如果问题看起来有些宽泛或奇怪，请事先道歉，我并不是要冒犯任何人，但也许有人可以提出建议。我试图寻找类似的问题，但冷不。

哪些更好的资源（书籍，博客等），可以教关于优化代码？

有很多资源让代码更易读（代码完成可能是第一选择）。但是如何让它运行得更快，更具有内存效率？

当然，每种特定语言都有很多书，但是我想知道是否有一些内容覆盖了操作的记忆/速度问题，并且有些语言无关？

Answer 1

阅读Structured Programming with go to Statements。尽管它是“不成熟的优化是万恶之源”的来源，但是现在有人想要做出更快或更小的事情 - 不管它们在过程中多么重要或迟到 - 它实际上是关于尽可能提高效率。

了解有关time complexity，空间复杂性和analysis of algorithms。

想出一些例子，如果您想牺牲空间复杂性更糟的空间以获得更好的时间复杂性，反之亦然。

了解您选择的语言和框架提供的算法和数据结构的时间和空间复杂性，尤其是您最常使用的语言和框架。

阅读关于创建一个好的哈希码的问题，在这个网站上的答案。

研究方法HTTP具有缓存的优点，没有不适当地使用陈旧数据的缺点。考虑应用于内存缓存的难易程度或难度。想想你什么时候会说“拧紧它，我可以忍受它为我提供的速度提升而陈旧”。考虑一下你什么时候会说“拧紧它，我可以忍受它为我提供的新鲜度的保证变得缓慢”。

了解如何进行多线程。了解它何时可以提高性能。了解为什么它通常不会或甚至使事情变得更糟。

看看很多Joe Duffy's blog，表现是他的写作经常关注的问题。

了解如何将项目处理为流或迭代，而不是每次都构建和重建每个项目的完整数据结构。了解什么时候你最好不要那样做。

知道什么东西的成本。你不能合理地决定“我会工作，所以这是在CPU高速缓存而不是主内存/主内存而不是磁盘/磁盘而不是通过网络”，除非你有一个好主意，被击中，以及成本差异是什么。更糟的是，如果你不知道自己花了多少钱，你不能忽视某些过早的优化 - 不打扰优化某些东西往往是最好的选择，但如果你甚至不考虑它，你就不会“过早地避免优化“，你会混淆和希望它的工作。

了解一下您使用的脚本引擎/ jitter/compiler/etc为您完成了哪些优化。学习如何与他们合作，而不是反对他们。无论如何，学习不要重新做它会为你做的工作。在一两种情况下，您也可以将相同的一般原则应用于您的工作。

搜索，其中一些被斥为实现细节在本网站的情况下 - 是的，所有这些都是情况下，问题的细节是不是当时最重要的事情，但所有这些的实现细节被选择因为某种原因。了解他们是什么。了解反驳的论点。

编辑（我会继续添加更多一些这个，因为我去）：

不同的书籍，当然在他们把对效率的关注的重点有所不同，但我记得Stroustrup的的C++编程语言为其中有很多时候他会解释几种不同的选择，如效率关系，以及如何不作出效率的决定，影响班级“从外部”的可用性。

这使我想到另一点。专注于您在不同项目中重复使用的库代码的效率。你不想永远想着“也许我应该在这里手动推出一个新的更有效率”，除非它是一个非常专业化的案例，你想确保大量工作能够用于高效使用的课堂在很多情况下，专注于识别热点。

对于特殊情况，一些比较隐晦的数据结构值得了解。例如，DAWG是一个非常紧凑的结构，用于存储具有大量通用前缀和后缀的字符串（这些字符在大多数自然语言中都是大多数字词），您只需在列表中找到匹配模式的列表。如果你需要一个“有效载荷”，那么一棵树中的每个字母都有一个随后每个字母的节点列表（DAWG的推广，但以“有效载荷”而不是终端节点为结尾）具有一些但并非全部的优点。他们还发现O(n)时间的结果，其中n是所寻求字符串的长度。

这会出现多久？不多。它曾经为我提供过一次（真的有几次，但是它们是同一案例的变种），因此，直到那时我才了解所有关于DAWG的知识。但我足够清楚知道这是我以后需要研究的，并且它为我节省了几千兆字节（实际上，对于需要处理16GB内存的计算机来说，这太少了，至少少于1.5GB）。直接进行手动滚动的DAWG完全是过早的优化，而不是将字符串放在哈希集合中，但通过弹出the NIST datastructure site意味着当它出现时我就可以。

考虑：“在DAWG中查找字符串是O（n）”“在Hashset中查找字符串是O（1）”这两个语句都是真实的，但两者的速度往往是可比较的。为什么？因为DAWG就字符串的长度而言是O（n），并且就DAWG的大小而言实际上是O（1）。就散列集的大小而言，散列集的大小为O（1），但根据字符串的长度计算散列值通常为O（n），并且就该长度而言，相等性检查也是O（n） 。两个陈述都是正确的，但他们正在考虑一个不同的n！在任何时间和空间复杂性的讨论中，你总是需要知道什么是 - 通常它是结构的大小，但并非总是如此。

不要忘记恒定效应：对于足够低的n值，O（n²）与O（1）相同！请记住，O（n2）这样的类似的翻译为n2 * k + n * k 1 + k 2，假设k 1 & k 2足够低并且k和我们比较的另一种算法或结构的k足够接近，他们并不重要，我们关心的只是n²。这不是一直如此，我们有时可以发现k，k 1或k 2足够高，以至于我们陷入困境。当n很小以至于不同方法的不变成本差异很重要时，也不是这样。当然，当n很小时，我们没有很大的效率问题，但是如果我们在平均n的结构上进行m次操作，而m很大。如果我们在O（1）和O（n²）之间进行选择，我们在O（m）和O（n 2m）方法之间进行选择。对于前者来说，它看起来似乎毫不费力，但是它的本质是在两种不同的O（m）方法之间进行选择，而常数因子更重要。

了解无锁多线程。或者也许不。就我个人而言，我有两个我自己的代码，我专业使用，除了最简单的无锁技术。一种是基于众所周知的方法，现在我不打扰了（它是.NET 2.0第一次为.NET 2.0编写的代码，.NET4.0库提供了一个完成相同功能的类）。另一个我第一次写作是为了好玩，并且只是在那段为了乐趣而给了我一些可靠的东西之后才被使用（在很多情况下它仍然被4.0库中的某些东西殴打，但对于我关心的其他人关于）。我不愿意在写作期限和客户时写下类似的文章。所有这一切说，如果你编写的兴趣不大，所涉及的挑战是有趣的，当你有自由放弃失败的计划时，这是一件令人愉快的事情，你正在为付费客户做些事情，而且你通常会对效率问题有所了解。 （如果你想看看我已经完成了一些工作，请看https://github.com/hackcraft/Ariadne）。

为例

其实包含的一些上述原则一个比较好的例子。看看目前在511行的方法https://github.com/hackcraft/Ariadne/blob/master/Collections/ThreadSafeDictionary.cs（我在这里开玩笑说它是引用Dijkstra的人的火焰诱饵，我们用它作为案例研究：

该方法首先写入使用递归，因为这是一个自然递归的问题 - 在对当前表执行操作之后，如果存在“下一个”表，我们希望对其执行完全相同的操作，依此类推，直到没有其他表为止。

对于一些不同的方法，递归几乎总是慢于迭代，我们是否应该使所有递归调用迭代？不，它通常不值得，而递归是编写清楚它正在做什么的代码的好方法。应用上面的原则，因为这个我这个图书馆可能会被称为性能至关重要的地方，应该对此加以特别的努力。

为了提高速度，我做的下一件事就是进行测量。我不依赖于“我知道迭代比递归更快，所以在更改以避免递归时它必须更快”。这是不正确的 - 一个写得不好的迭代版本可能不如一个写得很好的递归版本。

接下来的问题是，如何重新编写它。我有一种经过测试的方法，我知道它的工作原理，我将用不同的版本替换它。我不想用一个不起作用的版本来取代它，显然，如何重新编写，同时充分利用已有的版本？

那么，我知道关于尾巴消除;通常由编译器完成的优化改变了堆栈的管理方式，使得递归函数的属性更接近于迭代的属性（它仍然是从源代码的角度递归的，但是它的编译代码实际上是迭代的使用堆栈）。

这给了我两件事情要考虑：1.也许编译器已经这样做了，在这种情况下，我的额外工作不会做任何事情来帮助。 2。如果编译器还没有这样做，我可以手动采用相同的基本方法。

做出了这个决定，我替换了方法自己调用的所有点，并更改了下一个调用的不同参数，然后返回到开头。即而不是有：

CurrentMethod(param0.next, param1, param2, /*...*/); 

我们：

param0 = param0.next; 
goto startOfMethod; 

也正在做，我再次测量。贯穿整个单元测试的课程现在一直比以前快13％。如果距离更近，我会尝试更多的细节度量，但运行时的一致性为13％，其中包括甚至不称此方法的代码，这是我非常满意的。 （它也告诉我，编译器没有进行相同的优化，或者我没有获得任何东西）。

然后我清理该方法以进行更多有关新代码的更改。他们中的大多数让我拿出goto，因为goto确实令人讨厌（还有其他地方进行了相同的优化，因为goto完全被重构，所以不那么明显）。在某些情况下，我将它留下了，因为13％是值得打破我的脑海中的不规则规则！

所以上面给出了一个例子：

1. 决定在哪里集中优化工作（基于多久它可能被击中，我无法预测该库的所有使用）
2. 使用的知识一般成本（大多数情况下递归成本大于迭代成本）。
3. 测量而不是取决于假设上述始终适用。
4. 学习编译器的工作。
5. 了解到，因为我可能无法获得任何东西 - 也许编译器已经为我做了。
6. 避免导致不可读代码的优化（重构大部分goto是第一次通过）。

一些是舆论和样式的决定（在某些goto离开也不是没有争议）的问题，它肯定没事跟我决定不同意，但知识点在这个迄今募集职位将使其成为消息灵通的分歧，而不是一个下意识的分歧。

Answer 2

这里有一些链接，可能一般是有益的内存优化的主题

What Every Programmer Should Know About Memory by Ulrich Drepper

Herb Sutter: The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software

Slides: Herb Sutter: Machine Architecture (Things Your Programming Language Never Told You)

Video: Herb Sutter @ NWCPP: Machine Architecture: Things Your Programming Language Never Told You

The microarchitecture of Intel, AMD and VIA CPUs An optimization guide for assembly programmers and compiler makers, by Agner Fog

Answer 3

除了其他答案中提到的资源之外，Michael Abrash的Graphics Programming Black Book是了解优化的最佳解读。虽然具体细节有点过时，但它仍然是学习如何进行优化的极好资源。

任何时候你想优化代码，它是绝对必要的措施，措施，措施。学习优化的最佳途径之一就是通过这样做 - 获取一些您想要优化的代码，学习如何使用分析器来衡量其性能，然后进行更改并测量结果。