专栏首页猿人谷对缓存的思考——提高命中率

对缓存的思考——提高命中率

开篇

编写高效的程序并不只在于算法的精巧,还应该考虑到计算机内部的组织结构,cpu微指令的执行,缓存的组织和工作原理等。

好的算法在实际中不见得有高效率,如果完全没有考虑缓存、微指令实现的话。

前两篇博文

局部性原理浅析 介绍了程序的局部性原理,如何写出局部性良好代码。

提高程序性能、何为缓存 讨论了存储器层次结构,计算机内部的存储结构、缓存的概念,简单的介绍了缓存的工作机制。

建议先阅读前两篇博文,虽然他们之间联系不大,在前面也有一些对本文的铺垫。而且,这是一个系列的文章。旨在优化程序性能。

这篇博文主要介绍的是缓存的组织、工作原理。拨开迷雾,让你更加清晰的认识缓存。

通用缓存结构

回顾

提高程序性能、何为缓存中 提到:早起的cpu存储层次只有三层,即cup的寄存器,DRAM主存和磁盘存储。因为寄存器和主存之间的访问时间开销差距很大,于是设计者在寄存器(一 个时钟周期)和主存之间加入了L1缓存(2——4个时钟周期),后来由于L1缓存和主存之间的差距,又在主存和L1之间加入了L2缓存,当然后面还有L3 缓存,,,等等。

在这里为了简单起见,假设CPU寄存器和主存之间只有一个L1缓存。

下图是高速缓存存储器的典型总线结构:

缓存结构

下图清晰的说明了通用缓存的组织结构:

可以看到,缓存内部是以组的形式组织的。图中的每一块代表一组,每组由一到多行组成(当然图中的是每组有多行)。

每一行包括

1 位标记位(valid bit)标明这行的信息是否有可用

t 位的标记,标明它是属于这一组的哪一行

剩下的空间是存储数据的数据的空间

可以看出在下面的图中把数据地址分为了三部分,左边 t 位是标记行号的,中间的 s 位标明组号,最后的 b 位则是数据块在行内的偏移量。

通常来说,缓存器可描述为(S; E; B; m)其中S为缓存中的组数,E为每组的行数,B为每行存储的字节数,m为缓存的地址位数。

所以缓存的容量为C=S*E*B。

从缓存中取数据

(这个过程在上一篇博文中就有简单的介绍)当cpu需要从主存中取出地址为A的数据时,先把地址A发送给缓存,如果缓存中存有地址为A的数据,就从缓存中取出该数据传给cpu。

那么,缓存是如何知道自己是否存有地址为A的数据呢?这就和缓存的组织有关系了,上文中缓存把地址组分为了三部分,t 、s 、b。

所以,只要简单的检查地址中的数据位,就能判断该地址是否在缓存中,如果在的话,还能确定该数据的位置。

参数 s 、b 、m 把m个地址位分为三个字段。如下图:

下面的详细的寻址过程

地址A中的中间S 位标记了该地址在缓存中属于哪一组,先通过s 确定这个地址在缓存中的哪一组。

通过上面一步确定了属于的组后,地址A中的左边 t 位标记了该地址在该组的哪一行。

最后由右边的 b 指出地址A中的元素在该行的偏移位。也就是确定在这行的哪一个位置。

CPU从主存中读数据的详细过程

和上文中说的一样,这里假设计算机的存储结构只有:cpu寄存器,L1缓存,主存。

当cpu执行一条读存储器地址为A的指令,它向高速缓存请求该地址,如果缓存命中,缓存很快返回数据。如果缓存不命中,L1缓存向主存请求该数据, 在这期间cpu必须等待。当被请求块从主存到达缓存L1时,L1缓存将数据放在他的一个高速缓存行里,然后将数据从行中提取返回给cpu。也就是说,如果 缓存不命中,先要把数据存入缓存,再返回给cpu。

概括的说,高速缓存确定一个请求是否命中有三个过程: 

1、组选择

2、行匹配

3、字抽取

下面将会结合具体情况说明这一过程。

直接映射高速缓存

现在已经知道,我们用(S; E; B; m) 来描述缓存,这里就根据其中的E,也就是一组的行数, 把缓存分为不同的类别。

当E=1 时,也就是说每组只有一行的缓存组织形式,我们称为直接映射高速缓存。因为容易理解,先对它进行介绍。

(图片来源 《computer systems》)

正如上图所示,直接映射高速缓存中每组只有一行。

直接映射高速缓存中取数据

下面将以直接映射高速缓存为例,一步步说明cup从高速缓存中取数据的过程。

