乐趣区

关于缓存:CPU高速缓存与极性代码设计

摘要:CPU 内置大量的高速缓存的重要性显而易见,在体积、老本、效率等因素下产生了当今用到的计算机的存储构造。

1. 介 绍

2. CPU 缓存的构造

3. 缓存的存取与统一

4. 代码设计的考量

5. 最 后

CPU 频率太快,其处理速度远快于存储介质的读写。因而,导致 CPU 资源的节约,须要无效解决 IO 速度和 CPU 运算速度之间的不匹配问题。芯片级高速缓存可大大减少之间的解决提早。CPU 制作工艺的提高使得在比以前更小的空间中装置数十亿个晶体管,如此可为缓存留出更多空间,使其尽可能地凑近外围。

CPU 内置大量的高速缓存的重要性显而易见,在体积、老本、效率等因素下产生了当今用到的计算机的存储构造。

  1. 介 绍

计算机的内存具备基于速度的层次结构,CPU 高速缓存位于该层次结构的顶部,是介于 CPU 内核和物理内存 (动态内存 DRAM) 之间的若干块动态内存,是最快的。它也是最靠近中央处理的中央,是 CPU 自身的一部分,个别间接跟 CPU 芯片集成。

CPU 计算:程序被设计为一组指令,最终由 CPU 运行。

装载程序和数据,先从最近的一级缓存读取,如有就间接返回,逐层读取,直至从内存及其它内部存储中加载,并将加载的数据顺次放入缓存。

高速缓存中的数据写回主存并非立刻执行,写回主存的机会:

1. 缓存满了,采纳先进先出或最久未应用的程序写回;

2.#Lock 信号,缓存一致性协定,明确要求数据计算实现后要立马同步回主存。

  1. CPU 缓存的构造

古代的 CPU 缓存构造被分为多解决、多核、多级的档次。

2.1 多级缓存构造

分为三个次要级别,即 L1,L2 和 L3。离 CPU 越近的缓存,读取效率越高,存储容量越小,造价越高。

L1 高速缓存是零碎中存在的最快的内存。就优先级而言,L1 缓存具备 CPU 在实现特定工作时最可能须要的数据,大小通常可达 256KB,一些功能强大的 CPU 占用近 1MB。某些服务器芯片组 (如 Intel 高端 Xeon CPU) 具备 1 -2MB。L1 缓存通常又分为指令缓存和数据缓存。指令缓存解决无关 CPU 必须执行的操作的信息,数据缓存则保留要在其上执行操作的数据。如此,缩小了争用 Cache 所造成的抵触,进步了处理器效力。

L2 级缓存比 L1 慢,但大小更大,通常在 256KB 到 8MB 之间,功能强大的 CPU 往往会超过此大小。L2 高速缓存保留下一步可能由 CPU 拜访的数据。大多数 CPU 中,L1 和 L2 高速缓存位于 CPU 内核自身,每个内核都有本人的高速缓存。

L3 级高速缓存是最大的高速存储单元,也是最慢的。大小从 4MB 到 50MB 以上。古代 CPU 在 CPU 裸片上具备用于 L3 高速缓存的专用空间,且占用了很大一部分空间。

2.2 多处理器缓存构造

计算机早已进入多核时代,软件也运行在多核环境。一个处理器对应一个物理插槽、蕴含多个核(一个核蕴含寄存器、L1 Cache、L2 Cache),多核间共享 L3 Cache,多处理器间通过 QPI 总线相连。

L1 和 L2 缓存为 CPU 单个外围公有的缓存,L3 缓存是同插槽的所有外围都共享的缓存。

L1缓存 被分成独立的 32K 数据缓存和 32K 指令缓存,L2缓存 被设计为 L1 与共享的 L3 缓存之间的缓冲。大小为 256K,次要作为 L1 和 L3 之间的高效内存拜访队列, 同时蕴含数据和指令。L3缓存 包含了在同一个槽上的所有 L1 和 L2 缓存中的数据。这种设计耗费了空间,但可拦挡对 L1 和 L2 缓存的申请,加重了各个外围公有的 L1 和 L2 缓存的累赘。

