- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
摘要: 本文重点介绍几种通过优化Cache使用提高程序性能的方法。
本文分享自华为云社区《 编译器优化那些事儿(7):Cache优化 》,作者:毕昇小助手.
软件开发人员往往期望计算机硬件拥有无限容量、零访问延迟、无限带宽以及便宜的内存,但是现实却是内存容量越大,相应的访问时间越长;内存访问速度越快,价格也更贵;带宽越大,价格越贵。为了解决大容量、高速度、低成本之间的矛盾,基于程序访问的局部性原理,将更常用数据放在小容量的高速存储器中,多种速度不同的存储器分层级联,协调工作.
图1 memory hierarchy for sever [1] 。
现代计算机的存储层次可以分几层。如图1所示,位于处理器内部的是寄存器;稍远一点的是一级Cache,一级Cache一般能够保存64k字节,访问它大约需要1ns,同时一级Cache通常划分为指令Cache(处理器从指令Cache中取要执行的指令)和数据Cache(处理器从数据Cache中存/取指令的操作数);然后是二级Cache,通常既保存指令又保存数据,容量大约256k,访问它大约需要3-10ns;然后是三级Cache,容量大约16-64MB,访问它大约需要10-20ns;再接着是主存、硬盘等。注意,CPU和Cache是以word传输的,Cache到主存以块(一般64byte)传输的.
前文提到了程序的局部性原理,一般指的是时间局部性(在一定时间内,程序可能会多次访问同一内存空间)和空间局部性(在一定时间内,程序可能会访问附近的内存空间),高速缓存(Cache)的效率取决于程序的空间和时间的局部性性质。比如一个程序重复地执行一个循环,在理想情况下,循环的第一个迭代将代码取至高速缓存中,后续的迭代直接从高速缓存中取数据,而不需要重新从主存装载。因此,为了使程序获得更好的性能,应尽可能让数据访问发生在高速缓存中。但是如果数据访问在高速缓存时发生了冲突,也可能会导致性能下降.
篇幅原因,本文重点讨论编译器在Cache优化中可以做哪些工作,如果读者对其他内存层次优化感兴趣,欢迎留言。下面将介绍几种通过优化Cache使用提高程序性能的方法.
现代编译器可以通过调整代码和数据的布局方式,提高Cache命中率,进而提升程序性能。本节主要讨论数据和指令的对齐、代码布局对程序性能的影响,大部分处理器中Cache到主存是以Cache line(一般为64Byte,也有地方称Cache块,本文统一使用Cache line)传输的,CPU从内存加载数据是一次一个Cache line,CPU往内存写数据也是一次一个Cache line。假设处理器首次访问数据对象A,其大小刚好为64Byte,如果数据对象A首地址并没有进行对齐,即数据对象A占用两个不同Cache line的一部分,此时处理器访问该数据对象时需要两次内存访问,效率低。但是如果数据对象A进行了内存对齐,即刚好在一个Cache line中,那么处理器访问该数据时只需要一次内存访问,效率会高很多。编译器可以通过合理安排数据对象,避免不必要地将它们跨越在多个Cache line中,尽量使得同一对象集中在一个Cache中,进而有效地使用Cache来提高程序的性能。通过顺序分配对象,即如果下一个对象不能放入当前Cache line的剩余部分,则跳过这些剩余的部分,从下一个Cache line的开始处分配对象,或者将大小(size)相同的对象分配在同一个存储区,所有对象都对齐在size的倍数边界上等方式达到上述目的.
Cache line对齐可能会导致存储资源的浪费,如图2所示,但是执行速度可能会因此得到改善。对齐不仅仅可以作用于全局静态数据,也可以作用于堆上分配的数据。对于全局数据,编译器可以通过汇编语言的对齐指令命令来通知链接器。对于堆上分配的数据,将对象放置在Cache line的边界或者最小化对象跨Cache line的次数的工作不是由编译器来完成的,而是由runtime中的存储分配器来完成的[2].
图2 因块对齐可能会浪费存储空间 。
前文提到了数据对象对齐,可以提高程序性能。指令Cache的对齐,也可以提高程序性能。同时,代码布局也会影响程序的性能,将频繁执行的基本块的首地址对齐在Cache line的大小倍数边界上能增加在指令Cache中同时容纳的基本块数目,将不频繁执行的指令和频繁指令的指令放到不同的Cache line中,通过优化代码布局来提升程序性能.
Cache预取是将内存中的指令和数据提前存放至Cache中,达到加快处理器执行速度的目的。Cache预取可以通过硬件或者软件实现,硬件预取是通过处理器中专门的硬件单元实现的,该单元通过跟踪内存访问指令数据地址的变化规律来预测将会被访问到的内存地址,并提前从主存中读取这些数据到Cache;软件预取是在程序中显示地插入预取指令,以非阻塞的方式让处理器从内存中读取指定地址数据至Cache。由于硬件预取器通常无法正常动态关闭,因此大部分情况下软件预取和硬件预取是并存的,软件预取必须尽力配合硬件预取以取得更优的效果。本文假设硬件预取器被关闭后,讨论如何利用软件预取达到性能提升的效果.
预取指令prefech(x)只是一种提示,告知硬件开始将地址 x 中的数据从主存中读取到Cache中。它并不会引起处理停顿,但若硬件发现会产生异常,则会忽略这个预取操作。如果prefech(x)成功,则意味着下一次取 x 将命中Cache;不成功的预取操作可能会导致下次读取时发生Cache miss,但不会影响程序的正确性[2].
数据预取是如何改成程序性能的呢?如下一段程序:
double a[n]; for ( int i = 0 ; i < 100 ; i++ ) a[i] = 0 ;
假设一个Cache line可以存放两个double元素,当第一次访问a[0]时,由于a[0]不在Cache中,会发生一次Cache miss,需要从主存中将其加载至Cache中,由于一个Cache line可以存放两个double元素,当访问a[1]时则不会发生Cache miss。依次类推,访问a[2]时会发生Cache miss,访问a[3]时不会发生Cache miss,我们很容易得到程序总共发生了50次Cache miss.
我们可以通过软件预取等相关优化,降低Cache miss次数,提高程序性能。首先介绍一个公式[3]:
上述公式中L是memory latency,S是执行一次循环迭代最短的时间。iterationAhead表示的是循环需要经过执行几次迭代,预取的数据才会到达Cache。假设我们的硬件架构计算出来的iterationAhead=6,那么原程序可以优化成如下程序:
double a[n]; for ( int i = 0 ; i < 12 ; i+= 2 ) // prologue prefetch(& a[i]); for ( int i = 0 ; i < 88 ; i+= 2 ) { // steady state prefetch(&a[i+ 12 ]); a[i] = 0 ; a[i + 1 ] = 0 ; } for ( int i = 88 ; i < 100 ; i++) // epilogue a[i] = 0 ;
由于我们的硬件架构需要循环执行6次后,预取的数据才会到达Cache。一个Cache line可以存放两个double元素,为了避免浪费prefetch指令,所以prologue和steady state循环都展开了,即执行prefetch(&a[0])后会将a[0]、a[1]从主存加载至Cache中,下次执行预取时就无需再次将a[1]从主存加载至Cache了。prologue循环先执行数组a的前12个元素的预取指令,等到执行steady state循环时,当i = 0时,a[0]和a[1]已经被加载至Cache中,就不会发生Cache miss了。依次类推,经过上述优化后,在不改变语义的基础上,通过使用预取指令,程序的Cache miss次数从50下降至0,程序的性能将会得到很大提升.
注意,预取并不能减少从主存储器取数据到高速缓存的延迟,只是通过预取与计算重叠而隐藏这种延迟。总之,当处理器有预取指令或者有能够用作预取的非阻塞的读取指令时,对于处理器不能动态重排指令或者动态重排缓冲区小于我们希望隐藏的具体Cache延迟,并且所考虑的数据大于Cache或者是不能够判断数据是否已在Cache中,预取是适用的。预取也不是万能,不当的预取可能会导致高速缓存冲突,程序性能降低。我们应该首先利用数据重用来减少延迟,然后才考虑预取.
除了软件预取外,ARMv8还提供了Non-temporal的Load/Store指令,可以提高Cache的利用率。对于一些数据,如果只是访问一次,无需占用Cache,可以使用这个指令进行访问,从而保护Cache中关键数据不被替换,比如memcpy大数据的场景下,使用该指令对于其关键业务而言,是有一定的收益的.
重用Cache中的数据是最基本的高效使用Cache方法。对于多层嵌套循环,可以通过交换两个嵌套的循环(loop interchange)、逆转循环迭代执行的顺序(loop reversal)、将两个循环体合并成一个循环体(loop fusion)、循环拆分(loop distribution)、循环分块(loop tiling)、loop unroll and jam等循环变换操作。选择适当的循环变换方式,既能保持程序的语义,又能改善程序性能。我们做这些循环变换的主要目的是为了实现寄存器、数据高速缓存以及其他存储层次使用方面的优化.
篇幅受限,本节仅讨论循环分块(loop tiling)如何改善程序性能,若对loop interchange感兴趣,请 点击 查阅。下面这个简单的循环:
for ( int i = 0 ; i < m; i++ ) { for ( int j = 0 ; j < n; j++ ) { x = x+a[i]+c* b[j]; } }
我们假设数组a、b都是超大数组,m、n相等且都很大,程序不会出现数组越界访问情况发生。那么如果b[j]在j层循环中跨度太大时,那么被下次i层循环重用时数据已经被清出高速缓存。即程序访问b[n-1]时,b[0]、b[1]已经被清出缓存,此时需要重新从主存中将数据加载至缓存中,程序性能会大幅下降.
我们如何通过降低Cache miss次数提升程序的性能呢?通过对循环做loop tiling可以符合我们的期望,即通过循环重排,使得数据分成一个一个tile,让每一个tile的数据都可以在Cache中被hint[4]。从内层循环开始tiling,假设tile的大小为t,t远小于m、n,t的取值使得b[t-1]被访问时b[0]依然在Cache中,将会大幅地减少Cache miss次数。假设n-1恰好被t整除,此时b数组的访问顺序如下所示:
i= 1 ; b[ 0 ]、b[ 1 ]、b[ 2 ]...b[t- 1 ] i = 2 ; b[ 0 ]、b[ 1 ]、b[ 2 ]...b[t- 1 ] ... i =n; b[ 0 ]、b[ 1 ]、b[ 2 ]...b[t- 1 ] ... ... ... i = 1 ; b[n-t]、b[n-t- 1 ]、b[n-t- 2 ]...b[n- 1 ] i = 2 ; b[n-t]、b[n-t- 1 ]、b[n-t- 2 ]...b[n- 1 ] ... i =n; b[n-t]、b[n-t- 1 ]、b[n-t- 2 ]...b[n- 1 ]
经过loop tiling后循环变换成:
for ( int j = 0 ; j < n; j+= t) { for ( int i = 0 ; i < m; i++ ) { for ( int jj = j; jj < min(j+t, n); jj++ ) { x = x+a[i]+c* b[jj]; } } }
假设每个Cache line能够容纳X个数组元素,loop tiling前a的Cache miss次数为m/X,b的Cache miss次数是m*n/X,总的Cache miss次数为m*(n+1)/x。loop tiling后a的Cache miss次数为(n/t)*(m/X),b的Cache miss次数为(t/X)*(n/t)=n/X,总的Cache miss次数为n*(m+t)/xt。此时,由于n与m相等,那么loop tiling后Cache miss大约可以降低t倍[4].
前文讨论了loop tiling在小用例上如何提升程序性能,总之针对不同的循环场景,选择合适的循环交换方法,既能保证程序语义正确, 又能获得改善程序性能的机会.
汝之蜜糖,彼之砒霜。针对不同的硬件,我们需要结合具体的硬件架构,利用性能分析工具,通过分析报告和程序,从系统层次和算法层次思考问题,往往会有意想不到的收获。本文简单地介绍了内存层次优化相关的几种方法,结合一些小例子深入浅出地讲解了一些内存层次优化相关的知识。纸上得来终觉浅,绝知此事要躬行,更多性能优化相关的知识需要我们从实践中慢慢摸索.
John L. Hennessy, David A. Patterson. 计算机体系结构:量化研究方法(第6版). 贾洪峰,译 。
Andrew W.Apple, with Jens Palsberg. Modern Compiler Implenentation in C 。
http://www.cs.cmu.edu/afs/cs/academic/class/15745-s19/www/lectures/L20-Global-Scheduling.pdf 。
https://zhuanlan.zhihu.com/p/292539074 。
。
点击关注,第一时间了解华为云新鲜技术~ 。
最后此篇关于编译器优化丨Cache优化的文章就讲到这里了,如果你想了解更多关于编译器优化丨Cache优化的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
比较代码: const char x = 'a'; std::cout > (0C310B0h) 00C3100B add esp,4 和 const i
您好,我正在使用 Matlab 优化求解器,但程序有问题。我收到此消息 fmincon 已停止,因为目标函数值小于目标函数限制的默认值,并且约束满足在约束容差的默认值范围内。我也收到以下消息。警告:矩
处理Visual Studio optimizations的问题为我节省了大量启动和使用它的时间 当我必须进行 J2EE 开发时,我很难回到 Eclipse。因此,我还想知道人们是否有任何提示或技巧可
情况如下:在我的 Excel 工作表中,有一列包含 1-name 形式的条目。考虑到数字也可以是两位数,我想删除这些数字。这本身不是问题,我让它工作了,只是性能太糟糕了。现在我的程序每个单元格输入大约
这样做有什么区别吗: $(".topHorzNavLink").click(function() { var theHoverContainer = $("#hoverContainer");
这个问题已经有答案了: 已关闭11 年前。 Possible Duplicate: What is the cost of '$(this)'? 我经常在一些开发人员代码中看到$(this)引用同一个
我刚刚结束了一个大型开发项目。我们的时间紧迫,因此很多优化被“推迟”。既然我们已经达到了最后期限,我们将回去尝试优化事情。 我的问题是:优化 jQuery 网站时您要寻找的最重要的东西是什么。或者,我
所以我一直在用 JavaScript 编写游戏(不是网络游戏,而是使用 JavaScript 恰好是脚本语言的游戏引擎)。不幸的是,游戏引擎的 JavaScript 引擎是 SpiderMonkey
这是我在正在构建的页面中使用的 SQL 查询。它目前运行大约 8 秒并返回 12000 条记录,这是正确的,但我想知道您是否可以就如何使其更快提出可能的建议? SELECT DISTINCT Adve
如何优化这个? SELECT e.attr_id, e.sku, a.value FROM product_attr AS e, product_attr_text AS a WHERE e.attr
我正在使用这样的结构来测试是否按下了所需的键: def eventFilter(self, tableView, event): if event.type() == QtCore.QEven
我正在使用 JavaScript 从给定的球员列表中计算出羽毛球 double 比赛的所有组合。每个玩家都与其他人组队。 EG。如果我有以下球员a、b、c、d。它们的组合可以是: a & b V c
我似乎无法弄清楚如何让这个 JS 工作。 scroll function 起作用但不能隐藏。还有没有办法用更少的代码行来做到这一点?我希望 .down-arrow 在 50px 之后 fade out
我的问题是关于用于生产的高级优化级联样式表 (CSS) 文件。 多么最新和最完整(准备在实时元素中使用)的 css 优化器/最小化器,它们不仅提供删除空格和换行符,还提供高级功能,如删除过多的属性、合
我读过这个: 浏览器检索在 中请求的所有资源开始呈现 之前的 HTML 部分.如果您将请求放在 中section 而不是,那么页面呈现和下载资源可以并行发生。您应该从 移动尽可能多的资源请求。
我正在处理一些现有的 C++ 代码,这些代码看起来写得不好,而且调用频率很高。我想知道我是否应该花时间更改它,或者编译器是否已经在优化问题。 我正在使用 Visual Studio 2008。 这是一
我正在尝试使用 OpenGL 渲染 3 个四边形(1 个背景图,2 个 Sprite )。我有以下代码: void GLRenderer::onDrawObjects(long p_dt) {
我确实有以下声明: isEnabled = false; if(foo(arg) && isEnabled) { .... } public boolean foo(arg) { some re
(一)深入浅出理解索引结构 实际上,您可以把索引理解为一种特殊的目录。微软的SQL SERVER提供了两种索引:聚集索引(clustered index,也称聚类索引、簇集索引)和非聚集索引(no
一、写在前面 css的优化方案,之前没有提及,所以接下来进行总结一下。 二、具体优化方案 2.1、加载性能 1、css压缩:将写好的css进行打包,可以减少很多的体积。 2、css单一样式:在需要下边
我是一名优秀的程序员,十分优秀!