C中實(shí)現(xiàn)矩陣乘法的一種高效的方法
如何計(jì)算矩陣乘法，這個(gè)大家都知道。通常情況下，我們都是用以下代碼實(shí)現(xiàn)的：
for(i=0;i<n;++i)
for(j=0;j<n;++j){
sum=0;
for(k=0;k<n;++k)
sum+=A[i][k]*B[k][j];
C[i][j]+=sum;
}
但是考慮了高速緩存的問(wèn)題后，其實(shí)有一種更好的實(shí)現(xiàn)方式：
for(i=0;i<n;++i)
for(k=0;k<n;++k){
r=A[i][k];
for(j=0;j<n;++j)
C[i][j]+=r*B[k][j];
}
細(xì)看一番就會(huì)發(fā)現(xiàn)這兩種實(shí)現(xiàn)語(yǔ)義是等價(jià)的，但是后者的實(shí)際運(yùn)行效率卻比前者高。
那為什么會(huì)如此呢？
那是因?yàn)镃PU讀數(shù)據(jù)時(shí)，并不是直接訪問(wèn)內(nèi)存，而是先查看緩存中是否有數(shù)據(jù)，有的話直接從緩存讀取。而從緩存讀取數(shù)據(jù)比從內(nèi)存讀數(shù)據(jù)快很多。
當(dāng)數(shù)據(jù)不在緩存中時(shí)，CPU會(huì)將包含數(shù)據(jù)在內(nèi)的一個(gè)數(shù)據(jù)塊讀到緩存，如果程序具有良好空間局部性，那么第一次cache miss后，之后的幾次數(shù)據(jù)訪問(wèn)就可以直接在緩存中完成。除了空間局部性（程序傾向于引用與當(dāng)前數(shù)據(jù)鄰近的數(shù)據(jù)）之外，還有時(shí)間局部性（程序傾向于引用最近被引用過(guò)的數(shù)據(jù)）。
回到矩陣乘法。（我們只考慮內(nèi)循環(huán)）
前者對(duì)矩陣A，有良好的空間局部性，假設(shè)一次能緩存四個(gè)元素，則每次迭代對(duì)于A只有0.25次miss，但是對(duì)于B，則不然，因此B是按列訪問(wèn)的，每次訪問(wèn)都會(huì)miss，因此每次迭代總的miss數(shù)是1.25。
后者對(duì)于矩陣C和矩陣B都有良好的局部性，每次迭代都只有0.25詞miss，因此總的miss數(shù)是0.5。后者每次迭代多了一次存儲(chǔ)（對(duì)C[i][j]寫(xiě)入），但是即便如此，后者的運(yùn)行效率也比前者高。
總而言之，要想程序跑得快，就要在程序中多利用局部性，讓緩存hold住你的數(shù)據(jù)，減少訪存次數(shù)。要知道CPU可以在3個(gè)時(shí)鐘周期內(nèi)訪問(wèn)到L1 cache，10個(gè)時(shí)鐘周期左右的時(shí)間訪問(wèn)到L2 cache。訪問(wèn)內(nèi)存卻要上百個(gè)時(shí)鐘周期，孰快孰慢，很清楚了吧？
相關(guān)文章
C語(yǔ)言實(shí)現(xiàn)將彩色bmp圖像轉(zhuǎn)化為灰圖、灰度圖像反色
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)將彩色bmp圖像轉(zhuǎn)化為灰圖、灰度圖像反色，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-10-10
Qt學(xué)習(xí)之QListWidget控件的使用教程詳解
這篇文章主要為大家詳細(xì)介紹了Qt中QListWidget控件的使用教程，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)Qt有一定的幫助，需要的可以參考一下2022-12-12
C語(yǔ)言實(shí)現(xiàn)倉(cāng)庫(kù)物資管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)倉(cāng)庫(kù)物資管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-12-12
C語(yǔ)言通過(guò)三種方法實(shí)現(xiàn)屬于你的通訊錄
本文將實(shí)現(xiàn)一個(gè)通訊錄，來(lái)實(shí)現(xiàn)人員的增刪插改功能。文中通過(guò)三種形式來(lái)實(shí)現(xiàn)用戶的增刪插改，其實(shí)也就是一點(diǎn)點(diǎn)的優(yōu)化版本，從靜態(tài)的實(shí)現(xiàn)，到動(dòng)態(tài)的實(shí)現(xiàn)，最后以文件的形式來(lái)完成，請(qǐng)大家和我一起往下看吧2022-11-11
Qt實(shí)現(xiàn)數(shù)據(jù)進(jìn)行加密、解密的步驟
本文主要介紹了Qt實(shí)現(xiàn)數(shù)據(jù)進(jìn)行加密、解密的步驟,包含QCryptographicHash和Qt-AES兩種庫(kù)的實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下2024-03-03
無(wú)論是靜態(tài)鏈表還是動(dòng)態(tài)鏈表，有時(shí)在解決具體問(wèn)題時(shí)，需要我們對(duì)其結(jié)構(gòu)進(jìn)行稍微地調(diào)整。比如，可以把鏈表的兩頭連接，使其成為了一個(gè)環(huán)狀鏈表，通常稱為循環(huán)鏈表2022-05-05
std::addressof的作用是獲取一個(gè)對(duì)象的實(shí)際地址，即使這個(gè)對(duì)象的&操作符已被重載，本文詳細(xì)的介紹了源碼解析，感興趣的可以了解一下2021-06-06
這篇文章主要介紹了C++抽象基類講解，象基類abstract base class簡(jiǎn)稱ABC，C++實(shí)現(xiàn)繼承的時(shí)候，需要保證派生類和基類之間是一種is-a的關(guān)系。在大多數(shù)時(shí)刻，這樣的關(guān)系是沒(méi)有問(wèn)題的，然而在一些特殊的情況可能會(huì)遇到問(wèn)題，下面來(lái)看看文章的具體介紹吧2022-01-01
C語(yǔ)言中strcmp的實(shí)現(xiàn)原型
這篇文章主要介紹了C語(yǔ)言中strcmp的實(shí)現(xiàn)原型的相關(guān)資料,這里提供實(shí)例幫助大家理解這部分內(nèi)容，希望能幫助到大家，需要的朋友可以參考下2017-08-08
C語(yǔ)言模擬實(shí)現(xiàn)memmove的示例代碼
memmove函數(shù)用于拷貝字節(jié)，如果目標(biāo)區(qū)域和源區(qū)域有重疊的話，memmove能夠保證源串在被覆蓋之前將重疊區(qū)域的字節(jié)拷貝到目標(biāo)區(qū)域中，但復(fù)制后源內(nèi)容會(huì)被更改。本文主要介紹了C語(yǔ)言模擬實(shí)現(xiàn)memmove的示例代碼，需要的可以參考一下2022-12-12