程序性能优化-局部性原理

xiaokai 发布于2019-08-23 14:47 / 973人阅读

摘要：性能测试运行环境浏览器对一个长度为的二维数组子数组长度也为进行次空间局部性测试，时间毫秒取平均值，结果如下所用示例为上述两个空间局部性示例按列排序按行排序从以上测试结果来看，二维数组按列顺序访问比按行顺序访问快了个数量级的速度。

更多文章 概念

一个编写良好的计算机程序常常具有良好的局部性，它们倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身，这种倾向性，被称为局部性原理。有良好局部性的程序比局部性差的程序运行得更快。

局部性通常有两种不同的形式：

时间局部性

在一个具有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来被多次引用。

空间局部性

在一个具有良好空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。

时间局部性示例

function sum(arry) {
    let i, sum = 0
    let len = arry.length

    for (i = 0; i < len; i++) {
        sum += arry[i]
    }

    return sum
}

在这个例子中，变量sum在每次循环迭代中被引用一次，因此，对于sum来说，具有良好的时间局部性

空间局部性示例

具有良好空间局部性的程序

// 二维数组 
function sum1(arry, rows, cols) {
    let i, j, sum = 0

    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            sum += arry[i][j]
        }
    }
    return sum
}

空间局部性差的程序

// 二维数组 
function sum2(arry, rows, cols) {
    let i, j, sum = 0

    for (j = 0; j < cols; j++) {
        for (i = 0; i < rows; i++) {
            sum += arry[i][j]
        }
    }
    return sum
}

再回头看一下时间局部性的示例，像示例中按顺序访问一个数组每个元素的函数，具有步长为1的引用模式。

如果在数组中，每隔k个元素进行访问，就称为步长为k的引用模式。

一般而言，随着步长的增加，空间局部性下降。

这两个例子有什么区别？区别在于第一个示例是按照列顺序来扫描数组，第二个示例是按照行顺序来扫描数组。

数组在内存中是按照行顺序来存放的，结果就是按行顺序来扫描数组的示例得到了步长为rows的引用模式；
而对于按列顺序来扫描数组的示例来说，其结果是得到一个很好的步长为1的引用模式，具有良好的空间局部性。

性能测试 运行环境

cpu: i5-7400

浏览器: chrome 70.0.3538.110

对一个长度为9000的二维数组（子数组长度也为9000）进行10次空间局部性测试，时间（毫秒）取平均值，结果如下：

所用示例为上述两个空间局部性示例

按列排序	按行排序
124	2316

从以上测试结果来看，二维数组按列顺序访问比按行顺序访问快了1个数量级的速度。

总结

重复引用相同变量的程序具有良好的时间局部性

对于具有步长为k的引用模式的程序，步长越小，在内存中以大步长跳来跳去的程序空间局部性会很差

测试代码

const arry = []
let [num, n, cols, rows] = [9000, 9000, 9000, 9000]
let temp = []

while (num) {
    while (n) {
        temp.push(n)
        n--
    }
    arry.push(temp)
    n = 9000
    temp = []
    num--
}

let last, now, val

last = new Date()
val = sum1(arry, rows, cols)
now = new Date()
console.log(now - last)
console.log(val)

last = new Date()
val = sum2(arry, rows, cols)
now = new Date()
console.log(now - last)
console.log(val)

function sum1(arry, rows, cols) {
    let i, j, sum = 0

    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            sum += arry[i][j]
        }
    }
    return sum
}

function sum2(arry, rows, cols) {
    let i, j, sum = 0

    for (j = 0; j < cols; j++) {
        for (i = 0; i < rows; i++) {
            sum += arry[i][j]
        }
    }
    return sum
}

参考资料

深入理解计算机系统

混合云专线服务性能优化优化系统性能网站性能优化页面性能优化

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/101138.html

局部性原理——各类优化的基石

摘要：基于局部性原理，计算机处理器在设计时做了各种优化，比如现代的多级分支预测有良好局部性的程序比局部性差的程序运行得更快。目前计算机设计中，都是以块页为单位管理调度存储，其实就是在利用空间局部性来优化性能。　　学过计算机底层原理、了解过很多架构设计或者是做过优化的同学，应该很熟悉局部性原理。即便是非计算机行业的人，在做各种调优、提效时也不得不考虑到局部性，只不过他们不常用局部性一词。如果...

MadPecker 2019-08-19 10:23 评论0 收藏0
[ JS 进阶 ] 如何改进代码性能 (3)

摘要：这样就改进了代码的性能，看代码将保存在局部变量中所以啊，我们在开发中，如果在函数中会经常用到全局变量，把它保存在局部变量中避免使用语句用语句延长了作用域，查找变量同样费时间，这个我们一般不会用到，所以不展开了。本来在那片编写可维护性代码文章后就要总结这篇代码性能文章的，耽搁了几天，本来也是决定每天都要更新一篇文章的，因为以前欠下太多东西没总结，学过的东西没去总结真的很快就忘记了...

young.li 2019-08-21 10:27 评论0 收藏0
重学计算机组成原理（三）- 进击,更强的性能!

摘要：在上一篇中我们谈到过程序的执行时间指令数要提升计算机的性能，可以从上面这三方面着手。在摩尔定律和并行计算之外，在整个计算机组成层面，还有这样几个原则性的性能提升方法。 showImg(https://ask.qcloudimg.com/http-save/1752328/uskvyzme4j.png); 在上一篇中,我们谈到过程序的CPU执行时间 = 指令数×CPI×Clock Cy...

Tecode 2019-08-19 10:27 评论0 收藏0
Python 开发工具集：关于文档、测试、调试、程序的优化和分析

摘要：通过单元测试，开发者可以为构成程序的每一个元素例如，独立的函数，方法，类以及模块编写一系列独立的测试用例。在每个测试中，断言可以用来对不同的条件进行检查。当退出调试器时，调试器会自动恢复程序的执行。 Python已经演化出了一个广泛的生态系统，该生态系统能够让Python程序员的生活变得更加简单，减少他们重复造轮的工作。同样的理念也适用于工具开发者的工作，即便他们开发出的工具并没有出现...

shenhualong 2019-05-29 16:18 评论0 收藏0
为什么双重检查锁模式需要 volatile ？

摘要：注意，禁止指令重排序在之后才被修复使用局部变量优化性能重新查看中双重检查锁定代码。帮助文档双重检查锁定与延迟初始化有关双重检查锁定失效的说明双重检查锁定（Double check locked）模式经常会出现在一些框架源码中，目的是为了延迟初始化变量。这个模式还可以用来创建单例。下面来看一个 Spring 中双重检查锁定的例子。 showImg(https://segmentfaul...

geekzhou 2019-08-19 10:30 评论0 收藏0