optimization - 如何更好地进行优化？

知道东西的成本。你不能合理地决定“我会工作，所以这是在 CPU 缓存而不是主内存/主内存而不是磁盘/磁盘而不是通过网络”，除非你很清楚是什么导致每个被击中，成本差异是多少。更糟糕的是，如果您不知道它们的成本，您不能将某些东西视为过早优化 - 不费心优化某些东西通常是最好的选择，但如果您甚至不考虑它，那么您就不是“避免过早优化”，你正在蒙混过关，希望它能奏效。

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

在此站点上搜索某些被视为实施细节的案例 - 是的，所有这些案例都是相关细节在当时并不是最重要的事情，但所有这些实施细节都是出于某种原因而选择的。了解他们是什么。学习反论点。

编辑（我会继续添加更多内容）：

当然，不同的书对效率问题的重视程度不同，但我记得 Stroustrup 的《C++ 编程语言》中有好几次他会解释与效率有关的几个不同选项之间的选择，以及如何不为效率而做出决定对“从外部”类的可用性产生影响。

这让我想到了另一点。专注于您在不同项目中重用的库代码的效率。您永远不会想“也许我应该在这里手动滚动一个新的以提高效率”，除非这是一个非常专业的案例，否则您希望确信大量工作已投入使用以提高该类的效率在很多案例中，专注于识别热点。

至于特殊案例，一些比较晦涩的数据结构对于它们所服务的案例来说是值得了解的。例如，DAWG 是一种非常紧凑的结构，用于存储具有许多常见前缀和后缀的字符串（这将是大多数自然语言中的大多数单词），您只想在列表中找到与模式匹配的那些。如果您需要“有效负载”，那么每个字母都有一个节点列表用于每个后续字母的树（DAWG 的概括，但以该“有效负载”而不是终端节点结尾）具有一些但不是全部的优点。他们还O(n)及时找到结果，其中n是所寻找的字符串的长度。

多久会出现一次？不多。我曾经遇到过一次（确实有几次，但它们是同一案例的变体），因此在此之前了解所有关于 DAWG 的知识对我来说是不值得的。但我知道这是我以后需要研究的东西，它为我节省了千兆字节（真的，从对于 16GB RAM 的机器来说太多，到不到 1.5GB）。直接进行手动 DAWG 完全是过早的优化，而不是将字符串放入哈希集中，但浏览NIST 数据结构站点意味着当它出现时我可以。

考虑一下：“在 DAWG 中查找字符串是 O(n)”“在 Hashset 中查找字符串是 O(1)”这两种说法都是正确的，但两者的速度往往相当。为什么？因为 DAWG 就字符串的长度而言是 O(n)，而就 DAWG 的大小而言实际上是 O(1)。就哈希集的大小而言，哈希集是 O(1)，但就字符串的长度而言，计算哈希通常是 O(n)，就该长度而言，相等性检查也是 O(n) . 两种说法都是正确的，但他们正在考虑不同的说法n！你总是需要知道n在任何关于时间和空间复杂性的讨论中意味着什么——通常是结构的大小，但并非总是如此。

不要忘记常数效应：对于足够低的 n 值，O(n²) 与 O(1) 相同！请记住，O(n²) 之类的转换为 n²*k + n * k₁ + k₂，假设 k₁ 和 k₂ 足够低，并且我们正在比较的另一个算法或结构的 k 和 k 足够接近，即它们并不重要，我们只关心 n²。这并不总是正确的，我们有时会发现 k、k₁ 或 k₂ 足够高，以至于我们最终会遇到麻烦。当 n 太小以至于不同方法的恒定成本的差异很重要时，这也是不正确的。当然，通常当 n 很小时，我们没有很大的效率问题，但是如果我们对平均大小为 n 的结构进行 m 操作，并且 m 很大，该怎么办。如果我们在 O(1) 和 O(n²) 方法之间进行选择，我们总体上在 O(m) 和 O(n²m) 方法之间进行选择。它似乎仍然支持前者，但在 n 较低的情况下，它基本上成为两种不同 O(m) 方法之间的选择，并且常数因素更为重要。

