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