精华内容
下载资源
问答
  • 局部性原理的应用
    千次阅读
    2019-12-02 11:38:14

    01、前言

    作为有追求的程序员,我们日常在写代码的时候往往都会运用很多奇技淫巧,不单单是为了炫耀我们的技术,更是为了追求更高的效率。了解局部性原理,可以有效的帮助我们理解和写出更好的代码,对于局部性原理可能有的小伙伴知道,有的小伙伴不知道,知道的小伙伴就当做复习知识点,不知道的小伙伴也没关系,接着往下看就知道了。

    02、什么是局部性原理

    说到局部性原理,那我们首先要知道什么是局部性原理,局部性原理分为两部分:

    • 时间局部性:指的是在程序运行过程中最近被引用到的存储器位置在程序执行后期还会被多次引用到的可能性很大。
    • 空间局部性:指的是程序运行过程中如果一个存储器的位置被引用,那么在程序执行后期该存储器附近的位置被引用的可能性很大。

    简单来说就是一个变量在程序运行过程中,如果被引用过一次,那后续很有可能会再被引用到;一个变量被访问到过后,这个变量所在的位置附近的位置很有可能在程序后续运行中被访问到。

    03、示例

    上面是通过理论来说明的,下面我们通过一段代码来看看局部性y原理

    public int sum(int[] array) {
            int sum = 0;
            for (int i = 0; i < array.length; i++) {
                sum = sum + array[i];
            }
            return sum;
    }
    

    从上面的这段代码来看,就是一个很简单的数组元素求和,这里我们主要看 sum 和 array 两个变量,我们可以看到 sum 在每次循环中都会用到,另外它只是一个简单变量,所以我们可以看到,sum 是符合我们上面提到的时间局部性,再访问一次后还会被继续访问到,但是它不存在我们所说的空间局部性了。

    相反的,array 数组中的每个元素只访问一次,另外数组底层的存储是连续的,所以 array 变量符合我们上面提到的空间局部性,但是不符合时间局部性。

    这只是局部性原理的简单示例,对于局部性原理还有很多地方会用到,我们如果能熟练的掌握和使用,对我们的帮助会很大的。

    04、相关应用

    4.1、CPU 缓存

    上面的示例其实很简单,相信大家都能理解,另外局部性原理其实在我们日常使用的软件中随处可见,并且在操作系统中也少不了。我们知道 CPU 的速度是非常快的,而且 CPU 与内存之间有多级缓存,如下图(图片来源于网络)

    image-20191129115010857.png

    为了充分的利用 CPU,操作系统会利用局部性原理,将高频的数据从内存中加载的缓存中,从而加快 CPU 的处理速度。

    4.2、广义局部性

    其实我们的局部性原理不单单是上面提到的狭义性的局部性,还可以是广义的局部性。我们系统里面的热点数据,CDN 数据,微博的热点流量等等这些都利用了局部性原理。只是我们可能没有意识到而已,实际上已经在使用了。我们会通过 Redis 缓存热点数据,会通过 CDN 提前加载图片或者视频资源,等等,都是因为这些数据本身就符合局部性原理,合理的利用局部性可以得到了能效、成本上的提升。

    4.3、利弊结合

    任何事情都是多面性的,局部性原理虽然我们使用起来很不错,可以提高系统性能,但是在有些场景下,我们是需要避免局部性原理的出现的。或者说出现了这种情况,我们需要人工处理。我们可以试想一下,如果在我们的一个大数据处理平台上,由于局部性原理的存在,导致我们部分节点数据庞大运算吃力,部分节点数据量小十分空闲,这种情况自然是不合理,我们就需要把数据按照业务场景进行重新分配,以达到整个集群的最大利用。

    05、总结

    今天给大家介绍了一下局部性原理,我们提到了时间局部性和空间局部性,通过一个代码示例和几个业务场景给大家简单介绍了局部性的使用。最后也提到局部性原理有利也有弊,我们需要根据业务场景和需求合理话的使用。

    更多相关内容
  • 计算机体系结构资源
  • 这是一份计算机体系结构课堂展示的ppt,有关于缓存cache以及多种优化的核心思想:局部性原理,制作精美 内容详实覆盖面广,有需要的同学可以下载一下~
  • 局部性原理

    千次阅读 2018-11-07 21:26:30
    二、局部性原理应用 (1)缓存结构 (2)循环的局部性原理 案例A:数组循环长数据引用的局部性 案例B:排序对数组遍历的影响 参考资料 一、什么是局部性原理 一个编写良好的计算机程序常常具有良好的局部性...

    目录

    一、什么是局部性原理

    二、局部性原理的应用

    (1)缓存结构

    (2)循环的局部性原理

    案例A:数组循环长数据引用的局部性

    案例B:排序对数组遍历的影响

    参考资料


    一、什么是局部性原理

    一个编写良好的计算机程序常常具有良好的局部性。也就是说。它们倾向于引用临近于其他最近引用过的数据项的数据项,或者最近引用过的数据项本身。这汇总倾向性,就被称为局部性原理,这是一个持久的概念,对硬件和软件系统的设计和性能都有着极大的影响。

    之所以有这个规律,很多人认为原因是:程序的指令大部分时间是顺序执行的,而且程序的集合,如数组等各种数据结构是连续存放的。

    局部性原理讲的是:在一段时间内,整个程序的执行仅限于程序的某一部分,相应地,程序访问的存储空间也局限于某个内存区域。主要分为两类:

    1. 时间局部性:如果程序中的某条指令一旦执行,则不久之后该指令可能再次被执行;如果某数据被访问,则不久之后该数据可能再次被访问。
    2. 空间局部性:是指一旦程序访问了某个存储单元,则不久之后,其附近的存储单元也将被访问。

    二、局部性原理的应用

    (1)缓存结构

    CPU内部的ALU(运算器)进行信息的处理,寄存器进行信息的存储,总线连接各器件,进行数据的传送。

    CPU内部组成及工作原理

     

    存储器层次结构

    将计算机分为数个层次:

    • 寄存器 64位

    • 一级缓存L1 4×64KB

    • 二级缓存L2 4×256KB

    • 三级缓存L3 8MB

    • 内存 4GB

    • 磁盘 1TB

    寄存器是CPU的工作台,CPU在工作时,先从一级缓存里面找,找不到就从二级缓存里面找,依次类推。假如CPU到磁盘才有,那么这个数据就会存入内存,再存入三级缓存、二级缓存、一级缓存,最后存入寄存器,然后进行计算。所以说,可以这么看, L1是寄存器的缓存,L2是L1的缓存,依次这样下去,下面一层是上面一层的缓存。

    由于各层存储之间的速度差异,CPU要高速工作,我们希望CPU需要的数据更多的就在L1里面,能够告诉获取到,不希望更多的跑到下面内存乃至磁盘里面去找,这样会花更多的时间。所以当CPU用了一个数据,计算机会遇见性的存入其他等会儿CPU可能会用到的数据到L123内存,用到的可能性越大,就能存到越接近寄存器的层次。这也才是缓存的真正意义。那么,计算机怎样才能判断一个数据接下来可能被用到?

    时间局部性:如果一个信息项正在被访问,那么在近期它很可能还会被再次访问。所以数据在寄存器被计算完成后,将会放入告诉缓存中。

    空间局部性:在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的。而且基于指令顺序执行的特性,大部分的数据存储被认为是连续的。所以程序在装载入内存时,不是整体装入,而是分块(页框)装入的。

    (2)循环的局部性原理

    对于诸如For循环,其在执行时也遵循一定的局部性原理,我们以案例来进行讲解。

    案例A:数组循环长数据引用的局部性

    private static void loopArray() {
    	int[][] arrayC = new int[10000][10000];
    
    	long startA = System.currentTimeMillis();
    	int sum1 = 0;
    	for (int i = 0; i < 10000; i++) {
    		for (int j = 0; j < 10000; j++) {
    			sum1 += arrayC[i][j];
    		}
    	}
    	long endA = System.currentTimeMillis();
    	System.out.println("  Array行遍历结果:" + sum1 + ", 耗时:" + (endA - startA)
    			+ "ms");
    
    	long startB = System.currentTimeMillis();
    	int sum2 = 0;
    	for (int i = 0; i < 10000; i++) {
    		for (int j = 0; j < 10000; j++) {
    			sum2 += arrayC[j][i];
    		}
    	}
    	long endB = System.currentTimeMillis();
    	System.out.println("  Array列遍历结果:" + sum2 + ", 耗时:" + (endB - startB)
    			+ "ms");
    }

    执行结果:

      Array行遍历结果:0, 耗时:79ms
      Array列遍历结果:0, 耗时:1420ms

    上述代码中,通过对一个10000 * 10000的二维数组进行遍历,分别从行、列两个主序维度,可以看出行遍历是列遍历效率的10倍以上。因为数组在内存中大多是顺序存放的,而多维数组主要是以行为主序进行存放,如下图所示。

    preview

    对于行维度(即相当于一维数组)来说,在空间上具有良好的空间局部性原理,即a[i]总是a[i-1]后一个位置存放。

    但是对于列维度来说(以列序为主序遍历),意味着每访问一个元素,就要跳过N个元素才能访问下一个,这种情况下没有良好的空间局部性。所以在遍历时出现了明显的性能差异。

     

    案例B:排序对数组遍历的影响

    本案例主要涉及局部性原理和分支预测理论,故放在性能优化相关文章中,请参照:

    性能优化之分支预测


    参考资料

    https://www.zhihu.com/question/25142664/answer/60733489

    《码农翻身》——刘欣

    展开全文
  • 局部性原理——各类优化的基石

    千次阅读 多人点赞 2019-07-28 16:38:21
    学过计算机底层原理、了解过很多架构设计或者是做过优化的同学,应该很熟悉局部性原理。即便是非计算机行业的人,在做各种调优、提效时也不得不考虑到局部性,只不过他们不常用局部性一词。如果抽象程度再高一些,...

    学过计算机底层原理、了解过很多架构设计或者是做过优化的同学,应该很熟悉局部性原理。即便是非计算机行业的人,在做各种调优、提效时也不得不考虑到局部性,只不过他们不常用局部性一词。如果抽象程度再高一些,甚至可以说地球、生命、万事万物都是局部性的产物,因为这些都是宇宙中熵分布布局、局部的熵低导致的,如果宇宙中处处熵一致,有的只有一篇混沌。

    所以什么是 局部性 ?这是一个常用的计算机术语,是指处理器在访问某些数据时短时间内存在重复访问,某些数据或者位置访问的概率极大,大多数时间只访问_局部_的数据。基于局部性原理,计算机处理器在设计时做了各种优化,比如现代CPU的多级Cache、分支预测…… 有良好局部性的程序比局部性差的程序运行得更快。虽然局部性一词源于计算机设计,但在当今分布式系统、互联网技术里也不乏局部性,比如像用redis这种memcache来减轻后端的压力,CDN做素材分发减少带宽占用率……

    局部性的本质是什么?其实就是概率的不均等,这个宇宙中,很多东西都不是平均分布的,平均分布是概率论中几何分布的一种特殊形式,非常简单,但世界就是没这么简单。我们更长听到的发布叫做高斯发布,同时也被称为正态分布,因为它就是正常状态下的概率发布,起概率图如下,但这个也不是今天要说的。
    在这里插入图片描述
    其实有很多情况,很多事物有很强的头部集中现象,可以用概率论中的泊松分布来刻画,这就是局部性在概率学中的刻画形式。
    在这里插入图片描述
    在这里插入图片描述
    上面分别是泊松分布的示意图和概率计算公式, λ \lambda λ 表示单位时间(或单位面积)内随机事件的平均发生次数, e e e表示自然常数2.71828…,k表示事件发生的次数。要注意在刻画局部性时 λ \lambda λ表示不命中高频数据的频度, λ \lambda λ越小,头部集中现象越明显。

    局部性分类

    局部性有两种基本的分类, 时间局部性空间局部性 ,按Wikipedia的资料,可以分为以下五类,其实有些就是时间局部性和空间局部性的特殊情况。

    时间局部性(Temporal locality):

    如果某个信息这次被访问,那它有可能在不久的未来被多次访问。时间局部性是空间局部性访问地址一样时的一种特殊情况。这种情况下,可以把常用的数据加cache来优化访存。

    空间局部性(Spatial locality):

    如果某个位置的信息被访问,那和它相邻的信息也很有可能被访问到。 这个也很好理解,我们大部分情况下代码都是顺序执行,数据也是顺序访问的。

    内存局部性(Memory locality):

    访问内存时,大概率会访问连续的块,而不是单一的内存地址,其实就是空间局部性在内存上的体现。目前计算机设计中,都是以块/页为单位管理调度存储,其实就是在利用空间局部性来优化性能。

    分支局部性(Branch locality)

    这个又被称为顺序局部性,计算机中大部分指令是顺序执行,顺序执行和非顺序执行的比例大致是5:1,即便有if这种选择分支,其实大多数情况下某个分支都是被大概率选中的,于是就有了CPU的分支预测优化。

    等距局部性(Equidistant locality)

    等距局部性是指如果某个位置被访问,那和它相邻等距离的连续地址极有可能会被访问到,它位于空间局部性和分支局部性之间。 举个例子,比如多个相同格式的数据数组,你只取其中每个数据的一部分字段,那么他们可能在内存中地址距离是等距的,这个可以通过简单的线性预测就预测是未来访问的位置。

    实际应用

    计算机领域关于局部性非常多的利用,有很多你每天都会用到,但可能并没有察觉,另外一些可能离你会稍微远一些,接下来我们举几个例子来深入了解下局部性的应用。

    计算机存储层级结构

    极客时间
    上图来自极客时间徐文浩的《深入浅出计算机组成原理》,我们以目前常见的普通家用电脑为例 ,分别说下上图各级存储的大小和访问速度,数据来源于https://people.eecs.berkeley.edu/~rcs/research/interactive_latency.html
    在这里插入图片描述
    从最快的L1 Cache到最慢的HDD,其两者的访存时间差距达到了6个数量级,即便是和内存比较,也有几百倍的差距。举个例子,如果CPU在运算是直接从内存中读取指令和数据,执行一条指令0.3ns,然后从内存读下一条指令,等120ns,这样CPU 99%计算时间都会被浪费掉。但就是因为有局部性的存在,每一层都只有少部分数据会被频繁访问,我们可以把这部分数据从底层存储挪到高层存储,可以降低大部分的数据读取时间。
      
    可能有些人好奇,为什么不把L1 缓存做的大点,像内存那么大,直接替代掉内存,不是性能更好吗?虽然是这样,但是L1 Cache单位价格要比内存单位的价格贵好多(大概差200倍),有兴趣可以了解下DRAM和SRAM。

    我们可以通过编写高速缓存友好的代码逻辑来提升我们的代码性能,有两个基本方法 。

    1. 让最常见的情况运行的快,程序大部分的运行实际都花在少了核心函数上,而这些函数把大部分时间都花在少量循环上,把注意力放在这些代码上。
    2. 让每个循环内缓存不命中率最小。比如尽量不要列遍历二维数组。

    MemCache

    在这里插入图片描述
    MemCache在大型网站架构中经常看到。DB一般公司都会用mysql,即便是做了分库分表,数据数据库单机的压力还是非常大的,这时候因为局部性的存在,可能很多数据会被频繁访问,这些数据就可以被cache到像redis这种memcache中,当redis查不到数据,再去查db,并写入redis。
      
    因为redis的水平扩展能力和简单查询能力要比mysql强多了,查起来也快。所以这种架构设计有几个好处:

    1. 加快了数据查询的平均速度。
    2. 大幅度减少DB的压力。

    CDN

    CDN的全称是Content Delivery Network,即内容分发网络(图片来自百度百科) 。CDN常用于大的素材下发,比如图片和视频,你在淘宝上打开一个图片,这个图片其实会就近从CDN机房拉去数据,而不是到阿里的机房拉数据,可以减少阿里机房的出口带宽占用,也可以减少用户加载素材的等待时间。
    在这里插入图片描述
    CDN在互联网中被大规模使用,像视频、直播网站,电商网站,甚至是12306都在使用,这种设计对公司可以节省带宽成本,对用户可以减少素材加载时间,提升用户体验。看到这,有没有发现,CDN的逻辑和Memcache的使用很类似,你可以直接当他是一个互联网版的cache优化。

    Java JIT

    JIT全称是Just-in-time Compiler,中文名为即时编译器,是一种Java运行时的优化。Java的运行方式和C++不太一样,因为为了实现write once, run anywhere的跨平台需求,Java实现了一套字节码机制,所有的平台都可以执行同样的字节码,执行时有该平台的JVM将字节码实时翻译成该平台的机器码再执行。问题在于字节码每次执行都要翻译一次,会很耗时。
      在这里插入图片描述
    图片来自郑雨迪Introduction to Graal ,Java 7引入了tiered compilation的概念,综合了C1的高启动性能及C2的高峰值性能。这两个JIT compiler以及interpreter将HotSpot的执行方式划分为五个级别:

    • level 0:interpreter解释执行
    • level 1:C1编译,无profiling
    • level 2:C1编译,仅方法及循环back-edge执行次数的profiling
    • level 3:C1编译,除level 2中的profiling外还包括branch(针对分支跳转字节码)及receiver type(针对成员方法调用或类检测,如checkcast,instnaceof,aastore字节码)的profiling
    • level 4:C2编译

    通常情况下,一个方法先被解释执行(level 0),然后被C1编译(level 3),再然后被得到profile数据的C2编译(level 4)。如果编译对象非常简单,虚拟机认为通过C1编译或通过C2编译并无区别,便会直接由C1编译且不插入profiling代码(level 1)。在C1忙碌的情况下,interpreter会触发profiling,而后方法会直接被C2编译;在C2忙碌的情况下,方法则会先由C1编译并保持较少的profiling(level 2),以获取较高的执行效率(与3级相比高30%)。

    这里将少部分字节码实时编译成机器码的方式,可以提升java的运行效率。可能有人会问,为什么不预先将所有的字节码编译成机器码,执行的时候不是更快更省事吗?首先机器码是和平台强相关的,linux和unix就可能有很大的不同,何况是windows,预编译会让java失去夸平台这种优势。 其次,即时编译可以让jvm拿到更多的运行时数据,根据这些数据可以对字节码做更深层次的优化,这些是C++这种预编译语言做不到的,所以有时候你写出的java代码执行效率会比C++的高。

    CopyOnWrite

    CopyOnWrite写时复制,最早应该是源自linux系统,linux中在调用fork() 生成子进程时,子进程应该拥有和父进程一样的指令和数据,可能子进程会修改一些数据,为了避免污染父进程的数据,所以要给子进程单独拷贝一份。出于效率考虑,fork时并不会直接复制,而是等到子进程的各段数据需要写入才会复制一份给子进程,故此得名 写时复制
      
    在计算机的世界里,读写的分布也是有很大的局部性的,大多数情况下读远大于写, 写时复制 的方式,可以减少大量不必要的复制,提升性能。 另外这种方式也不仅仅是用在linux内核中,java的concurrent包中也提供了CopyOnWriteArrayList CopyOnWriteArraySet。像Spark中的RDD也是用CopyOnWrite来减少不必要的RDD生成。

    处理

    上面列举了那么多局部性的应用,其实还有很多很多,我只是列举出了几个我所熟知的应用,虽然上面这些例子,我们都利用局部性得到了能效、成本上的提升。但有些时候它也会给我们带来一些不好的体验,更多的时候它其实就是一把双刃剑,我们如何识别局部性,利用它好的一面,避免它坏的一面?

    识别

    文章开头也说过,局部性其实就是一种概率的不均等性,所以只要概率不均等就一定存在局部性,因为很多时候这种概率不均太明显了,非常好识别出来,然后我们对大头做相应的优化就行了。但可能有些时候这种概率不均需要做很详细的计算才能发现,最后还得核对成本才能考虑是否值得去做,这种需要具体问题具体分析了。

    如何识别局部性,很简单,看概率分布曲线,只要不是一条水平的直线,就一定存在局部性。

    利用

    发现局部性之后对我们而言是如何利用好这些局部性,用得好提升性能、节约资源,用不好局部性就会变成阻碍。而且不光是在计算机领域,局部性在非计算机领域也可以利用。

    性能优化

    上面列举到的很多应用其实就是通过局部性做一些优化,虽然这些都是别人已经做好的,但是我们也可以参考其设计思路。

    恰巧最近我也在做我们一个java服务的性能优化,利用jstack、jmap这些java自带的分析工具,找出其中最吃cpu的线程,找出最占内存的对象。我发现有个redis数据查询有问题,因为每次需要将一个大字符串解析很多个键值对,中间会产生上千个临时字符串,还需要将字符串parse成long和double。redis数据太多,不可能完全放的内存里,但是这里的key有明显的局部性,大量的查询只会集中在头部的一些key上,我用一个LRU Cache缓存头部数据的解析结果,就可以减少大量的查redis+解析字符串的过程了。

    另外也发现有个代码逻辑,每次请求会被重复执行几千次,耗费大量cpu,这种热点代码,简单几行改动减少了不必要的调用,最终减少了近50%的CPU使用。

    非计算机领域

    《高能人士的七个习惯》里提到了一种工作方式,将任务划分为重要紧急、不重要但紧急、重要但不紧急、不重要不紧急四种,这种划分方式其实就是按单位时间的重要度排序的,按单位时间的重要度越高收益越大。《The Effective Engineer》里直接用leverage(杠杆率)来衡量每个任务的重要性。这两种方法差不多是类似的,都是优先做高收益率的事情,可以明显提升你的工作效率。

    这就是工作中收益率的局部性导致的,只要少数事情有比较大的收益,才值得去做。还有一个很著名的法则__82法则__,在很多行业、很多领域都可以套用,80%的xxx来源于20%的xxx ,80%的工作收益来源于20%的工作任务,局部性给我们的启示“永远关注最重要的20%” 。

    避免

    上面我们一直在讲如何通过局部性来提升性能,但有时候我们需要避免局部性的产生。 比如在大数据运算时,时常会遇到数据倾斜、数据热点的问题,这就是数据分布的局部性导致的,数据倾斜往往会导致我们的数据计算任务耗时非常长,数据热点会导致某些单节点成为整个集群的性能瓶颈,但大部分节点却很闲,这些都是我们需要极力避免的。

    一般我们解决热点和数据切斜的方式都是提供过重新hash打乱整个数据让数据达到均匀分布,当然有些业务逻辑可能不会让你随意打乱数据,这时候就得具体问题具体分析了。感觉在大数据领域,局部性极力避免,当然如果没法避免你就得通过其他方式来解决了,比如HDFS中小文件单节点读的热点,可以通过减少加副本缓解。其本质上没有避免局部性,只增加资源缓解热点了,据说微博为应对明星出轨Redis集群也是采取这种加资源的方式。

    参考资料

    1. 维基百科局部性原理
    2. 《计算机组成与设计》 David A.Patterson / John L.Hennessy
    3. 《深入浅出计算机组成原理》 极客时间 徐文浩
    4. 《深入理解计算机系统》 Randal E.Bryant / David O’Hallaron 龚奕利 / 雷迎春(译)
    5. interactive latencies
    6. Introduction to Graal 郑雨迪
    展开全文
  • 局部性原理的理解

    千次阅读 2021-03-08 23:07:54
    本文首先介绍了局部性原理的定义,然后列举了一些局部性原理应用,接着具体讨论了局部性原理在page coloring中的应用,最后分析了局部性原理的本质。 什么是局部性原理 在计算机学科的概念中,局部性原理是一个...

    局部性原理的理解

    17300240036 杜逸闲

    本文首先介绍了局部性原理的定义,然后列举了一些局部性原理的应用,接着具体讨论了局部性原理在page coloring中的应用,最后分析了局部性原理的本质。

    什么是局部性原理

    在计算机学科的概念中,局部性原理是一个常用的术语,指处理器在访问某些数据时短时间内存在重复访问,某些数据或者位置访问的概率极大,大多数时间只访问局部的数据。主要可以分为时间局部性和空间局部性两种。

    时间局部性

    如果一个数据正在被访问,那么在近期它很可能还会被再次访问。任何编写过程序的人都知道,这个原理是正确的。我们在编写程序时,总是在一段时间内(比如一个循环或者一个函数内)对相同的地址进行反复的操作。

    但为什么人们在编写程序的时候不会先计算出一个数据,将其存放在某个地方,然后在很长一段时间内都不使用呢?Locality Principle 一文提到这是因为人类解决问题的思维方式是分治(divide and conquer),将大事化小,小事化了。一个很庞大的问题会被分解成若干个子问题,在各自的模块分别解决,而某一个子问题涉及到的数据会在存放后不久被读取。

    空间局部性

    在不久的将来将用到的数据很可能与现在正在使用的数据在空间地址上是临近的。
    这条原理的原因也同样是因为分治的思想。当一个模块正在解决一个子问题时,他会申请使用很多局部变量,这些变量在空间上连续,同时在逻辑上也有关联。因此正在使用的这个数据地址旁边的数据,当然也是很可能被用到的。

    局部性原理的应用

    局部性原理最先在操作系统领域被发现且应用,但慢慢延申至计算机科学的其他领域。最主要的应用就是在各种缓存的replacement algorithm中。下面列举一些其应用的例子:

    1. 操作系统中,在将虚拟内存转换到物理内存的过程中,我们需要用到TLB。在交换页至硬盘时,内存可以看作是硬盘的一种缓存。在缓存的replacement algorithm中我们会应用到局部性原理。
    2. CPU的多级缓存技术。
    3. 数据库中的memcache。当使用关系型数据库(如mysql时),即使我们分库分表储存,高峰期单机的查询压力还是很大。由于查询的项同样有局部性,此时可以使用如redis一类的kv数据库做memchache。
    4. 计算机网路中的CDN。由于同一个用户,甚至同一个地区的用户,在访问的数据上都存在局部性。大型的网站都引入了CDN来帮助分散主机的压力。CDN可以看作是服务器的一个cache。
    5. CopyOnWrite. 在Linux的fork中,子进程应该拥有独立的地址空间,父进程拥有的数据也应该复制一份。但由于局部性原理的存在,只有一小部分的数据是会被修改的,而大部分数据是只需要读的,有的数据甚至不会被使用。因此只有当子进程写数据时,这块数据才会被真正的复制。

    page coloring与局部性原理

    缓存的架构

    我们知道,在CPU的cache中会缓存一些内存,其中缓存的组织方式分别有三种,VIVT、VIPT和PIPT,见下图:在这里插入图片描述
    而在实际使用中,因为VIPT的效率比较高,我们会使用VIPT架构。VIPT架构使用虚拟地址做索引,物理地址做Tag。在利用虚拟地址索引cache同时,同时会利用TLB将虚拟地址转换为物理地址。然后将转换后的物理地址,与虚拟地址索引到的cache line中的Tag作比较,如果匹配则命中。

    但这种方式由于仍然拿虚拟地址做索引,仍然会出现cache alias问题。

    cache alias

    cashe alias是指,当两个不同的虚拟地址都映射至同一个物理地址时,他们在cache中可能不存在于同一个cache line中。那么当其中一个地址中储存的值被修改时,另一个cache line就会有失效的问题,要解决这个问题会严重影响效率,因此应当避免cache alias出现。

    下面我们将举例说明在VIPT架构下什么时候会出现cache alias。

    假设页大小为4KB。对于不同的两个VA和他们映射的同一个PA,他们的offset即最低的12位bit[0…11]一定是相同的。在使用虚拟地址查找cache line的组时,若能保证用于索引的虚拟地址的位数在bit[0…11]中,就能确保两个虚拟地址查找到同一个cache line组内。而由于我们并行地在TLB中查询到了PA,并用这个PA作为tag在这个cache line组内查找,这两个VA最终会查找到同一个cache line内,不会出现cache alias.

    假设cache大小为16KB,4路组相联,cache line大小为32(5个bit)。此时我们需要虚拟地址的7个bit作为索引,而由于cache line大小为32,占据了bit[0…4],为了对齐我们只能用bit[5…11]作为索引。而由于两个VA的bit[0…11]都是相同的,他们都会被映射到同一个cache line组内,不会出现cache alias.

    但假设现在cache大小为32KB,其余条件不变。此时我们就需要虚拟地址的7个bit作为索引,同理为了对其我们需要用bit[5…12]作为索引,而两个VA的bit[12]可能并不一样,这就导致他们被索引到不同的组内,占用了两个不同的cache line,导致了cache alias.

    如何解决cache alias

    其实方法的原理很简单。只要保证这两个VA用作映射的bit都是一样的,就可以保证他们映射到同一个组内。那么我们只要在建立VA到PA的映射时,强制让VA和PA的一定数量的低位保持一致即可。

    如上一节的第一个例子,操作系统不需要做任何工作,VA和PA的最低12位必定一样,因此在mapping时不需要额外操作。

    而第二个例子中,我们便需要保证VA和PA的bit[12]是一致的。比如VA的bit[12]是1,我们就只会将其分配到bit[12]为1的PA上,而不将其分配到bit[12]为0的PA上。用一种比喻的手法来说,PA和VA都拥有了0和1两种颜色,只有颜色一样的page才有可能建立虚拟地址到物理地址的映射。

    这就是所谓的page coloring.

    与局部性原理的关系

    page coloring可能会导致一个问题。那就是内存和缓存的利用率可能下降。假设我们的page拥有四种颜色。此时cache line组实际上会被分成四种颜色。考虑下面一种情况,所有的VA的颜色均为0. 在这种情况下,分配的所有PA的颜色也为0. 这会导致更多的物理内存分配失败,需要更多的交换,从而带来更多的缺页,严重影响了效率。同时,由于只有颜色为0的cache line组被使用,缓存命中率会降低,效率又会大打折扣。

    实际上,由于空间局部性原理,一段程序在一定时间内总是会使用相邻的一段内存,也就是说,VA和PA的颜色应该是在四种颜色中均匀分布的。上述问题在实际中并不会存在,或不会造成什么可观的影响。

    局部性原理的本质

    从物理的视角看,局部性原理的本质是熵的不均匀。不同事物的熵有高有低,熵低的事物组织性更强,这一组事物中的联系更紧密。而局部性原理认为在时间上或者空间上距离近的事物他们的联系更强,因此熵更低,暗示我们将他组织在一起。

    从数学的角度上考虑,局部性原理的本质,就是一部分事情发生的概率与另一些事情发生的概率不相等。比如空间局部性指的是,与当前正在使用的内存在空间中相邻的部分,接下来被使用的概率比离得远得更大。
    在自然界中,不存在完美的平均分布。实际上自然界中大量事物发生的概率都遵循泊松分布。局部性原理其实就是对泊松分布的一个应用。
    在这里插入图片描述
    如果定义x=k为距离当前被访问资源距离为k的资源被访问。那么当k越小时,p(x=k)越大,我们就应该将距离尽可能近的资源提前加载。

    认识局部性原理的本质的意义在于什么呢?如果意识到狭义上的局部性原理只是泊松分布的一个应用,那么当一些事情发生的概率并不符合泊松分布时,狭义上的局部性原理就需要修改。或者我们需要对其中的k做出一些变换,使得其服从泊松分布。具体到实际应用中,我们不能奉狭义上的局部性原理为真理,而在这个优化方向上蒙蔽了双眼,错过了可优化的空间。

    展开全文
  • 局部性原理 局部性原理不仅适用于程序结构,也适用于数据结构 正是由于局部性原理的存在,才可以实现只装入部分程序到内存就开始运行 局部性原理的表现: 时间局部性:如果程序中的某条指令一旦执行,不久之后该...
  • 程序设计原则——局部性原理

    千次阅读 2018-07-23 09:52:25
    局部性:一般较好的程序都有较好的局部性,也就是说,它们倾向于引用的数据项邻近于其他最近引用过的数据项,或者邻近于最近自我引用过的数据项。对应的就是空间局部性和时间局部性。   局部性小结: 1、...
  • 说到局部性原理,那我们首先要知道什么是局部性原理局部性原理分为两部分: 时间局部性:指的是在程序运行过程中最近被引用到的存储器位置在程序执行后期还会被多次引用到的可能性很大。 空间局部性:指的是程序...
  • 3.程序的局部性原理

    2018-09-11 17:16:26
    在现代计算机系统的各个层次,从硬件到操作系统、应用程序等,设计上都利用了局部性原理。比如缓存机制,CPU指令顺序处理等。 局部性通常有两种形式:时间局部性和空间局部性。 时间局部性(temporal loc...
  • 常用概念之程序局部性原理

    千次阅读 2017-06-10 19:55:56
     在现代计算机系统的各个层次,从硬件到操作系统、应用程序等,设计上都利用了局部性原理。比如缓存机制,CPU指令顺序处理等。  局部性通常有两种形式:时间局部性和空间局部性,下面分别进行
  • 局部性原理与磁盘预读原理来了解索引机制

    千次阅读 多人点赞 2019-11-26 16:52:44
    参考文章,链接如下: https://blog.csdn.net/coolwriter/article/details/80346454 https://blog.csdn.net/u010727189/article/details/79399384 ... 目录 局部性原理...
  • 时间局部性和空间局部性

    千次阅读 2020-08-10 15:03:21
    在CPU访问寄存器时,无论是存取数据抑或存取指令,都趋于聚集在一片连续的区域中,这就被称为局部性原理局部性原理又分为时间局部性(temporal locality) 和空间局部性 (spatial locality) 。 1. 时间局部性: ...
  • 文章目录1、局部性分类1)时间局部性2)空间局部性3)局部性原理举例2、对程序数据引用的局部性3、评价局部性提出问题:为什么有良好局部性的程序通常比局部性差的程序运行得更快?参考 1、局部性分类 局部性原理对...
  • 局部性原理的一点理解

    千次阅读 2016-01-23 19:02:59
    这汇总倾向性,就被称为局部性原理,这是一个持久的概念,对硬件和软件系统的设计和性能都有着极大的影响。 局部性通常有两种不同的形式:时间局部性和空间局部性。在一个具有良好时间局部性的程序中,被引用一次的...
  • 首先对特征点提取的原理进行了详细研究,针对SIFT算法原理分模块进行了研究;然后本文对SIFT特征点在图像匹配和图像拼接领域的应用进行了讨论;最后,为了验证本文算法的有效和优越,本文进行了仿真实验实验。...
  • 随笔七:高速缓存的局部性原理

    千次阅读 2012-06-19 14:52:12
    高速缓存的局部性原理,即程序具有访问局部区域的数据和代码的趋势。通过让高速缓存里存放可能经常访问的数据的方法,大部分的存储器操作都能在快速的高速缓存中完成。  重要结论:意识道高速缓存存在的应用程序员...
  • 在CPU访问寄存器时,无论是存取数据还是存取指令,都趋于聚集在一片连续的区域中,这就被称为局部性原理局部性原理又分为时间局部性(temporal locality) 和空间局部性 (spatial locality) 。 1. 时间局部...
  • 阐述了ZJL-450型矿用局部制冷设备的原理、配置、结构特点、技术特性及先进的核心技术,并介绍了其在中平能化集团矿井掘进工作面的应用。在实践应用中,该设备的先进、灵活和安全得到了充分体现,达到了较好的降温...
  • 存储系统层次结构的概念,掌握缓存-主存和主存-辅存层次作用,以及程序访问的局部性原理与存储系统层次结构的关系。存储器分类存储器的层次结构程序访问的局部性2.熟知主存储器的基本组成;掌握主存中存储单元地址的...
  • 相位一致的基本原理应用问题

    千次阅读 2021-09-02 11:26:01
    Morrone和Owens于1987年提出了基于局部能量特征的检测方法,为解决该问题提供了新思路,即用相位一致检测特征。P. Kovesi于1995年对该方法做出了改进,克服了噪声等问题,使该方法的应用得以保证。近期阅读有关...
  • CAN总线原理应用系统设计[PDF]

    千次下载 热门讨论 2009-09-30 15:38:41
    下面是CAN总线原理应用系统设计的目录 目录: 引论 1.1 计算机网络和协议 1.1.1 计算机网络 1.1.2 协 议 1.1.3 计算机网络体系结构 1.2 局域网 1.2.1 概 述 1.2.2 局域网协议 1.3 现场总线 1.3.1 背景和发展 1.3.2...
  • 数据库原理应用(mysql版)

    千次阅读 2021-05-17 10:06:32
    数据库原理应用(mysql版) 这是对于学校教材的学习,我也希望能好好学习 这个并不是正儿八经的数据库,只是lz酷爱使用md编写笔记,孩子要期末考试了,所以想在闲暇时刻也能复习,就上传到csdn用手机查看md格式的...
  • 数据库原理及其应用

    千次阅读 2021-01-01 13:43:40
    数据库原理及其应用 第一章:数据库系统 数据库管理系统(DBMS) 数据库应用系统(DBAS) 数据库(DB) 第二章:关系运算 第三章:数据库应用系统设计概述 3.1生命周期 1、用户需求分析:逻辑描述 2、概念结构设计:生成...
  • 物联网的原理应用和技能

    万次阅读 2019-02-09 10:29:17
    1物联网的原理 物联网是在计suanji互联网的基础shang,li用RFID、无xian数据通讯deng技能,构zaoyi个覆盖世界shang万shi万物的InternetofThings。在这个网络中,物pin商品)ke以互xiang进行“jiao流”,而无需人的...
  • 【最全】《数据库原理应用》知识点整理+习题

    万次阅读 多人点赞 2020-05-26 10:57:22
    目录 第1章 绪论 1.1术语 1.2重要概念 数据库管理技术的发展过程(三个阶段) 数据模型(Data Model) 逻辑模型的分类(非关系模型与关系模型) 画E-R图 ...2.3关系的完整 2.4关系代数 选择 投影 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 156,724
精华内容 62,689
关键字:

局部性原理的应用