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

xiaokai 發布于2019-08-23 14:47 / 1147人閱讀

摘要：性能測試運行環境瀏覽器對一個長度為的二維數組子數組長度也為進行次空間局部性測試，時間毫秒取平均值，結果如下所用示例為上述兩個空間局部性示例按列排序按行排序從以上測試結果來看，二維數組按列順序訪問比按行順序訪問快了個數量級的速度。

更多文章 概念

一個編寫良好的計算機程序常常具有良好的局部性，它們傾向于引用鄰近于其他最近引用過的數據項的數據項，或者最近引用過的數據項本身，這種傾向性，被稱為局部性原理。有良好局部性的程序比局部性差的程序運行得更快。

局部性通常有兩種不同的形式：

時間局部性

在一個具有良好時間局部性的程序中，被引用過一次的內存位置很可能在不遠的將來被多次引用。

空間局部性

在一個具有良好空間局部性的程序中，如果一個內存位置被引用了一次，那么程序很可能在不遠的將來引用附近的一個內存位置。

時間局部性示例

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
}

參考資料

深入理解計算機系統

云服務器 GPU云服務器性能優化優化系統性能網站性能優化頁面性能優化

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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