1、组选择

如上图所示,缓存从地址A中抽取出中间的s 位,这 s 为的数值就标记了该地址所在的组。这里可以把缓存当作是一维数组,其中每个元素是一个组,而地址中的 s 位则是这些组的索引。如图中的组标记为 0001 对应组 set1。这要把地址中间的 s 为提取,就能得到该地址在缓存中对应的组。

2、 行选择

选好组 i 之后,就是确定地址A在组 i 的哪一行。因为直接映射缓存的每一组只有一个行。所以只要看A地址中的行标记是否和缓存中的行标记位匹配。匹配则地址A中的数据在缓存中。

3、字抽取

既然已知道了地址A中的数据在缓存中的位置,最后一步只要更具地址A中表示偏移量的位,从缓存中取出数据即可。

如下图所示:

直接映射高速缓存不命中

当缓存不命中的时候,就要从下一层存储中取出数据,放入缓存的某个位置中,放入的位置就由请求地址A中的组索引确定所在缓存的组,行所以确定应该放 置的行。如果组中的行都是有效缓存行了,就必须要驱逐现有的一个行。对于直接映射高速缓存,每组包含一个行,替换策略就变的很简单,用新来的行替换当前 行。

直接映射缓存寻址示例

通过上面的介绍,已经基本了解了缓存的组织形式以及如何从缓存中取出数据,但是上面都只是理论上的阐述。

为了能更好的了解,这里会有一个具体的示例。诚然,学习一种只是最好的方式就是应用它。 如果你已经对上面的知识有所了解,那么请继续吧。下面的内容会让你更清楚的了解到缓存工作的机制。

假设我们有一个直接映射的高速缓存,描述如下

(S; E; B; m)=(4;1;2;4)

也就是说:该缓存有4个组(s=4),每组有一行(E=1),每一块有两个字节(B=2)存储器的地址是4位的(m=4)

该状态有图描述如下:

其中最左边的一列是地址,中间的三列是地址的二进制表示形式。最右边的一列是虚拟存储器的块的标号。

和上文中说的一样,缓存寻址时,把地址分为了三个部分。分别表示该地址在缓存中所在的组、行、以及偏移。和上图所对应是四位的地址,

行:其中最高的一位标记所在的行,因为是直接映射高速缓存,每组只有一行,所以一位就能表示。

:中间的两位表示地址所在的组。从图中可以看出,拥有相同组的地址有四个,比如组号为00 的地址有四个,为0、2、8、9

偏移:偏移位由最右边的一位表示。每行中有两个数据块,所以偏移位用一位也就能表示。

看这个表的时候有一点提示:中间的三列其实是第一列地址的二进制表示形式。

下面是对这个特定缓存的一点分析:

(S; E; B; m)=(4;1;2;4)

该缓存有四个组,每组一行。有图中可知,要放入缓存的地址为16个。所以每组对应四个地址。在图中的表现就是:四个相同的地址有相同的组索引。

每行有两个数据块,用地址最低位表示(0表示第一个,1为第二个)。

看组索引为00的地址,为0 、1 和 8 、9。0和1有相同的行标记0,8和9有相同的行标记1.所以地址为0、1的数据要么都在组00中,要么多不在。地址为8、9的也一样。说明了0、1是一 个整体,8、9也一样。如果在,都在;不在,都不在。这两个整体通过最高位(标记为)来标明。

下面是寻址实例

刚开始时,缓存是空的,也就是还没有预热,如下图所示

1)读地址0的字

地址0的为 0 00 0 对应缓存中第0组,行标记位为0的,偏移为0的位置。显然,现在缓存还是空的(标志位 valid 都为0)。缓存不命中,所以缓存先从下一级的存储中取出改行对应的所有地址的元素,放入缓存中。(也就是地址为0 和1 的元素)。然后再从缓存中取出数据m[0],传递给cpu。

进过对地址0的读操作后,缓存的组织情况如下所示

这也验证了上文的说法,地址0 和1 是一体的,他们要么都在,要么都不在。因为他们有相同的组索引、行索引。

2)读取地址1的字

地址1为0 00 1 对应缓存中的第0组,行标记为0,偏移为1。这次缓存命中,从缓存返回m[1]

3)读地址13的字

地址13为1 10 1 对应缓存中的第2组 行标记为1 偏移为1。同1)一样,缓存不命中,从低一级存储中取出 组索引为10 行为1 的数据放入缓存,然后返回m[13]

对地址13进行操作后的缓存情况为

4)读地址为8的字

