PTT數位生活區 / C_and_CPP (C/C++)

[問題] 不連續的陣列讀取

看板C_and_CPP (C/C++)作者 (阿通)時間13年前 (2013/04/25 18:54), 編輯推噓4(4推 0噓 8→)
留言12則, 9人參與, 最新討論串1/1
開發平台(Platform): (Ex: VC++, GCC, Linux, ...) VS_2010 C++ 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 無 問題(Question)： 我宣告了一個24*24*256的3維陣列供查表用， 但在查表時，並非連續的讀取陣列，例如說： int P[24][24][256]; int C[24][24]; for(int j = 23; j>=0; --j) { for(int i = 23; i>=0; --i) { sum += P[i][j][C[i][j]]; } } 其中C陣列的值0~255 這樣的每次重新計算位址取值，速度好像會被拖住， 所以想請教版上各位，有沒有辦法改善這個問題，讓速度提升? 在此麻煩各位了，謝謝。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.118.7.206
→
04/25 18:56, , 1F
不能再快了，船長
04/25 18:56, 1F
→
04/25 23:20, , 2F
你只需要 P[ 576 ][ 256 ] 跟 C[ 576 ]
04/25 23:20, 2F
→
04/25 23:21, , 3F
i, j 的位置互換, 只需要兩個指標跑個 576 次就好
04/25 23:21, 3F
→
04/25 23:34, , 4F
你確定這裡是你的速度瓶頸嗎？XD
04/25 23:34, 4F
→
04/26 00:27, , 5F
累加差不多是電腦做最快的事 連續記憶體定址大概排第二
04/26 00:27, 5F
推
04/26 01:00, , 6F
船長 你需要多開幾艘船 可參考： http://ppt.cc/~fPH
04/26 01:00, 6F
→
04/26 01:02, , 7F
2樓說的照理來說只要有開最佳化編譯器應該已經做了
04/26 01:02, 7F
→
04/26 10:26, , 8F
換CPU跟記憶體最快, 去敗家吧~
04/26 10:26, 8F
推
04/26 10:51, , 9F
這邊最大的瓶頸大概是cache miss
04/26 10:51, 9F
推
04/26 12:57, , 10F
這例 row/column 定址方式互換就可提升 cache hit.
04/26 12:57, 10F
因為這裡運算量是(576次查表相加)*63,936次， 用計算時間的方式來看最花運算的地方是這邊。 ※ 編輯: b9707114 來自: 140.118.7.206 (04/26 15:26)
推
04/26 15:50, , 11F
建議...另外建一個 576的陣列, 把這回圈會用到的資料先
04/26 15:50, 11F
→
04/26 15:51, , 12F
算好, 預期這樣應該可以快很多
04/26 15:51, 12F
其實P陣列就是已建好的資料供查表，因為C矩陣內的值會一直變化，應該沒辦法先算好。 ※ 編輯: b9707114 來自: 140.118.7.206 (04/26 16:05) EdusonX大，可以提供具體的改法嗎? 謝謝。 ※ 編輯: b9707114 來自: 140.118.7.206 (04/26 16:24)
‣ 更多 b9707114 的文章
文章代碼(AID): #1HUGjXzN (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 b9707114 的文章
文章代碼(AID): #1HUGjXzN (C_and_CPP)