2.3 Cache Line

Cache 存储数据以固定大小为单位,称为 Cache Line/Block。给定容量和 Cache Line size,则就固定了存储的条目个数。对于 X86,Cache Line 大小与 DDR 一次访存能失去的数据大小统一,即 64B。旧的 ARM 架构的 Cache Line 是 32B,因而常常是一次填两个 Cache Line。CPU 从 Cache 获取数据的最小单位为字节,Cache 从 Memory 获取的最小单位是 Cache Line,Memory 从磁盘获取数据通常最小是 4K。

Cache 分成多个组,每组分成多个 Cache Line 行,大抵如下图:

Linux 零碎下应用以下命令查看 Cache 信息,lscpu 命令也可。

  1. 缓存的存取与统一

上面表格形容了不同存储介质的存取信息,供参考。

存取速度:寄存器 > cache(L1~L3) > RAM > Flash > 硬盘 > 网络存储

以 2.2Ghz 频率的 CPU 为例,每个时钟周期大略是 0.5 纳秒。

3.1 读取存储器数据

按 CPU 层级缓存构造,取数据的程序是先缓存再主存。当然,如数据来自寄存器,只需间接读取返回即可。

1) 如 CPU 要读的数据在 L1 cache,锁住 cache 行,读取后解锁、返回

2) 如 CPU 要读的数据在 L2 cache,数据在 L2 里加锁,将数据复制到 L1,再执行读 L1

3) 如 CPU 要读的数据在 L3 cache,也一样,只不过先由 L3 复制到 L2,再从 L2 复制到 L1,最初从 L1 到 CPU

4) 如 CPU 需读取内存,则首先告诉内存控制器占用总线带宽,后内存加锁、发动读申请、期待回应,回应数据保留至 L3,L2,L1,再从 L1 到 CPU 后解除总线锁定。

3.2 缓存命中与提早

因为数据的局部性原理,CPU 往往须要在短时间内反复屡次读取数据,内存的运行频率远跟不上 CPU 的处理速度,缓存的重要性被凸显。CPU 可避开内存在缓存里读取到想要的数据,称之为命中。L1 的运行速度很快,但容量很小,在 L1 里命中的概率大略在 80% 左右,L2、L3 的机制也相似。这样一来,CPU 须要在主存中读取的数据大略为 5%-10%,其余命中全副能够在 L1、L2、L3 中获取,大大减少了零碎的响应工夫。

高速缓存旨在放慢主内存和 CPU 之间的数据传输。从内存拜访数据所需的工夫称为提早,L1 具备最低提早且最靠近外围,而 L3 具备最高的提早。缓存未命中时,因为 CPU 需从主存储器中获取数据,导致提早会更多。

3.3 缓存替换策略

Cache 里的数据是 Memory 中罕用数据的一个拷贝,存满后再存入一个新的条目时,就须要把一个旧的条目从缓存中拿掉,这个过程称为 evict。缓存治理单元通过肯定的算法决定哪些数据须要从 Cache 里移出去,称为替换策略。最简略的策略为 LRU,在 CPU 设计的过程中,通常会对替换策略进行改良,每一款芯片简直都应用了不同的替换策略。

3.4 MESI 缓存一致性

在多 CPU 的零碎中,每个 CPU 都有本人的本地 Cache。因而,同一个地址的数据,有可能在多个 CPU 的本地 Cache 里存在多份拷贝。为了保障程序执行的正确性,就必须保障同一个变量,每个 CPU 看到的值都是一样的。也就是说,必须要保障每个 CPU 的本地 Cache 中可能如实反映内存中的实在数据。

假如一个变量在 CPU0 和 CPU1 的本地 Cache 中都有一份拷贝,当 CPU0 批改了这个变量时,就必须以某种形式告诉 CPU1,以便 CPU1 可能及时更新本人本地 Cache 中的拷贝,这样能力在两个 CPU 之间保持数据的同步,CPU 之间的这种同步有较大开销。

