CPU高速缓存行对齐和代码优化

CacheLine
众所周知，计算机将数据从主存读入Cache时，是把要读取数据附近的一部分数据都读取进来这样一次读取的一组数据就叫做CacheLine，每一级缓存中都能放很多的CacheLine

两种方法查看：

1.cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size

2. cat /proc/cpuinfo

3.lscpu

多核CUP

L1、L2、L3指一级缓存，二级缓存，三级缓存。其中一级缓存分指令缓存和数据缓存，通过lscpu命令，可以看到l1d和l1i。
CUP中的每个核均可单独处理一个线程
每个核公用L3

超线程
一个核中有多套PC和Register，他们公用一个ALU，这样一个核可以处理多个线程
如四核八线程就由此而来

Volatile的可见性

1、x被标记了volatile
2、两个线程运算时是将缓存中要被运算数所在的整条CacheLine复制到线程自己的存储，并进行运算，运算之后写回缓存
3、假设线程1修改了x并写回，但是线程2中的x还是未修改的x
4、由于x被标记了volatile，在线程1写回x缓存时，线程1会通知线程2重新读取缓存中的x

伪共享

1、线程1、2公共使用同一个CacheLine
2、x、y在同一个CacheLine
3、x、y都是volatile（x和y不是线程安全的，如果不是volatile，数据会不同步）
4、如果线程1不断修改x，线程2不断修改y，那么修改的时候线程1就要不断通知线程2更新x、线程2就要不断通知线程1更新y
5、这样的不断通知不断重新读取很浪费性能
6、这就叫伪共享

CacheLine对齐
多线程会有上面的伪共享的问题，如果在缓存读取数据到CacheLine时，两个volatile的数被读取到不同的CacheLine中的话，就不需要一直通知另一个线程更新数据了，因为另一个线程根本没有这个数据

那么如何让两个数据一定在不同的CacheLine呢，方法就是Cache Line对齐

一般一个CacheLine是64字节，也就是8个long，我们可以把x定义为long，并同时定义7个没有用的long变量，这样这8个数就在同一个CacheLine中
之后再定义y，y自然也就在下一个CacheLine中了
这就叫CacheLine对齐，这样两线程就不会出现伪共享的现象了

       CPU的高速缓存一般分为一级缓存、二级缓存和三级缓存。CPU在运行时首先从一级缓存读取数据，如果读取失败则会从二级缓存读取数据，如果仍然失败则再从三级缓存，再失败最后从内存中存读取数据。而CPU从缓存或主内存中最终读取到数据所耗费的时钟周期差距是非常之大的。因此高速缓存的容量和速度直接影响到CPU的工作性能。一级缓存都内置在CPU内部并与CPU同速运行，可以有效的提高CPU的运行效率。一级缓存越大，CPU的运行效率往往越高。

缓存对齐如何编码
 一级缓存又分为数据缓存和指令缓存，他们都由高速缓存行组成，对于X86_64架构的CPU来说，高速缓存行一般是64个字节，CPU大约只有512行高速缓存行，也就是说约32k的一级缓存。二级缓存一般有1-2MB，三级缓存可以达到33MB-64MB.

 查看cpu0 的一级缓存中的有多少组

$ cat /sys/devices/system/cpu/cpu0/cache/index0/number_of_sets

$64

查看cpu0的一级缓存中一组中的行数

$cat /sys/devices/system/cpu/cpu0/cache/index0/ways_of_associativity

$8

        当CPU需要读取一个变量时，该变量所在的以64字节分组的内存数据将被一同读入高速缓存行，所以，对于性能要求严格的程序来说，充分利用高速缓存行的优势非常重要。一次性将访问频繁的64字节数据对齐后读入高速缓存中，减少CPU高级缓存与低级缓存、内存的数据交换。

       但是对于多CPU的计算机，情况却又不一样了。例如：

1、      CPU1 读取了一个字节，和它相邻的字节被读入 CPU1 的高速缓存。

2、      CPU2 做了上面同样的工作。这样 CPU1 ， CPU2 的高速缓存拥有同样的数据。

