[問題] 請教如何增加這段 code 之 cache hit ?

[EdisonX (卡卡獸)]

        for( i = 0 ; i < h ; ++i){
                for(j = 0 ; j < w ; ++j) {
                        dst[j][h - i] = src[i * w+ j];
                }
        }

上面這段 code 是用在影像處理的某點截取，
瓶頸效能出在這裡，但想半天想不到有什麼妙招可避開，
不知各位版友先進是否能指點一二？
另這種 code 開 thread 下去划算嗎？
小弟先行感激，謝謝各位。

--- 補充 ---

補充一下，我在「猜」瓶頸可能是使用了 bcb 裡速度慢的 Componment，

原始碼整理過後大致是這樣

        TImage * img;
        for( i = 0 ; i < h ; ++i){
                for(j = 0 ; j < w ; ++j) {
                        img->Canvas->Pixel[j][h-i] =  \
                                    (TColor) src[ i * w + j];
                }
        }

w * h = 640 * 480 , 裡面 array 不需考慮 o.v 問題 (實際上有考慮過了),

這段跑完超過 1 sec , 非常慢，我做了以下的嚐試

(a) loop 對換  (b) src 改用 pointer 表示 , 做 increment

然後想說換成 img->Canvas->Picture->Bitmap->ScanLine ，但換算卡卡的 Orz

還是這部份最後自己手動搞，再呼叫底層 API 去做是最直接有效的方式？

附上回覆，先謝謝各位耐心看完問題。

-- 已解 -- 


問題如 andyjy12 所言， img->Canvas->Pixel[j][h-i] ，主要死在這 member func.

太耗時，最後解法如下

(1) 做一個標準 bmp header + raw_data (可以存成一張 bmp 的記憶體體)

(2) 塞到 bcb-vcl-class :: TMemoryStream * stream

(3) 再用 img->Picture->Bitmap->LoadFromStream( stream );

效能差了 50 倍以上。

最後感謝各位的參與討論與意見，謝謝。

--

~ 這輩子與神手無緣

      我只好當神獸了 ~
                                 卡卡獸

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.213.184

推 stimim:內外迴圈互換？
這點我忘了說我試過了，抱歉。

→ EdisonX:換過了，效用不大, 差異在 1/700 以下
→ azureblaze:w、h夠大應該可以叫gpu幫你做
→ cutekid:h - i 跟 i - w 提到 j loop 一開始只做一次？
→ cutekid:           *
→ suhorng:有數據範圍嗎？
目前的 dst array 是開 1024 * 768 * 4 大小, 但大概只會考慮 640*480 而已

→ EdisonX:不好意思，現在有點忙，我晚點把問題補充清楚，先謝謝各位
推 LPH66:這是個順時針旋轉 90 度  我是想不太到有什麼改進空間就是
嗯, 若真如此, 可能只能先做前測動作, 單純資料搬移是不是會花那麼多時間...

→ scwg:不知道 matrix multiplication 的 block algorithm 有沒有用?
這個小弟本身之前研究了, 但助益似乎不大,
google "[C語言數值分析] 矩陣乘法 < cache block >" , 是我所知道的東西,
卡在 loop 怎麼換, 一定會有一方 cache hit 高,
事先先做 transpose 這方法還沒先試就是了。

推 singlovesong:矩陣乘法的話 不知道可不可以用lapack blas...?
→ EdisonX:matrix mult. 加速方法有很多沒錯,只是本文重點只有資料的
→ EdisonX:搬移. 應還用不到 library ???
推 singlovesong:想問一下為什麼640*480會需要跑一秒阿@@
→ EdisonX:卡死在 gui ??
→ firose:img->Canvas->Pixel 效率不好 至少先改掉吧
推 andyjy12:我猜轉型他做了一堆事,"[][]"可能也被overload?
→ EdisonX:先謝謝各位，這問題最後解掉了，原因真的是 componment
→ EdisonX:效率不好，晚些發註解，謝謝。
→ IdFormat:用微塊的方法解 就是一次做4x4這種大小
→ IdFormat:也就是寫成四層回圈 最內兩個是4x4(也可試8x8)
→ IdFormat:然後這樣微塊大小選的恰當 可以快個70趴以上吧...
※ 編輯: EdisonX         來自: 114.37.184.86        (05/01 14:39)