为保障缓存统一,古代 CPU 实现了非常复杂的多核、多级缓存一致性协定 MESI, MESI 具体的操作上会针对单个缓存行进行加锁。

MESI:Modified Exclusive Shared or Invalid

1) 协定中的状态

CPU 中每个缓存行应用 4 种状态进行标记(应用额定的两位 bit 示意)

M: Modified

该缓存行只被缓存在该 CPU 的缓存中,且被批改过 (dirty), 即与主存中的数据不统一,该缓存行中的内容需在将来的某个工夫点(容许其它 CPU 读取主存中相应内存之前) 写回主存。当被写回主存之后,该缓存行的状态变成独享 (exclusive) 状态

E: Exclusive

该缓存行只被缓存在该 CPU 的缓存中,未被批改,与主存中数据统一。在任何时刻当有其它 CPU 读取该内存时变成 shared 状态。同样,当批改该缓存行中内容时,该状态能够变成 Modified 状态.

S: Shared

象征该缓存行可能被多个 CPU 缓存,各个缓存中的数据与主存数据统一,当有一个 CPU 批改该缓存行中,其它 CPU 中该缓存行能够被作废(Invalid).

I: Invalid,缓存有效(可能其它 CPU 批改了该缓存行)

2) 状态切换关系

由下图可看出 cache 是如何保障它的数据一致性的。

譬如,以后外围要读取的数据块在其外围的 cache 状态为 Invalid,在其余外围上存在且状态为 Modified 的状况。能够从以后外围和其它外围两个角度观察,其它外围角度:以后状态为 Modified,其它外围想读这个数据块(图中 Modified 到 Shared 的绿色虚线):先把扭转后的数据写入到内存中(先于其它外围的读),并更新该 cache 状态为 Share. 以后外围角度:以后状态为 Invalid,想读这个数据块(图中 Invalid 到 Shared 的绿色实线):这种状况下会从内存中从新加载,并更新该 cache 状态 Share

以下表格从这两个角度列举了所有状况,供参考:

3) 缓存的操作形容

一个典型零碎中会有几个缓存 (每个外围都有) 共享主存总线,每个相应的 CPU 会收回读写申请,而缓存的目标是为了缩小 CPU 读写共享主存的次数。

l 一个缓存除在 Invalid 状态外都能够满足 CPU 的读申请,一个 Invalid 的缓存行必须从主存中读取 (变成 S 或 E 状态) 来满足该 CPU 的读申请。

l 一个写申请只有在该缓存行是 M 或 E 状态时能力被执行,如果缓存行处于 S 状态,必须先将其它缓存中该缓存行变成 Invalid(不容许不同 CPU 同时批改同一缓存行,即便批改该缓存行中不同地位的数据也不可),该操作常以播送形式来实现。

l 缓存能够随时将一个非 M 状态的缓存行作废,或变成 Invalid,而一个 M 状态的缓存行必须先被写回主存。一个处于 M 状态的缓存行必须时刻监听所有试图读该缓存行绝对主存的操作,操作必须在缓存将该缓存行写回主存并将状态变成 S 状态之前被提早执行。

l 一个处于 S 状态的缓存行需监听其它缓存使该缓存行有效或独享该缓存行的申请,并将该缓存行变成有效。

l 一个处于 E 状态的缓存行也必须监听其它读主存中该缓存行的操作,一旦有这种操作,该缓存行需变成 S 状态。

l 对于 M 和 E 状态而言总是准确的,和该缓存行的真正状态是统一的。而 S 状态可能是非统一的,如果一个缓存将处于 S 状态的缓存行作废了,而另一个缓存实际上可能曾经独享了该缓存行,然而该缓存却不会将该缓存行升迁为 E 状态,是因为其它缓存不会播送作废掉该缓存行的告诉,同样,因为缓存并没有保留该缓存行的 copy 的数量,因而也没有方法确定本人是否曾经独享了该缓存行。

