性能注意事项

性能注意事项
- 编译期性能
- 运行期性能

C++程序员偏爱性能，所以这里是一个性能专题。由于Hana运行时和编译时计算处于前沿领域，我们不仅对运行时性能感兴趣，而且对编译时性能也感兴趣。由于这两个主题是相当不相交的，我们在下面分别对待。

注意： 当我们推送到存储库时，本节中提供的基准会自动更新。如果您发现不能承受此处声明的结果，请开一个GitHub issue; 它可能是一个性能回归。

警告： 在写这篇文章的时候，并不是所有的Hana容器都经过了优化。实施Hana是一个足够大的挑战，容器最初写成直白的，现在正在严格优化的过程。特别是，关联容器（hana::map和hana::set）由于其朴素的实现而具有相当差的编译时行为，并且它们的运行时行为在某些情况下也似乎是有问题的。改进这种情况是在TODO列表中。

编译期性能

C++元编程带来了它的可怕的东西的份额。与它相关的最恼人和众所周知的问题之一是不可分的编译时间。 Hana声称比前任更有编译时效率; 这是一个大胆的声明，我们现在将尝试回复它。当然，Hana没有创造奇迹; 元编程是C++模板系统的副产品，编译器并不意味着用作某些元语言的解释器。然而，通过使用尖端和强烈的基准测试技术，Hana能够最小化编译器的压力。

注意： 虽然Hana比前C++11元编程库具有更好的编译时间，但是现代库仅支持类型级计算（例如Brigand）可以以通用性为代价提供更好的编译时间。事实上，无论我们如何努力减轻它，Hana的操纵运行时价值的能力都是以编译时的成本。如果你想使用Hana进行密集型类型计算，你应该进行基准测试，看看它是否适合你。

在我们潜水之前，让我快速评论一下用于衡量Hana编译时性能的方法。先前的元编程库通过查看编译器必须执行的实例化的数量来测量它们的元算法和元序列的编译时复杂度。虽然容易理解，这种测量编译时复杂性的方法实际上不给我们有关编译时间的很多信息，这是我们有兴趣在一天结束时最小化。基本上，原因是模板元编程是这样一个扭曲的计算模型，很难找到一个标准的方法来衡量算法的性能。因此，我们不是呈现无意义的复杂性分析，而是对每个支持的编译器上的所有内容进行基准测试，并选择该编译器上最好的实现。还要注意，我们在这里提供的基准是相当精确的。事实上，即使我们不采取多个测量，并采取他们的意思或类似的减少不安，基准是非常稳定的，当他们被再生，这表明一个相当好的精度。现在，让我们潜水。

首先，Hana最小化其对预处理器的依赖。除了在许多情况下产生更干净的错误消息，这减少了头文件的整体解析和预处理时间。此外，因为Hana只支持最前沿的编译器，库中只有很少的解决方法，这导致更干净和更小的库。最后，Hana最小化对任何类型的外部依赖性的依赖。特别是，它只在几个特定情况下使用其他Boost库，并且它不依赖于标准库的最大部分。这样做有几个原因（除了包括时间）;他们被记录在理由。

以下是显示包含不同库所需时间的图表。该图表显示将每个库包含在每个库的（非外部）公共API中的时间。例如，对于Hana，这意味着包含<boost/hana.hpp>头文件，它排除外部适配器。对于其他库，如Boost.Fusion，这意味着包括boost/fusion/目录中的所有公共头文件，但不包括外部库（如MPL）的适配器。

除了减少预处理时间，Hana还使用现代技术以尽可能高的编译时高效方式实现异构序列和算法。在跳转到编译时性能的算法之前，我们将看看创建异构序列的编译时成本。事实上，由于我们将展示用于序列的算法，因此我们必须意识到创建序列本身的成本，因为这将影响算法的基准。下图显示了创建n个异构元素序列的编译时成本。

注意： 您可以通过选择要放大的区域来放大图表。此外，您可以通过在右侧的图例中单击来隐藏一系列点。

基准方法是始终以最有效的方式创建序列。对于Hana和std::tuple，这只是意味着使用适当的make_tuple函数。然而，对于MPL，这意味着创建一个大小为20的mpl::vectorN，然后使用mpl::push_back创建更大的向量。我们使用类似的技术融合序列。这样做的原因是Fusion和MPL序列具有固定的大小限制，并且已经发现这里使用的技术是产生更长序列的最快方式。

