摘要:性能測(cè)試運(yùn)行環(huán)境瀏覽器對(duì)一個(gè)長(zhǎng)度為的二維數(shù)組子數(shù)組長(zhǎng)度也為進(jìn)行次空間局部性測(cè)試,時(shí)間毫秒取平均值,結(jié)果如下所用示例為上述兩個(gè)空間局部性示例按列排序按行排序從以上測(cè)試結(jié)果來(lái)看,二維數(shù)組按列順序訪問(wèn)比按行順序訪問(wèn)快了個(gè)數(shù)量級(jí)的速度。
更多文章 概念
一個(gè)編寫(xiě)良好的計(jì)算機(jī)程序常常具有良好的局部性,它們傾向于引用鄰近于其他最近引用過(guò)的數(shù)據(jù)項(xiàng)的數(shù)據(jù)項(xiàng),或者最近引用過(guò)的數(shù)據(jù)項(xiàng)本身,這種傾向性,被稱(chēng)為局部性原理。有良好局部性的程序比局部性差的程序運(yùn)行得更快。
局部性通常有兩種不同的形式:時(shí)間局部性
在一個(gè)具有良好時(shí)間局部性的程序中,被引用過(guò)一次的內(nèi)存位置很可能在不遠(yuǎn)的將來(lái)被多次引用。
空間局部性
在一個(gè)具有良好空間局部性的程序中,如果一個(gè)內(nèi)存位置被引用了一次,那么程序很可能在不遠(yuǎn)的將來(lái)引用附近的一個(gè)內(nèi)存位置。
時(shí)間局部性示例function sum(arry) { let i, sum = 0 let len = arry.length for (i = 0; i < len; i++) { sum += arry[i] } return sum }
在這個(gè)例子中,變量sum在每次循環(huán)迭代中被引用一次,因此,對(duì)于sum來(lái)說(shuō),具有良好的時(shí)間局部性
空間局部性示例具有良好空間局部性的程序
// 二維數(shù)組 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 }
空間局部性差的程序
// 二維數(shù)組 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 }
再回頭看一下時(shí)間局部性的示例,像示例中按順序訪問(wèn)一個(gè)數(shù)組每個(gè)元素的函數(shù),具有步長(zhǎng)為1的引用模式。
如果在數(shù)組中,每隔k個(gè)元素進(jìn)行訪問(wèn),就稱(chēng)為步長(zhǎng)為k的引用模式。
一般而言,隨著步長(zhǎng)的增加,空間局部性下降。
這兩個(gè)例子有什么區(qū)別?區(qū)別在于第一個(gè)示例是按照列順序來(lái)掃描數(shù)組,第二個(gè)示例是按照行順序來(lái)掃描數(shù)組。
數(shù)組在內(nèi)存中是按照行順序來(lái)存放的,結(jié)果就是按行順序來(lái)掃描數(shù)組的示例得到了步長(zhǎng)為rows的引用模式;
而對(duì)于按列順序來(lái)掃描數(shù)組的示例來(lái)說(shuō),其結(jié)果是得到一個(gè)很好的步長(zhǎng)為1的引用模式,具有良好的空間局部性。
cpu: i5-7400
瀏覽器: chrome 70.0.3538.110
對(duì)一個(gè)長(zhǎng)度為9000的二維數(shù)組(子數(shù)組長(zhǎng)度也為9000)進(jìn)行10次空間局部性測(cè)試,時(shí)間(毫秒)取平均值,結(jié)果如下:
所用示例為上述兩個(gè)空間局部性示例
按列排序 | 按行排序 |
---|---|
124 | 2316 |
從以上測(cè)試結(jié)果來(lái)看,二維數(shù)組按列順序訪問(wèn)比按行順序訪問(wèn)快了1個(gè)數(shù)量級(jí)的速度。
總結(jié)重復(fù)引用相同變量的程序具有良好的時(shí)間局部性
對(duì)于具有步長(zhǎng)為k的引用模式的程序,步長(zhǎng)越小,在內(nèi)存中以大步長(zhǎng)跳來(lái)跳去的程序空間局部性會(huì)很差
測(cè)試代碼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 }參考資料
深入理解計(jì)算機(jī)系統(tǒng)
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/101138.html
摘要:基于局部性原理,計(jì)算機(jī)處理器在設(shè)計(jì)時(shí)做了各種優(yōu)化,比如現(xiàn)代的多級(jí)分支預(yù)測(cè)有良好局部性的程序比局部性差的程序運(yùn)行得更快。目前計(jì)算機(jī)設(shè)計(jì)中,都是以塊頁(yè)為單位管理調(diào)度存儲(chǔ),其實(shí)就是在利用空間局部性來(lái)優(yōu)化性能。 學(xué)過(guò)計(jì)算機(jī)底層原理、了解過(guò)很多架構(gòu)設(shè)計(jì)或者是做過(guò)優(yōu)化的同學(xué),應(yīng)該很熟悉局部性原理。即便是非計(jì)算機(jī)行業(yè)的人,在做各種調(diào)優(yōu)、提效時(shí)也不得不考慮到局部性,只不過(guò)他們不常用局部性一詞。如果...
摘要:這樣就改進(jìn)了代碼的性能,看代碼將保存在局部變量中所以啊,我們?cè)陂_(kāi)發(fā)中,如果在函數(shù)中會(huì)經(jīng)常用到全局變量,把它保存在局部變量中避免使用語(yǔ)句用語(yǔ)句延長(zhǎng)了作用域,查找變量同樣費(fèi)時(shí)間,這個(gè)我們一般不會(huì)用到,所以不展開(kāi)了。 本來(lái)在那片編寫(xiě)可維護(hù)性代碼文章后就要總結(jié)這篇代碼性能文章的,耽擱了幾天,本來(lái)也是決定每天都要更新一篇文章的,因?yàn)橐郧扒废绿鄸|西沒(méi)總結(jié),學(xué)過(guò)的東西沒(méi)去總結(jié)真的很快就忘記了...
摘要:在上一篇中我們談到過(guò)程序的執(zhí)行時(shí)間指令數(shù)要提升計(jì)算機(jī)的性能,可以從上面這三方面著手。在摩爾定律和并行計(jì)算之外,在整個(gè)計(jì)算機(jī)組成層面,還有這樣幾個(gè)原則性的性能提升方法。 showImg(https://ask.qcloudimg.com/http-save/1752328/uskvyzme4j.png); 在上一篇中,我們談到過(guò) 程序的CPU執(zhí)行時(shí)間 = 指令數(shù)×CPI×Clock Cy...
摘要:通過(guò)單元測(cè)試,開(kāi)發(fā)者可以為構(gòu)成程序的每一個(gè)元素例如,獨(dú)立的函數(shù),方法,類(lèi)以及模塊編寫(xiě)一系列獨(dú)立的測(cè)試用例。在每個(gè)測(cè)試中,斷言可以用來(lái)對(duì)不同的條件進(jìn)行檢查。當(dāng)退出調(diào)試器時(shí),調(diào)試器會(huì)自動(dòng)恢復(fù)程序的執(zhí)行。 Python已經(jīng)演化出了一個(gè)廣泛的生態(tài)系統(tǒng),該生態(tài)系統(tǒng)能夠讓Python程序員的生活變得更加簡(jiǎn)單,減少他們重復(fù)造輪的工作。同樣的理念也適用于工具開(kāi)發(fā)者的工作,即便他們開(kāi)發(fā)出的工具并沒(méi)有出現(xiàn)...
摘要:注意,禁止指令重排序在之后才被修復(fù)使用局部變量?jī)?yōu)化性能重新查看中雙重檢查鎖定代碼。幫助文檔雙重檢查鎖定與延遲初始化有關(guān)雙重檢查鎖定失效的說(shuō)明 雙重檢查鎖定(Double check locked)模式經(jīng)常會(huì)出現(xiàn)在一些框架源碼中,目的是為了延遲初始化變量。這個(gè)模式還可以用來(lái)創(chuàng)建單例。下面來(lái)看一個(gè) Spring 中雙重檢查鎖定的例子。 showImg(https://segmentfaul...
閱讀 2484·2023-04-25 19:24
閱讀 1700·2021-11-11 16:54
閱讀 2833·2021-11-08 13:19
閱讀 3547·2021-10-25 09:45
閱讀 2552·2021-09-13 10:24
閱讀 3276·2021-09-07 10:15
閱讀 4014·2021-09-07 10:14
閱讀 2950·2019-08-30 15:56