安德烈·亚历山德列斯库（Andrei Alexandrescu）是一个真实的传奇人物。 这是对现代编程语言以及广义和元编程技术的历史做出了重大贡献的人。 在现代C ++设计和编码标准101 （由Sutter的杰出C ++徽章编写）以及其他书籍和文章的讨论中，打破了多少份副本。 作为D语言的合著者，他不仅有进行理论化的机会，而且还使自己的梦想成为现实-并且有其独特之处。

现在您掌握了DotNext 2018 Piter会议的报告 ，该会议讨论了现代优化技术。 .NET与它有什么关系？ 这是一个一直在优化自己一生的人的基本报告。 如果性能对您很重要，则需要观看（或阅读本文）。 欢迎来到猫！

标杆管理的艺术

我想与您讨论一些与基准测试相关的主题。 首先，让我们重复一些基本的事情。 阿姆达尔定律是计算机科学经典的一部分，主要用于并行计算，但可在任何复杂的系统中使用。 如果要提高某个系统的性能，则需要从集中该系统主要问题的地方着手。 法律本身是显而易见的：如果某个组件占系统的20％，则仅通过优化该组件的操作就可以实现的系统性能的最大改善是20％。 我常常不得不见到一些诸如优化命令行解析之类的人（当然，我们的读者并不属于他们）。 这些操作需要花费程序的前10微秒，因此人们会分析其算法复杂性，如果时间是二次方，则会感到恐惧。

您可能知道，在开始优化之前，有必要分析应用程序并在其中选择热点。 在这里应该说关于Ladma的法律 （这不是真实的姓氏，而Amdal，倒读）。 您需要将精力集中在最节省时间的组件上。 需要将其移到应用程序外部，执行必要的工作，返回并再次测试。 您需要执行此操作的原因是，性能提高20％通常是十个提高2％的结果。 在大型系统的框架中，不可能衡量出如此小的改进。 为此，必须在测试套件中测试组件。 系统主要组件之一的性能提高20％意味着整个系统提高5％，对于某些领域来说，这是一个极好的结果。 不要忘记优化会产生许多全局影响，因此基于选择性基准测试的结果，在得出关于系统整体运行的结论时应该非常小心。

我确信我们的读者不会犯一个错误，但这通常是很常见的：人们衡量调试组装的速度。 永远不要这样做。 由于蜗牛在比赛中的速度很慢，这类似于感到沮丧：它不是为此类比赛而设计的，它还有人生中的其他目标。 另一个似乎不太明显的错误：人们首先测量系统的基本性能，然后立即执行基准测试。 但是在收集了基准之后，许多资源被预热了。 例如，打开的文件被缓冲并保留在内存中（至少在Linux下）。 因此，第二个测试只会更快，因为它是在第一个测试之后启动的。 即使使用malloc调用也会发生这种情况。 这些调用之后，即使进行了内存释放调用，系统也不会返回到其原始状态。 内存分配器使用的内部配置，缓存和功能允许以下malloc调用运行得更快。 即使不考虑缓存的影响，malloc也会记住，例如，某些函数多次为4 KB的对象分配内存，这意味着您需要有一个4 KB元素大小的空闲列表。 或另一个示例：DNS查询在第一个查询后被缓存以供重用。 如果可能，在基准测试期间，您需要每次从头到尾重新启动整个过程。

例如，为了使系统完全恢复到原始状态，就文件而言，它们需要在单独的磁盘上打开，在测试结束后需要将其删除（据我所知，可以在Windows下完成）。 该操作并不容易，但是在大多数情况下是必需的。

继续讨论优化过程中的错误，我不得不处理将printf的成本包括在测试结果中的情况。 在每次测量之前更改一项以上的事情时，会出现程序错误，这违反了科学实验的最基本原理，因为不清楚您要测量哪种效果。 另一个严重的错误是对一些罕见的案例进行了优化，从而导致了其他情况下的悲观化。



这是堆栈溢出的示例。 作者经常对已经排序的数据进行排序并感到惊讶，因为“ is_sorted”函数显然比“ sort”要快得多。 如果is_sorted返回，为什么在sort中第一行不是呢？ 您正在优化一个极其罕见的案例，即已完全排序的数据，并且其他每个拥有至少一个未排序元素的人都将承担此优化的费用。 这不值得做。

