前面主要讲了cpu层面的寻址, 接下来, 讲下cache是如何工作的.当然,我们依旧化简成单核的场景的来简单介绍下cache的工作原理.

• cache的最小管理单元
  cache的最小单元是cacheline,一般是32或者64个字节,在x86上,是64个字节;在arm上,是32个字节
  也就是说,你更新8个字节,其实会更新他所在的完整的64个字节进cacheline, 而不是只有那个8个字节更新了

• cache的层次结构
  cache会分为多层,离cpu最近的叫做L1,然后是L2, L3(一般只有3层,所以L3也叫做LLC)
  L1容量最小,访问速度最快,离cpu最近
  LLC容量最大.访问速度最慢,离cpu最远
  L2介于两者之间

• cache的写入方式
  这里用一个例子来做cpu写cache的对比: 我们通过redis做数据库的缓存

  • write-through(x86的cpu几乎不存在这个情况了; arm, mips表示不清楚)
    写cache的行为, 等待写完下一层存储再返回
    更新完redis的数据, 还要等待db的数据更新完, 再返回
  • write-back
    更新完redis的数据, 立即返回, 后台同步redis的数据到db
  • write-combining
    缓存一批需要更新的数据(对于x86来说是4个cacheline), 然后统一通过更新cache(可以是write-back,也可以是write-through)
    积攒一批数据,统一提交给redis, 相当于batch写

• cache和地址的关系
  cache_set_index = hash(addr)

  • cache set
    在现代cpu实现中,一般来说,为了防止cache太容易被覆盖, 会把cacheline分成N组, 每组由M个cacheline组成
    首先, cpu通过hash算出cache_set_index, 然后, 比较这个cache_set里面的每个cacheline是否和地址匹配
  • N-way
    所谓的N-way就是指上文的cache_set里面的cacheline数目

• prefetch

  • hareware prefetch
    cpu检测到连续的虚拟内存访问的时候, cpu会提前把接下来的虚拟内存地址中的数据,加载到cache中来
  • software prefetch
  • 通过prefetch指令, 通知cpu记载目标虚拟内存地址的数据
  • 通过普通的内存读写指令, 提前访问需要访问目标虚拟内存地址, 让cpu提前加载数据到内存中, 后续的访问, 就可以避免cache miss

• LLC(last level cache)的特殊作用
  某些外设, 比如显卡,网卡, 他们的数据,可以直接通过pcie总线写到llc中, 避免从内存中读取.
  如果说一段地址是交给外设作为io地址使用的,那么, cpu是无法从cache中访问对应内存地址中的数据的, 因为DMA的情况下,外设可以不通过cpu修改制定的内存.
  这个时候,cpu去读取最新的数据,就不得不直接访问内存,这将花费大量的时间.

• cache的延迟
  内存 > LLC > L2 > L1 > 寄存器, 点我查看访问延迟

然后,我们简单看下啥情况下会导致cache miss, 同样,我们分成下面几个简单的场景来看

• read dcache miss

  看下面一段代码

这是一个很典型的案例, 先说结论: 场景1会比场景2快.
因为数组元素只有4个字节,一个cacheline有64个字节,所以当我们访问a[n][0] -> a[n][15]的时候,其实都是读同一个cacheline的内容
换句话说,不考虑任何预取的场景下, 场景1的情况下16次读才有一次cache miss,场景2的情况下,只要n的大小大于16, 那么, 几乎每次读都是cache miss

• icache miss
  branch instruction
  条件跳转, call指令这些会导致指令执行出现大的内存地址跨度的时候, 可能就会导致, cache不在icache中

• write dcache miss
  这里我们主要关注下write-back, write-through, write-combining 性能的区别
  write-through对于write而言,其实cache是没有意义的,他保证的是数据的一致性,只对read场景有意义
  write-back对于write而言,只要还有空闲的cache(和下层存储状态一致)立即返回,所以cache miss的成本比较低
  write-combining本质是提供了一个额外的写缓冲区, 可以一次提交多份数据, 在吞吐量大的情况下, 可以提高性能

最后,我们看下如何避免cache miss

• 延迟初始化, 在c++和java中, 有一条规则叫做,对象真的要用的时候再去new
  数据在需要使用的时候, 再去初始化.
  因为数据的初始化需要写cache, 写cache也就意味着, 如果这部分数据原本不在cache中,那么需要占用cache(抢占其他内存对象的cache), 但是这个对象在不立即用的情况下, 等于降低了cache的有效使用率

• 数据的局部性
  因为cacheline的大小是64个字节, 外加连续的内存访问硬件会做prefetch,因此尽可能采用连续的数据存储

• array, array, array
  参考上述理由, 数组是最好的数据结构,如果可能,尽可能选择数组

• 其他cache-oblivious数据结构
  不展开, 有兴趣大家可以看看

• 恰当的prefetch
  对于指针的访问, 比如list的遍历, 程序确定需要访问后续的内存, 可以考虑使用prefetch, 但是prefetch不是立即生效的, 所以, 一定要严格测试对比, 确定有性能提升

老问题,继续引出几个问题

• 多核情况下, cache的工作方式有啥不同
• 多核情况下, 又有啥需要额外的注意cache访问方式
• 前面一直提的流水线又是个什么玩意