为了完整性，我们还提供了创建一个带有n个元素的std::array的编译时成本。但是，请注意，std::array只能包含单一类型的元素，因此我们在这里比较苹果和橘子。正如你所看到的，创建std::array的代价是恒定的，本质上是不存在的（非零开销是简单地包括<array>头文件）。因此，虽然Hana提供了比其他异构容器更好的编译时间，请坚持使用正常的均匀容器，如果这是您的应用程序所需要的;你的编译时间会快得多。

您还可以看到创建序列具有不可忽略的成本。实际上，这是做异构计算的最昂贵的部分，你会在下面的图表中看到。因此，当您查看下面的图表时，请记住仅仅创建序列的成本。还要注意，这里只介绍最重要的算法，但Metabench项目为几乎所有Hana算法的编译时性能提供了微观基准。此外，我们提供的基准比较几个不同的库。然而，由于Hana和Fusion可以使用值，而不仅仅是类型，比较他们的算法和类型的库像MPL不是真的公平。实际上，Hana和Fusion算法更强大，因为它们还允许执行运行时效应。但是，Fusion和Hana之间的比较是公平的，因为两个库都是一样强大的（严格来说）。最后，我们不能显示std::tuple的算法的基准，因为标准不提供等效算法。当然，我们可以使用Hana的外部适配器，但这不会是一个忠实的比较。

元编程中普遍存在的第一种算法是变换。它需要一个序列和一个函数，并返回一个包含将该函数应用于每个元素的结果的新序列。下面的图表给出了将变换应用到n个元素的序列的编译时性能。 x轴表示序列中元素的数量，y轴表示编译时间（以秒为单位）。还要注意，我们在每个库中使用变换等效;我们不使用Hana的转换通过Boost.Fusion适配器，例如，因为我们真的想要基准我们的实现。

在这里，我们可以看到，Hana的元组表现比所有其他的选择。这主要是因为我们使用C++11可变参数包扩展来实现这种算法，这是非常有效的。

在我们继续前，重要的是要提到一些关于融合算法的基准测试方法。 Fusion中的一些算法是惰性的，这意味着它们实际上不执行任何操作，而只是将已修改的视图返回到原始数据。这是fusion::transform的情况，它简单地返回一个变换的视图，将这个函数应用到原始序列的每个元素，因为这些元素被访问。如果我们想对任何东西进行基准测试，我们需要强制对该视图进行评估，最终在实际代码中访问序列的元素时会发生这种情况。然而，对于具有多个层的复杂计算，惰性方法可能产生实质上不同的编译时间简档。当然，这种差异在微基准测试中表现不佳，因此请记住，这些基准测试仅仅是一部分的大局。为了使本节其余部分的完整性，我们将提到Fusion算法是否为惰性，以便您知道何时人为地强制对算法进行评估以用于基准化。

注意： 我们正在考虑给Hana添加惰性的意见。如果此功能对您很重要，请通过评论此问题告诉我们。

第二类重要的算法是折叠。折叠可以用于实现许多其他算法，如count_if，minimum等。因此，折叠算法的良好编译时性能确保这些派生算法的良好的编译时性能，这就是为什么我们只在这里展示折叠。还要注意，所有非monadic折叠变体在编译时间方面有些等同，因此我们只呈现左折叠。下图显示了将fold_left应用于n个元素的序列的编译时性能。 x轴表示序列中元素的数量，y轴表示编译时间（以秒为单位）。用于折叠的函数是一个不起作用的虚拟函数。在实际代码中，您可能会使用非平凡操作进行折叠，因此曲线会比这更糟糕。然而，这些是微基准，因此它们只显示算法本身的性能。

我们在这里提出的第三个也是最后一个算法是find_if算法。该算法难以有效地实现，因为它需要在满足给定谓词的第一元素处停止。出于同样的原因，现代技术并不真正帮助我们，所以这个算法构成了对Hana的实现质量的一个很好的测试，没有考虑到由C++14使用的免费午餐。

正如你所看到的，Hana的性能优于Fusion，以及MPL，但是Hana的find_if也可以与值一起使用，与MPL不同。最后是关于编译时性能的部分。如果你想看到一个我们没有在这里提出的算法的性能，Metabench项目提供了大多数Hana算法的编译时基准。

运行期性能

Hana被设计成在运行时非常有效。但在我们深入细节之前，让我们澄清一件事。 Hana是一个元编程库，允许操纵类型和值，它并不总是有意义，甚至谈论运行时性能。实际上，对于IntegralConstants的类型级计算和计算，运行时性能根本不是一个问题，因为计算的结果包含在一个类型中，该类型是纯编译时实体。换句话说，这些计算仅涉及编译时工作，并且甚至不生成代码以在运行时执行这些计算。讨论运行时性能的唯一情况是在异构容器和算法中操作运行时值，因为这是编译器必须生成一些运行时代码的唯一情况。因此，只有这种计算，我们将在本节的剩余部分进行研究。

