1 存储技术
作为一名程序员，你必须了解存储器的层次结构，因为它对应用程序的性能有着巨大的影响。
- 如果你的数据是在cpu寄存器上，那么指令执行期间在0个周期就能访问到
- 如果是在高速缓存中，需要4-75个周期
- 如果在主存，需要上百个周期
- 如果是在磁盘，那么就需要大约几千万个周期，时间大概是毫秒级，比主存慢10万倍，比高速缓存慢100万倍
1.1 随机访问存储器
随机访问存储器(RAM)有两类：静态和动态。静态RAM(SRAM)比动态DRAM(DRAM)更快，但也更贵，因此SRAM一般集成在CPU上作为高速缓存，DRAM则作为主存。断电以后，DRAM和SRAM都会丢失它们的信息
访问主存：每次CPU和主存之间的数据传送都是通过一系列的步骤来完成，这些步骤称为总线事务。读事务从主存传输数据到CPU，写事务从CPU传送数据到主存。总线是一组并行的导线，能携带地址、数据和控制信号。 
1.2 磁盘
磁盘由盘片构成，每个盘片有两面或者称为表面，表面覆盖着磁性记录材料。盘片中央有一个可以旋转的主轴，它使得盘片以固定的旋转速率旋转，通常在5400-15000转没分钟。
下图展示了一个典型的磁盘表面结构。每个表面都是由一组称为磁道的同心圆组成的。每个磁道被划分为一组扇区。每个扇区包含相等数量的数据位，通常是512个字节。扇区之间由一些间隙分隔开，这些间隙不存储数据位，它们用来存储标识扇区的格式化位 
- 旋转磁盘：b图的整个装置被称为磁盘驱动器，也简称磁盘，为了与固态硬盘SSD区分，也叫旋转磁盘，SSD是没有移动结构的，也因为这种特性，SSD读取数据更快。
- 柱面：柱面是所有盘面上到主轴中心距离相等的磁道组合。
1.3 磁盘容量
一个磁盘可记录的最大位数就是它的最大容量，它由记录密度、磁道密度和面密度所决定。磁盘容量的计算公式如下：
\[ 磁盘容量=每个扇区字节数×每个磁道平均扇区数×每个面磁道数×每个磁盘表面数×磁盘数 \] 值得一提的是，我们在电脑或者手机中，会发现所显示的逻辑磁盘容量<实际容量，这是因为由两个原因：
- 一是厂商的磁盘容量计算不是按2进制的，即\(1GB=10^9字节\)，而不是\(1GB=2^{30}字节\)，明显\(2^{10}>10^3\)
- 二是在电脑或手机中不会把所有的磁盘都用上，它会保留一些柱面作为预留手段，当磁盘的一些存储区域出现损坏时，这些预留柱面能作为应对策略，将数据拷贝到这些预留柱面来使用 。这就是为什么逻辑容量要小于实际容量
1.4 磁盘操作* 磁盘用读/写头来读写存储在磁性表面的位，读写头的另一端连接到一个传动臂。
- 寻道：通过沿着半径轴前后移动这个传动臂，驱动可以将读写头定位在盘面的任何磁道上，
- 旋转：一旦读写头完成寻道定位在某个磁道上，驱动器就会等待期望的扇区的第一位旋转到读写头下，这样就能够读写数据
磁盘一扇区大小的块来读写数据，对扇区的访问时间由三个主要的部分：寻道时间、旋转时间和传送时间
- 寻道时间：位读取某个扇区的内容，传动臂首先将读写头定位到包含目标扇区的磁道上，移动传动臂所需要的时间称为寻道时间。其平均寻道时间是在
ms级，大概为3~ms，一次寻道的最大时间为20mss x旋转时间：一旦读写头定位到了期望的磁道，驱动器等待目标扇区的一个位旋转到读写头下。最大的旋转延迟数以
ms为单位，为\(1/RPM*1000ms\)，其中RPM是转速传送时间：当目标扇区的第一位位于读写头下时，驱动器就可以开始读写扇区内容，一个扇区的传送时间依赖与旋转速度和每条磁道的三区数目。
值得一提的是，磁盘操作中消耗时间的主要是寻道时间和旋转时间，传送时间所占的延迟是可忽略的的
1.5 固态硬盘
固态硬盘是一种基于闪存的存储技术，一个SSD封装由一个或多个闪存芯片和闪存翻译层组成，闪存芯片代替传统的旋转磁盘中的器械驱动器，而闪存翻译层是一个硬件设备，扮演与磁盘控制器相同的角色。将对逻辑块的请求翻译成对低层物理设备的访问。 
2 局部性* 一个编写良好的计算机程序常常具有良好的局部性，即他们更加倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用或的数据项本身，这种特性，常常称为局部性原理。局部性由两种不同的形式：时间局部性和空间局部性
- 时间局部性：被引用过一次的内存位置很有可能在不久的将来再次被多次引用。
- 空间局部性：一个内存被引用过了，那么极有可能在不久的将来会引用器附近的内存位置。
我们应该理解局部性原理，因为一般而言，一个良好局部性的程序比局部性差的程序运行得更快，这是由现代计算机系统得设计结构所决定得，在现代计算系统得各个层次之哦你给，都引入了局部性原理：
- 在硬件层，计算机设计者通过引入称为高速缓存存储器这样小而快得快速存储器来保存最近引用得指令和数据项，从而提高对主存得访问速度。
- 在操作系统中，系统使用主存作为虚拟地址空间，来存储最近被引用得数据项，来避免因从磁盘取数据过慢而导致CPU资源的浪费
- 类似的，操作吸引还用主存来缓存磁盘文件中最近被使用的磁盘块。
- 局部性原理在应用程序中也有应用，入
Web浏览器将最近引用的文档放在本地磁盘上，利用的就是时间局部性。
从上可以看出，局部性原理贯穿现代计算机系统的方方面面，因此设计局部性良好的程序是编程应该注意的事项。 
- 原则：
- 1.重复引用相同变量的程序有良好的局部性
- 对于具有步长位k的引用模式程序，步长越小，空间局部性越好。
- 对于取指令，循环有好的时间和空间局部性，循环越小，循环迭代次数越多，局部性越好。
3 存储器的层次结构
现代计算机系统都是使用了一种组织存储器系统的方法，称为存储器层次结构，从高层往低层走，存储设备变得更慢、更便宜和更大，在最高层，是少量的CPU寄存器，CPU可以在一个始终周期访问它们；接下啦是L1~L3的高速缓存。 
高速缓存cache是一个小而快速的存储设备，他作为存储在更大、也更慢的设备中的对象的缓冲区域。存储器层次结构的中心思想是，对于每个K，位于K层的更快更小的存储设备作为位于K+1层的更大更慢的存储设备的缓存。即层次结构的设计是为了每一层都缓存来自较低一层的数据对象 
数据总是以块大小为传送单元在第K层和第K+1层之间来回复制，这不过这个块大小在各层是不一样的，在L0和L1是一个字大小，在L1和L2是几十个字节。一般而言，层次结构中较低层的设备访问时间较长，因此为了补偿这些较长的访问时间，倾向于使用更大的块。
命中和未命中：说到缓存层次结构就必须提到缓存命中和未命中的情况。
- 缓存命中：当程序需要第
K+1层的某个数据对象d时，它首先会正在当前存储在k层之前的存储层次中查找d，如果d刚好缓存在K层中，那么就是我们所说的缓存命中。缓存命中读数据明显会快于缓存未命中时的情形。 - 缓存未命中：缓存未命中恰好是缓存命中相反的情况，这时就会去下层存储结构找到包含数据
d的数据块。并且会将数据缓存至K层，如果K层已满，可能会覆盖现存在K层中的数据块冷不命中：冷不命中是由于冷缓存所导致，这是因为计算机刚启动时，缓存肯定是空的，这时候在高层存储结构肯定是没有数据被命中。冷不命中是短暂事件，因为反复访问存储器器会使得缓存暖身，直至缓存占满。冷不命中也称为强制性不命中
冲突不命中：这时因为硬件缓存使用的是像哈希一样的缓存放置策略，就是第
k+1的某个块被限制在放置在第k层的一个小子集里（甚至是某一个块），比如某些缓存放置策略使用mod，即k+1的数据块i，必须放置在k层i mod len(k)上。这样可能导致k层的缓存并不是满，但是也没有位置存储数据d，导致冲突未命中，这样就会在k+1层查找数据d，找到后放置在k层并覆盖原缓存数据
缓存与局部性是浑然一体的，这时因为：
- 利用时间局部性原理：由于时间局部性，同一数据对象可能会被多次使用。一旦一个数据对象在第一次不命中是被复制到缓存中，我们期望后面对该目标有一系列的访问命中，因为缓存比低一层的存储设备更快，对后面的命中服务会比最开始的不命中快很多
- 利用空间局部性原理：块通常包含多个数据对象，。由于空间局部性，我们会期望后面对该块中其他对象的访问能够补偿不命中后复制该块的花费。
4.高速缓存存储器
高速缓存存储器因为可以缓存数据，那么这些数据是如何被寻址查找、替换的呢。在高速缓存存储器中存在四个参数：S标识有几组高速缓存存储器、E表示每组有多少行、B表示每行有\(2^B\)字节数据块组成、m位标记位,即使用\((S,E,B,m)\)： 
在寻址的过程中通过确定所在的组S、查看有效位是否有效和标记为是否对应，如果满足上面三个，那么就说明数据在这个缓存区域内，通过行偏移地址得到该数据块的指定数据，如下面所示： 
- 从上面的结构我们可以分析知道，造成冲突不命中的情况是源于每个缓存组只有一行,即
E=1，那么为了减小冲突不命中情况，可以增加行，此时称为组相联高速缓存
4.1 读写时情况
高速缓存出现不命中时，由不命中带来的开销是很大的，为了弥补这种开销，计算机设计者们充分利用空间局部性，以数据块的形式进行缓存。
同时在缓存未命中的清况下，高速缓存就必须从内存中取出包含这个数据的块，不过一旦高速缓存取出该块，该替换哪一行呢(直接映射高速缓存没有这种困扰，因为它就只有一行）。我们之前讲过不同的计算机使用不同的策略，有一些使用哈希所有它们的形式不尽相同。如果有一个空行可替换，那最好，但是如果没有空行，在组相联高速缓存中，替换哪一行是一个问题。
在计算机中，有使用最不常使用(LFU)和最近最少使用(LRU)
读：高速缓存的读非常简单，首先，在高速缓存查找所需数据，若命中，立即返回该数据给CPU；若未命中，从存储器层次结构的较低层中取出包含该数据的块，将这个块存储到某个高速缓存行中（可能会驱逐某一行），然后返回该数据给CPU.
- 写：写要复杂一些。
- 首先考虑写命中，加入我们写一个已经缓存的数据
W之后，它会怎么来保持数据的一致性呢。有两种方法：- 直写（write-through)：直接将数据
w写回紧接着缓存的低一层。这种方法简单，但是每次写都会引起总线流量 - 写回(write-back)：尽可能的推迟这种更新，只有当替换算法要驱逐这个更新过的块时，才将它写到紧接着的下一层。由于局部性，这种放松明显减少了总线流量，但是缺点是在缓存的硬件中要额外维护一个修改标志位，这样才能识别是否被修改过。
- 直写（write-through)：直接将数据
- 写不命中时，也有两种情况：
- 写分配（write-allocate)：加载相应低一层的数据块到高速缓存中，然后更新这个高速缓存块。利用空间局部性来弥补未命中情况
- 写不分配(not write-allocate)：避开高速缓存，直接把这个字写到低一层中，
- 首先考虑写命中，加入我们写一个已经缓存的数据
4.2 高速缓存参数的性能影响
- 未命中率：在一个程序执行或程序的一部分执行期间，内存引入不命中的比率
不命中数量/引用数量 - 命中率：
1-未命中率 - 命中时间：从高速缓存传送一个字节到CPU的时间，包括组选择、行确认和字选择的时间。L1只需几个时钟周期
- 未命中时间：由于不命中需要额外的时间。L1不命中需要从L2得到服务的惩罚，通常为数十个周期；L2不命中从L3得到服务的惩罚，50个周期；从主存得到服务的惩罚，200个周期。
高速缓存大小、块大小和相联度的影响：
- 高速缓存的大小：较大的高速缓存能够提升命中率，然后却会增加命中时间，这时因为缓存越多，要组、行和字偏移就越复杂，那么寻址中的组选择、行确认和字选择的时间越多。
- 块大小：大的数据块充分利用空间局部性，帮助提高命中率；但是，由于给定的高速缓存大小，块越大说明行越少，会损害时间局部性。同样较大的块也会对未命中惩罚造成负面影响，因为块越大，传送的时间就越多，
- 相联度：
E较高可以降低高速缓存的冲突不命中情况；但较高的相联度，造价昂贵，也增加了命中时间。
4.3 高速缓存友好的代码特点
让最常见的情况运行得快。程序通常把大部分时间都花在少量的核心函数上，而这些函数通常把大部分时间都花在了少量的循环上。所以要把注意力集中在核心函数的循环上，而忽略其他部分。
在每个循环内部使缓存不命中数量最小。在其他条件，例如加载和存储的总次数相同的情况下，不命中率低的程序运行得更快。
注意：编译器将局部变量存储到寄存器中，因此循环内对局部变量的引用不需要任何加载或存储指令。
高速缓存对程序性能的影响
通过重新排列循环以提高空间局部性：降低高速缓冲的不命中率。例子（求两个矩阵的乘积）
使用分块来提高时间局部性。
