【编程】程序的局部性原理对代码效率的影响

简介: 【编程】程序的局部性原理对代码效率的影响

70151bd7a0480be53af131d42644a025_20200416161142938.png

局部性原理分为了时间局部性和空间局部性。

时间局部性:一条指令和下次执行,一个数据的访问和下一次访问都集中在一个较短时期内。

空间局部性:当前指令和邻近几条指令、当前访问和邻近的几个数据都集中在一个较小区域内。

分支局部性:一条跳转指令的两次执行,很可能跳到相同的内存位置

访问速度快、空间大、使用方便(不需要程序猿过多构思数据结构)

例子:

89f9b4f8a8f6644de59e046ffc59f398_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoYWhvdA==,size_16,color_FFFFFF,t_70.png

这个整数数组的空间大小是1024x1024,int型每一个是4byte,也就说这一个数组整体会占4M的内存空间。但是物理内存只有4K。此时,

程序1:A【0】【0】~ A【1023】【0】==>A【1023】【1023】


程序2:A【0】【0】~ A【0】【1023】==>A【1023】【1023】


区别:实际上A【1】【0】和A【0】【0】从空间上来看,中间差了1024个数据也就说是4K的数据大小,但是A【1】【0】和A【1】【1】之间的距离只有一个数据也就说4byte。


那么对于程序2而言,在数据A【0】【x】占据了一个页。当他第一次访问时,数组的数据还在硬盘上时,会产生缺页异常,此时OS会把仅有的4K空间使用上,并把A【0】【x】数组放入内存空间 ,然后就可以对A【0】【x】数组进行正常访问了。根据循环,第二次访问A【0】【1】时,因为已经有了对应的页,就不会发生页异常。内循环执行完后,进入下一个内循环,此时访问A【1】【0】发生一次中断,然后接下来的1023次访问不会再发生中断。具备很好的空间局部性和时间局部性。也就意味着一共发生了1024次缺页中断


对于程序1而言,在数据A【0】【x】占据了一个页。当他第一次访问时,数组的数据还在硬盘上时,会产生缺页异常,此时OS会把仅有的4K空间使用上,并把A【0】【x】数组放入内存空间 ,然后就可以对A【0】【x】数组进行正常访问了。根据循环,第二次访问时,会访问A【1】【0】,此时会再次产生缺页异常,因为对应A【1】【x】的页仍然不在内存,在硬盘中,需要再次把4K的物理内存用到A【1】【x】数组上,此后导入A【1】【x】的页。同理,在一个内循环中,每一次都会跳4K空间去访问一个数据,每一次访问都会发生缺页异常。也就意味着一共发生了1024x1024次缺页中断

可以看出程序的不同写法对开销的影响是相当大的。


目录
相关文章
|
6月前
|
Linux 编译器 C++
C/C++性能优化:从根本上消除拷贝操作的浪费
C/C++性能优化:从根本上消除拷贝操作的浪费
842 1
|
5月前
|
存储 算法 Java
性能优化:Java垃圾回收机制深度解析 - 让你的应用飞起来!
Java垃圾回收自动管理内存,防止泄漏,提升性能。GC分为标记-清除、复制、标记-整理和分代收集等算法。JVM内存分为堆、方法区等区域。常见垃圾回收器有Serial、Parallel、CMS和G1。调优涉及选择合适的GC、调整内存大小和使用参数。了解和优化GC能提升应用性能。
145 3
|
4月前
|
缓存 自然语言处理 Java
浅析JAVA日志中的性能实践与原理解释问题之减少看得见的业务开销问题如何解决
浅析JAVA日志中的性能实践与原理解释问题之减少看得见的业务开销问题如何解决
|
4月前
|
存储 Java
浅析JAVA日志中的性能实践与原理解释问题之测试日志内容大小对系统性能的影响问题如何解决
浅析JAVA日志中的性能实践与原理解释问题之测试日志内容大小对系统性能的影响问题如何解决
109 0
|
4月前
|
开发者
编程问题之逻辑编程有什么缺点
编程问题之逻辑编程有什么缺点
|
4月前
|
设计模式 存储
代码优化设计问题之优化枚举的getByName方法以提高效率问题如何解决
代码优化设计问题之优化枚举的getByName方法以提高效率问题如何解决
|
5月前
|
算法 Linux 测试技术
Linux编程:测试-高效内存复制与随机数生成的性能
该文探讨了软件工程中的性能优化,重点关注内存复制和随机数生成。文章通过测试指出,`g_memmove`在内存复制中表现出显著优势,比简单for循环快约32倍。在随机数生成方面,`GRand`库在1000万次循环中的效率超过传统`rand()`。文中提供了测试代码和Makefile,建议在性能关键场景中使用`memcpy`、`g_memmove`以及高效的随机数生成库。
|
6月前
|
存储 人工智能 程序员
【重学C++】【内存】关于C++内存分区,你可能忽视的那些细节
【重学C++】【内存】关于C++内存分区,你可能忽视的那些细节
164 1
|
缓存 算法 Cloud Native
面试技巧:如何在有限时间内优化代码性能
面试技巧:如何在有限时间内优化代码性能
70 0
|
测试技术
代码为啥不能过度优化
代码为啥不能过度优化
74 0