了解无锁多线程。或者也许不。就个人而言，我有两段我自己专业使用的代码，除了最简单的无锁技术之外，它们都使用了所有的代码。一个是基于众所周知的方法，我现在不会打扰（它是首先为 .NET2.0 编写的 .NET 代码，而 .NET4.0 库提供了一个做同样事情的类）。另一个我第一次写是为了好玩，只是在那个只是为了好玩的时期给了我一些可靠的东西之后才使用（而且在很多情况下它仍然被 4.0 库中的某些东西打败，但对于我关心的其他一些情况则不然关于）。我不想写类似的东西，但要考虑到最后期限和客户。

综上所述，如果您出于兴趣而编写代码，那么所涉及的挑战很有趣，并且当您可以自由地放弃一个失败的计划时，这是一件令人愉快的事情，而您在做的时候却没有得到对于付费客户来说，你肯定会学到很多关于效率问题的知识。（如果您想了解我对此所做的一些事情，请查看https://github.com/hackcraft/Ariadne ）。

案例研究

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

这个方法最初是为了使用递归而编写的，因为它是一个自然的递归问题——在对当前表执行操作之后，如果有一个“下一个”表，我们想要对其执行完全相同的操作，依此类推，直到没有进一步的操作桌子。

对于一些不同的方法，递归几乎总是比迭代慢。我们应该让所有递归调用迭代吗？不，这通常是不值得的，递归是编写代码的好方法，它清楚地知道它在做什么。在这里，虽然我应用了上面的原则，因为这是一个在性能至关重要的地方可能会被调用的库，因此应该在它上面付出特别的努力。

做出尝试提高速度的决定后，我做的下一件事就是进行测量。我不依赖于“我知道迭代比递归快，因此在更改以避免递归时它必须更快”。这不是真的——一个写得不好的迭代版本可能不如一个写得好的递归版本好。

下一个问题是，如何重写它。我有一个经过测试的方法，我知道它有效，我将用不同的版本替换它。显然，我不想用不起作用的版本替换它，那么如何在充分利用现有内容的同时重新编写？

好吧，我知道尾声消除；一种通常由编译器完成的优化，它改变了堆栈的管理方式，以便递归函数最终具有更接近于迭代的属性（从源代码的角度来看它仍然是递归的，但就编译代码的实际方式而言它是迭代的使用堆栈）。

这让我需要考虑两件事： 1. 也许编译器已经在这样做了，在这种情况下，我的额外工作将无济于事。2. 如果编译器还没有这样做，我可以手动采用相同的基本方法。

做出该决定后，我将方法调用自身的所有点替换为对下一次调用不同的一个参数的更改，然后返回开始。即而不是：

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

我们有：

param0 = param0.next;
goto startOfMethod;

完成后，我再次测量。运行该类的整个单元测试现在始终比以前快 13%。如果它更接近我会尝试更详细的测量，但在包含甚至不调用此方法的代码的运行中保持一致的 13% 是我非常满意的。（它还告诉我编译器没有进行相同的优化，否则我将一无所获）。

然后我清理该方法以进行更多对新代码有意义的更改。他们中的大多数让我删除了，goto因为goto确实很讨厌（还有其他地方进行了相同的优化，但由于goto完全重构了而不那么明显）。在某些情况下，我把它留在了，因为 13% 值得打破我心中的 no-goto 规则！

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

决定将优化工作集中在哪里（基于它可能被击中的频率以及我无法预测库的所有用途）
使用一般成本的知识（在大多数情况下，递归成本高于迭代）。
测量而不是依赖于假设以上总是适用的。
从编译器的工作中学习。
了解这一点，因此我可能一无所获——也许编译器已经为我做了。
避免导致代码不可读的优化（重构goto第一遍引入的大部分内容）。

其中一些是观点和风格的问题（离开某些goto人的决定并非没有争议），当然可以不同意我的决定，但了解本文迄今为止提出的观点将使其成为知情的分歧，而不是下意识的。

score 2 · Accepted Answer

除了其他答案中提到的资源之外，Michael Abrash 的Graphics Programming Black Book是学习优化的绝佳读物。虽然有些地方的细节有些过时，但它仍然是学习如何进行优化的重要资源。

任何时候你想优化代码，测量、测量、测量都是绝对必要的。了解优化的最佳方法之一是通过实践——获取一些您想要优化的代码，学习如何使用分析器来衡量其性能，然后进行更改并衡量结果。

optimization - 如何更好地进行优化？

3 回答 3

Related

Reference