Golang 内存对齐和伪共享False Sharing

内存对齐有多大作用?

为了减少cpu的访存次数,提高cpu的吞吐量,并不会让cpu逐个字节访问内存,而是以字长(word size)为单位访问。比如 64 位的 CPU ,字长为 8 字节,那么 CPU 访问内存的单位也是 8 字节。但是,如果被访问的数据在内存中的起始地址不是字长的倍数的话,反而有可能增加cpu的访存次数,这是为什么呢?解释这现象要从内存的工作原理入手。

一般一条RAM上每面由8个内存颗粒chip组成一个rank,每个chip拥有8张二维矩阵bank,bank是由一个个的存储单元cell组成的矩阵,每个cell存储一个bit,bank的每一行就叫做一个 row,每一列叫做一个 column,通过colum 和 row 可以定位一个cell,每一行的cell组成一个page,一般一个page有8个cell。

Golang 内存对齐和伪共享False Sharing

问题来了,内存每次都是只获取一个 cell 上的数据(1 bit)吗?并不是。每个 chip 中还有一个行缓存row buffer,所以每次内存都会获取一个page即1byte,而不单单一个 cell,即使 cpu 只需要其中一个 cell,这既体现了局部性原理,同时也解释了为什么memory存储数据的单位是byte,因为就是这么设计的呀。

第二个问题,对于指定类型的值,它的各个byte是连续的存储在rank上面的吗?并不是。对于指定类型的值,它的每个byte都会存储在不同的chip中,cpu从RAM读取数据时需要使用多条地址总线并行的从一组chip中定位byte,然后并行读取再拼成原始的数据。例如在64位系统中,假如每个chip的page为1byte,因为字长是8,那么就让8个chip为一组进行编址,并规定各个chip中相同偏移的page组成逻辑上连续的8byte内存空间,那么在cpu读取数据的时候只需要并行的从这8个chip上分别读取1byte,就能取出完整的1个字长(1byte)数据。这个过程是由RAM上的memory controllers来控制的,目的就是利用数据的并行读写来提高内存的吞吐量。

Golang 内存对齐和伪共享False Sharing

这样的设计毫无疑问大大的提高了cpu的访存效率,但是在为指定类型的值分配的内存块(起始)地址的时候,这个地址就必须遵循一定的规则,否则cpu可能要两次访存才能取到需要的值,而这个规则就叫内存对齐。

内存对齐说白了就是给数据分配一个合理的起始地址,比如在64位系统中给int64类型的值分配的内存块起始地址就必须是字长的整数倍,才能保证cpu一次访存就能取出该类型对应值。

在64为系统中,cpu读取一个int64类型的值,如果这个值的起始地址为0(8的倍数),那么它恰好就能被cpu的一次访问就全部取出。

Golang 内存对齐和伪共享False Sharing

如果这个值所在的起始地址为1(不是8的倍数),那么cpu需要两次访问内存才能将这个值取出。第一次先取这个值的低7个byte,即第1byte到第7byte,第二次再取第8byte,这等于是白白的浪费掉了一倍的cpu性能。

Golang 内存对齐和伪共享False Sharing

怎样实现内存对齐呢

对齐值/对其边界

为了充分使用CPU的指令并获得最佳性能,为指定类型的值分配的内存块(起始)地址必须是一个整数N的倍数,则N称为该类型的值的(内存)地址对齐值Align,对齐值和对齐边界和对齐保证是一个意思。

Golang目前支持32位和64位平台,并根据各数据类型的大小和平台字长来确定对齐边界Align。

  • 下表是32位系统和64位系统各大小数据的对齐边界

类型种类 尺寸(字节数)


uint8, int8 1
uint16, int16 2
uint32, int32, float32 4
uint64, int64 8
float64, complex64 8
complex128 16
uint, int 取决于编译器实现。通常在
32位架构上为4,在64位
架构上为8。
uintptr 取决于编译器实现。但必须
能够存下任一个内存地址。


