为什么要量化分析；

image-20231108104449383

  • 为什么要量化分析：量化才能分析
    摩尔定律，HPC TOP500

  • 软件属性重要性排序：很多属性比性能更重要
    image-20231108104644008

    • 性能是计算的货币。你通常可以通过性能“购买所需的属性

  1. 早期程序设计，受限于机器资源

    • 程序必须依照机器来规划

    • 如果没有认真的进行性能工程，许多程序将无法“适应”

  2. 摩尔定律继续提高计算 机的性能
    但是现在性能看起来像 具有复杂的缓存结构、 宽向量单元、GPU、 FPGA等的巨大的多核 处理器
    通常，必须调整软件以 有效地利用硬件!

案例：矩阵乘法

  1. 不同编程语言：python，Java，C：解释型和编译型
  2. 循环，i,j,k的顺序： 空间局部性，cache命中
  3. 编译器优化：
  4. 多核并行性：并行循环：cilk_for
  5. 数据重用：数据分块： 矩阵分块（Tiling) : 增加cache hit
  6. 多级缓存分块
  7. 递归进行矩阵乘法：并行分块
  8. 向量硬件：向量化编译技术
  9. 人工AVX Intrinsics优化
  10. Intel MKL: 专业数学库

宾利优化规则

  • 工作：
    程序在一个给定的输入上的工作，是该程序执 行的所有操作的总和
  • 优化工作
    算法设计可以使解决一个问题所需的工作量大幅减少。例如使用 Θ(n log n) 时间复杂度的排序取代一个 Θ(n²) 时间的排序

大部分宾利规则的原始内容都是关于工作的，但也有 一些是关于四十年前变幻莫测的计算机架构的。 • 我们创建了一套新的宾利规则，只处理工作问题。

  • 数据结构

    1
    2
    3
    4
    5
    6
    打包和编码
    增强
    预计算
    编译时初始化
    缓存
    惰性计算稀疏性

  • 循环

    1
    2
    3
    4
    5
    变量提升
    哨兵
    展开
    合并
    消除无效迭代

  • 逻辑

    1
    2
    3
    4
    5
    常数折叠和传播共元表达式的消除
    代数恒等式
    循环短路有序测试
    创建一个快速路径
    合并测试

  • 函数

    1
    2
    3
    内联优化
    尾递归优化
    粗粒度递归

数据结构

1
2
3
4
5
6
7
打包和编码
增强
预计算
编译时初始化
缓存
惰性计算稀疏性

  1. 打包的思路是在一个机器字中存储一个以上的数据值。
  2. 编码的思路是将数据值转换为所需位更少的表示形式。
  3. 数据结构增强的思路是将更多信息添加到数据结构 中，以减少常见操作的工作量。
  4. 预计算的思路是提前执行计算，以避免在“关键任 务”期间进行计算。
  5. 编译时初始化的思路是在编译期间就存储常量的值， 节省执行时的工作
    思路：通过元编程创建大型静态表。
  6. 缓存的思路是存储最近访问过的结果，以节省程序 再次计算它们的时间。
  7. 利用稀疏性的思路是避免存储和计算无用值（一般是0） “最快的计算方法是根本不计算。”

循环

1
2
3
4
5
变量提升
哨兵
展开
合并
消除无效迭代
  1. 提升（也称为循环不变代码运动）的目标是避免每次 在循环内重新计算循环不变代码
  2. 哨兵是放置在数据结构中的特殊虚拟值，用于简化边 界条件的逻辑，特别是循环退出测试的处理
  3. 循环展开尝试通过将循环的几个连续迭代组合成单个迭代来节省工作，从而减少循环的总迭代次数，从而减少控制循环的指令必须执行的次数。
    完全循环展开 : 展开所有迭代部分循环展开 : 展开多个但不是全部的迭代。
    循环展开的好处
    循环控制代码中的指令数量较少
    启用更多编译器优化
    展开过多会导致指令缓存使用不当
  4. 循环合并（也称为干扰）的思路是将同一索引范围内 的多个循环组合在一起，从而节省循环控制的开销。
  5. 消除无效迭代的思路是修改循环边界以避免在本质上 为空的循环体上执行循环迭代。

逻辑

1
2
3
4
5
常数折叠和传播共元表达式的消除
代数恒等式
循环短路有序测试
创建一个快速路径
合并测试
  1. 常量折叠和传播的思路是在编译期间求值常量表达式 并将结果替换为进一步的表达式
  2. 共元表达式消除的思路是通过计算一次表达式，并存 储结果以供以后使用，来避免多次计算相同的表达式。
  3. 利用代数恒等式的思路是用工作代价更小的代数等价 表达式替换昂贵的表达式
  4. 在执行一系列测试时，短路的思路是在得到结果后立 即停止求值
  5. 对于执行一系列逻辑测试的代码，有序测试的思路是 在很少成功的测试之前执行那些更经常“成功”的测 试——测试选择了一个特定的替代方案。 同样，廉价 的测试应该先于昂贵的测试。
  6. 创建快速路径的思路是，通过添加条件更宽松但成本 更小的测试尽快结束判断，来节省该判断消耗的总资 源。
  7. 组合测试的思路是用一个测试或switch替换一系列测试。

函数

1
2
3
内联优化
尾递归优化
粗粒度递归
  1. 内联的思路是通过用函数本身的主体替换对函数的调 用来节省函数调用的开销
  2. 尾递归消除的想法是将作为函数的最后一步发生的递 归调用替换为分支跳转，从而节省函数调用开销。
  3. 粗化递归的思路是扩大基本情况的范围并使用更有效 的代码来处理它，从而避免函数调用开销。

总结

避免过早优化。首先得到正确的工作代码。然后优化，通过回归测试保持正确性。
减少程序的工作量并不一定会减少其运行时间，但它是一种很好的启发式方法。
编译器会自动执行许多低级优化。
要判断编译器是否确实在执行特定优化，请查看汇编代码。

作业

矩阵乘法

时间（s） 相对于python提升
python 22393.544347286224 1
java 689.336
c 716.050691
jik 611.963059