地址8为 1 00 0 组索引为00 行标记为1 偏移为0 在看上图的缓存组织情况,可判读发生缓存不命中。于是从低一级存储中取出组索引为00 行标记为1 的数据,也就是m[8]、m[9]放入第一行中,然后返回m[8]

操作后的缓存组织为

通过上面的示例,应该对缓存的工作原理有一定了解了把。

其实就是吧地址分为不同的部分,划分为表示组、行 和偏移。然后根据这些去判断所需地址是否在缓存中。如果在,则返回数据,不在则从低一级的存储中取出数据放入缓存中(放入的位置由地址确定)。然后返回地址。

组相联高速缓存

 刚才讨论的直接映射高速缓存可以看作是缓存中的一个特例,因为每组只有一行。这里介绍一下更普遍的缓存结构:组相连高速缓存。

其实就是每一组有多行。如下图是E =2 的缓存

同样的,当要从缓存中取地址为A的数据时,

1)先确定地址A所在的组,如下图所示

2)确定行

3)抽取字(偏移)

全联高速缓存

 全联高速缓存中的S =1 ,也就是说,全联高速缓存只有一个组。

全联高速缓存中对数据的操作和之前讨论过的两种情况大同小异,主要就是三部。这里就不说了。

小结

这篇博文先介绍了缓存内部的组织形式,并介绍了从缓存中读取数据的方式,主要包括1)组选择2)行匹配 3)字抽取

缓存可以用形如(S; E; B; m)的形式表述。其中S代表缓存中的组数,E为每组的行数,B为每个缓存块的大小。

更具E的不同可将缓存分类。

这篇文章主要介绍的是缓存的工作机制。在以后的文章中会介绍如何写出缓存友好的代码

全文完。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 对缓存的思考【续】——编写高速缓存友好代码

    开篇 上一篇博文对缓存的思考——提高命中率详细介绍了高速缓存的组织结构,并通过实例说详细明了cpu从高速缓存中取数据的过程,对于缓存的工作机制应该有了清晰的认识...

    猿人谷
  • cocos2d-x 学习笔录:将iOS项目编译成Andriod项目

    一、Android 环境搭建 1、安装Andriod-NDK(Native Development Kit)   新建一个文件夹(eg:NDK),解压Andro...

    猿人谷
  • cctype

    在头文件<ctype.h>中定义了一些测试字符的函数。在这些函数中,每个函数的参数都是整型int,而每个参数的值或者为EOF,或者为char类型的字符。<cty...

    猿人谷
  • 对缓存的思考【续】——编写高速缓存友好代码

    开篇 上一篇博文对缓存的思考——提高命中率详细介绍了高速缓存的组织结构,并通过实例说详细明了cpu从高速缓存中取数据的过程,对于缓存的工作机制应该有了清晰的认识...

    猿人谷
  • Mybatis—一级缓存–二级缓存——缓存穿透,缓存击穿,缓存雪崩

    缓存(也成为cache)的作用是为了减去数据库的压力,提高数据库的性能,缓存实现的原理是从数据库中查询处理的对象再使用完后不要销毁,而是储存在内存(缓存)中,当...

    Java架构师必看
  • 微服务架构中缓存模式

    在微服务世界中,每个人都使用缓存,缓存无处不在。缓存可以提高性能,减少后端负载,或者减少down机时间。有许多方法可以配置系统中的缓存,缓冲应该被放在系统的哪个...

    程序你好
  • 大型分布式系统中的缓存架构

    CDN(Content Delivery Network 内容分发网络)的基本原理是广泛采用各种缓存服务器,将这些缓存服务器分布到用户访问相对集中的地区或网络中...

    搜云库技术团队
  • HTTP(二) 缓存

    重用已获取的资源能够有效的提升网站与应用的性能。Web 缓存能够减少延迟与网络阻塞,进而减少显示某个资源所用的时间。借助 HTTP 缓存,Web 站点...

    用户2202688
  • 缓存穿透、缓存击穿和缓存雪崩实践

    我们使用缓存的主要目是提升查询速度和保护数据库等稀缺资源不被占满。而缓存最常见的问题是缓存穿透、击穿和雪崩,在高并发下这三种情况都会有大量请求落到数据库,导致数...

    哲洛不闹
  • 微服务前端数据加载的最佳实践

    目前在不少团队里已经逐步实践落地了微服务架构,比如前端圈很流行的 BFF(Backend For Frontend)其实就是微服务架构的一种变种,即让前端团队维...

    lucifer210

扫码关注云+社区

领取腾讯云代金券