+ 平台的最大对齐边界等于其字长,因为各平台的寄存器宽度是一个字长,而且地址的size也是一个字长。

编程语言原生数据类型的内存对齐,是由编译器自动完成的。有的语言的编译器可以指定最大对齐边界(不超过一个字长),比如C语言,可以在64位平台上指定最大对齐边界位为4,那么编译后的程序就可以无缝迁移到32位平台上运行。但是Go语言不支持指定最大对齐边界。



## 编译器内存对齐

编译器先根据平台确定指定类型的对其边界和偏移,然后再计算得出其值得起始地址

以编译器编译64位的程序为例,

1. 如果待存储数据是int8类型的,可知int8的对齐边界为1,因此该类型得值可以存储在任意位置,如下图,起始地址为1

 <img src="https://gitee.com/usmiles/blog-image/raw/master/img/Avoiding-MemoryAlignment-cpuRead03.png" style="zoom:50%;" />

2. 如果有一个int32类型的数据待存储,可知其对齐边界为4,即起始地址必须为4的整数倍的内存空间才可以存储该值,如下图,该值的起始地址为8

 <img src="https://gitee.com/usmiles/blog-image/raw/master/img/Avoiding-MemoryAlignment-cpuRead04.png" style="zoom:50%;" />

3.  如果上面int32类型的数据没有进行内存对齐,那么它在内存中的起始地址有可能如下图,cpu需要两次访存才能将其取出。

 <img src="https://gitee.com/usmiles/blog-image/raw/master/img/Avoiding-MemoryAlignment-cpuRead05.png" style="zoom:50%;" />

虽然编译器通过给指定类型的值自动做内存对齐有效的节省了内存,但是对于struct来说,编译器却不支持自动自动对齐。struct中各成员的排列顺序会直接影响到struct所占地址空间的大小,例如

