forked from GHScan/TechNotes
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path10.html
5 lines (4 loc) · 26.1 KB
/
10.html
1
2
3
4
5
<head>
<meta http-equiv=Content-Type content="text/html; charset=utf-8">
</head>
<div>■ 11. 程序员修炼之道：21. 按合约设计<br> ■ 与计算机系统打交道难，与人打交道更难。确保坦率的最佳方案之一就是合约。合约规定双方的权利与责任以及违约的后果。可以采用同样的概念进行软件模块的交互<br> ■ DBC（Design By Contract）:(1)precondition, 为了调用例程，必须为真的条件，即需求；如果不为真，不应该被调用（2）postcondition，例程承诺会完成的事情（3）class invariant，类承诺从使用者的角度来看，该条件总为真。例程内部，class invariant不一定保持，但退出例程是一定为真。<br> ■ 相比“羞涩”的代码（总是在例程内部校验输入），DBC的代码是“懒惰”的：只在precondition为真的时候才被调用，因此不必校验输入；而postcondition限制了输出的内容<br> ■ 断言不能完全实现DBC，比如断言不能沿继承链传递<br> ■ 在内建DBC的语言中，precondition和postcondition由runtime来检测，或者由编译器自动输出代码完成，这样DBC能完全发挥。而一些主流语言，可能通过调试器（比如C++的Nana）或者预处理器（比如Java的iContract）来完成约束校验。<br> ■ 因为precondtion一定是在进入例程前完成的，因此，等价于在调用点内联校验代码<br> ■ loop invariant：循环不变量<br> ■ semantic invariant：语意不变量。比如强异常保证；比如主键不能重复<br> ■ 动态合约和代理：...<br>■ 11. 程序员修炼之道：22. 死程序不说谎<br> ■ Crash early。出现问题时，让你的程序崩溃可能是最佳的选择。当然，很多时候你不能简单的退出，比如，可能需要释放资源、写日志、清理事务<br> ■ 原则：当你的代码发现某项不可能发生的事情已经发生，你的 程序不再有活力，从此，它所做的任何事情都会变得可疑，要尽快终止它。<br> ■ 死程序带来的危害通常比有疾患的程序小得多<br>■ 11. 程序员修炼之道：23. 断言式编程<br> ■ If it can't happen, use assertions to ensure that it won't<br> ■ 断言条件不应该有副作用，因为它可能会在发布版中被移除<br> ■ 小而简单的程序，可以总是使用release断言；正式的程序，需要区分逻辑错误和运行时异常（比如非法输入），前者用release断言，后者使用异常并进行错误处理；只在性能hotspot点考虑将release断言替换为debug断言<br>■ 13. 程序员修炼之道：24. 何时使用异常<br> ■ 不赞成“一个例程应该有且只有一个return语句”<br> ■ “如果移走异常相关代码，程序能否执行正常逻辑？”如果答案是否，则可能异常被使用在了非异常的情况中<br> ■ 是否应该引发异常，取决于实际情况：如果文件应该在那里，但没有在，则应该抛出异常；如果你不知道文件是否在那里，则返回错误或其他更合适<br> ■ Use exceptions for exceptional problems<br> ■ 异常是nonlocal jump，近似于级联的goto（cascading jump）。goto已经不被推荐，更何况级联，所以异常不应该被用于正常逻辑<br>■ 14. 程序员修炼之道：25. 怎样配平资源<br> ■ 资源包括：内存、事务、线程、文件、定时器——所有数量有限的东西！！<br> ■ 分配-》使用-》释放<br> ■ 嵌套的分配：（1）分配的次序应该和释放相反（2）有多个资源时，总是以固定的顺序分配<br> ■ 当无法配平资源时，确定清晰的ownership，父层对子层负责<br> ■ 检查资源配平：比如，在服务器主循环等待下个请求的地方，检测内存占用没有增长<br> ■ C++释放资源后将指针清空，这样，非法使用会内存访问错误；Java等语言将引用清空，才能释放ownership，资源等待被回收<br>■ 14. CSAPP：第6章：存储器层次结构<br> ■ 寄存器（L0）作为cache的缓冲区，cache作为主存的缓冲区，主存作为磁盘的缓冲区，磁盘作为网络文件系统的缓冲区<br> ■ 利用locality，memory hierarchy可以得到这样一个效果：一个大的存储器池，其成本与容量与最底层设备相当，而性能却接近最顶部的存储设备<br> ■ 具有良好locality的程序，倾向于访问相同的数据集合（temporal locality），或是访问邻近的数据集合（spatial locality），最终是倾向于更多的访问memory hierarchy较高层次中的数据项<br>■ 15. 程序员修炼之道：第5章：弯曲，或者折断<br> ■ 为了赶上近乎疯狂的变化步伐，我们必须尽一切努力编写尽可能宽松、灵活的代码，否则，我们的代码将很快过时、过于脆弱或者难于修理，从而在向未来的疯狂突进中掉队<br>■ 15. 程序员修炼之道：26. 解耦与德墨忒尔法则<br> ■ “羞涩”的代码有两种：不向别人暴露自己；不与太多人打交道<br> ■ 间谍、反政府人员、革命者或类似组织，会组成小组，cell。cell内人们都认识，而cell间不认识，所以麻醉药也无法使一个cell透露其他cell成员的名字。这也是适用于编码的好原则<br> ■ 使耦合减少到最小：假设你在改建房子，典型的是找一位总承包人，他负责和其他子承包人打交道安排工作，他会搞定那些令你头疼的事情。（即门面模式，facade pattern）<br> ■ 对象间横贯的关系可能会带来依赖关系的组合爆炸：如果n个对象全部需要了解彼此，那个修改一个对象会导致其他n-1个对象也需要改动<br> ■ Minimize coupling between modules<br> ■ 与具有较小响应集（response set，类的各个方法直接调用的函数。这里的类叫calling class，调用类）的类相比，具有较大响应集的类更容易出错<br> ■ 函数的德墨忒尔法则：某个对象的方法只能调用以下几类方法：（1）该对象的方法（2）参数对象的方法（3）方法体内创建的新对象的方法（4）该对象持有的组件对象的方法。总结：只调用ownership属于自己的对象的方法 <br> ■ 德墨忒尔法则缩小了calling class的response set的规模，按此原则设计的类往往错误也更少。缺陷是所需的facade pattern可能引入额外的时间、空间开销<br> ■ 随着系统的增大，另外一种相互依赖会变得越来越重要：物理设计问题。包括组成系统的文件、目录和库之间的关系，他们可能带来天文数字计的构建周期、单元测试复杂度。详见Large-scale C++ software design<br>■ 16. 程序员修炼之道：27. 元程序设计<br> ■ 细节会弄乱我们整洁的代码，特别是如果他们经常因为商业逻辑、法律或者管理者的个人口味而变化时；每次改动都可能引入bug或破坏系统<br> ■ 我们让代码变得高度可配置和“软和”，才容易适应变化<br> ■ 屏幕颜色、提示文本、算法、数据库产品、中间件技术和用户界面风格之类的选择，应该作为配置选项，而不是通过集成和工程（engineering）实现<br> ■ configure, don't integrate<br> ■ 元数据（metadata）是关于数据的数据，如数据库的schema或数据字典或者应用的配置选项。你可以像操纵任何数据一样操纵元数据<br> ■ 元数据在典型情况下是运行时而不是编译时使用，比如，web浏览器的偏好设置、windows系统的ini文件和注册表、unix的rc文件、java的property文件<br> ■ 元数据可以用来驱动应用：为一般情况编写程序，把具体情况放到编译的代码库之外。好处：（1）迫使你解耦（2）迫使你推迟细节处理（3）无需重新编译，就可以定制系统（4）可以用更接近问题域的DSL（5）可以用相同的应用引擎配合不同的元数据实现不同的项目<br> ■ 除了用配置选项（metadata）来选择数据库引擎和界面风格，还可以用来应用商业规则、企业政策<br> ■ put abstractions in code, details in metadata<br> ■ 协作式配置：让应用自身适应其环境。如操作系统适应不同的硬件，你的软件适应不同的操作系统、库和不同版本的存档<br>■ 17. CSAPP：第6章第1.1节：储存技术-RAM<br> ■ 随机访问存储器（RAM）分为SRAM和DRAM,SRAM更快但更小更贵，常用作cache，而DRAM常用作主存和图形适配器的帧缓冲<br> ■ SRAM是双稳态（bistable）的，每个存储位需要6个晶体管。双稳态之外的其他状态，都是亚稳态(metastable)，都不稳定，一旦电子噪音等干扰消除后，电路会恢复稳定。只要有电，SRAM会永远保持其值<br> ■ DRAM每个位需要1个晶体管和1个电容，可以被制造得非常密集，一旦电容的电压被扰乱过后，就永远不会恢复，而它的存储单元大概会在10~100毫秒间由于外部因素失去电荷，这远低于CPU频率，因此存储器系统可以周期性的读值并写回，这是动态刷新。<br> ■ DRAM被设计为二维阵列，因此可以通过行列地址来寻址。可以使用更多的管脚，一次传送行列地址来寻址，也可以以更高的频率先后传送行列地址来寻址，后者分别叫RAS（raw access strobe，行访问选通脉冲）和CAS。<br> ■ 将相同的地址，分别传送到不同的存储器模块（memory module）中，模块并联后分别提供一个字中的不同字节。多个这样的芯片共同组成存储器，物理地址的高位用于片选<br> ■ DRAM和SRAM断电后丢失信息，是易失的（volatile），而ROM是非易失的（nonvolatile memory）。PROM（programable ROM），可编程一次，通过熔断熔丝来写位。EPROM（erasable PROM），可擦写可编程ROM，通过紫外线照进石英窗口来清除位，重编程次数可达1000次。EEPROM(electrically EPROM)，电子可擦除PROM，可达10^5次。flash memory基于EEPROM。SSD也是一种flash。<br> ■ ROM中的程序被称为firmware(固件)，计算机通电后会首先读取它。一些固件提供了基本IO函数，如BIOS。图形卡和磁盘驱动器也依赖固件翻译来自CPU的IO请求。<br> ■ 处理器和主存及IO设备间用于传输数据的共享电路成为bus（总线）。从CPU发起的一次主存读写或者IO请求并完成称为一次bus transaction。数据总线和地址总线可以共享一组电路也可以分开。<br> ■ CPU通过总线接口与其他设备连接。在CPU、主存和IO设备间可能会有IO bridge，IO桥又分为北桥和南桥，北桥连接CPU、主存和显卡，通信率高，速度快，南桥连接其他IO设备。CPU和IO bridge之间的bus称为系统总线（system bus），主存和IO桥之间的总线称为存储总线（memory bus），最后IO设备IO桥之间的总线称为IO总线。<br>■ 17. CSAPP：第6章第1.2节：存储技术-磁盘存储<br> ■ 从磁盘读取信息，比DRAM慢了10万倍，比SRAM慢了100万倍<br> ■ 磁盘构成：disk（磁盘）->platter（盘片）->surface（表面）->track（磁道）->sector（扇区）->bytes。扇区之间有gap（间隙），是格式化后用来标识扇区的空白位。等半径的磁道集合是cylinder（柱面）<br> ■ 磁盘容量跟面密度有关。面密度（areal density）=磁道密度（track density）x记录密度（record density）。最初每个磁道有固定的扇区，直到后来，外层磁道扇区间的间隙不可接受的大，于是有了多区记录（multiple zone recording）的概念，每个zone是一组磁道的集合，每个磁道的扇区数等于最内层磁道的扇区数<br> ■ 磁盘通过转动传动臂（actuator arm）来定位磁道，然后等待目标扇区转动到读写头（read/write head）下面，最后读取整个扇区。<br> ■ 一次磁盘访问时间分为：seek time（寻道时间）+rotational latency（旋转时间）+transfer time（传送时间）。三个时间的具体值取决于转臂和目标扇区的位置差。前两者绝对值较大，而传送时间较小，因此，磁盘适合连续读取至少一个扇区大小的数据，而不适合随机读写。<br> ■ 格式化操作时，磁盘控制器（firmware）将所有的扇区编号，从0~N-1，叫做逻辑编号，去掉坏道和备用扇区，之后，当CPU发起读写第i个扇区的请求时，控制器将i转化为（表面号，磁道号，扇区号）的三元组，然后控制转臂和io头完成读写。<br> ■ io bus比system bus和memory bus慢，连接了各种io设备，包括图形适配器、磁盘控制器、usb（universal serial bus）控制器。其中usb用于连接键盘、鼠标、相机、打印机、cd-rom、调制解调器等慢速io设备<br> ■ CPU使用存储器映射io（memory-mapped io）来向IO设备发起命令。地址空间中有一块地址被保留用作与io设备进行通信，每个这样的地址（char*）被称为一个io端口（io port），某个设备接入时，它与一个或多个io port相关联。<br> ■ DMA（direct memory access）是由io设备的控制器（一个由micro CPU执行的firmware）执行的内存和io设备间的数据传输<br> ■ 一个读磁盘的例子：（1）CPU往IO port写入命令字，告知磁盘控制器要执行读操作，以及其他参数，比如，是否完成后中断CPU（2）写入第2个命令字，告知要读取的扇区逻辑编号（3）写入第3个命令字，告知接受数据的主存物理地址（4）线程挂起，CPU调度到其他任务（5）磁盘控制器执行DMA过程，进行读写和发起总线事务（6）IO完毕，通过管脚向CPU发起中断信号，CPU被调度到一个系统中断函数，函数内部记录下事件完成，最后返回中断点<br>■ 17. CSAPP：第6章第1.3节：存储技术-存储技术趋势<br> ■ 历史趋势：增加密度比减少时延更容易；memory hierarchy上层的设备和下层设备速度差距进一步扩大，故开始出现L3<br>■ 17. CSAPP：第6章第2节：局部性<br> ■ 一个编写良好的计算机程序倾向于展示出良好的局部性（locality），这个倾向，被成为局部性原理（principle of locality），是一个持久的概念，对硬件和软件系统的设计有着极大影响<br> ■ 时间局部性（temporal localtiy）：被引用过一次的位置可能会在不久的将来被多次引用<br> ■ 空间局部性（spatial localtiy）：如果一个位置被引用，那么不远的将来可能引用一个附近的位置<br> ■ 将数组a的所有元素累加到变量sum中，这里的sum具有时间局部性，而a具有空间局部性，故局部性很好。如果累加二维数组，内层循环是遍历第2维，则空间局部性好，如果遍历第1维，则空间局部性差（stride太大，可能会造成capacity miss甚至conflict miss）。<br> ■ 指令执行的局部性：顺序执行，空间局部性好，if/switch太多（forward jmp），空间局部性差；for循环（往往是backward jmp），时间局部性好<br> ■ 量化评价一个程序局部性的简单原则：（1）重复引用同一个变量具有良好的时间局部性（2）stride-k reference pattern，步长越小，空间局部性好（3）对取指令来说，循环有好的空间、时间局部性，循环体越小、循环次数越多，局部性越好<br>■ 17. CSAPP：第6章第3节：存储器层次结构<br> ■ 总结前文：（1）不同存储设备访问时延差距很大，更快的设备成本高，而且小；CPU与主存的速度差距进一步拉大（2）好的程序倾向于体现出良好的局部性<br> ■ 考虑以上两点，提出存储器组织方法，即memory hierarchy：register file->L1 cache(SRAM)->L2 cache(SRAM)->L3 cache(SRAM)->main memroy (DRAM)->disk->distributed file system<br> ■ cache的概念：memory hierarchy中，每一层都是下一层的缓存；任意第k和k+1层之间，有一个传输单元（transfer unit），越靠下的层间TU越大（为弥补访问时延更大的问题）；k和k+1层被划分为TU的集合，而k层集合是k+1层的子集。根据访问情况，会发生cache hit和cache miss<br> ■ cache miss后，会加载一个块覆盖现有块，这个过程叫replacinng，选择牺牲块的策略有随机或LRU，策略不同开销不同。<br> ■ 一个算法所访问的内存块集合被叫做working set，当算法刚开始时，working set没有被加载进cache，这样的cache叫相对于这组working set的cold cache，然后随着算法的执行，会发生一系列的cold miss，进而cache被warmed up为warm cache。如果working set大于某级cache，那么在这级cache上可能反复发生capacity miss。一个算法的内存引用模式，可能还会造成某级cache上反复发生conflict cache。<br> ■ 现代memory hierarchy的（cache类型，TU大小，管理者）：（CPU寄存器，字长，编译器）->（TLB，地址翻译单元，硬件MMU）->（L1/L2/L3，cache line size，硬件）->（虚拟存储器，page size，MMU和OS）->（web view，web page，浏览器）<br>■ 18. 程序员修炼之道：28. 时间耦合<br> ■ 时间耦合（temporal coupling）<br> ■ Analyze workflow to improve concurrency<br> ■ Design using services<br> ■ Always design for concurrency. 到部署的时候才选择单机或单机-服务器或n层<br>■ 20. CSAPP：第6章第4节：高速缓存存储器<br> ■ L2/L3可以连接到存储器总线，或者连接到独立的cache bus<br> ■ cache由一个cache set数组构成，每个set上有E个cache line，每个cache line由cache block（这个才是通常术语中的cache line，大小是cache line size）、tag bit（用于行匹配，由cache idx和associative idx构成）、valid bit、dirty bit构成<br> ■ 一个物理地址，相对于某层cache来说，从高位到低位依次是：cache index、associative index、set index、block offset<br> ■ 对于set index，放在物理地址的低位而不是高位，可以让连续地址均匀的分布在不同的set中，从而spatial locality的内存访问能够获得更高的并行性<br> ■ cache确定一个地址请求是否命中时：（1）以set index来索引set数组，组选择，set selection（这一步可以并行）（2）以tag bit和valid标识来选择行，line match（3）根据cache line offset来进行字提取，word pickup。如果cache miss，则向下层cache请求，此时CPU被stalling，加载数据后将其缓存到本层cache<br> ■ 如果相关度(associativity)为1，即是direct-mapped cache；大于1，即是E-way set associative cache；等于C/B（即只有一个set），即是full associative cache<br> ■ 发生cache miss并加载cache line后，如果没有空行，需要选择一个line来替换，采用随机策略需要较复杂的硬件，适合放在较低的cache层次（因为那里miss penalty很大），而LFU、LRU等策略相对开销稍小<br> ■ 全相联cache因为没有并行性（特指ILP），只适合做较小的cache，如TLB以full associative cache来实现用于缓存页表项<br> ■ 写cache：（1）当cache hit时，可以write-through和write-back，前者是修改cache的时候同时更新主存，后者是只更新cache并打上dirty标记，发生cache miss被replacing的时候才写回主存。write-back需要的硬件更复杂，但bus transaction次数少，bus占用率低，因此更适合用在底层cache（2）当cache miss时，可以write-allocate，先加载cache line再按（1）处理；也可以直接更新主存<br> ■ 由于硬件电路性能提高，几乎可以假设所有的cache层次上都采用write-back和write-allocate策略，尤其是低层cache，比较典型的是虚拟存储器系统（用主存作为磁盘的cache）<br> ■ 至少从Pentium 3开始，intel的CPU就已经是：L1有独立的i-cache和d-cache，而L2是一个unified cache<br> ■ 高速缓存的性能指标：（1）miss rate（2）hit rate（3）hit time（3）miss penalty<br> ■ cache设计中的trade-off：（1）cache size越大，hit rate越大，但hit time也越大（大cache成本高速度慢）（2）block size（cache line size）越大，hit rate越大，但hit time也越大（block transfer time变大）（3）相关度越大，conflict miss的影响越小（miss penaty），hit time更大（replacing机制复杂，set selection慢）、cache line更冗余（tag bit）<br> ■ （4）越下层cache的miss penalty大，因此更可能是write-back而不是write-through，因为bus transaction少<br>■ 20. CSAPP：第6章第5节：编写高速缓存友好的代码<br> ■ 确保代码是cache friendly的方法：（1）让最常见的情况运行的最快。程序大部分的时间都花在少量的核心函数上，进一步时间都在循环上。因此焦点应该在核心函数的循环上（2）让每个循环的cache miss次数最少<br> ■ 具体结论：（1）对局部变量的反复引用是好的，因为编译器会尽量将它们缓存在register file中，temporal locality（2）stride-1 referrence pattern是好的，因为各级cache都将数据组成连续的，spatial locality<br>■ 20. CSAPP：第6章第6节：高速缓存对程序性能的影响<br> ■ 一个程序从存储系统中读取数据的速度被称为读吞吐量（read throughput），也叫读带宽（read bandwidth），典型的单位是MB/s<br> ■ 对一个数组访问程序进行benchmark，可以得到一个memory mountain，array size为x轴，stride为z轴，bandwidth为y轴，则：（1）size越大，bandwidth越小，在size分别为L1/L2/L3的时候有明显的分界（2）stride在cache line size以内，相对平稳，超过line size，bandwidth一路降低<br> ■ cache friendly的程序应该尽量跑在memory mountain的山巅，好的temporal locality和spatial localtiy等价于小的size和stride<br> ■ 改写算法以得到更好的局部性：（1）通过改写循环变量的层次，可能得到更好的空间局部性，如，矩阵乘法能够写成纯粹的stride-1访存（2）可以通过blocking的方法，将算法拆成小的块运算，最后再组合，从而只使用有限的cache，得到好的时间局部性<br> ■ 对于麦克风、照相机、网络连接等数据连续的流媒体，由于它们有好的空间局部性，所以可以采取prefetch等手段尽量让数据提前被cache到缓存中。但不佳的prefetch也有干扰DMA等降低系统性能的风险<br>■ 20. CSAPP：第6章第7节：在程序中利用局部性<br> ■ 推荐：（1）焦点放在内部循环上（2）通过存储顺序来访问数据，使空间局部性最大（3）一旦读取一个对象，就尽量反复访问，使时间局部性最大（4）miss rate是一个性能因素，但memory access数也有很大影响，需要折中<br>■ 23. 程序员修炼之道：29. 它只是视图<br> ■ subscriber、publisher：observer pattern<br> ■ mvc：一个m可以有多个v；一个v也可以为多个m服务；c适配m和v<br> ■ 模型（model）：表示目标对象的抽象数据模型，对view和controller都一无所知<br> ■ 视图（view）：解释模型的方式（数据的展示、解释方式）。订阅model的变化和controller的事件<br> ■ 控制器（controller）：担任模型和视图中间的中介者、适配器，向双方发布事件和提供数据<br></div>