我想我不必长时间证明当今竞争的架构非常复杂：动态频率变化，其他进程中断，虚拟化等。 因此，几乎不可能在测量时获得相同的时间，您的指标将总是颤抖。 因此，不应依赖看似显而易见的事物。 说，对我们来说似乎显而易见的是，更少的指令意味着更快的代码，而这并不总是正确的。 似乎使用存储的数据似乎总是比重新执行计算更快，因此，如果缓存结果，就可以了。 与前面的情况一样，它不能被明确地陈述，就像不能无条件地陈述相反的情况一样-这都取决于上下文。 显然，您应该只有一件事：一切都需要度量。 如果您进行所有测量，那么与不进行测量的有知识的专家相比，您将获得更好的结果。

有许多相当可靠的实践，对它们的讨论可能会使您产生有趣的想法。 我们必须从数学不会让您失望的事实开始。 它可以显示具有不同速度的系统是等效的。 数学给出规则以显示某些事物的等效性并确定某些属性，尽管它没有偏见，但哪些事物有趣和哪些不有趣无关紧要。 许多人认为优化是基于对机器代码的了解并使用位来进行的，但是实际上它具有很多数学运算，因为您证明了速度更快的系统与速度较慢的系统等效。

另一个普遍的规则是，计算机喜欢无聊的事情。 您是否需要将两个向量相乘，每个向量有十亿个元素？ 对于计算机而言，这是一项理想的任务，计算机中的所有设备都针对此类任务进行了特别的锐化。 为了分析这些数据，基于它们构建一个正则表达式-我不想这样做。 简而言之，计算机不喜欢分支，依赖项，间接调用之类的东西，它们不喜欢智能代码，而喜欢无聊的代码。 计算机不喜欢间接记录-涉及铁的人们长期苦苦挣扎且无法解决的复杂问题。

另一个规则是，您应该优先选择功能最弱的运算，换句话说，应该优先选择除乘法之外的其他运算，而不要对乘法求幂。 同样，数学在这里很有用。

最后，最后一条法则-越小越漂亮。 较小的尺寸使计算机可以最好地实现其优势，因为它们希望数据（尤其是指令）彼此靠近。 几次测量应用程序速度的结果将始终不同，您将获得一些分布的结果。 通常我们只取这几个结果的平均值。 但是问题在于，由于计算机的特性，平均水平会包含很多噪音。 当比尔·盖茨乘坐公共汽车时，平均而言，公共汽车上的每个乘客都是亿万富翁。 听起来不错，但对于无家可归的人乘坐同一辆公交车来说，舒适度却很小。 中断也会发生类似的情况：乘法运算需要十亿分之一秒，但是当您对此类运算进行多次测量时，其中之一将不可避免地产生两毫秒的中断。 差异为三个数量级，但是，开发人员并不总是将其考虑在内。

因此，我再说一遍：计算机中的噪声总是相加的。 对于人们来说，这似乎微不足道，但是对于微基准测试而言，它却很重要，并且算术平均值将包含很多噪声。 而不是平均值，您需要一个指标，该指标仅衡量您可以以某种方式影响的时间。 如果我们从数学的角度解决这个问题，我们将发现我们需要找到一个与我们已进行的最大测量次数相对应的值。 换句话说，我们需要一个mod。 这立即给我们带来了问题：如果您使用quicksort mod，会发生什么？ 如果算法是概率性的，或者数据是随机的，则几乎永远不会流行。 在整个光谱范围内，值的密度几乎相同。 在这种情况下，我们只舍弃最大测量值的5％，然后取平均值或最大值，在后一种情况下，我们将有一个在95％的情况下不会超过的上限。 几乎总是有一个主题坐在旧的地下室里，并装有慢速调制解调器，每页将加载一个小时。 我们当然是纯人类的，对他表示同情，但我们不能从技术上帮助所有人-因此，其余5％的案件必须忽略。 通常，在解决网络问题时，我们通常关注第95个百分位数，因为不可能关注第100个百分位数。 百分位表示所有收集的测量中最慢的结果-这不是提供信息。

用算术替换分支

我希望如何清楚地表明测量并非易事。 让我们看一些示例，首先尝试用算术替换分支。 我们正在谈论需要if语句的情况，但是过分使用是不理想的。 相反，我们会将分支结果积分为0/1值。 该代码看起来是线性的，计算机只需要从头到尾遍历它，而无需考虑下一步需要采取什么步骤。

让我们尝试解决以下问题：将数组每个四分位数的低点转移到第一个四分位数。 换句话说，必须将数组分为四个部分，每个部分的最小值应放置在数组的开头。

static void min4(double[] p) { int n = p.Length; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < n / 4; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } } 