从下面的意义来看,E 状态是一种投机性的优化:如果一个 CPU 想批改一个处于 S 状态的缓存行,总线事务须要将所有该缓存行的 copy 变成 Invalid 状态,而批改 E 状态的缓存不须要应用总线事务。

  1. 代码设计的考量

了解计算机存储器层次结构对应用程序的性能影响。如果须要的程序在 CPU 寄存器中,指令执行时 1 个周期内就能拜访到;如果在 CPU Cache 中,需 1~30 个周期;如果在主存中,须要 50~200 个周期;在磁盘上,大略须要万级周期。另外,Cache Line 的存取也是代码设计者须要关注的局部, 以躲避伪共享的执行场景。因而,充分利用缓存的构造和机制可无效进步程序的执行性能。

4.1 局部性个性

一旦 CPU 要从内存或磁盘中拜访数据就会产生一个很大的时延,程序性能显著升高,为此咱们不得不进步 Cache 命中率,也就是充分发挥局部性原理。一般来说,具备良好局部性的程序会比局部性较差的程序运行得更快,程序性能更好。

局部性机制确保在拜访存储设备时,存取数据或指令都趋于汇集在一片间断的区域。一个设计低劣的计算机程序通常具备很好的局部性,工夫局部性和空间局部性。

1) 工夫局部性

如果一个数据 / 信息项被拜访过一次,那么很有可能它会在很短的工夫内再次被拜访。比方循环、递归、办法的重复调用等。

2) 空间局部性

一个 Cache Line 有 64 字节块,能够充分利用一次加载 64 字节的空间,把程序后续会拜访的数据,一次性全副加载进来,从而进步 Cache Line 命中率(而非从新去寻址读取)。如果一个数据被拜访,那么很有可能位于这个数据左近的其它数据也会很快被拜访到。比方程序执行的代码、间断创立的多个对象、数组等。数组就是一种把局部性原理利用到极致的数据结构。

3) 代码示例

示例 1,(C 语言)

// 程序 array1.c  多维数组替换行列拜访程序
char array[10240][10240];

int main(int argc, char *argv[]){
   int i = 0;
   int j = 0;
   for(i=0; i < 10240 ; i++) {for(j=0; j < 10240 ; j++) {array[i][j] =‘A’; // 按行进行拜访
      }
   }
   return 0;
}

红色字体的代码调整为:arrayj =‘A’; // 按列进行拜访

编译、运行后果如下:

从测试后果看,第一个程序运行耗时 0.265 秒,第二个 1.998 秒,是第一个程序的 7.5 倍。

案例参考:https://www.cnblogs.com/wangh…

后果剖析

数组元素存储在地址间断的内存中,多维数组在内存中是按行进行存储 。第一个程序按行拜访某个元素时,该元素左近的一个 Cache Line 大小的元素都会被加载到 Cache 中,这样一来,在拜访紧挨着的下一个元素时,就可间接拜访 Cache 中的数据,不需再从内存中加载。也就是说, 对数组按行进行拜访时,具备更好的空间局部性,Cache 命中率更高

第二个程序按列拜访某个元素,尽管该元素左近的一个 Cache Line 大小的元素也会被加载进 Cache 中,但接下来要拜访的数据却不是紧挨着的那个元素,因而很有可能会再次产生 Cache miss,而不得不从内存中加载数据。而且,尽管 Cache 中会尽量保留最近拜访过的数据,但 Cache 大小无限,当 Cache 被占满时,就不得不把一些数据给替换掉。这也是空间局部性差的程序更容易产生 Cache miss 的重要起因之一。

示例 2,(Java)

以下代码中长度为 16 的 row 和 column 数组,在 Cache Line 64 字节数据块上内存地址是间断的,能被一次加载到 Cache Line 中,在拜访数组时命中率高,性能施展到极致。

public int run(int[] row, int[] column) {
       int sum = 0;
       for(int i = 0; i < 16;i++) {sum += row[i] * column[i];
       }
       return sum;
}

