精华内容
下载资源
问答
  • 这里我给大家分享的一种折衷的办法,局部优化,即实现单独对代码中某个函数或者某个C文件进行优化,这样就可以保证对优化带来的风险进行有效的控制。
  • 对于一个给定的程序,我们可以把它划分为一系列的基本块。...局限于基本块范围内的优化称为基本块内的优化,或者称为局部优化。所谓基本块,是指程序中一个顺序执行的语句序列,其中只有一个入口和一个出口。 ...

    预备知识简述.

    对于一个给定的程序,我们可以把它划分为一系列的基本块。在各个基本块范围内,分别进行优化。局限于基本块范围内的优化称为基本块内的优化,或者称为局部优化。

    所谓基本块,是指程序中一个顺序执行的语句序列,其中只有一个入口和一个出口。入口就是其中的第一个语句。对于一个基本块来说,执行时只能从其入口进入,从其出口退出。

    下面的三地址码序列就构成了一个基本块:
    T1:=a*a
    T2:=a*b
    T3:=2*T2
    T4:=T1+T2
    T5:=b*b
    T6:=T4+T5
    如果一条三地址码语句为x:=y+z,则称对x定值引用y和z。对于基本块内的某个名字某个给定点,如果在程序中(包括在本基本块和其他基本块)这个名字在这个点以后被引用,我们就称这个名字在这个给定点是活跃的。

    划分基本块の算法.

    1. 首先要求出四元式程序中各个基本块的入口语句,它们是:
      a).程序的第一个语句;
      b).能由条件转移语句或无条件转移语句转移到的语句;
      c).紧跟在条件转移语句后面的语句。
    2. 对以上求出的每一入口语句,构造其所属的基本块。基本块是由该入口语句A到另一入口语句B(不包括语句B),或者到一条转移语句C(包括语句C),或者到一条停语句D(包括语句D)之间的语句序列组成的;
    3. 凡未被纳入某一个基本块中的语句,都是程序中控制流无法到达的语句,所以这些语句也是不会执行到的,我们完全可以把他们从程序中删除。

    介绍完了划分基本块的算法之后,我们用一个例子来具体地看看算法执行的过程和结果:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    根据算法流程,第一步先找出入口语句,它们分别是第1、4、6、8,我们在下一张图中用红色序号标明。

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    下一步是构造每一个入口语句的基本块。对于语句1来说,它的基本块范围只能到3号语句,因为4号语句是另一个入口语句了。对于语句4来说,它的基本块范围是[4…5],因为6号语句是另一个入口语句。[6…7]基本块的划分方法与上面同理,而8号语句遇到halt语句才完成了自己基本块的构造。综上,上面的四元式代码序列,划分出来4个基本块:[1…3]、[4…5]、[6…7]和[8…9],如下图所示:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述

    基本块内可以实现の优化.

    除了我们在中间代码优化(一)中介绍过的删除多余运算以及删除无用赋值两种技术外,基本块内还可以实现下列优化操作。

    1.合并已知量.

    假设在一个基本块内有下面这样的语句:
    T:=2
    ...
    S=2*T
    如果在对T赋值以后没有改变过,则S=2*T中的两个运算对象也都是在编译时的已知量,那么就可以在编译时计算出S的值,而不必等到程序运行时才计算。也就是说可以把上面基本块中的最后一句变换为S=4,这样的变换叫做合并已知量。

    2.临时变量改名.

    假设在一个基本块内有语句T=b+c,其中T是一个临时变量名,那么如果我们将这一语句改为S=b+c并且将整个基本块中所有出现T的地方都改成S,则不改变基本块的值。事实上,总可以将一个基本块变换成另一个等价的基本块,是其中定义临时变量的语句改成定义新的临时变量。

    3.交换语句位置.

    假设在一个基本块里有下列两个相邻的语句:T=b+c;S=x+y,并且x、y均不为T,b、c均不为S,那么交换这两个语句的顺序并不会影响基本块的执行结果。有时候我们通过交换语句的次序,可以产生出更加高效的代码。

    4.代数变换.

    代数变换的具体含义是对于基本块中的求值表达式,用代数上等价的形式替换,目的是将复杂的运算变成简单的运算。很有名的秦九韶公式(Horner’s Rule)就是一种代数等价的变换,将多项式求值变得很高效率。例如语句x=x+0;y=y*1中的运算并没有执行的意义,可以从基本块中删除;再比如x=y**2中的幂运算,通常需要调用函数来实现,通过代数变换,可以用x=y*y来代替。

    程序流图.

    通过构造一个有向图,我们称之为流图。在这个图中我们可以将程序的控制流信息附加到图的有向边上,从而表示一个程序。流图以基本块为结点,那个以程序的第一条语句为入口语句的基本块作为首结点。如果在某个执行顺序中,基本块B2_2紧接在基本块B1_1之后执行,则从B1_1到B2_2有一条有向边。也就是说如果:

    1. 有一个条件(无条件)转移语句从B1_1的最后一条语句转移到B2_2的第一条语句,或者;
    2. 在程序的序列中,B2_2紧跟在B1_1之后,并且B1_1的最后一条语句不是一个无条件转移语句

    我们就说B2_2是B1_1的后继,而B1_1是B2_2的前驱。前面我们给出的基本块划分算法中的实例中,就是一个程序流图的例子。控制流图的优势在于,它可以清晰地表示出三地址码所不能表征的控制流信息,从而有助于我们进行控制流、数据流分析。从本质上来说,控制流图也是一种中间代码。

    DAG表示及其应用.

    DAG是Directed Acyclic Graph的首字母缩略词,意为有向无环图。基本块的DAG表示,是一种图中结点带有标记附加信息的形式。标记可以有下述的三种:

    1. 图的叶结点以一标识符(变量名)或常数作为标记,表示该结点代表了这个变量或常数的。如果需要叶结点表示某个变量A的地址,则使用addr(A)作为这个结点的标记。有些叶结点上的标记有下标0,代表它是这个变量的初值。
    2. 图的内部结点以一运算符作为标记,表示该结点代表使用这一运算符,并将其后继结点代表的值作为操作数而获得的运算结果
    3. 图中的结点可能附加一个或多个变量标识符,这意味着这些变量都具有该结点所代表的值。

    我们先看一个DAG图的实例,对其有一个宏观的印象,再介绍代码基本块的DAG构造算法。

    (1)T0:=3.14
    (2)T1:=2*T0
    (3)T2:=R+r
    (4)A:=T1*T2
    (5)B:=A
    (6)T3:=2*T0
    (7)T4:=R+r
    (8)T5:=T3*T4
    (9)T6:=R-r
    (10)B:=T5*T6
    

    在这里插入图片描述

    【上图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    图中是这个四元式代码序列对应的DAG图构建过程,最终的DAG图展示如下:

    【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

    在这里插入图片描述
    我们可以对照上面给出的标记信息的解释,来理解一下每个结点所代表的值、意义以及对应了哪一条三地址码语句。

    DAG构造算法.

    假设DAG各结点的信息将采取某种适当的数据结构来存放,例如链表。并且设有一个标识符(当中包括常数)与结点的对应表,NODE(A)是描述这种对应关系的一个函数,它的返回值或者是一个结点编号n,或者没有返回值。当NODE(A)=n时,意味着DAG中存在一个结点n,它的标记或者附加标识符是A。
    我们讨论的中间代码形式,只限于以下三种:

    1. A:=B
    2. A:=op B
    3. A:=B op C 或 A:=B[C]

    基于以上假定,我们给出基本块的DAG构造算法。

    1. 初始化,DAG=NULL. 考察基本块中的每一条中间代码,依次执行以下步骤;
    2. 如果NODE(B)无定义,则构造一个标记为B的叶结点,并且定义NODE(B)的返回值是这个结点。①如果当前代码是(0)型A:=B,则记NODE(B)的值为n,跳转到第四步;②如果当前代码是(1)型A:=op B,则跳转到第二步的第一分支;③如果当前代码是(2)型,并且如果NODE(C)无定义,那么就构造一个标记为C的叶结点并且定义NODE(C)的返回值是这个结点,跳转到第二步的第二分支。
    3. ①如果NODE(B)是标记为常数的叶结点,则跳转到第二步的第三分支,否则跳转到第三步的第一分支;②如果NODE(B)和NODE(C)都是标记为常数的叶结点,则跳转到第二步的第四分支,否则跳转到第三步的第二分支;③执行op B(合并已知量),令得到的新常数为k. 如果NODE(B)是处理当前代码新构造出来的结点,则删除它。如果NODE(k)无定义,则构造一个以k为标记的叶结点。置NODE(k)=n,跳转到第四步。④执行B op C(合并已知量),令得到的新常数为k. 如果NODE(B)或NODE©是处理当前代码新构造出来的结点,则删除它。如果NODE(k)无定义,则构造一个以k为标记的叶结点。置NODE(k)=n,跳转到第四步。
    4. ①检查DAG中是否已经存在一个结点,它的唯一后继为NODE(B)并且标记为op(查找公共子表达式),如果没有则构造结点n,否则就把已有的结点作为它的结点并设该结点为n。跳转到第四步。②检查DAG中是否已经存在一个结点,它的左后继为NODE(B),右后继为NODE(C),并且标记为op(查找公共子表达式),如果没有则构造结点n,否则就把已有的结点作为它的结点并设该结点为n。跳转到第四步。
    5. 如果NODE(A)无定义,则把A附加在结点n上并令NODE(A)=n;否则先把A从NODE(A)结点上的附加标识符集中删除(如果NODE(A)是叶结点,则不用删除A),把A附加到新的结点n上,并令NODE(A)=n。
    6. 跳转回第一步,继续处理下一条代码。

    接下来我们以上面示例中的三地址码序列作为实例,来模拟一次DAG构造算法的执行。

    (1)T0:=3.14
    (2)T1:=2*T0
    (3)T2:=R+r
    (4)A:=T1*T2
    (5)B:=A
    (6)T3:=2*T0
    (7)T4:=R+r
    (8)T5:=T3*T4
    (9)T6:=R-r
    (10)B:=T5*T6
    
    1. T0:=3.14,作为(0)型代码,根据算法中的步骤,在第1步中先构造NODE(B),并将它的值标记为n,然后跳转到第4步,将T0附加在构造出的结点n上,得到下面这个DAG:

      【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

      在这里插入图片描述

    2. T1:=2*T0,作为(2)型代码,先构造出标记为常数2的结点,因为NODE(T0)已经存在,就跳转到第2步的第二分支。由于标记2和标记3.14都是常数,所以再跳转到第2步的第四分支,执行2*T0的运算,构造出以6.28为标记的结点NODE(k),并且由于NODE(2)是当前语句生成的结点,所以需要删除以NODE(2),跳转到第4步。因为NODE(T1)无定义,所以将T1附加到这个结点上,最后生成下示的DAG图:

      【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

      在这里插入图片描述

    3. T2:=R+r,作为(2)型代码,首先构造NODE(R),再构造NODE(r),跳转到第2步的第二分支,由于R和r都不是常数,所以跳转到第3步的第二分支。查找发现DAG中并没有左后继为NODE(R),右后继为NODE(r)的结点,所以构造这样的一个结点n,跳转到第4步,将T2附加在结点n上,得到下面的DAG图:

      【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

      在这里插入图片描述

    4. A:=T1*T2,作为(2)型代码,通过算法的流程到达第3步的第二分支,查找发现并没有左后继为NODE(T1),右后继为NODE(T2)的结点,于是构造一个这样的结点n,在第4步中将A附加到结点n的标记上,得到这样的DAG图:

      【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】
      在这里插入图片描述

    5. [5…8]的三地址码序列,都是以及存在的结点,只要将标识符附加到既有的结点上即可,DAG如下:

      【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

      在这里插入图片描述

    6. T6:=R-r的构造过程和T2:=R+r类似,区别在于T6这一语句构造时R和r的结点已经存在了,所以只需要构造标记为-的内部节点;B:=T5*T6的构造过程和A:=T1*T2一致,需要注意的是在第四步中要将原本附加在NODE(A)结点上的标记B删去,重新附加在T5*T6的结点上,最终的DAG图如下:

      【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

      在这里插入图片描述

    通过上面的例子,我们可以得到下面的一些结论:

    1. 对于任何一句代码,如果其中的运算量都是编译时的已知量,那么DAG中并不会生成其内部节点,而是直接进行运算,将结果(也是常数)作为一个标记生成叶结点。例如我们T1:=2*T0的构造过程,可以看出步骤2的作用就是合并已知量
    2. 算法的步骤3是查找公共子表达式,对具有公共子表达式的代码,DAG算法只产生一个计算该表达式值的内部结点,而将那些被赋值的变量直接附加在这唯一的结点上。例如我们T3:=2*T0这样代码的构造过程。
    3. 如果某个变量被赋值后,在它被引用前又被重新赋值,那么算法的步骤4能够将其从前一个值的结点上删除,也就是说步骤4有删除无用赋值的作用。

    因此我们可以利用这样的DAG来重新生成原基本块的,一个经过了优化的中间代码序列。

    DAG与基本块の优化.

    如果DAG的某个内部结点上附有多个标识符,说明计算该结点值的表达式是一个公共子表达式,当我们将该结点重新写成中间代码时,就可以实现删除多余运算,所以按照这样的思想,我们可以根据DAG写出下面的中间代码:

    (1)T0:=3.14
    (2)T1:=6.28
    (3)T3:=6.28
    (4)T2:=R+r
    (5)T4:=T2
    (6)A:=6.28*T2
    (7)T5:=A
    (8)T6:=R-r
    (9)B:=A*T6
    

    这段代码就是对最初的中间代码实现了合并已知量、删除多余运算、删除无用赋值三种优化后的结果。除了可以应用DAG进行基本块的优化之外,我们从DAG中还能得出下列信息:

    • 在基本块之外被定值,并且在基本块内被引用的所有标识符,就是DAG图中叶结点上标记的那些标识符;
    • 在基本块内被定值,并且定值之后能够被引用的所有标识符,就是DAG图中内部结点上附加的那些标识符。

    利用这些信息,我们还可以进一步地删除中间代码中的无用赋值,但这需要获取有关变量在基本块后面被引用的情况(数据流分析)。如果DAG中某个结点上附加的标识符在后面并没有被引用,那么就不生成对该标识符的赋值语句;又如某个结点上不附有任何标识符或者上面附加的标识符在后面不被引用,而且它也没有前驱结点,这就意味着基本块内以及基本块之后都不会引用该结点的值,那么就可以不生成该结点的代码;再比如有这样的两条语句A=x op y;B=A并且第一条语句的结果A只在第二条语句被引用,那么完全可以将这两条语句合并为B=x op y.
    我们现在假设,对于上面已经经过DAG优化的中间代码来说,T0,T1,T2,T3,T4,T5,T6在后面的代码都不会被引用,那么中间代码序列就可以写成下面的样子:

    S1=R+r
    A=6.28*S1
    S2=R-r
    B=A*S2
    

    其中没有生成对T0,T1,T2,T3,T4,T5,T6赋值的语句,S1、S2是用于存放中间结果的临时变量。上述语句序列是根据结点的构造顺序[n5_5,n6_6,n7_7,n8_8]来生成的,如果我们采用其他顺序,并且保证任意结点的语句在其后继结点的语句之后、转移语句(如果有的话)仍然是基本块的最后一个语句即可。这里如果我们按照[n7_7,n5_5,n6_6,n8_8]的顺序来重写中间代码:

    S1=R-r
    S2=R+r
    A=6.28*S2
    B=A*S1
    

    在目标代码生成部分,我们会看到后一种中间代码是优于前一种代码的,我们会介绍如何重排DAG的结点顺序以生成更加高效的目标代码。

    复杂基本块.

    我们前面在讨论DAG构造算法时,假定了代码种类只有三种:

    1. A:=B
    2. A:=op B
    3. A:=B op C 或 A:=B[C]

    然而当基本块中出现数组元素引用、指针以及过程调用时,情况就复杂起来。例如我们考察下列语句序列:

    x=a[i]
    a[j]=y
    z=a[i]
    

    如果我们头铁,不做变通地应用DAG构造算法,将a[i]视为公共子表达式,那么“优化”后的代码序列就会如下:

    x=a[i]
    z=x
    a[j]=y
    

    我们考虑i=j并且y≠a[i]的情况,这确实是存在的一种情况,那么上述"优化"前后的代码结果是不同的。问题的原因在于,当我们对一个数组元素赋值时,我们可能改变表达式a[i]的右值,即使a和i的值都没有改变。因此我们对数组a的一个元素赋值时,我们“注销”所有标记为[ ]、左边的变元是a加上或减去一个常数的结点。即我们认为对于这样的结点来说,再添加附加标识符是非法的,从而取消了它作为公共子表达式的资格。这一操作要求我们对每个结点设置一个标志位来标记该结点是否被“注销”。另外,对每个基本块中引用的数组a,我们可以保存一个节点表,当中的内容是当前未被注销,但若有对a中一个元素赋值则必须被注销的结点。
    对指针赋值*p=w,其中p是一个指针会产生同样的问题。如果我们不知道p指向哪一个变量,就要认为它可能指向基本块中的任何一个变量。当构造这种赋值语句的结点时,要将DAG中各结点上所有标识符(包括叶结点标识符)都予以注销。将DAG中所有结点上的标识符都注销,也同时意味着DAG中的所有结点都被注销。
    在一个基本块中的一个过程调用将注销所有的结点,因为对被调用过程的情况缺乏了解,我们必须假定任何变量都可能因为副作用而发生变化。
    在DAG与基本块の优化中我们提到过,可以不按照DAG结点的构造顺序来重写代码,这种操作就必须注意DAG中的某些结点一定要遵守某种顺序。我们根据上面对于数组元素、指针以及过程调用情况的本来意义,将重写中间代码时DAG结点之间必须遵守的顺序归纳如下:

    1. 对于数组a任何元素的引用或赋值,都必须跟在原来位于其前面(如果有的话)对于数组a任何元素的赋值之后;
    2. 对于数组a任何元素的赋值,都必须跟在原来位于其前面(如果有的话)对于数组a任何元素的引用之后;
    3. 对于任何标识符的引用或赋值,都必须跟在原来位于其前面的任何过程调用或通过指针进行的间接赋值之后;
    4. 任何过程调用或通过指针进行的间接赋值,都必须跟在原来位于其前面的对于任何标识符的引用或赋值之后。

    总结来说就是,当重写基本块时,任何数组a 的引用不可以互相调换次序,并且任何语句不得跨越一个过程调用语句或者一个通过指针的间接赋值语句。

    展开全文
  • 局部优化-基本块优化0 目录23 优化123.1 局部优化-基本块优化23.1.1 课堂重点23.1.2 测试与作业24 下一章 0 目录 23 优化1 23.1 局部优化-基本块优化 23.1.1 课堂重点 23.1.2 测试与作业 ...

    慕课广西大学.编译原理.第二十三章.优化1.局部优化-基本块优化

    0 目录

    23 优化1

    23.3 局部优化-基本块优化

    23.3.1 课堂重点

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    23.3.2 测试与作业

    下面图中哪个是有向无环图(DAG)?
    A.
    在这里插入图片描述
    B.
    在这里插入图片描述
    C.
    D.
    B

    24 下一章

    博客地址:

    展开全文
  • 本文以同煤集团挖金湾煤矿为工程背景,针对局部通风漏风问题,运用数值模拟对通风系统进行了优化以及提出了新的堵漏风技术
  • 通过将粒子群优化算法(PSO)与经典局部一维搜索技术相结合,提出一种嵌入局部一维搜索技术的混合粒子群优化算法(LLS-PSO)。该算法在基本粒子群优化算法中引入一维搜索技术,选取最优粒子进行局部一维搜索,增强了在最...
  • 2020-09-11:Hive的优化策略有哪些

    千次阅读 2020-09-11 20:47:39
    Hive调优及优化的12种方式 1.请慎重使用COUNT(DISTINCT col)。可以考虑使用Group By 或者 ROW_NUMBER() OVER(PARTITION BY col)方式代替COUNT(DISTINCT col)。 2.小文件会造成资源的多度占用以及影响查询效率。在...

    福哥答案2020-09-11:

    Hive调优及优化的12种方式
    1.请慎重使用COUNT(DISTINCT col)。可以考虑使用Group By 或者 ROW_NUMBER() OVER(PARTITION BY col)方式代替COUNT(DISTINCT col)。
    2.小文件会造成资源的多度占用以及影响查询效率。在数据源头HDFS中控制小文件产生的个数。
    3.请慎重使用SELECT *。在查询数据表时,指定所需的待查字段名,而非使用 * 号。
    4.不要在表关联后面加WHERE条件。采用谓词下推的技术,提早进行过滤有可能减少必须在数据库分区之间传递的数据量。
    5.处理掉字段中带有空值的数据。
    6.设置并行执行任务数。
    7.设置合理的Reducer个数。
    8.JVM重用。
    9.为什么任务执行的时候只有一个reduce?避免使用全局排序,可以使用sort by进行局部排序。使用GROUP BY进行统计,不会进行全局排序。
    10.选择使用Tez引擎。
    11.选择使用本地模式。
    12.选择使用严格模式。

    Hive 任务优化策略-整合,持续更新。
    1、好的模型设计事半功倍 。
    2、解决数据倾斜问题 。
    3、减少 job 数 。
    4、设置合理的 MapReduce 的 task 数,能有效提升性能。(比如,10w+级别的计算,用 160个 reduce,那是相当的浪费,1 个足够) 。
    5、了解数据分布,自己动手解决数据倾斜问题是个不错的选择。这是通用的算法优化,但算法优化有时不能适应特定业务背景,开发人员了解业务,了解数据,可以通过业务逻辑精 确有效的解决数据倾斜问题 。
    6、数据量较大的情况下,慎用 count(distinct),group by 容易产生倾斜问题 。
    7、对小文件进行合并,是行之有效的提高调度效率的方法,假如所有的作业设置合理的文 件数,对云梯的整体调度效率也会产生积极的正向影响 。
    8、优化时把握整体,单个作业最优不如整体最优。


    评论

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

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

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

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

    局部性的本质是什么?其实就是概率的不均等,这个宇宙中,很多东西都不是平均分布的,平均分布是概率论中几何分布的一种特殊形式,非常简单,但世界就是没这么简单。我们更长听到的发布叫做高斯发布,同时也被称为正态分布,因为它就是正常状态下的概率发布,起概率图如下,但这个也不是今天要说的。
    在这里插入图片描述
    其实有很多情况,很多事物有很强的头部集中现象,可以用概率论中的泊松分布来刻画,这就是局部性在概率学中的刻画形式。
    在这里插入图片描述
    在这里插入图片描述
    上面分别是泊松分布的示意图和概率计算公式,λ\lambda 表示单位时间(或单位面积)内随机事件的平均发生次数,ee表示自然常数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 郑雨迪
    展开全文
  • 通过将粒子群优化算法(PSO)与经典局部一维搜索技术相结合,提出一种嵌入局部一维搜索技术的混合粒子群优化算法(LLS-PSO)。该算法在基本粒子群优化算法中引入一维搜索技术,选取最优粒子进行局部一维搜索,增强了...
  • 考虑局部裂纹失效的拓扑优化,刘湃,亢战,本文基于断裂力学分析和拓扑优化技术,研究了抑制结构局部断裂失效的设计方法。考虑了线弹性材料的脆性断裂问题,采用有限元方法
  • gcc的三级优化到底优化哪些

    千次阅读 2016-11-13 23:28:51
    不同的优化级别使用的优化技术也可以单独的应用于代码。 可以使用-f命令行选项引用每个 单独的优化技术。 第一级:代码调整  代码调整是一种局部的思维方式;基本上不触及算法层级;它面向的是代码,而不是问
  • 性能优化技巧

    千次阅读 2013-11-18 11:37:05
    系列目录 性能优化方法和技巧 性能优化的方法和技巧:概述 性能优化的方法和技巧:代码 ...我以前就说过,性能优化有三个层次: 系统层次 算法层次 代码层次 系统层次关注系统的控制流程和数据
  • Java程序性能优化技巧

    2015-07-23 12:50:33
    1、优化循环体 如果循环次数很多,循环体内代码处理不好问题就会被放大。 for(int i=0;i
  • 面试官:关于Java性能优化,你什么技巧

    万次阅读 多人点赞 2019-11-27 10:13:05
    一般两种方案:即优化代码或更改设计方法。我们一般会选择后者,因为不去调用以下代码要比调用一些优化的代码更能提高程序的性能。而一个设计良好的程序能够精简代码,从而提高性能。 下面将提供一些在JAVA程序的...
  • js性能优化技巧

    千次阅读 2013-11-04 10:48:59
    下面是一些关于客户端JS性能的一些优化的小技巧: 1. 关于JS的循环,循环是一种常用的流程控制。JS提供了三种循环:for(;;)、while()、for(in)。在这三种循环中 for(in)的效率最差,因为它需要查询Hash键,因此应...
  • Java性能优化技巧

    千次阅读 2010-04-28 09:43:00
    Java性能优化技巧参考了些书籍,网络资源整理出来,适合于大多数Java应用在JAVA程序中,性能问题的大部分原因并不在于JAVA语言,而是程序本身。养成良好的编码习惯非常重要,能够显著地提升程序性能。1.尽量使用...
  • 手机游戏优化技巧

    千次阅读 2010-11-10 14:35:00
    手机游戏优化技巧:  a.减少内存使用:  —尽可能避免使用对象:具备某种意义功能时才使用对象,否则用基本数据类型;  —重用对象:重用对象(初始化对象状态)而不重新创建;  —...
  • 4.2 模拟退火算法 5.优化技巧 5.1 正则化 5.2 集成模型 ...​ 在一般的优化问题中,防止算法陷入局部最优解一直是某些算法的难点,对于基于梯度的算法,如果优化的目标函数不是一个凸函数,那它的表...
  • Web业务性能优化技术总结

    千次阅读 2017-03-18 01:00:25
    Web业务的性能优化是一个系统工程,既深度,又广度。以下所简称性能均特指Web业务性能。 技术的广度上,主要从大背景下考虑到其各个相关方,基于共同的数据指标发掘和评估方案。 技术的深度上是一个渐进和迭代的...
  • MapReduce编程模型及优化技巧

    千次阅读 2016-04-20 18:57:07
    (一)MapReduce 编程模型(如果你已经了解请直接进入第二部分MapReduce 的优化讲解)  在学习MapReduce 优化之前我们先来了解一下MapReduce ... 第一步:假设一个文件三行英文单词作为 MapReduce 的Input(输入
  • 浅析嵌入式C优化技巧

    千次阅读 多人点赞 2015-07-26 20:34:26
    嵌入式C语言优化技巧1 概述 嵌入式系统是指完成一种或几种特定功能的计算机系统,具有自动化程度高,响应速度快等优点,目前已广泛应用于消费电子,工业控制等领域.嵌入式系统受其使用的硬件以及运行环境的限制,非常...
  • 前端优化技巧(一)

    万次阅读 2014-12-08 17:32:34
    闲暇没事整理了下前端常用的优化技巧,按目的分类如下:  在文档开头显示一个加载中图案(俗称菊花) ,然后把不重要的JS文件放在文档末尾, 给script标签添加defer属性 目的:防止JS文件阻塞页面加载 CSS...
  • MySQL SQL语句优化技巧

    万次阅读 2016-10-18 16:38:14
    2、对查询进行优化,应尽量避免全表扫描,首先应考虑在 where 及 order by 涉及的列上建立索引。 3、应尽量避免在 where 子句中对字段进行 null 值判断,否则将导致引擎放弃使用索引而进行全表扫描,如: ...
  • 软件优化技术

    千次阅读 2007-06-07 11:53:00
    软件优化技术真经-框架篇 软件优化是一项系统工程。总体而言,整个优化框架可以分为两个部分:设计优化和代码优化。1,设计优化 设计优化包括了软件体系结构的优化,数据结构的优化,算法的优化...
  • [技巧篇] 循环代码优化技巧

    千次阅读 2019-07-23 09:00:00
    本文字数:1178 字阅读本文大概需要:3 分钟00.写在之前「代码优化」应该是我们时刻记在心里的一件事情,从一开始就建立一种正确的编程观念,养成一种好的编程习惯,避免一...
  • python 代码 性能优化技巧

    千次阅读 2012-07-24 13:22:55
    Python 代码优化常见技巧 代码优化能够让程序运行更快,它是在不改变程序运行结果的情况下使得程序的运行效率更高,根据 80/20 原则,实现程序的重构、优化、扩展以及文档相关的事情通常需要消耗 80%
  • 循环优化: 虽然计算机越来越快,空间也越来越大,我们...3.局部变量查询较快,尽量使用局部变量 其他优化注意点: 1.连接多个字符串,使用join()而不使用 + 2.列表进行元素加入或删除,尽量在列表尾部操作 ...
  • Python 代码性能优化技巧

    千次阅读 2012-10-10 16:37:31
    选择了脚本语言就要忍受其速度,这句话在某种程度上说明了 python 作为脚本的一个不足之处,那就是执行效率和性能不够理想,特别是在 performance 较差的机器上,因此必要进行一定的代码优化来提高程序的执行效率...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 147,266
精华内容 58,906
关键字:

局部优化的技术有哪些