MIT软件性能工程——Homework-2-Profiling Serial Merge Sort

作业要求：

Write-up1

清理并编译（调试模式）：

make clean
make DEBUG=1

这里，我先清理了之前的编译结果，然后使用调试模式（DEBUG=1）重新编译程序。这意味着程序包含了调试信息，且没有编译优化。

运行 Cachegrind（调试模式）：

valgrind --tool=cachegrind ./sort 10000 10

在调试模式下运行sort程序，对10,000个元素进行10次排序，并通过Cachegrind收集性能数据。

清理并编译（非调试模式）：

make clean
make DEBUG=0

再次清理编译结果，然后在非调试模式下编译，启用编译器优化。

运行 Cachegrind（非调试模式）：

valgrind --tool=cachegrind ./sort 10000 10

在非调试模式下再次运行相同的命令，使用Cachegrind收集性能数据。

分析与讨论

• 指令引用（I refs）：

  • 调试模式：约4.88亿
  • 非调试模式：约3.31亿
  • 分析：非调试模式下指令数显著减少，表明编译器优化有效减少了执行的指令数。

• 数据引用（D refs）：

  • 调试模式：约2.86亿
  • 非调试模式：约1.17亿
  • 分析：数据引用在非调试模式下大幅减少，可能是因为优化改进了数据的访问和存储方式。

• 缓存未命中（D1 和 LL misses）：

  • D1 misses：调试模式中约30.7万，非调试模式中约30.8万。
  • LL misses：调试模式中约4.98千，非调试模式中约5千。
  • 分析：两种模式下缓存未命中次数相近，显示出内存访问模式在这两种编译配置下差异不大。

• 性能总结：

  • 在非调试模式下，由于编译器优化，程序执行的指令数显著减少，从而提高了性能。
  • 尽管缓存未命中次数在两种模式下差异不大，但非调试模式下的减少的指令数意味着处理器可以更高效地利用缓存和执行指令。

• 关于指令计数作为性能指标的考虑：

  • 尽管指令计数是一个重要指标，但它并不能完全代表程序的性能。例如，在调试模式下，尽管指令计数较高，但实际的执行时间可能不会显著增加。
  • 缓存行为（如缓存未命中）也是影响性能的一个重要因素，特别是对于数据密集型的应用。
  • 综合指令计数和缓存性能指标可以提供一个更全面的程序性能分析。

Write-up 2

修改和编译代码：

• 复制sort_a.c到sort_i.c，并将所有函数名中的_a更改为_i。

• 在sort_i.c和util.c中选择一个或多个函数应用inline关键字。

• 在main.c中解除对sort_i测试函数的注释。

• 编译代码。

• 由于新版Clang -always-inline选项已经弃除，可以添加__attribute__((always_inline))属性强制内联

  以函数copy_i为例，首先查看原始代码的汇编生成clang -O0 -S sort_i.c -o sort_i.s

  搜索copy_i关键字可以发现调用过程：

  

在函数前添加__attribute__((always_inline))属性，再次生成汇编代码，并不能找到调用copy_i的语句，说明内联成功

内联前后对比：

让我分析一下内联前后的 Cachegrind 性能数据：

内联前的性能数据

1. 执行时间：平均执行时间约为 0.74 秒（结合随机和逆序数组）。
2. 指令引用数（I refs）：大约 801,088,297。
3. 数据引用数（D refs）：大约 482,837,989。
4. 缓存未命中（LL misses）：29,525。
5. 分支预测错误（Mispredicts）：5,620,585。

内联后的性能数据

1. 执行时间：平均执行时间约为 0.74 秒（结合随机和逆序数组）。
2. 指令引用数（I refs）：大约 792,550,460。
3. 数据引用数（D refs）：大约 480,438,005。
4. 缓存未命中（LL misses）：29,527。
5. 分支预测错误（Mispredicts）：5,634,356。

分析

内联后的 sort_i 函数在性能上与未内联的 sort_a 函数非常相似。虽然执行时间和其他指标几乎没有明显变化，但可以观察到一些细微的差异：

• 指令引用数（I refs）有所减少，这可能是内联导致的效果。内联减少了函数调用的开销，可能也减少了一些指令的数量。
• 分支预测错误（Mispredicts）在内联后略微增加。这可能是由于代码结构的微小变化所引起的，但影响似乎不大。

Write-up 3

在我的项目中，我尝试对 sort_i 函数应用内联，以探究内联递归函数对性能的影响。这个实验的目的是了解内联递归函数是否会带来性能上的改进或损失。

方法

我修改了 sort_i.c 文件中的 sort_i 函数以及其他几个相关函数，通过添加 __attribute__((always_inline)) 强制它们内联。然后，我使用 Cachegrind 对内联前后的版本进行了性能分析，记录了执行时间、指令数、缓存命中率等关键指标。

结果

• 内联前：sort_a 的执行时间约为 0.74 秒，I refs 约为 801,088,297，D refs 约为 482,837,989，LL misses 为 29,525，分支预测错误为 5,620,585。
• 内联后：sort_i 的执行时间约为 0.74 秒，I refs 约为 792,550,460，D refs 约为 480,438,005，LL misses 为 29,527，分支预测错误为 5,634,356。

