在实际应用中，经常会遇见如果提升程序执行效率的问题。这里给出一些具体方案
程序是由CPU执行的，CPU中的Cache（高速缓存）的使用情况对CPU的工作效率起着举足轻重的影响。
这里以Cache为核心，介绍CPU的程序优化
高速缓存 Cache
通常情况下，CPU和内存的运行速度并不一致，CPU访问内存需要200-300个时钟周期。为了弥补他们之间的性能差异，在CPU中引入了高级缓存Cache。
Cache使用SRAM，其价格比内存的DRAM高很多。（1MB的SRAM需要7美金，而1MB的DRAM只需要0.015美金）所以只在CPU中使用少量的SRAM，而内存中只能使用速度稍慢的DRAM。
在CPU中，Cache被分为三级： L1 Cache, L2 Cache, L3 Cache。
其中L1 Cache, 最小，也离CPU最近，可分为数据缓存和指令缓存。通常它们的大小是一样的。
L1 Cache 和 L2 Cache 都是每个 CPU 核心独有的，而 L3 Cache 是多个 CPU 核心共享的。
可以使用一下命令查看：
cat /sys/devices/system/cpu/cpu0/cache/index0/size
32K # L1 Cache 数据缓存大小 单个CPU独有
cat /sys/devices/system/cpu/cpu0/cache/index1/size
32K # L1 Cache 指令缓存大小 单个CPU独有
cat /sys/devices/system/cpu/cpu0/cache/index2/size
256K # L2 Cache 大小 单个CPU独有
cat /sys/devices/system/cpu/cpu0/cache/index3/size
12288K ## L3 Cache 大小 多CPU共有
越是靠经CPU核心，其Cache的访问速度越快.
| 部件 | CPU 访问所需时钟周期 |
|---|---|
| L1 Cache | 2~4 |
| L2 Cache | 10~20 |
| L3 Cache | 20~60 |
| 内存 | 200~300 |
程序执行时，会先将内存中的数据加载到共享的 L3 Cache 中，再加载到每个核心独有的 L2 Cache，最后进入到最快的 L1 Cache，之后才会被 CPU 读取。它们之间的层级关系，
Cache的读取过程
CPU从Cache中读取数据是按块来读取的。每一小块数据称为缓存块Cache Line。
可以使用一下命令查看：
cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64
CPU在读取数据时，首先会访问Cache，只有当Cache中找不到数据时，才会把内存中的数据读入到Cache中，再从Cache中读取数据。
例如：
当CPU需要读取 int array[100]中的array[0]，CPU会先检测Cache中有没有，如果没有就载入 array[0]到Cache。但是array[0]的大小为 4 字节，不足 64 字节，CPU 就会顺序加载数组元素array[0]~ array[15]到Cache中。在下次访问时这些数组元素时，会直接从 CPU Cache 读取，而不用再从内存中读取，提高了 CPU 读取数据的性能。
Cache中的数据结构
Cache 和内存之间都是按数据块读取的。数据快的大小为coherency_line_size，在内存称为内存块Block。所以在读取时所涉及的地址主要是内存块的地址。
直接映射 Cache Direct Mapped Cache
直接映射 Cache 的策略，就是把内存块的地址始终映射在一个 CPU Line（缓存块） 的地址。映射关系实现使用取模运算，取模运算的结果就是内存块地址对应的 CPU Line（缓存块） 的地址。
举个例子
内存共有 32 个块，Cache 共有 8 个 CPU Line，假设 CPU 想要访问第 15 号内存块，如果 15 号内存块中的数据已经缓存在 CPU Line 中的话，则是一定映射在 7 号 CPU Line 中，因为 15 % 8 的值是 7。
不同的内存块可能对应同一个CPU Line，所以在CPU Line中海需要一个组标记（Tag）用来记录CPU Line中的数据对应的内存块。
这样CPU Line中一共包含如下信息：
- 组标记 （Tag）
- 实际数据 （Data）
- 有效位（Valid bit）
CPU在读取CPU Cache的数据时，并不读取整个数据快，而是读取需要的一个数据片段，称为字（Word）。字在CPU Line中的位置称为偏移量（offset）。
至此，一个内存的访问地址包含：
- 组标记
- CPU Line 索引
- 偏移量
一个CPU Cache里的数据结构包含： - 索引
- 组标记
- 数据快
- 有效位
CPU读取内存数据步骤
当内存中的数据已经在 CPU Cache 中后，CPU 访问一个内存地址会经历 4 个步骤：
- 根据内存地址中索引信息，计算在 CPU Cache 中的索引，也就是找出对应的 CPU Line 的地址；
- 判断对应 CPU Line 中的有效位，判断 CPU Line 中数据是否有效。如果无效，CPU 就会直接访问内存，并重新加载数据到CPU Line，如果有效，则往下执行；
- 对比内存地址中组标记和 CPU Line 中的组标记，确认 CPU Line 中的数据是我们要访问的内存数据，如果不是的话，CPU 就会直接访问内存，并重新加载数据，如果是的话，则往下执行；
- 根据内存地址中偏移量信息，从 CPU Line 的数据块中，读取对应的字。
如何让CPU 跑的更快——缓存命中
通过上面的介绍，CPU读取Cache的速度比读取内存的速度块了100多倍。如果要读的数据正好就在缓存里面，那数据读取速度将会有极大的提升。
所以代码跑的块的核心问题就是提高缓存命中率。
CPU L1 Cache 通常包含数据缓存和指令缓存。
提高数据缓存命中率
在遍历数组时，按照内存布局顺序访问，可以有效的利用 CPU Cache，代码的性能就会得到很大的提升。
一个例子:
const int N = 100;
int array[N][N] = {};
//形式1
for (int i =0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
array[i][j] = 0;
}
}
//形式2
for (int i =0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
array[j][i] = 0;
}
}
实际上形式1比形式2的结果块了很多倍，因为用形式1访问数组的顺序和内存中数据的存放顺序一致。
当 CPU 访问 array[0][0] 时，由于该数据不在 Cache 中，于是会顺序把跟随其后的 3 个元素从内存中加载到 CPU Cache，这样当 CPU 访问后面的 3 个数组元素时，就能在 CPU Cache 中成功地找到数据，这意味着缓存命中率很高，缓存命中的数据不需要访问内存，这便大大提高了代码的性能。
当N=2时，array在内存中的位置：
{array[0][0], array[0][1], array[1][0], array[1][1]}
而形式2中，对内存的访问是跳跃式的，下一个要访问的元素很难在Cache中找到，所以每次都需要重新读内存中的数据。所以工作效率低。
提高指令缓存命中率
CPU 中含有分支预测器。对于if...else...条件语句，意味着至少可以选择跳转到两段不同的指令执行。如果分支预测可以预测到接下来要执行的是 if 里的指令，还是 else 里指令的话，就可以提前把这些指令放在指令缓存中，这样 CPU 可以直接从 Cache 读取到指令，于是执行速度就会很快。
所以在代码中，需要能够帮助提升分支预测器的预测成功率。
当数组中的元素是随机的，分支预测就无法有效工作，而当数组元素都是是顺序的，分支预测器会动态地根据历史命中数据对未来进行预测，这样命中率就会很高。
一个例子：
const int N = 100;
int array[N];
for (int i =0; i < N; i++)
{
array[i] = rand() % 100;
}
//方法1
for (int i =0; i < N; i++)
{
if (array[i] < 50)
{
array[i] = 0;
}
}
sort(array, array + N);
//方法2
sort(array, array + N);
for (int i =0; i < N; i++)
{
if (array[i] < 50)
{
array[i] = 0;
}
}
第一个方法，先判断赋值，再排序。第二个方法，先排序，再判断赋值。
对于这个例子，当array中的元素是随机的，分支预测就无法有效工作，而当数组元素都是是顺序的，分支预测器会动态地根据历史命中数据对未来进行预测，这样命中率就会很高。
所以先排序再遍历速度会更快，这是因为排序之后，数字是从小到大的，那么前几次循环命中 if < 50 的次数会比较多，于是分支预测就会缓存 if 里的 array[i] = 0 指令到 Cache 中，后续 CPU 执行该指令就只需要从 Cache 读取就好了。
使用显示分支预测工具——宏 likely , unlikely
如果比较肯定代码中 if 的表达式判断为 true 的概率比较高，可以使用显示分支预测工具。如 C/C++ 中编译器提供了 likely 和 unlikely 这两种宏，如果 if 条件为 ture 的概率大，则可以用 likely 宏把 if 里的表达式包裹起来，反之用 unlikely 宏。
#include<stdio.h>
#include<stdlib.h>
#define likely(x) __builtin_expect(!!(x), 1) //gcc内置函数, 帮助编译器分支优化
#define unlikely(x) __builtin_expect(!!(x), 0)
int main(int argc, char* argv[]){
int x = 0;
x = atoi(argv[1]);
if (unlikely(x == 3)){ //告诉编译器这个分支非常不可能为true
x = x + 9;
}
else{
x = x - 8;
}
printf("x=%d\n", x);
return 0;
}
多核CPU 绑定
单核 CPU，虽然只能执行一个进程，但是操作系统给每个进程分配了一个时间片，时间片用完了，就调度下一个进程，于是各个进程就按时间片交替地占用 CPU，从宏观上看起来各个进程同时在执行。
现在很多 CPU 都是多核心的，进程可能在不同 CPU 核心来回切换执行，这对 CPU Cache 不是有利的，虽然 L3 Cache 是多核心之间共享的，但是 L1 和 L2 Cache 都是每个核心独有的，如果一个进程在不同核心来回切换，各个核心的缓存命中率就会受到影响，相反如果进程都在同一个核心上执行，那么其数据的 L1 和 L2 Cache 的缓存命中率可以得到有效提高，缓存命中率高就意味着 CPU 可以减少访问 内存的频率。
当有多个同时执行「计算密集型」的线程，为了防止因为切换到不同的核心，而导致缓存命中率下降的问题，我们可以把线程绑定在某一个 CPU 核心上，这样性能可以得到非常可观的提升。
在 Linux 上提供了 sched_setaffinity 方法，来实现将线程绑定到某个 CPU 核心这一功能。
CPU亲合力就是指在Linux系统中能够将一个或多个进程绑定到一个或多个处理器上运行.
一个进程的CPU亲合力掩码决定了该进程将在哪个或哪几个CPU上运行.在一个多处理器系统中,设置CPU亲合力的掩码可能会获得更好的性能.
一个CPU的亲合力掩码用一个cpu_set_t结构体来表示一个CPU集合,下面的几个宏分别对这个掩码集进行操作:
·CPU_ZERO() 清空一个集合
·CPU_SET()与CPU_CLR()分别对将一个给定的CPU号加到一个集合或者从一个集合中去掉.
·CPU_ISSET()检查一个CPU号是否在这个集合中.
设置、获取线程CPU亲和力状态的函数:
-
sched_setaffinity(pid_t pid, unsigned int cpusetsize, cpu_set_t mask)
该函数设置进程为pid的这个进程，让它运行在mask所设定的CPU上。如果pid的值为0，则表示指定的是当前进程，使当前进程运行在mask所设定的那些CPU上。第二个参数cpusetsize是mask所指定的数的长度.通常设定为sizeof(cpu_set_t)。如果当前pid所指定的进程此时没有运行在mask所指定的任意一个CPU上，则该指定的进程会从其它CPU上迁移到mask的指定的一个CPU上运行。 -
sched_getaffinity(pid_t pid, unsigned int cpusetsize, cpu_set_t mask)
该函数获得pid所指示的进程的CPU位掩码，并将该掩码返回到mask所指向的结构中。即获得指定pid当前可以运行在哪些CPU上。同样,如果pid的值为0，也表示的是当前进程。
磁盘读写的优化
比内存读写更慢的是磁盘。速度相差10倍以上。所以针对磁盘读写的优化操作也能提升程序的执行效率。针对磁盘的优化技术有L零拷贝，直接I/O，异步I/O，以及内核中的磁盘高速缓存。
一般的磁盘操作步骤如下：
可以看出，这种磁盘读写方式需要CPU产于太多细节。
DMA
将I/O和内存之间数据传输任的控制交给一个专门的控制器，称为：直接内存访问计数 DMA（Direct Memory Access）。DMA的工作流程如下图所示：
DMA 在收到磁盘的信号后，将磁盘控制器缓冲区中的数据拷贝到内核缓冲区中，此时 CPU 被解放，可以执行其他任务；当DMA数据读取完成后，发送中断信号给CPU，使得CPU回来读取内核缓冲区的数据。
在代码实现层面，传统磁盘读、写多用read()，write()函数。一般执行过程如下图所示：
在这个过程中，
- 有4次CPU内核态，用户态之间的上下文切换，每次切换大约需要耗费几十纳秒到几微微秒。
- 有4次数据拷贝，2次DMA，2次CPU。
所以，这里考虑的优化方法为减少用户态和内核态的上下文切换，减少内存拷贝次数。
减少用户态，内核态的上下文切换次数——减少系统调用
之所以会静茹内核态，是因为用户空间没有磁盘和网卡的直接操作权限。用户程序只能调用系统函数来完成对应功能，让内核去执行对应的功能。然而，每一次系统调用必然会发生2次上下文的切换（用户态-1->内核态-2->用户态）。
所以减少系统调用的次数能够有效的减少上下文的切换。
减少数据拷贝——零拷贝
零拷贝（zero-copy）是为了减少读写操作中的那4次拷贝操作。
一般所说的零拷贝是指没有在内存层面拷贝数据，全程由DMA来进行数据的搬运而非CPU。
其基本实现方式有如下2种：
-
mmap + write
-sendfile
-SG-DMA
mmap是用来替代read()函数，将内核缓冲区直接映射到了内存上，这样，在执行write操作的时候可以由CPU直接将内核的数据直接写入socket缓冲区。这样节约了缓冲区到内存的一次拷贝。这里可以看出，全过程中还是出现了2次系统条用，4次上下文切换，3次拷贝。
sendfile是Linux内核中的函数sendfile()：
#include <sys/socket.h>
ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);
它可以直接替代read()和write()操作，用一次系统调用完成read()和write()的功能。在的操作中，系统调用直接将数据从内核缓冲区拷贝到socket的缓冲区中。这里可以看出全过程中，只由一次系统调用，2次上下文切换，3次拷贝。
SG-DMA（The Scatter-Gather Direct Memory Access）是真正的零拷贝技术。SG-DMA的支持情况可以使用如下命令查询：
$ ethtool -k eth0 | grep scatter-gather
scatter-gather: on
对于内核版本>2.4时，sendfile()的工作方式为：DMA将数据直接拷贝到内核缓冲区，然后缓冲区的描述符和数据长度直接传到socket的缓冲区。最后网卡的SG-DMA的控制器直接将内核中昂的数据拷贝到网卡的缓冲区里。这样，就直接跳过了socket的缓冲区，只进行了2次拷贝。
由此可以看出使用零拷贝计数，将上下文切换次数由4次减少为2次，数据拷贝次数由4次减少为2次，并且过程中都不需要CPU产于，由DMA直接实现。由此可见零拷贝可以将文件传输性能提高至少1倍以上。
PageCache
参考：
https://www.cnblogs.com/xiaolincoding/p/13836230.html
https://www.cnblogs.com/xiaolincoding/p/13719610.html
