缓存对齐与字节对齐

缓存对齐与字节对齐  

一. Cache 【指的是CPU和内存间的那个高速缓存存储器，不是内存里一块做缓存用的区域】

Cache一般来说，需要关心以下几个方面

1）Cache hierarchy

Cache的层次，一般有L1, L2, L3 （L是level的意思）的cache。通常来说L1，L2是集成  在CPU里面的（可以称之为On-chip cache），而L3是放在CPU外面（可以称之为Off-chip cache）。当然这个不是绝对的，不同CPU的做法可能会不太一样。这里面应该还需要加上register，虽然register不是cache，但是把数据放到register里面是能够提高性能的。

2）Cache size

Cache的容量决定了有多少代码和数据可以放到Cache里面，有了Cache才有了竞争，才有了替换，才有了优化的空间。如果一个程序的热点(hotspot)已经完全填充了整Cache，那么再从Cache角度考虑优化就是白费力气了，巧妇难为无米之炊。我们优化程序的目标是把程序尽可能放到Cache里面，但是把程序写到能够占满整个Cache还是有一定难度的，这么大的一个Code path，相应的代码得有多少，代码逻辑肯定是相当的复杂（基本上是不可能，至少我没有见过）。

3）Cache line size

CPU从内存load数据是一次一个cache line；往内存里面写也是一次一个cache line，所以一个cache line里面的数据最好是读写分开，否则就会相互影响。

4）Cache associative

Cache的关联。有全关联(full associative)，内存可以映射到任意一个Cache line；也有N-way关联，这个就是一个哈希表的结构，N就是冲突链的长度，超过了N，就需要替换。

5）Cache type

有I-cache（指令cache），D-cache（数据cache），TLB（MMU的cache），每一种又有L1,L2等等，有区分指令和数据的cache，也有不区分指令和数据的cache。

二. 代码层次的优化

1) 字节 alignment （字节对齐）

要理解字节对齐，首先得理解系统内存的组织结构. 把1个内存单元称为1个字节，字节再组成字，在8086时代，16位的机器中1字=2个字节=16bit，而80386以后的32位系统中，1字=4个字节。大多数计算机指令都是对字进行操作，如将两字相加等。也就是说，32位CPU的寄存器为32位，导致指令的操作对象是32位字；16位CPU的寄存器为16位，移动、加、减等指令的操作对象也是16位字。由于指令的原因，内存的寻址也同样是按字进行操作，在16位系统中，如果你访问的只是低8位，内存寻址还是按16位进行，然后再根据A0地址线选择低8位还是高8位，这一过程成为一次内存读（写），在16位系统中，如果读取一个32位数，要花费两个内存读周期（先读低16，再读高16）。同理32位CPU的内存寻址按4个单元进行。

为了达到高效的目的，在16位系统中，变量存储的起始地址是2的倍数，32位系统中，变量存储的起始地址是4的倍数，而这些工作都是由编译器来完成的。下面举个例子来说明这个问题。如下图所示： 

    上图是16位系统的内存布局图，深蓝色表示变量覆盖的内存范围，假设变量的大小为2个字节，变量的起始物理内存地址为0000H时，访问这个变量时，只需要一次内存的读写。然而，当变量的内存起始地址为0001H时，cpu将耗费两次读周期进行变量访问，具体过程如下：为了访问变量的低8位，cpu将通过寻址访问起始地址为0000H所在的字，然后找到当前字的高8位；随后cpu再访问0002H所处字的低8位，此低8位就是变量的高8位，这样经过cpu的拼装变量的访问就结束了，可见，需要经过两次读周期才能正确访问变量的值，效率是前者的1/2。

__attribute__((aligned(n)))表示所定义的变量为n字节对齐； 

字节对齐的细节和编译器实现相关，但一般而言，满足三个准则：
1) (结构体)变量的首地址能够被其(最宽)基本类型成员的大小所整除；
2) 结构体每个成员相对于结构体首地址的偏移量（offset）都是成员大小的整数倍，如有需要编译器会在成员之间加上填充字节（internal adding）；
3) 结构体的总大小为结构体最宽基本类型成员大小的整数倍，如有需要编译器会在最末一个成员之后加上填充字节（trailing padding）。

__attribute__ ((packed)) 的作用就是告诉编译器取消结构在编译过程中的优化对齐,按照实际占用字节数进行对齐，是GCC特有的语法。这个功能是跟操作系统没关系，跟编译器有关，gcc编译器不是紧凑模式的.例如：

__attribute__ ((packed)) 的作用就是告诉编译器取消结构在编译过程中的优化对齐,按照实际占用字节数进行对齐，是GCC特有的语法。