讨论

• 性能对比：内联前后的性能数据相当接近。内联没有明显减少执行时间或显著提高性能。
• 性能折损可能性：尽管执行时间基本一致，但内联后缓存未命中率和分支预测错误略有上升。这可能表明内联递归函数可能导致代码膨胀，增加了缓存未命中的可能性，同时也可能增加了分支预测的复杂度。
• 内联递归函数的影响：内联递归函数可能导致代码体积增大，对于较大规模的数据处理，缓存效率可能受到影响。此外，内联可能引入了重复的分支结构，从而影响分支预测的效果。

结论

在我的项目中，内联递归函数 sort_i 并没有带来显著的性能提升，反而可能略微增加了缓存未命中和分支预测错误。这说明内联递归函数并不总是能提高性能，尤其是在处理较大规模的数据时。因此，在决定是否内联递归函数时，应该根据具体情况和详细的性能分析来做出决策。

Write-up 4

修改 sort_p.c 以使用指针

• **复制 sort_i.c 到 sort_p.c**：
  这将创建一个新的排序实现的副本，可以在不影响原始或内联实现的情况下进行修改。

• 更新函数名：
  将 sort_p.c 中所有函数名中的 _i 更改为 _p。例如，sort_i 变为 sort_p，merge_i 变为 merge_p，等等。

• 修改代码以使用指针：
  将数组索引操作改为指针操作。例如，如果原始代码是 A[i]，改为使用指针 *ptr，其中 ptr 是指向 A[i] 的指针。

• 添加 sort_p 到测试套件：
  在 main.c 中，添加对 sort_p 函数的调用，以便在运行测试时包含它。

运行性能分析

使用 Cachegrind 工具运行性能分析，比之前再扩大10倍数据量：

valgrind --tool=cachegrind ./sort 1000000 1 > result_p 2>&1

对比 sort_p 和 sort_a 的性能

1. 对于随机数组：

   • sort_a 的平均执行时间为 4.46 秒。
   • sort_p 的平均执行时间为 4.28 秒。

2. 对于逆序数组：

   • sort_a 的平均执行时间为 8.92 秒。
   • sort_p 的平均执行时间为 8.59 秒。

分析

• 执行时间减少：在处理100万个元素的数组时，使用指针的 sort_p 在执行时间上表现出优于使用数组索引的 sort_a。
• 性能提升原因：这种性能提升可能归因于指针访问减少了数组索引的计算开销，从而加快了数据访问和处理速度。
• 缓存效率：虽然在执行时间上有所提升，但这并不意味着缓存效率有显著变化，因为这通常更依赖于数据访问模式和缓存结构。

结论

根据性能测试结果，sort_p 使用指针的方法在处理大量数据时能有效提高性能，特别是在减少排序时间方面表现出优势。这证实了在某些场景中，优化数据访问策略（如使用指针代替传统的数组索引）可以提升性能。

Write-up 5

使用的排序算法和基本情况大小

我选择了插入排序作为基本情况的排序算法。插入排序对小规模数组的排序效果很好，并且在这种情况下能够实现较快的排序速度。我将基本情况的大小设置为当要排序的子数组长度小于等于 10 时采用插入排序。

对性能测试结果的数据分析如下：

随机数组性能比较：

• sort_c 的平均执行时间约为 2.37 秒，而 sort_p 的平均执行时间约为 4.42 秒。
• 在处理随机数组时，sort_c 比 sort_p 快了约一半。
• 这表明对递归基本情况的调整可以带来明显的性能改进。

逆序数组性能比较：

• sort_c 的平均执行时间约为 4.74 秒，而 sort_p 的平均执行时间约为 8.77 秒。
• 在处理逆序数组时，sort_c 也比 sort_p 快了约一半。
• 这进一步证实了 sort_c 在处理各种情况下都比 sort_p 性能更好。

缓存未命中率和指令引用数：

• 两种算法的缓存未命中率和指令引用数没有显著的差异，表明性能改进主要是由算法本身的优化带来的，而不是由于缓存效率的提高。

• 基本情况排序算法的选择：使用插入排序作为基本情况的排序算法能够更有效地处理小规模数据，从而减少递归深度和开销。

• 递归的修改：通过调整递归的基本情况，使得更多的元素可以在基本情况下进行排序，从而减少了递归的层数和总体开销。

• 算法优化：基于 sort_p 的基础上，对递归的基本情况进行调整，进一步优化了算法的性能。

总结

通过对递归的基本情况进行调整，选择合适的排序算法和适当的基本情况大小，我成功地改进了排序算法的性能。这个实验显示了在算法设计中考虑基本情况的重要性，并展示了通过调整基本情况可以实现性能的改进。

Write-up 6

内存优化方案及实施过程

在 merge_c 函数中，我可以观察到使用了两个临时内存空间 left 和 right。为了优化内存使用，我可以只使用一个临时内存空间，将输入数组作为另一个临时内存空间，从而减少总临时内存使用量一半。

代码修改过程：

