本文提出了performance annotations的概念（性能Metrics是特征Features的函数）。通过插桩、动态分析得到records，通过回归树和混合模型进行建模。

首先，论文提出了probabilistic performance annotations的性能。其本质上是为组件（如methods）标注了可测量的性能指标（如运行时间）与输入的（一个或多个）特征/该组件的状态之间的关系。这里特征可能是参数的值和基于其类型信息的一些相关属性等。然后，作者通过动态分析得到performance annotations。自动识别输入的相关特征，并通过一个合成的统计模型（回归树和混合模型）将这些特征与感兴趣的性能指标联系起来。

Introduction里面关于sort的例子非常有意思。尽管该函数的计算复杂度为O(n logn)，但图1显示运行时间有三种不同的模式：小输入的n log n（尽管它看起来几乎是恒定的），中等输入的线性增加，斜率很高，而大输入的斜率很低。想使用这段代码的程序员怎么会知道这些模式呢？程序员可以在使用之前仔细研究这段代码。但是，除了这将是非常繁重的，并且会失去模块化的大部分好处之外，即使这样做也是不够的：运行时间的中间的一段跳跃并不明显，甚至从代码中也看不到，而是代码与底层内核和内存子系统交互的结果。

在高层次上，我们的方法是这样的。我们将性能数据（例如，CPU时间、内存使用量、锁保持/等待时间等）与函数的参数特征放在一起。然后，我们使用统计分析来建立与输入特征和性能相关的数学模型。我们的模型考虑了各种模式：在std::list::sort的例子中，我们产生了三个模型，每个模式一个。我们将这些模型翻译成有语义的注释语言，程序员可以阅读和理解。这个过程是完全自动化的。

Performance Annotations

Freud Analyzer

一些假设：假设用户拥有被分析软件的领域知识，并选择了他们想要研究的方法。假设代码可以被测量，以确定感兴趣的性能指标，如运行时间、内存消耗、锁保持时间、RPC数量等。许多系统已经提供了相关的工具。如果没有这样的工具，我们可以使用二进制或字节码插桩来添加它。

大概的工作流程如下： Freud使用调试信息对二进制代码进行分析，然后使用Pin来添加插桩，以收集特征和指标。然后，用户用多个输入运行程序，这些输入可能是标准的工作负载，也可能是为了锻炼用户感兴趣的方法而挑选的特殊输入。这些运行的结果是日志文件：每个日志条目都给出了感兴趣的指标值，以及所有的特征。然后，Freud对日志进行统计分析，产生annotation。

Annotation Language

performance annotations是一个表达式，它将性能指标描述为一个随机变量（因变量），其分布是method的输入/状态（自变量）的函数。也就是Y~expr(x)

如果系统无法确定特征和范围之间的关系，它就会产生概率性注释（即一种混合模型）。例如，如果在20%的时间里观察到expr1(x)的性能行为，在80%的时间里观察到expr2(x)的性能行为，那么注释的形式是：Y∼{0.2}expr1(x)；{0.8}expr2(x)。

Derivation of Performance Annotations

Instrumentation

第一步是对代码进行分析和插桩，以收集相关数据。对于每个目标方法的每一次执行，我们收集

所有需要的性能指标
所有可以用来提取输入或系统状态的潜在相关特征的数据
每一个执行的条件性分支指令的结果（采取或不采取分支）

Metric。 metric是performance annotations中的因变量。与传统的剖析器相比，Freud收集了运行时间以外的指标，例如内存占用和锁持有/阻塞时间。此外还可以自定义。

收集性能指标的具体程序因指标和编程语言的不同而不同。例如，为了测量一个方法执行的运行时间，我们可以用代码包装该方法，在该方法的进入和退出点记录时间戳。而要测量堆内存的消耗量，我们可以用代码包装一个方法，测量在某一时刻分配的总内存，就像我们对PHP所做的那样。或者我们可以跟踪对主内存分配函数的所有调用，就像我们对C/C++所做的那样。

Features。 feature是performance annotations中的自变量。与由用户选择的指标不同，Freud为每个目标方法自动选择特征。Freud选择三种类型的特征：程序变量、系统变量和从程序变量计算出来的数字。

第一个和最直接相关的变量是方法的参数。 Freud收集标量变量的值，同时我们也通过遍历指针来提取堆对象的字段值。这种分析依赖于语言，尤其是基于目标方法所处理的对象的类型信息。例如，在C/C++的情况下，Freud使用调试信息来确定数据类型并探索复杂的数据结构。

除了程序中的变量外，Freud还收集系统中存在但不一定在被插桩程序中的信息，如处理器的时钟频率、机器上的活动进程数以及其他系统性能指标。

然后，我们启发式地发现可能影响性能的衍生特征。这些是由一个或多个状态变量或参数的值计算出来的数值。例如，如果我们发现一个对象包含一对名为begin和end、first和last或start和finish的变量，我们会记录一个新的衍生特征，计算为这两个变量之间的差值。经验证实的理由是，这个特征可能代表一个大小，因此可能与性能有很好的关联。

得到的instrumentation logs。每条record包含以下的信息。

id：组件的名称
性能指标yi
原始和派生特征xi
执行第一条分支指令的二进制结果b1,1, b1,2, ...
第二条分支指令的结果b2,1, b2,2, ...
以此类推

Model Selection

第二步就是分析工作。分析工作分两个阶段进行。

在第一阶段，Freud试图制定一个回归树，根据特征（x1, x2, ...）的具体条件对记录进行partition，并在每个分区中拟合一个回归模型。如果部分记录不能用一个足够简单和准确的回归模型，如果不能找到进一步分割这部分记录的条件，那么我们就根据指标值（y，而不是x1，x2，...）对该部分的记录进行聚类。

在聚类之后，无论是对特定的分区还是对整个数据集，我们仍然试图为每个聚类确定一个依赖于特征的模型，以及基于特征值的定义条件。如果这也失败了，我们就求助于每个聚类的更简单的概率表征，我们首先尝试用回归的方法对每个聚类的数据进行建模，然后用一个与输入无关的模型。