注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

蒙奇D小豌豆的博客

蒙奇D小豌豆的学习记录

 
 
 

日志

 
 

缓存对齐与字节对齐  

2011-08-27 14:41:31|  分类: network |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

. Cache

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

1Cache hierarchy

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

2Cache size

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

3Cache line size

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

4Cache associative

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

5Cache type

I-cache(指令cache),D-cache(数据cache),TLBMMUcache),每一种又有L1,L2等等,有区分指令和数据的cache,也有不区分指令和数据的cache

. 代码层次的优化

1) 字节 alignment (字节对齐)

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

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

    上图是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)值是8sizeof(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)
    计算asize为倍数的下界数:

  就让这个数(要计算的这个数)表示成二进制时,最后三位为0就可以达到这个目标。只要下面这个数与a进行"与运算"就可以了:
  11111111 11111111 11111111 11111000
  
而上面这个数实际下就是 ~(size - 1),可以将该数称为size的对齐掩码size_mask.
  
计算asize为倍数的上下界数:
  #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应当为2n次方, 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 <testfun>:
   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 <testfun+0x11>
   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 <testfun+0xf>


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

8:   75 07              jne    11 <testfun+0x11>
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 <testfun>:
   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 <testfun+0x11>
   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 <testfun+0xf>


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

   8:   74 07                je     11 <testfun+0x11>
   a:   b8 19 00 00 00             mov    $0x19,%eax

 

  评论这张
 
阅读(2039)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018