与cache相关的一些问题和思考

cache在性能优化里面占有很重要的地位，在性能优化的不同层次上，都会用到与cache相关的知识，下面是一些问题和思考。

1）很显然，cache的容量是有限的，所以就会有cache miss，cache miss一般有三种原因：

a: 当cache为空的时候，需要把内容调入cache。

b: 当超出cache容量的时候，需要淘汰一些旧的内容，腾出空间给新的内容。

c: cache conflict，在有冲突的时候，需要用旧的覆盖新的。

第一种情况对任何cache都是适用的；第二种情况，比如CPU的L2 cache，如果是全关联的cache，那么超出容量是，任何一个旧的都可能被踢出去；第三种情况一般是在N-way 关联的时候，映射到相同cache line的内容之间有冲突。

一般来说CPU有如下的cache类型：

  L1 I-cache, L1 D-cache, TLB, L2 cache, L3 cache。L1 cache和TLB cache容量较小，可以做成全关联的，L2, L3 cache一般是N-way关联的。cache在正常情况下，应该是可以提高性能的，但是在cache thrashing (pingpong)的时候，对性能却是有害的。在这种情况下，所有的访问都不能从cache里得到数据，而是需要到Main memory里去拿数据，所以编程的时候要比较cache thrashing。

2）如果避免cache thrashing，如何提高性能？

一般来说，跨边界的数据结构都是有害的。比如一个小于32 bytes的数据结构跨两个cache line，比如程序代码太大，正好在这个路径上，发生了cache conflict。一般来说L1 cache有64k，而L2 cache有1M或者更大。代码路径的长度不太可能有这么大的跨度。但是，最好是把相关的代码放在一起，最好减小代码的体积，最好把数据结构cache line对齐等等一下基本规则还是从一开始就遵守的好。

解决这个问题使用的技巧就是coloring。page coloring比较好理解，相同color的page会映射到相同的cache上去，所以在分配的时候，尽量比较给同一个process分配相同color的page。但是对于slab allocator的color就有点不太明白了。如果color的偏移是cache line大小还好理解，如果是其他的大小，感觉就没什么用。而且在slab allocator的论文里面提到memory channel，这个和cache没什么关系。memory channel是特定的物理地址在特定的内存片里面，如果是dual channel，最好数据地址能够分配到两个channel上，这样就可以并行读入，而不是顺序读入。这个是用来提高内存带宽的（当然可以可以说是避免冲突，因为如果是顺序访问，就说明两次读入是有冲突的）

3）L1 cache或者TLB里面，是虚地址，还是物理地址。这个和cache本身没有关系，这涉及到一个转换的问题。所以我认为在cache里面应该是物理地址，也就是说CPU在访问内存时，MMU是首先执行的，首先解决了TLB miss的问题，才能解决cache miss的问题，顺序不能乱。

The Elements of Cache Programming Style

http://en.wikipedia.org/wiki/Cpu_cache