APP下载

何为程式的区域性性原理

消息来源:baojiabao.com 作者: 发布时间:2024-05-03

报价宝综合消息何为程式的区域性性原理

一个编写良好的计算机程式常常具有很好的区域性性(locality)。

区域性性是程式倾向于引用邻近于最近引用过的资料项A的资料项B,或者最近引用过的资料项A。这种倾向性称为区域性性原理(principle of locality)。良好的区域性性对硬件和软件系统的设计和效能都有着极大的影响。

区域性性通常有两种形式:

时间区域性性(temporal locality):在一个具有良好时间区域性性的程式中,被引用过一次的内存位置很可能在不远的将来再被多次引用。空间区域性性(spatial locality)在一个具有良好空间区域性性的程式中,如果一个内存位置被引用了一次,那么程式很可能在不远的将来引用附近的一个内存位置。程序员应该理解区域性性原理,一般而言,有良好区域性性的程式比区域性性差的程式执行得更快。

现代计算机系统的各个层次,从硬件到操作系统,再到应用程序,它们的设计都利用了局部性。

在硬件层,区域性性原理允许计算机设计者通过引入小而快速的快取内存储存器来储存最近被引用的指令和资料项,从而提高对主存的访问速度。在操作系统级,区域性性原理允许系统使用主存作为虚拟地址空间最近被引用块的快取内存。类似的,操作系统用主存来快取磁盘档案系统中最近被使用的磁盘块。在应用程序的设计中,区域性性原理也扮演者重要角色。如Web浏览器将最近被引用的文件放在本地磁盘上,利用的就是时间区域性性。大容量的Web服务器将最近被请求的文件放在前端磁盘快取内存中,这些快取能满足对这些文件的请求,而不需要服务器的干预。下面以一个例子说明对程式资料引用的区域性性。下图是一个实现对向量所有元素求和的函式。

在这个例子中,变数sum在每次循环迭代中被引用一次,因此对sum来说有好的时间区域性性。因为sum是标量,所以对sum来说没有空间区域性性。

另外,对于向量v来说,它的元素是按照它们储存在内存中的顺序(假设从地址0开始)一个接一个被顺序读取的。因此对于变数v来说有很好的空间区域性性,但时间区域性性很差,因为每个元素只被访问一次。

在这个函式的循环体中,变数要么有很好的时间区域性性,要么有很好的空间区域性性,因此说这个函式有良好的区域性性。

下面是一个二维阵列的求和函式,双重巢状循环按照行优先的顺序读取阵列中的元素,而C阵列在内存中是按照行顺序来存放的,因此具有良好的空间区域性性。

若交换i和j的循环,即按照列顺序来扫描阵列,则空间区域性性变差。

相关阅读

基于快取的储存器层次结构

基于闪存的储存技术:固态硬盘

磁盘的构造、容量和扇区访问操作

随机访问储存器:静态RAM和动态RAM

深入理解C语言的指标

学习笔记:深入了解计算机系统

2020-01-13 03:50:00

相关文章