__attribute__((aligned(n)))表示所定义的变量为n字节对齐； 

struct B{ char b;int a;short c;}; (默认4字节对齐)

这时候同样是总共7个字节的变量，但是sizeof(struct B)的值却是12。

下面我们使用预编译指令__attribute__((aligned(n)))来告诉编译器，使用我们指定的对齐值来取代缺省的:

struct C{char b;int a;short c;}; __attribute__((aligned(2)))

这时候同样是总共7个字节的变量，但是sizeof(struct B)的值却是8

struct D{ char b;int a;short c;}; __attribute__ ((packed))

       sizeof(struct C)值是8，sizeof(struct D)值为7。

字节对齐的细节和编译器实现相关，但一般而言，满足三个准则：
1) (结构体)变量的首地址能够被其(最宽)基本类型成员的大小所整除；
2) 结构体每个成员相对于结构体首地址的偏移量（offset）都是成员大小的整数倍，如有需要编译器会在成员之间加上填充字节（internal adding）；
3) 结构体的总大小为结构体最宽基本类型成员大小的整数倍，如有需要编译器会在最末一个成员之后加上填充字节（trailing padding）。

2) Cache line alignment （cache对齐）

数据跨越两个cache line，就意味着两次load或者两次store。如果数据结构是cache line对齐的，  就有可能减少一次读写。数据结构的首地址cache line对齐，意味着可能有内存浪费（特别是  数组这样连续分配的数据结构），所以需要在空间和时间两方面权衡。

对于普通代码，内存边界对齐也是有好处的，可以降低高速缓存(Cache)和内存交换数据的次数。 主要问题是在于Cache本身是分成很多Cache-Line,每条Cache-Line具有一定的长度，比如一般来说L1 Cache每条Cache Line长度在32个字节或64个字节；而L2的会更大，比如64个字节或128个字节。用户每次访问地址空间中一个变量，如果不在Cache当中，那么就需要从内存中先将数据调入Cache中.
       比如现在有个变量 int x;占用4个字节,它的起始地址是0x1234567F;那么它占用的内存范围就在0x1234567F-0x12345682之间。如果现在Cache Line长度为32个字节，那么每次内存同Cache进行数据交换时，都必须取起始地址时32(0x20)倍数的内存位置开始的一段长度为32的内存同Cache Line进行交换.   比如0x1234567F落在范围0x12345660~0x1234567F上，但是0x12345680~0x12345682落在范围 0x12345680~0x1234569F上，也就是说，为了将4个字节的整数变量0x1234567F~0x12345682装入Cache,我们必 须调入两条Cache Line的数据。但是如果int x的起始地址按4的倍数对齐，比如是 0x1234567C~0x1234567F,那么必然会落在一条Cache Line上，所以每次访问变量x就最多只需要装入一条Cache Line的数据了。比如现在一般的malloc()函数，返回的内存地址会已经是8字节对齐的，这个就是为了能够让大部分程序有更好的性能。

1.  __attribute__((aligned(cache_line)))对齐实现;

    struct syn_str { ints_variable; };__attribute__((aligned(cache_line)))；

2. 算法实现
  
   引子
    int a; 
    int size = 8;        <----> 1000(bin)
    计算a以size为倍数的下界数:

  就让这个数(要计算的这个数)表示成二进制时，最后三位为0就可以达到这个目标。只要下面这个数与a进行"与运算"就可以了:
  11111111 11111111 11111111 11111000
  而上面这个数实际下就是 ~(size - 1)，可以将该数称为size的对齐掩码size_mask.
   计算a以size为倍数的上下界数:
  #define alignment_down(a, size) (a & (~(size-1)) )
  #define alignment_up(a, size)   ((a+size-1) & (~ (size-1)))
  注: 上界数的计算方法，如果要求出比a大的是不是需要加上8就可以了?可是如果a本身就是8的倍数,这样加8不就错了吗,所以在a基础上加上(size - 1), 然后与size的对齐掩码进行与运算.
  例如:
  a=0, size=8, 则alignment_down(a,size)=0, alignment_up(a,size)=0.
  a=6, size=8, 则alignment_down(a,size)=0, alignment_up(a,size)=8.
  a=8, size=8, 则alignment_down(a,size)=8, alignment_up(a,size)=8.
  a=14, size=8,则alignment_down(a,size)=8, alignment_up(a,size)=16.
  注:size应当为2的n次方, 即2, 4, 8, 16, 32, 64, 128, 256, 1024, 2048, 4096 ...
  
   实现例子:

    struct syn_str { int s_variable; };

    void *p = malloc ( sizeof (struct syn_str) + cache_line );

    syn_str *align_p=(syn_str*)((((int)p)+(cache_line-1))&~(cache_line-1);

3) Branch prediction （分支预测）