1. ```go
 type Test1 struct{
     A int 32	// Alignof(T.A) ==  4 , Offsetof(T.A) ==  0
     B []int32	// Alignof(T.B) ==  8 , Offsetof(T.B) ==  8
     C string	// Alignof(T.C) ==  8 , Offsetof(T.C) ==  32
     D bool		// Alignof(T.D) ==  1 , Offsetof(T.D) ==  48
 }
 var T Test1{}
 // Test1: Sizeof(T) ==  56
Golang 内存对齐和伪共享False Sharing
  1. type Test2 struct{
        A int 32	// Alignof(T.A) ==  4 , Offsetof(T.A) ==  0
        D bool		// Alignof(T.D) ==  1 , Offsetof(T.D) ==  4
        B []int32	// Alignof(T.B) ==  8 , Offsetof(T.B) ==  8
        C string	// Alignof(T.C) ==  8 , Offsetof(T.C) ==  32
    }
    var T Test2{}
    // Test2: Sizeof(T) ==  48
    
    Golang 内存对齐和伪共享False Sharing
  2. type Test3 struct{
        D bool		// Alignof(T.D) ==  1 , Offsetof(T.D) ==  0
        A int 32	// Alignof(T.A) ==  4 , Offsetof(T.A) ==  4
        B []int32	// Alignof(T.B) ==  8 , Offsetof(T.B) ==  8
        C string	// Alignof(T.C) ==  8 , Offsetof(T.C) ==  32
    }
    var T Test3{}
    // Test3: Sizeof(T) ==  48
    
    Golang 内存对齐和伪共享False Sharing

上面 的Test1、Test2、Test3 拥有相同的成员,只不过他们各自成员的排列顺序不一样,却最终导致它们的实例实际占用了不同size的内存,这便是struct内存对齐的威力。

struct内存对齐

除了上面所说的struc的内存对齐规则外,还有两点需要注意

  1. struct本身也是需要对齐的,struct的对齐边界等于它的成员所拥有最大的对齐边界,比如上例中Test1、Test2、Test3的对齐边界就等于他们各自成员中最大的对齐边界,为8。struct的内存对齐是指,struct所占的地址空间必须为8的整数倍,注意,这里跟原生数据类型的对齐起始地址不同。正是因为struct本身也需要对齐,所以Test1所占的地址空间要比Test2和Test3要多一些。

  2. 空struct{}对齐,看下面的例子

    • type Test4 struct {
      	A struct{}	// Alignof(T.A) ==  1 , Offsetof(T.A) ==  0
      	B int32		// Alignof(T.B) ==  4 , Offsetof(T.B) ==  0
      }
      var T Test4
      // Sizeof(T) ==  4
      
      Golang 内存对齐和伪共享False Sharing
    • type Test5 struct {
      	B int32	// Alignof(T.B) ==  4 , Offsetof(T.B) ==  0
      	A struct{}	// Alignof(T.A) ==  1 , Offsetof(T.A) ==  4
      }
      var T Test5
      // Test5: Sizeof(T) ==  8
      
      Golang 内存对齐和伪共享False Sharing

从这个例子中可以看出来,当空struct{}作为其它struct的成员的时候,如果它的位置不是在最后,那它所占的内存空间的确是0,但是当它处在最后一个位置时,那它所占的内存空间大小就等于外层struc的对齐边界个byte。

struct{} 大小为 0,作为其他 struct 的字段时,一般不需要内存对齐。但是有一种情况除外:即当 struct{} 作为结构体最后一个字段时,需要内存对齐。因为如果有指针指向该字段, 返回的地址将在结构体之外,如果此指针一直存活不释放对应的内存,就会有内存泄露的问题(该内存不因结构体释放而释放)。

伪共享False Sharing

我们知道现代计算机中为了匹配memory和processor的速度,cpu中内置了三种级别的缓存Cache,这样的设计极大的提高了cpu的处理速度,但是它并非完美。要想发挥出Cache的全部性能,在代码中还需要做一些优化。先看下golang源码中做优化的例子:

在分析sync.Pool源码的那篇文章里,有这么一个结构体

type poolLocal struct {
	poolLocalInternal

	// Prevents false sharing on widespread platforms with
	// 128 mod (cache line size) = 0 .
	pad [128 - unsafe.Sizeof(poolLocalInternal{})%128]byte
}

看注释,可以知道这个pad数组就是用来防止false sharing的,那么什么是false sharing呢?它有什么危害?

先从CacheLine说起

CacheLine

  • 在cpu的Cache中数据是以缓存行(CacheLine)为单位进行存储的
  • cpu取缓存都是按照一行为最小单位操作的
  • 在64位cpu中Cacheline的大小为64byte
  • CacheLine正体现了局部性原理
Golang 内存对齐和伪共享False Sharing

伪共享的产生

当今的主流CPU都是多Core(核)CPU,在这些多核CPU中,L1和L2缓存不在内核(Core)之间共享。由于缓存维护的是来自主存的数据副本,因此处理器需要实现一种机制来使得缓存的内容与主存和其他缓存保持同步;这种机制被称为“缓存一致性”或“内存一致性”协议。

缓存一致性的朴素解决思想也比较简单:只要在多核共享缓存行上有数据修改操作,就通知所有的CPU核更新缓存,或者放弃缓存,等待下次访问的时候再重新从内存中读取。

当今大多数英特尔处理器使用的缓存一致性协议称为 MESI,这样命名以表示特定CacheLine所处的四种状态:已修改、独占、共享和无效

  • Modified(被修改的):处于这一状态的数据只在当前Core中有缓存,且其数据已被修改,但还没有更新到内存中。
  • Exclusive(独占的):处于这一状态的数据只在当前Core中有缓存,且其数据没有被修改,与内存一致。
  • Shared(共享的):处于这一状态的数据在多个Core中都有缓存。
  • Invalid(无效的):本CPU中的这份缓存已经无效了。

假设两个处理器 A 和 B, 都在各自本地 Cache Line 里有同一个变量的拷贝时,此时该 Cache Line 处于 Shared 状态。当处理器 A 在本地修改了变量,除去把本地变量所属的 Cache Line 置为 Modified 状态以外,

还必须在另一个处理器 B 读同一个变量前,对该变量所在的 B 处理器本地 Cache Line 发起 Invaidate 操作,标记 B 处理器的那条 Cache Line 为 Invalidate 状态。

随后,若处理器 B 在对变量做读写操作时,如果遇到这个标记为 Invalidate 的状态的 Cache Line,即会引发 Cache Miss,从而将内存中的数据拷贝到 Cache Line 里,然后处理器 B 再对此 Cache Line 对变量做读写操作。

Cache Line 伪共享问题,就是由多个 CPU 上的多个线程同时修改自己的变量引发的。这些变量表面上是不同的变量,但是实际上却存储在同一条 Cache Line 里。

在这种情况下,由于 Cache 一致性协议,两个处理器都存储有相同的 Cache Line 拷贝的前提下,本地 CPU 变量的修改会导致本地 Cache Line 变成 Modified 状态,然后在其它共享此 Cache Line 的 CPU 上,引发 Cache Line 的 Invaidate 操作,导致 Cache Line 变为 Invalidate 状态,从而使 Cache Line 再次被访问时,发生本地 Cache Miss,cpu不得不再次访存,从而伤害到应用的性能。参考

Golang 内存对齐和伪共享False Sharing

AMD 5800X 8核CPU的Cache信息:

Golang 内存对齐和伪共享False Sharing
总容量 类型 数量x容量 其它信息
L1$ 512 KiB L1I$ 256 KiB 8x32 KiB 8-way set associative
L1D$ 256 KiB 8x32 KiB 8-way set associative write-back
L2$ 4 MiB 8x512 KiB 8-way set associative write-back
L3$ 32 MiB 1x32MiB 16-way set associative write-back
  • 由表可知,每个Core都有自己的L1 Cache和L2 Cache,所有的Core共享一个L3 Cache

避免False Sharing

简单来说,就是用空间换时间,主动给struct填充一些字段,使它避免任意两个成员同时出现在同一个CacheLine中。

golang示例

  • 未作优化的struct

    type noPad struct {
    	a uint64
    	b uint64
    	c uint64
    }
    
    func (np *noPad)Increase() {
        // 原语:原子操作自增1,目的是避免自增操作被干扰
    	atomic.AddUint64(&np.a, 1)
    	atomic.AddUint64(&np.b, 1)
    	atomic.AddUint64(&np.c, 1)
    }
    -----------------------------
    cpu: AMD Ryzen 7 5800H with Radeon Graphics         
    BenchmarkNoPad_Increase
    BenchmarkNoPad_Increase-16    	37386787	        32.68 ns/op
    PASS
    
  • 在struct中使用匿名数组填充Cache Line,避免两个成员同时出现在同一个CacheLine中

    type Pad7 struct {
    	a uint64
    	_ [7]uint64
    	b uint64
    	_ [7]uint64
    	c uint64
    	_ [7]uint64
    }
    
    func (p *Pad7)Increase() {
    	atomic.AddUint64(&p.a, 1)
    	atomic.AddUint64(&p.b, 1)
    	atomic.AddUint64(&p.c, 1)
    }
    ---------------------------
    cpu: AMD Ryzen 7 5800H with Radeon Graphics         
    BenchmarkPad7_Increase
    BenchmarkPad7_Increase-16    	65326725	        18.37 ns/op
    PASS
    
  • 可以看到,对struct优化过的程序执行速度是未优化过的三倍还多,这个差距简直离谱。

像上面案例中的Pad7,就是通过填充匿名数组,使得任意两个具名成员分别处在不同的CacheLine上。

需要注意的是,这种机械处理方式仅仅针对特定的平台,比如CacheLine为64Byte的平台,要是跨平台,这样的处理很可能就是纯粹的浪费Cache。而且在当今的处理器中Cache的命中率已经非常高了,与其花大量的精力去解决False Sharing问题,不如优先专注于业务。

上一篇:高速缓存cache详解


下一篇:浏览器缓存 expires cache-control last-modified etag 详解 —— FEI面试官养成系列