就像我们对编译时基准测试一样，用于测量Hana运行时性能的方法是数据驱动而不是分析。换句话说，不是通过对作为输入大小的函数的基本操作的数量进行计数来尝试确定算法的复杂性，而是简单地对最有趣的情况进行测量并且观察它的行为。有这样做的几个原因。首先，我们不希望Hana的算法在大型输入上被调用，因为那些算法用于在编译时长度必须已知的异构序列。例如，如果您试图在100k个元素的序列上调用find_if算法，那么您的编译器会在尝试生成此算法的代码时死机。因此，不能在非常大的输入上调用算法，并且分析方法然后失去很大的吸引力。其次，处理器已经发展成为非常复杂的野兽，你能够挤出的实际性能实际上受控于比你的算法所执行的步骤数量少得多。例如，坏的高速缓存行为或分支误预测可以将理论上有效的算法变成慢速的，特别是对于小输入。由于Hana导致大量展开发生，这些因素必须更仔细地考虑，任何分析方法可能只会让我们认为我们是高效的。相反，我们想要硬数据，和漂亮的图表来显示它！

注意： 就像编译时的性能一样，我们迫使对一些通常是懒惰的fusion算法进行评估。同样，取决于计算的复杂性，惰性算法可能导致产生实质上不同的代码或者使用不同的设计，或多或少。当您查看这些运行时基准时，记住这一点。如果性能对于您的应用程序是绝对关键的，您应该在从Fusion切换到Hana之前和之后进行配置。让我们知道Hana是否更糟糕; 我们会解决它！

有几个不同的方面，我们将要基准。首先，我们显然希望基准算法的执行时间。其次，由于在整个库中使用的按值语义，我们也希望确保最小数量的数据被复制。最后，我们将确保使用Hana不会导致太多的代码膨胀，因为展开，如算法一节中所解释。

就像我们只研究了几个用于编译时性能的关键算法，我们将关注几个算法的运行时性能。对于每个基准方面，我们将比较不同库实现的算法。我们的目标是始终至少与Boost.Fusion一样高效，这在运行时性能方面接近最优。为了比较，我们还显示了与在运行时序列上执行的算法相同的算法，以及在编译时已知其长度但其变换算法不使用显式循环展开的序列。这里提出的所有基准都是在CMake配置中完成的，它配置了合适的优化标志（通常为-O3）。让我们从以下图表开始，其中显示了转换不同类型序列所需的执行时间：

注意： 请记住，fusion::transform通常是惰性的，我们正在强制它的评估为基准的目的。

正如你所看到的，Hana和Fusion几乎是一样的。对于较大的集合数据集，std::array稍慢，对于较大的集合，std::vector明显更慢。因为我们也想要寻找代码膨胀，让我们来看看为完全相同的场景生成的可执行文件的大小：

正如你可以看到，代码膨胀似乎不是一个问题，至少没有一个可以在微基准测试，如这一个。让我们来看看折叠算法，它经常使用：

在这里，你可以看到，每个的表现都差不多，这是一个好的迹象，Hana至少不是让人神经紧绷的东西。再次，让我们看看可执行文件的大小：

这里再次，代码大小没有爆炸。因此，至少对于Hana的适度使用（和Fusion就此事，因为他们有同样的问题），代码膨胀不应该是一个主要关注。在我们刚刚介绍的图表中的容器包含随机生成的int，这是便宜的复制和适合微基准。但是，当我们在一个容器中链接多个算法时会发生什么情况，这些容器的元素复制很昂贵？更一般地，问题是：当一个算法被传递一个临时对象，它抓住机会，以避免不必要的副本？考虑：

auto xs = hana::make_tuple("some"s, "huge"s, "string"s);
// No copy of xs's elements should be made: they should only be moved around.
auto ys = hana::reverse(std::move(xs));

为了回答这个问题，我们将看看基准化上述代码时生成的图表的字符串大约为1k个字符。但是，请注意，对标准库算法进行基准测试并不合理，因为它们不返回容器。

注意： 请记住，fusion::reverse通常是惰性的，我们强制其评估为基准的目的。

如你所见，Hana比Fusion快，可能是因为在实现中更一致地使用了move语义。如果我们没有提供一个临时容器来撤销，Hana不能执行任何动作，两个库也会执行类似的操作：

这就是关于运行时性能的部分。希望你现在确信Hana是为速度而建的。性能对我们很重要：如果你遇到一个场景，其中Hana导致坏代码生成（并且故障不在编译器上），请开一个issue，以便解决问题。