变量 i 体现了工夫局部性,作为计数器被频繁操作,始终寄存在寄存器中,每次从寄存器拜访,而不是从缓存或主存拜访。

4.2 缓存行的锁竞争

在多处理器下,为保障各个处理器的缓存统一,会实现缓存一致性协定,每个处理器通过嗅探在总线上流传的数据来查看本人缓存的值是不是过期,当处理器发现自己缓存行对应的内存地址被批改,就会将以后处理器的缓存行置成有效状态,当处理器要对这个数据进行批改操作的时候,会强制从新从零碎内存里把数据读到处理器缓存里。

当多个线程对同一个缓存行拜访时,如其中一个线程锁住缓存行,而后操作,这时其它线程则无奈操作该缓存行。这种状况下,咱们在进行程序代码设计时是要尽量避免的。

4.3 伪共享的躲避

间断紧凑的内存调配带来高性能,但并不代表它始终都卓有成效,伪共享就是无声的性能杀手。所谓伪共享(False Sharing),是因为运行在不同 CPU 上的不同线程,同时批改处在同一个 Cache Line 上的数据引起。缓存行上的写竞争是运行在 SMP 零碎中并行线程实现可伸缩性最重要的限度因素,一般来说,从代码中很难看清是否会呈现伪共享。

在每个 CPU 来看,各自批改的是不同的变量,但因为这些变量在内存中彼此紧挨着,因而它们处于同一个 Cache Line 上。当一个 CPU 批改这个 Cache Line 之后,为了保证数据的一致性,必然导致另一个 CPU 的本地 Cache 的有效,因此触发 Cache miss,而后从内存中从新加载变量被批改后的值。多个线程频繁的批改处于同一个 Cache Line 的数据,会导致大量的 Cache miss,因此造成程序性能的大幅降落。

下图阐明了两个不同 Core 的线程更新同一缓存行的不同信息项:

上图阐明了伪共享的问题。在 Core1 上运行的线程筹备更新变量 X,同时 Core2 上的线程筹备更新变量 Y。然而,这两个变量在同一个缓存行中。每个线程都要去竞争缓存行的所有权来更新变量。如果 Core1 取得了所有权,缓存子系统将会使 Core2 中对应的缓存行生效。当 Core2 取得了所有权而后执行更新操作,Core1 就要使本人对应的缓存行生效。来来回回的通过 L3 缓存,大大影响了性能。如果相互竞争的 Core 位于不同的插槽,就要额定横跨插槽连贯,问题可能更加重大。

1) 躲避解决形式

l 增大数组元素的距离使得不同线程存取的元素位于不同 cache line,空间换工夫

l 在每个线程中创立全局数组各个元素的本地拷贝,而后完结后再写回全局数组

2) 代码示例阐明

示例 3,(JAVA)

从代码设计角度,要思考分明类构造中哪些变量是不变,哪些是常常变动,哪些变动是齐全互相独立,哪些属性一起变动。如果业务场景中,上面的对象满足几个特点

public class Data{

    long modifyTime;

    boolean flag;

    long createTime;

    char key;

    int value;

}

l 当 value 变量扭转时,modifyTime 必定会扭转

l createTime 变量和 key 变量在创立后就不会再变动

l flag 也常常会变动,不过与 modifyTime 和 value 变量毫无关联

当下面的对象须要由多个线程同时拜访时,从 Cache 角度,当咱们没有加任何措施时,Data

对象所有的变量极有可能被加载在 L1 缓存的一行 Cache Line 中。在高并发拜访下,会呈现这种问题:

如上图所示,每次 value 变更时,依据 MESI 协定,对象其余 CPU 上相干的 Cache Line 全副被设置为生效。其余的处理器想要拜访未变动的数据 (key 和 createTime) 时,必须从内存中从新拉取数据,增大了数据拜访的开销。

无效的 Padding 形式

