C3 - Cachline详解
开头
我们都知道CacheLine（简称CL）在CPU内部起到缓存的作用，多核CPU还有缓存行一致性协议来协同各个核心的CL数据，达到同步与高效共享数据的作用（参考）。在详细讨论CL的内部结构的时候我们需要明白两件事情，或者说任何缓存系统都有的本质特点：
1、缓存 = DATA(key) → DATA(value)；任何缓存体系中都有数据(DATA)，这个DATA包含两个维度的信息key与value。key来自于DATA，而value通常就是DATA本身；缓存系统就是提供通过key快速找到value的机制；
2、如果说CL缓存的数据是DATA，它就包含两个维度的信息，DATA的虚拟内存地址，value就是虚拟地址对应的数据啦。所以，对于SMP的CPU来说，同一个虚拟地址在不同的Core上，只要虚拟地址一样，CL的value就一样，但他们不是同一个CL，可以说是不同的副本吧。
CL的架构
CL怎么实现的呢？
CL的结构
CL很简单，跟很多计算机中的结构一样，CL可以分为：
头 + 体两个部分。头包含标识，而体包含数据。其中标识就是key，有效位就是指示这个CL是否被占用的标志。
存取机制
CL怎么存取呢？其实原理跟Hashtable非常相似：
- 设计一个通过虚拟内存地址得到
key的映射； - 按照
key存储数据到CL中。
设计的关键在如何解决冲突
因为，内存要比CPU缓存空间大不少，内存往往动不动就是几个G，十几个G甚至几十个G；而CPU缓存只有从几十KB到几MB不等，少4、5个数量级，所以根据鸽巢原理，肯定有严重的冲突发生=>多个虚拟地址共享同一个CL位子。
怎么解决冲突？没有巧的，hashtable怎么解决，CL就怎么解决。
-
hashtable的办法有：
1、开链法——同一个key，不同的value串起来，形成链表存放；
2、开放地址法——根据key第一次找到位子，如果已经占用，就隔壁位子，隔壁再占用就隔壁的隔壁；以此类推，总能找到。 -
这两种算法对应两种不同的CL的组织结构：
1、开链法——组相联
2、开放地址法——全相联
全相联与组相联优缺点分析
全相联高速缓存
- 优点：可以充分的使用有限的缓存空间，也就是说在空间没有用完的情况下，总是可以找到空闲的CL位子的。
- 缺点:查询效率比较低，因为查找
key对应的CL，最坏的情况下需要遍历整个缓存空间。
全相联高速缓存
但是，存在就是合理的。对于L1缓存，使用全相联就很合适：
- L1本身就很小，只有32KB大小，遍历起来速度很快；
- 因为很小所以利用率要比较高，才划算。
组相联高速缓存
对于空间比较大的L2与L3选择开链法的组相联就比较合适了。但是构造方法跟hashtable还是有些许不同之处：
1、开链的个数，也就是冲突集合大小，是固定的。通常是4个，8个，16个。也就是，同一个key最多容纳4个，8个或者16个不同的value，再来，对不住，就要淘汰了。有个专门的词——路来表示这个冗余量。通常看到的L2是8路组相联高速缓存，就说明L2是组相联结构，每个key对应8个冗余的CL位子。
2、没有了。
优点：适用比较大的存储空间，速度也很快。
缺点：路数有限，不能利用所有的缓存空间。比如，如果持续要缓存冲突的内存数据，只能在固定的冲突集合中存储，所以当冲突集合满了以后，就要淘汰集合中的热数据，造成不命中的风险，即便缓存空间还有很多空闲的位子也无法使用。这就要求我们在选取索引上下功夫来降低这种情况的发生。
优化之路
来看个例子：
组相联-1
根据著名的局部性原理，我们可以知道冷热数据的规律：
- 刚刚访问完的数据，相邻的数据可能马上被访问；如循环遍历数组元素，这个数组中相邻的数据也都是热数据；
- 刚刚访问完的代码，还可能继续访问；如for循环等。
所以，如图所示，如果用虚拟地址的开头部分做分组索引显然不合适，空间局部性不满足。
组相联-2
稍微变一下索引的取值就可以提高命中率，四两拨千斤。
应用场景
除开L1 - L3的高速缓存是CL来构造的，MMU的TLB也是CL方式来构造的。我在这里有详细的画图解释MMU的运行原理，一图胜千言。
CL伪共享
最后提一下著名的伪共享问题。为什么要提伪共享，我是想阐明工程设计中的一个普遍规律——有好必有坏。不知道你发现过一个规律没有——当你用缓存解决了一个问题，那么缓存本身就会成为一个问题。所以，还是那句老话说的好做工程就是在做权衡。当我们用局部性原理提高了CPU运行效率的问题后，我们也要想想它的弊端在什么地方，无疑“伪共享”就是！当我们用64Byte的粒度来缓存数据的时候，提升程序的局部性时，在某些情况下——例如多线程访问，就会带来CL bouncing——就是把冷热数据放在同一个CL中带来的性能问题。
伪共享
当常量数据与变量数据放在一起，被加载到同一个CL，不同的core中，那么常量就会因为变量的不断更新而受到牵连，不断CL失效，从而被击穿到内存——形成伪共享。
解决方案也很直接——空间换时间——用空座位把“好学生”与“坏学生”隔开就行了。
缓存行padding