以上是基本代码。 顺便说一句，我可以自豪地报告我将这些示例转换为C＃，并且它们已成功编译。 代码本身非常简单：为m分配了位于索引i和j处的两个值中最小的索引，然后根据其他两个索引将相似的分配再重复两次。 最后，数组中的索引m的值与索引i的值相反。 如您所见，我们使用四个归纳变量绕过数组。

测试这样的算法的问题将是有趣的并且不是显而易见的。 我们将不需要对一个数据集进行测试，而是对各种情况下可能出现的数据进行测试。 例如，对于看起来像器官管的数据：首先增加，然后减少； 具有均匀分布的随机数据； 在零和一的随机集合上-从这里的随机数据中得出的区别是将有许多重复值； 根据已经排序的数据； 最后，是通过对某些物理现象的真实测量获得的数据。 这将是衡量算法速度的一种严肃方法，并且在研究算法的人们中普遍接受。

让我们尝试改进刚刚遇到的代码。

 static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < q; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } } 

作为第一个优化，我们将尝试避免过多的重复操作，为此，我们从循环中取出了几个除法运算-将n除以2和4，然后将3 *`n除以4。但是在此优化之后，我们发现计算并非针对我们遇到的主要问题是：尽管代码会更紧凑，但不会变得更快。 在最好的情况下，我们将实现百分之五的改善。

 static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = q, k = 2 * q, l = 3 * q; for (; i < q; ++i, ++j, ++k, ++l) { int m0 = p[i] <= p[j] ? i : j; int m1 = p[k] <= p[l] ? k : l; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } } 

我们将对代码进行的第二个更改是减少依赖关系。 在该算法的先前版本中，将m分配给k或l取决于上面分配给m行的值。 为了减少`m个依赖项的数量，我们分别计算`m0和`m1，然后进行比较。 当我执行此优化时，我希望算法的速度得到显着改善，但最终结果却是零。 但是，我认为将依赖项的数量保持在最低限度很重要，因此我保存了代码。

 static void min4(double[] p) { int q = p.Length / 4; for (int i = 0; i < q; ++i) { int m0 = p[i] <= p[i + q] ? i : i + q; int m1 = p[i + 2 * q] <= p[i + 3 * q] ? i + 2 * q : i + 3 * q; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } } 

现在让我们尝试将归纳变量的数量从四个减少到一个，并且我们将算术计算剩余的三个，因为它们彼此之间是恒定的关系。 这很简单：我们将得到i + q而不是k，而不是其他两个变量i + 2 * q和i + 3 * q。 我也对该优化抱有很高的期望，但是，与上一个优化一样，它没有及时给出任何结果。 这再次证明了测量的重要性：没有测量，我可以夸耀自己已经大大改善了算法的操作，并且我将有非常重要的观点。

 static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2: ++i) { int m0 = p[i - q] < p[i] ? i - q : i; int m1 = p[i + q2] < p[i + q] ? i + q2 ? i + q; Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } } 

作为第四次尝试，我们重构了循环以消除乘以3。这将使我们提高3％。 结果仍然不令人满意。 接下来，尝试摆脱三元运算符。

 // Returns: value if flag is true, 0 otherwise static int optional(bool flag, int value) { return -Convert.ToInt32(flag) & value; } 

为此，我想向您介绍一个新功能-静态int可选（布尔标志，int值）。 它将输入布尔值转换为Int32，乘以-1，并将其与第二个输入值一起传递给按位AND运算符。 如果输入标志为false，则在int32中它将为0，并且在所有输出转换之后，我们仍将为0。如果输入标志为true，则在int32中将为1，当乘以-1时，我们得到FFFFFFFF，在位之后任何数字的“和”将给出第二个数字。 请注意，在任何地方都没有if语句，代码没有分支，这对计算机很无聊（尽管对我们来说似乎很复杂）。

 static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2; ++i) { int m0 = i - optional(p[i - q] <= p[i], q); int m1 = i + q + optional(p[i + q2] < p[i + q], q); Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } } 

我们将使用此可选函数替换三元运算符，并将其集成到计算中。 我们将其应用两次，在第三种情况下，留下问号。 因此，在这个周期中，我将只进行一次检查，而不是四次检查。



从幻灯片上看到的测量结果可以清楚地看出，在几个不同的数据集上测试算法的重要性。 一方面，我们什么都不懂。 在随机数据和真实数据上，我们的加速度超过两倍，在器官管和分类数据上，我们的速度略有下降。 这是由于以下事实：对于过渡预测变量的排序数据不会有任何意外，它将以100％的准确性进行预测。 对于风琴管，我们将在数据集的中间有一个错误的预测-再次是非常高的准确性。 相反，对于随机数据，我们两种方法之间的差异将是巨大的。 我们用简单的逻辑替换了所有不可预测的支票。 在这里，我们回到一个简单的道理：顾名思义，计算机是为计算而设计的（计算机-计算）。 分支，在屏幕上显示图像-所有这些都使它们表现得差得多。 对它们执行按位“与”要比传递if语句简单得多。

 static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = 0; i < q; ++i) { int m = i + optional(p[i + q] < p[i], q); m += optional(p[i + q2] < p[m], q); m += optional(p[i + q2 + q] < p[m], q); Swap(ref p[i], ref p[m]); } } 