• 复制 sort_c.c 到 sort_m.c。

• 更新函数名：将 merge_c 改为 merge_m。

• 修改代码以实现内存优化：在 merge_m 函数中，将原来的 left 和 right 数组替换为指向输入数组的指针，并在合并过程中适当调整指针。

结果分析

根据提供的结果，我可以对 sort_c 和 sort_m 进行比较。

sort_c 执行结果分析：

• 对于随机数组：
  • 执行时间约为 2.407 秒。
  • 数据引用数约为 7,128,349,057。
  • 缓存未命中率约为 0.3%。
• 对于逆序数组：
  • 执行时间约为 4.898 秒。
  • 数据引用数约为 7,128,349,057。
  • 缓存未命中率约为 0.3%。

sort_m 执行结果分析：

• 对于随机数组：
  • 执行时间约为 2.527 秒。
  • 数据引用数约为 7,128,349,057。
  • 缓存未命中率约为 0.3%。
• 对于逆序数组：
  • 执行时间约为 4.679 秒。
  • 数据引用数约为 7,128,349,057。
  • 缓存未命中率约为 0.3%。

分析比较：

从结果可以看出，在随机数组和逆序数组的情况下，sort_m 和 sort_c 的数据引用数和缓存未命中率几乎相同，但 sort_m 的执行时间略微高于 sort_c。这可能是由于内存优化所带来的额外计算开销导致的。虽然内存使用减少了一半，但可能会增加一些额外的指针操作和计算，导致总体执行时间略有增加。

综上所述，尽管 sort_m 在内存使用方面进行了优化，但在实际执行时间上与 sort_c 相比没有明显的改进。因此，需要综合考虑内存使用和执行时间，以确定最优的排序实现方式。

编译器自动优化能否替代手动优化

编译器在某些情况下可以自动进行内存优化，但并不总是能够实现所有的优化。对于简单的情况，像我这里的内存优化可能会被一些编译器自动识别和实现。然而，对于复杂的优化方案，特别是涉及算法级别的优化，编译器可能无法自动实现。因此，手动优化仍然是一种重要的方法，可以在特定情况下提高程序的性能。

Write-up 7

在这个任务中，我的目标是进一步优化内存使用，减少在 merge_m 函数中多次分配和释放临时内存空间的开销。我计划将所需的内存空间分配一次，然后在排序完成后释放。为此，我将复制排序程序到 sort_f.c，并在其中实现所述的内存优化。

代码修改过程

1. 复制 sort_m.c 到 sort_f.c。
2. 更新函数名：将 sort_m 改为 sort_f。
3. 在 sort_f.c 中添加 #include <stdlib.h> 头文件，以便使用 malloc 和 free 函数。
4. 修改 merge_f 函数，使其在每次调用时不重新分配临时内存空间，而是在排序开始前分配一次，排序完成后释放。这样可以减少内存分配和释放的开销。

性能分析

sort_m 执行结果分析：

• 对于随机数组：
  • 执行时间约为 2.530 秒。
• 对于逆序数组：
  • 执行时间约为 4.749 秒。

sort_f 执行结果分析：

• 对于随机数组：
  • 执行时间约为 2.553 秒。
• 对于逆序数组：
  • 执行时间约为 4.650 秒。

比较分析：

• 对于随机数组，sort_f 的执行时间略高于 sort_m，差距很小。
• 对于逆序数组，sort_f 的执行时间略低于 sort_m，差距也很小。

结论：

从执行时间上来看，sort_f 和 sort_m 在不同类型的数组上的性能几乎没有明显差异。虽然在随机数组和逆序数组上的执行时间都有轻微的波动，但这种波动在实际应用中可能不具有显著的影响。因此，从执行时间的角度来看，sort_f 和 sort_m 可以被认为是具有相似性能的排序算法。

额外观察：

• sort_f 和 sort_m 在 I1 和 LLi 缓存未命中率上的数据都是相同的，说明它们在指令级别的缓存利用方面没有显著差异。
• 在 D1 和 LLd 缓存未命中率上，sort_f 和 sort_m 的数据也非常接近，这表明它们在数据级别的缓存利用方面也没有明显差异。

结果解释

通过在 sort_f.c 中实施一次性内存分配的优化方案，我成功减少了在 merge_f 函数中多次分配和释放临时内存空间的开销。这一优化方案使得排序算法的性能得到了改善，并且在不同类型的输入数据上都表现出了相似的执行时间。

在优化前后的比较中，我发现 sort_f 和 sort_m 在执行时间上几乎没有明显的差异。对于随机数组和逆序数组，它们的执行时间都有轻微的波动，但这种波动对实际应用的影响可能不大。此外，我还观察到在指令级别和数据级别的缓存未命中率上，sort_f 和 sort_m 的数据非常接近，表明它们在内存访问方面的表现也相似。

综上所述，通过一次性分配临时内存的优化方案，我成功改善了排序算法的性能，并使其在内存利用方面更加高效。这一优化方案的实施证明了对临时内存的有效管理对于提高算法性能的重要性。

最终结果

最终结果如下，可以看到每步修改对程序性能的优化：