正确形式是将该对象属性分组,将一起变动的放在一组,与其余无关的放一组,将不变的放到一组。这样当每次对象变动时,不会带动所有的属性从新加载缓存,晋升了读取效率。在 JDK1.8 前,个别在属性间减少长整型变量来分隔每一组属性。被操作的每一组属性占的字节数加上前后填充属性所占的字节数,不小于一个 cache line 的字节数就可达到要求。

public class DataPadding{
       long a1,a2,a3,a4,a5,a6,a7,a8;// 避免与前一个对象产生伪共享
       int value;
       long modifyTime;
       long b1,b2,b3,b4,b5,b6,b7,b8;// 避免不相干变量伪共享;
       boolean flag;
       long c1,c2,c3,c4,c5,c6,c7,c8;//
       long createTime;
       char key;
       long d1,d2,d3,d4,d5,d6,d7,d8;// 避免与下一个对象产生伪共享
}

采取上述措施后的图示:

在 Java 中

Java8 实现字节填充防止伪共享,JVM 参数 -XX:-RestrictContended

@Contended 位于 sun.misc 用于注解 java 属性字段,主动填充字节,避免伪共享。

示例 4,(C 语言)

**//**** 程序 thread1.c** ** 多线程拜访数据结构的不同字段 **

#include <stdio.h>
#include <pthread.h>

struct {
     int a;
     // charpadding[64]; // thread2.c 代码
     int b;
}data;

 void *thread_1(void) {
        int i = 0;
     for(i=0; i < 1000000000; i++){data.a = 0;}
}
void *thread_2(void) {
       int i = 0;
    for(i=0; i < 1000000000; i++){data.b = 0;}
}

// 程序 thread2.c

Thread1.c 中的红色字体行,关上正文即为 thread2.c

main()函数很简略,创立两个线程并运行, 参考代码如下:

pthread_t id1;
int ret = pthread_create(&id1,NULL, (void*)thread_1,NULL);

编译、运行后果如下:

从测试后果看,第一个程序耗费的工夫是第二个程序的 3 倍

案例参考:https://www.cnblogs.com/wangh…

后果剖析

此示例波及到 Cache Line 的伪共享问题。两个程序惟一的区别是,第二个程序中字段 a 和 b 两头有一个大小为 64 个字节的字符数组。第一个程序中,字段 a 和字段 b 处于同一个 Cache Line 上,当两个线程同时批改这两个字段时,会触发 Cache Line 伪共享问题,造成大量的 Cache miss,进而导致程序性能降落。

第二个程序中,字段 a 和 b 两头加了一个 64 字节的数组,这样就保障了这两个字段处在不同的 Cache Line 上。如此一来,两个线程即使同时批改这两个字段,两个 cache line 也互不影响,cache 命中率很高,程序性能会大幅晋升。

示例 5,(C 语言)

在设计数据结构的时候,尽量将只读数据与读写数据离开,并具尽量将同一时间拜访的数据组合在一起。这样 CPU 能一次将须要的数据读入。譬如,上面的数据结构就很不好。

struct __a

{

   int id; // 不易变

   int factor;// 易变

   char name[64];// 不易变

   int value;// 易变

};

在 X86 下,能够试着批改和调整它

#define CACHE_LINE_SIZE 64  // 缓存行长度

struct __a

{

   int id; // 不易变

   char name[64];// 不易变

  char __align[CACHE_LINE_SIZE – sizeof(int)+sizeof(name) * sizeof(name[0]) %
CACHE_LINE_SIZE]

   int factor;// 易变

   int value;// 易变   char __align2[CACHE_LINE_SIZE –2* sizeof(int)%CACHE_LINE_SIZE ]};

CACHE_LINE_SIZE–sizeof(int)+sizeof(name)*sizeof(name[0])%CACHE_LINE_SIZE看起来不谐和,CACHE_LINE_SIZE示意高速缓存行(64B 大小)。__align 用于显式对齐,这种形式使得构造体字节对齐的大小为缓存行的大小。

4.4 缓存与内存对齐

1)字节对齐