通过优化最终获得了积极的结果，我们将尝试用我们的可选函数替换最后一个三元运算符。 这次，速度增益将很小。 要了解为什么会发生这种情况，您需要查看生成的代码。 在以前的代码版本中，问号仍然存在，编译器已经找到了一种无需分支即可执行代码的方法。 当他到达三元运算符时，他已经可以预测它了。 用`optional代替最后一部分会产生更糟糕的代码。 因此，我重复一遍，每次都要进行测量很重要。

 // Returns: v1 if flag is true, v2 otherwise static int ifelse(bool flag, int v1, int v2) { return (-Convert.ToInt32(flag) & v1) | ((Convert.ToInt32(flag) - 1) & v2); } 

我想向您推荐的另一个功能是“无分支的无痕”，您现在可以在屏幕上看到它。 是的，在我们的示例中，我无法用它来实现性能改进。 如果将0作为标志传递给它，则第一行将为0；否则为0。 在第二个步骤中，我们在Int32中从0中减去1并得到FFFFFFFF，此后将这个值与函数参数v2一起传递给按位“与”，这将使我们本身无需更改就可以了。 最后，第一和第二行传递给按位“ OR”，这将再次给我们v2。 如果标志为1，则第一行将等于`v1; 在第二个步骤中，我们从1中减去1并得到0，结果整行将为0，0和按位“或”中的v1将得出v1。

我希望这样一个没有分支功能的“精简版”会引起后端人员的兴趣-目前，现代编译器出于某种原因不使用这种方法。 使用这些功能，您可以重新组织算法，以便编译器为您理解它们，因为您比编译器更聪明，更有创造力。

大集合路口

稍微改变我们谈话的主题，然后转到大集合的交集。 到目前为止，我们一直在讨论单个运算符，现在我们将创建新的算法，因此我们将需要从细节上转移注意力，并开阔视野。 我假设您熟悉合并排序，将两个向量相乘以及搜索两个排序向量的公共元素。 遍历两个排序的集合，当其中包含相等的元素时，这被视为匹​​配。 如果要比较的两个元素之一较小，则会发生变化。 该算法非常简单，但是却很常见-很可能是世界上使用最广泛的算法。 它用于所有来自几个单词的查询，每个这样的查询都是两个集合的交集。 特别是，此算法使用Google，并且还应将其应用于所有数据库查询中。

 int Intersect(double[] a1, double[] a2, double[] t) { if (a1.Length == 0 || a2.Length == 0) return 0; int i1 = 0, i2 = 0, i = 0; for (;;) if (a1[i1] < a2[i2]) { if (++i1 == a1.Length) break; } else if (a2[i2] < a1[i1]) { if (++i2 == a2.Length) break; } else { t[i++] = a1[i1]; if (++i1 == a1.Length || ++i2 == a2.Length) break: } return i; } 

看一下该算法的基本实现。 如果两个输入集都为空，则显然返回0。接下来，我们开始一个无限循环，如果有匹配项，则将结果加1，并检查循环是否应完成。 代替无限循环，可以使用for语句并指定结束循环的条件。 但这将意味着额外的工作。 在幻灯片中看到的实现中，在第一个分支中有`if（a1 [i1] <a2 [i2]），此后i1增加1，我们只能检查`i1。 同样，在第二个分支中，我们只需要检查`i2。 这两个值仅需要在第三分支中检查。 如果此检查是在周期开始时进行的，那么我们将做额外的工作。

让我们尝试改进此实现。 目前，它的算法复杂度是线性的，取决于两个输入参数。 在机器学习中，很多时候必须找到在大小或统计上彼此非常不同的集合的交集。 例如，您要检查一个长输入向量和一个短特征向量。 在我们的代码中，`a1中可以有一百万条记录，而`a2中可以有一千条记录。 在这种情况下，我们还不准备通过一百万步来完成此算法。 这里最大的负载将在以下代码行上：`if（++ i1 == a1.length）break。 在此之前，将进行比较，然后在此行中增加值； 从本质上讲，这是线性搜索。 我们遍历一个长向量以寻找一个短向量。 在最坏的情况下，我们将沿着向量缓慢执行许多此类搜索。