3、      CPU1 修改了那个字节，被修改后，那个字节被放回 CPU1 的高速缓存行。但是该信息并没有被写入RAM 。

4、      CPU2 访问该字节，但由于 CPU1 并未将数据写入 RAM ，导致了数据不同步。

        当一个 CPU 修改高速缓存行中的字节时，计算机中的其它 CPU会被通知，它们的高速缓存将视为无效。于是，在上面的情况下， CPU2 发现自己的高速缓存中数据已无效， CPU1 将立即把自己的数据写回 RAM ，然后 CPU2 重新读取该数据。 可以看出，高速缓存行在多处理器上会导致一些不利。

         从上面的情况可以看出，在设计数据结构的时候，应该尽量将只读数据与读写数据分开，并具尽量将同一时间访问的数据组合在一起。这样 CPU 能一次将需要的数据读入。

如：

struct __a
{
    int id; // 不易变
    int factor;// 易变
    char name[64];// 不易变
    int value;// 易变
}；
这样的数据结构就很不利。

在 X86_64 下，可以试着修改和调整它

struct __a
{
    char name[64];// 不易变
    int id; // 不易变
    char __Align[64 – sizeof(int)+sizeof(name)*sizeof(name[0])%64]
    int factor;// 易变
    int value;// 易变
    char __Align2[64 – 2* sizeof(int)%64]
}；
64 – sizeof(int)+sizeof(name)*sizeof(name[0])%64

64表示 X86_64 架构缓存中，高速缓存行为64字节 大小。 __Align 用于显式对齐。

再来一个有利于高速缓存行的例子：

struct CUSTINFO
{
    DWORD dwCustomerID; //Mostly read-only
    int nBalanceDue; //Read-write
    char szName[100]; //Mostly read-only
    FILETIME ftLastOrderDate; //Read-write
};
改版后的结构定义 :

// Determine the cache line size for the host CPU.
//为各种CPU定义告诉缓存行大小
#ifdef _X86_
#define CACHE_ALIGN 32
#endif
 
#ifdef _X86_64
#define CACHE_ALIGN 64
#endif
 
#ifdef _ALPHA_
#define CACHE_ALIGN 64
#endif
 
#ifdef _IA64_
#define CACHE_ALIGN ??
#endif
 
 
#define CACHE_PAD(Name, BytesSoFar) \
BYTE Name[CACHE_ALIGN - ((BytesSoFar) % CACHE_ALIGN)]
 
struct CUSTINFO
{
    DWORD dwCustomerID; // Mostly read-only
    char szName[100]; // Mostly read-only
 
    //Force the following members to be in a different cache line.
    //这句很关键用一个算出来的Byte来填充空闲的告诉缓存行
    //如果指定了告诉缓存行的大小可以简写成这样
    //假设sizeof(DWORD) + 100 = 108；告诉缓存行大小为32
    //BYTE[12]；
    //作用呢就是强制下面的数据内容与上面数据内容不在同一高速缓存行中。
    CACHE_PAD(bPad1, sizeof(DWORD) + 100);
    int nBalanceDue; // Read-write
 
    FILETIME ftLastOrderDate; // Read-write
 
    //Force the following structure to be in a different cache line.
    CACHE_PAD(bPad2, sizeof(int) + sizeof(FILETIME));
};

    高速缓存控制器是针对数据块，而不是字节进行操作的。从程序设计的角度讲，高速缓存其实就是一组称之为缓存行(cache line)的固定大小的数据块，其大小是以突发读或者突发写周期的大小为基础的。

    每个高速缓存行完全是在一个突发读操作周期中进行填充或者下载的。即使处理器只存取一个字节的存储器，高速缓存控制器也启动整个存取器访问周期并请求整个数据块。缓存行第一个字节的地址总是突发周期尺寸的倍数。缓存行的起始位置总是与突发周期的开头保持一致。

    现代处理器有专门的功能单元来执行加载和存储操作。加载单元每个时钟周期只有启动一条加载操作；与加载操作一样，在大多数情况下，存储操作能够在完整流水线化的模式中工作，每个周期开始一条新的存储。

​