优化程序性能

编译器优化

现代编译器已经非常成熟，~~优化后的代码有时候程序员自己都看不懂~~。

但是，编译器还是保守，假设你的每个操作都是黑盒子，小心翼翼在不会影响你的操作的前提下进行优化，编译器必须很小心的使用安全的优化

关于指针的例子

void test(int *pt1,int *pt2){
    *pt1+=*pt2;
    *pt1+=*pt2;
}

假设我们的本意是 pt1+=2 (*pt2);这样写更快一点。

编译器并不会进行这样更快的优化，因为它无法确定 pt1和pt2是否指向内存中相同的位置。它只能假设不同的指针可能会指向内存中的同一位置。

循环中的低效率

for(int i=0;i<strlen(s);i++){
    ...
}

int length=strlen(s)
for(int i=0;i<length;i++){
    ...
}

每次循环都要计算strlen(s) 低效率

假如代码修改了字符串S，编译器并不知道这是否会影响strlen(s)，因此每次都会计算，并不会进行优化。

过程中函数多次调用的低效率

int fun1();

void test1(){
    return fun1()+fun1()+fun1();
}

void test2(){
    return 3*fun1();
}

假设我们知道fun1()并不会产生副作用，每次调用结果相同，那么test2更加高效。

编译器不能判断fun1()是否会产生副作用，因此不会把test1优化到test2；

inline代替优化函数调用；

不必要的内存引用

for(;j<10;j++)
b[6]+=a[j];


//优化 
int temp=0; // 优化后 该局部变量被保存在寄存器中，不用一次次的进行内存读写
for(;j<10;j++)
temp+=a[j];

b[6]=t;

因为不确定a[j]的变化是否会改变b[6]的数值，因此每次都要从内存读入b[6]，再把更新后的b[6]写进内存,这种内存读写是不必要的，要一次次再内存和寄存器中传送数据。

因为b[6]和a[j]可能指向同一个地址，因此编译器不会进行优化。

流水线处理和并行

进行循环展开，减少循环迭代次数，提高效率。(减少过程中的索引计算和条件分支，减少计算中关键路径的操作数量)。

不相关的计算可以进行流水线处理

循环展开和并行累计多个值一起计算，会提高程序的流水线处理的效率，提高程序并行性。

编译器会自行进行优化，仅作为了解 ~~其实是我现在这部分学的不好~~

下学期一定要看看 CAAQA 这本经典书

存储器层次结构

存储技术

SRAM(在CPU芯片上) DRAM(主存) 闪存等等

如何进行内存读写

cpu将地址传入总线上发出信号；主存将对应地址的数据x传入总线；cpu 读出数据x 复制到寄存器中。cpu将地址放到总线上，主存读出地址，等待数据字；cpu将数据放到总线上；主存接收数据并且储存到先前指定的地址。

磁盘构造，如何进行磁盘读写(指令，逻辑块号，内存地址)

CPU通知磁盘控制器进行磁盘读写后切换执行其他进程，磁盘写数据到主存中无需CPU操作，写数据结束后中断通知CPU。这称为直接内存访问DMA，这种数据传送称为DMA传送

奇怪的SSD(固态硬盘).

局部性原理

程序倾向于使用其地址接近或者等于最近使用过的数据和指令的地址的那些数据和地址。

program tend to use data and instructions with addresses near or equal to those they have used recently.

时间局部性和空间局部性

避免代码出现差的局部性。

缓存不命中的种类

冷不命中：一个空的缓存称为冷缓存，冷缓存必然不命中，称为冷不命中。

冲突不命中：常用的放置策略是将 k+1 层的某个块限制放置在 k 层块的一个小的子集中。比如 k+1 层的块 1,5,9,13 映射到 k层的块 0。这会带来冲突不命中。

容量不命中：当访问的工作集的大小超过缓存的大小时，会发生容量不命中。即缓存太小了，不能缓存整个工作集。

高速缓存存储器

最好看书回忆具体步骤

大概就是，将k个固定大小的字节作为一个整体即“块”，按块储存到高速缓存中，所以要考虑块的大小也会影响到缓存效率（直接映射高速缓存容易引起抖动，例如 p432的例子）

高速缓存确定一个请求是否命中，然后抽取出被请求的字的过程分为三步：

组选择行匹配字抽取

具体例子参考 p430

有关写的问题

写命中（写一个已经缓存了的字 w）的情况下，高速缓存更新了本层的 w 的副本后，如何处理低一层的副本有两种方法：

直写：立即将 w 的高速缓存块写回到低一层中。
1. 优点：简单
2. 缺点：每次写都会占据总线流量
写回：尽可能地推迟更新，只有当替换算法要驱逐这个更新过的块时，才把它写到低一层中。
1. 优点：利用了局部性，可以显著地减少总线流量。
2. 缺点：增加了复杂性。必须为每个高速缓存行维护一个额外的修改位，表明此行是否被修改过。

写不命中情况下的两种方法：

写分配：加载相应的低一层的块到本层中，然后更新这个高速缓存块。
1. 优点：利用写的空间局部性
2. 缺点：每次不命中都会导致一个块从低一层传送到高速缓存
非写分配：避开高速缓存，直接把这个字写到低一层中

直写一般与非写分配搭配，两者都更适用于存储器层次结构中的较高层。

写回一般与写分配搭配，两者都更适用于存储器层次结构中的较低层，因为较低层的传送时间太长。

因为硬件上复杂电路的实现越来越容易，所以现在使用写回和写分配越来越多。

程序中利用局部性

写完配套的lab就行了

注意力集中在内循环中
按照数据对象存储在内存中的数据，按照步长为1来读数据，利用空间局部性
一旦从存储器中读入了一个数据对象，就尽可能多使用它，利用时间局部性

源之居

深入理解计算机系统第五章笔记