3 回答

TA貢獻1810條經驗 獲得超4個贊
第一種方法稍好一些,因為分配給的像元彼此相鄰放置。
第一種方法:
[ ][ ][ ][ ][ ] ....
^1st assignment
^2nd assignment
[ ][ ][ ][ ][ ] ....
^101st assignment
第二種方法:
[ ][ ][ ][ ][ ] ....
^1st assignment
^101st assignment
[ ][ ][ ][ ][ ] ....
^2nd assignment

TA貢獻1995條經驗 獲得超2個贊
在您的第二個代碼段中j,每次迭代中的更改都會產生一種空間局部性較低的模式。請記住,在幕后,數組引用會計算:
( ((y) * (row->width)) + (x) )
考慮一個簡化的L1緩存,該緩存具有足夠的空間來容納數組的50行。對于前50個迭代,您將為50個緩存未命中付出不可避免的代價,但是接下來會發生什么呢?對于從50到99的每次迭代,您仍將緩存未命中,并且必須從L2(和/或RAM等)獲取。然后,x更改為1并重新y開始,導致另一個高速緩存未命中,因為陣列的第一行已從高速緩存中逐出,依此類推。
第一個片段沒有這個問題。它以行優先的順序訪問數組,從而獲得更好的局部性-您僅需為每行最多一次(如果在循環開始時數組中的行不存在于高速緩存中)支付高速緩存未命中的費用。
話雖如此,這是一個非常依賴于體系結構的問題,因此您必須考慮細節(L1緩存大小,緩存行大小等)才能得出結論。您還應該同時衡量這兩種方式,并跟蹤硬件事件,以獲取具體的數據以得出結論。
添加回答
舉報