代码在内存里面是顺序排列的。对于分支程序来说，如果分支语句之后的代码有更大的执行几率，  那么就可以减少跳转，一般CPU都有指令预取功能，这样可以提高指令预取命中的几率。分支预测  用的就是likely/unlikely这样的宏，一般需要编译器的支持，这样做是静态的分支预测。现在也有  很多CPU支持在CPU内部保存执行过的分支指令的结果（分支指令的cache），所以静态的分支预测  就没有太多的意义。如果分支是有意义的，那么说明任何分支都会执行到，所以在特定情况下，静态 分支预测的结果并没有多好，而且likely/unlikely对代码有很大的侵害（影响可读性），所以一般不  推荐使用这个方法.

if(likely(value)) 等价于 if(value)

if(unlikely(value)) 也等价于 if(value)

也就是说 likely() 和 unlikely() 从阅读和理解代码的角度来看，是一样的！！！

这两个宏在内核中定义如下：

#define likely(x)       __builtin_expect((x),1)
#define unlikely(x)     __builtin_expect((x),0)

__builtin_expect() 是 GCC (version >= 2.96）提供给程序员使用的，目的是将“分支转移”的信息提供给编译器，这样编译器可以对代码进行优化，以减少指令跳转带来的性能下降。

__builtin_expect((x),1) 表示 x 的值为真的可能性更大；
__builtin_expect((x),0) 表示 x 的值为假的可能性更大。

也就是说，使用 likely() ，执行 if 后面的语句 的机会更大，使用unlikely()，执行else 后面的语句的机会更大。
例如下面这段代码，作者就认为 prev 不等于 next 的可能性更大，

if (likely(prev != next)) {
       next->timestamp = now;
        ...
} else {
        ...;
}
通过这种方式，编译器在编译过程中，会将可能性更大的代码紧跟着起面的代码，从而减少指令跳转带来的性能上的下降。

下面以两个例子来加深这种理解：

第一个例子： example1.c

int testfun(int x)
{
   if(__builtin_expect(x, 0)) {
         ^^^--- We instruct the compiler, "else" block is more probable
     x = 5;
     x = x * x;
   } else {
       x = 6;
   }
   return x;
}
在这个例子中，我们认为 x 为0的可能性更大

编译以后，通过 objdump 来观察汇编指令，在我的 2.4 内核机器上，结果如下：

# gcc -O2 -c example1.c
# objdump -d example1.o

Disassembly of section .text:

00000000 :
   0:   55             push   %ebp
   1:   89 e5            mov    %esp,%ebp
   3:   8b 45 08          mov    0x8(%ebp),%eax
   6:   85 c0            test   %eax,%eax
   8:   75 07            jne    11
   a:   b8 06 00 00 00        mov    $0x6,%eax
   f:   c9              leave
    10:   c3              ret
    11:   b8 19 00 00 00        mov    $0x19,%eax
    16:   eb f7            jmp    f

可以看到，编译器使用的是 jne （不相等跳转）指令，并且 else block 中的代码紧跟在后面。

8:   75 07              jne    11
a:   b8 06 00 00 00          mov    $0x6,%eax

第二个例子： example2.c

int testfun(int x)
{
  if(__builtin_expect(x, 1)) {
           ^^^ --- We instruct the compiler, "if" block is more probable
       x = 5;
       x = x * x;
  } else {
       x = 6;
  }
       return x;
}
在这个例子中，我们认为 x 不为 0 的可能性更大

编译以后，通过 objdump 来观察汇编指令，在我2.4内核机器上，结果如下：

# gcc -O2 -c example2.c
# objdump -d example2.o

Disassembly of section .text:

00000000 :
   0:   55                 push   %ebp
   1:   89 e5                mov    %esp,%ebp
   3:   8b 45 08              mov    0x8(%ebp),%eax
   6:   85 c0                test   %eax,%eax
   8:   74 07                je     11
   a:   b8 19 00 00 00             mov    $0x19,%eax
   f:   c9                 leave
10:   c3                   ret
11:   b8 06 00 00 00                 mov    $0x6,%eax
16:   eb f7                  jmp    f

这次编译器使用的是 je （相等跳转）指令，并且 if block 中的代码紧跟在后面。

   8:   74 07                je     11
   a:   b8 19 00 00 00             mov    $0x19,%eax