让我们尝试改进此算法。 好吧，如果不是线性搜索，那么二进制更好，对吗？ 让我们使用二进制。 它的优点是它给出较小元素中最大的索引。

 int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, a1[i1]); if (m == a2.Length) continue; --m; if (!(a2[m] < a1[i1])) t[i++] = a1[i1]; } return i; } 

上面的代码是我们的二进制搜索算法的实现。 但这不是很有效。 最糟糕的情况是二进制搜索每次都失败。 它将在非常重要的场景中出现-例如，当两组相同时。 您就像傻瓜一样，用二进制搜索切出圆，而您只需要经历第一个线性算法即可。 为什么要进行二进制搜索，何时需要的项目-每次都在列表中的第一个位置？

如何使算法在相同和不同的数据上成功工作？ 检查所有数据对于资源来说太昂贵了。 我会保留一点，即这不是关于完全相同的数据，而是关于非常相似的数据，具有相似的统计信息，大小也可能有所不同。 您可以检查以下几项。 显而易见的解决方案是减少搜索。 当我们执行二进制搜索时，找到了一些元素后，我们不再对小于它的元素感兴趣，因为第二个向量也已排序。 因此，我们每次都可以缩小搜索范围，从找到的元素中减少所有元素。

 int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i2 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, i2, a2.Length, a1[i1]); if (m == i2) continue; if (!(a2[m - 1] < a1[i1])) t[i++] = a1[i1]; i2 = m + 1; } return i; } 

这是此方法的实现。 您会看到我们每次都对原始数组的一部分执行二进制搜索，这些数组以i2开始，以a2.length结尾。 由于每次搜索都会增加i2，因此搜索区域将减小。

我想在此处实现的下一个优化与奔腾搜索算法有关。 本质上，这是一个二进制搜索，但步骤不同。 对于二进制搜索，我们每次都从中间开始-但是让我们想一想，当我们在电话簿中查找名称时，我们是不是在中间打开它？ 如果某人的姓氏开头，例如在“ B”上，我们将在更接近开头的位置打开这本书。 在快速搜索中实现了这一原理：在每次检查之后，我们以递增的方式开始对数据进行升序爬取：首先是1，然后是2，然后是4。这给我们带来了很好的算法复杂性。 如果步长线性增长，那么复杂度将是二次的。 当我们“跳过”要查找的元素时，我们将对剩余的段执行常规的二进制搜索，该搜索将很小并且不会显着影响算法的执行时间。 因此，我们结合了两种方法的所有优点。 这种算法的实现：

 int GBsearch(double[] a, int i, int j, double v) { for (int step = 1;; step *= 2) { if (i >= j) break; if (a[i] > v) break; if (i + step >= j) return Bsearch(a, i + 1, J, v); if (a[i + step] > v) return Bsearch(a, i + 1, i + step, v); i += step + 1; } return i; } 

现在我们讨论缩放，即尝试查找两个以上集合的交集。 对于每个单词的搜索，我们将需要找到几个集合的交集。 为此，例如，我们可以比较前两个集合，然后将它们与第三个集合相交，依此类推。 但这不是最佳解决方案。 我们需要采用所有集合的第一个元素，并找到其中的最小元素，然后将其移动。 我们需要一个数据结构，该结构允许我们找到许多元素中的最小元素并具有恒定的复杂性。 这样的数据结构是一堆。 但这将是一堆奇怪的东西，它不会基于物理阵列。 这将是虚构的，我们将在其中仅组织布景的最初元素。 一旦找到堆中最小的元素，我们仍然可以搜索所有其他集合。

我们今天在实践中讨论的主题的工作具有相当手工的形式。 实际上，我们通常会有几套，而不仅仅是两套，关于此主题的工作很多。 这里的经典算法是SVS，其中我们对集合进行分组，取最小的两个，然后选择最短的作为候选。 在这里您可以找到有关此主题的良好概述。 与相交集，稀疏向量的标量积，通过合并进行排序以及随时间推移与图像进行任何形式的比较相关的问题变得越来越有趣。 我向您展示的算法已经证明它非常有用。 谢谢您的关注。

安德烈·亚历山德列斯库（Andrei Alexandrescu）不会参加2018年莫斯科DotNext会议，但杰弗里·里希特（Jeffrey Richter），格雷格·扬（Greg Young），帕维尔·约瑟夫维奇（Pavel Yosifovich）等人将出席。 演讲者的姓名和报告主题可在此处找到，票证在此处 。 立即加入！