attribute ((packed))通知编译器勾销构造在编译过程中的优化对齐, 依照理论占用字节数进行对齐,是 GCC 特有的语法;

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

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

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

字节对齐的细节和编译器实现相干,但一般而言,满足三个准则:

1)(构造体)变量的首地址可能被其 (最宽) 根本类型成员的大小所整除;

2)构造体每个成员绝对于首地址的偏移量都是成员大小的数倍,如有须要, 编译器会在成员之间加上填充字节(internal adding)

3)构造体的总大小为构造体最宽根本类型成员大小的数倍,如有须要, 编译器会在最末一个成员之后加上填充字节(trailing padding)

2)缓存行对齐

数据逾越两个 cache line,意味着两次 load 或两次 store。如果数据结构是 cache line 对齐的,就有可能缩小一次读写。数据结构的首地址 cache line 对齐,意味着可能有内存节约 (特地是数组这样间断调配的数据结构),所以须要在空间和工夫两方面衡量。比方当初个别的 malloc() 函数,返回的内存地址会曾经是 8 字节对齐的,这就是为了可能让大部分程序有更好的性能。

在 C 语言中,为了防止伪共享,编译器会主动将构造体,字节补全和对齐,对齐的大小最好是缓存行的长度。总的来说,构造体实例会和它的最宽成员一样对齐。编译器这样做是因为这是保障所有成员自对齐以取得疾速存取的最容易办法。

__attribute__((aligned(cache_line)))对齐实现 struct syn_str {ints_variable;
};__attribute__((aligned(cache_line)));

示例 6,(C 语言)

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);

4.5 CPU 分支预测

代码在内存外面是顺序排列的,能够程序拜访,无效进步缓存命中。对于分支程序来说,如果分支语句之后的代码有更大的执行几率,就能够缩小跳转,个别 CPU 都有指令预取性能,这样能够进步指令预取命中的几率。分支预测用的就是 likely/unlikely 这样的宏,个别须要编译器的反对,属动态的分支预测。当初也有很多 CPU 反对在外部保留执行过的分支指令的后果(分支指令 cache),所以动态的分支预测就没有太多的意义。

示例 7,(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 的可能性更大,编译后察看汇编指令,后果如下:

`Disassembly of section .text:00000000 <testfun>:
   0:  55             push  %ebp
   1:   89e5           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

4.6 命中率的监控

程序设计要谋求更好的利用 CPU 缓存,来缩小从内存读取数据的低效。在程序运行时,通常须要关注缓存命中率这个指标。

监控办法(Linux):查问 CPU 缓存无命中次数及缓存申请次数,计算缓存命中率

perf stat -e cache-references -e cache-misses

4.7 小 结

程序从内存获取数据时,每次不仅取回所需数据,还会依据缓存行的大小加载一段间断的内存数据到缓存中,程序设计中的优化范式参考如下。

l 在汇合遍历的场景,可应用有序数组,数组在内存中是一段间断的空间;

l 字段尽量定义为占用字节小的类型,如 int 可满足时,不应用 long。这样单次可加载更多的数据到缓存中;

l 对象或构造体大小尽可能设置为 CPU 外围缓存行的整数倍。基于 64B 大小的缓存行,如读取的数据是 50B,最坏状况下须要两次从内存加载;当为 70B 时,最坏状况须要三次内存读取,能力加载到缓存中;

l 对同一对象 / 构造体的多个属性,可能存在于同一缓存行中,导致伪共享问题,需为属性的不变与常变,变动的独立与关联而隔离设计,及缓存行对齐,解决多线程高并发环境下缓存生效、彼此牵制问题;

l CPU 有分支预测能力,在应用 ifelse case when 等循环判断的场景时,能够程序拜访,无效进步缓存的命中

. . . . . .

除了本章节中介绍的案例之外,在零碎中 CPU Cache 对程序性能的影响随处可见。

点击关注,第一工夫理解华为云陈腐技术~

退出移动版