優化項目的反轉

Question

我有一個可以反轉數組中元素的循環。我已簡化並將問題簡化爲以下內容：

for (int x=0;x<w/2;++x) { 
    int il =  x; 
    int ir = w-1-x; 
    type_copy l = data[il]; 
    type_copy r = data[ir]; 
    data[il] = r; 
    data[ir] = l; 
} 

此代碼反轉元素，但速度較慢。首先，它不能被自動矢量化，因爲數組訪問是不連續的。另一方面，右側的訪問是從理想的高速緩存遍歷向後的。最後，可能會有一些拖延，因爲在提交最後一個循環的數據之前，下一個循環的負載不可能發生，因爲編譯器可能無法說明自我別名指針本身沒有命中。

在我的情況，sizeof(type_copy)要麼4*sizeof(uint8_t) = 4否則4*sizeof(float) = 4*4 = 16。因此請注意，字節級的反轉是不可接受的。

我的問題是：這段代碼如何優化，如果可以呢？

Answer 1

假設你的數據類型，如：

struct float_data 
{ 
    float f1; 
    float f2; 
    float f3; 
    float f4; 
}; 

struct uint8_t_data 
{ 
    uint8_t f1; 
    uint8_t f2; 
    uint8_t f3; 
    uint8_t f4; 
}; 

你可以嘗試上證所內部函數。對於uint8_t_data有相當不錯的速度提高：

typedef uint8_t_data type_copy; 

for (int x = 0; x<w/2; x += 4) 
{ 
    int il = x; 
    int ir = w - 1 - x - 3; 

    __m128i dl = _mm_loadu_si128((const __m128i*)&data[il]); 
    __m128i dr = _mm_loadu_si128((const __m128i*)&data[ir]); 
    _mm_storeu_si128((__m128i*)&data[ir], _mm_shuffle_epi32(dl, _MM_SHUFFLE(0, 1, 2, 3))); 
    _mm_storeu_si128((__m128i*)&data[il], _mm_shuffle_epi32(dr, _MM_SHUFFLE(0, 1, 2, 3))); 
} 

輸出：

g++ -O3 non vectorized: 16ms 
g++ -O3 vectorized: 5ms 

然而，對於float_data沒有太大的提高速度：

typedef float_data type_copy; 

for (int x = 0; x<w/2; x+=2) { 
    int il = x; 
    int ir = w - 1 - x - 1; 

    __m256 dl = _mm256_loadu_ps((const float*)&data[il]); 
    __m256 dr = _mm256_loadu_ps((const float*)&data[ir]); 

    _mm256_storeu_ps((float*)&data[ir], _mm256_permute2f128_ps(dl, dl, 1)); 
    _mm256_storeu_ps((float*)&data[il], _mm256_permute2f128_ps(dr, dr, 1)); 

} 

輸出：

g++ -O3 -mavx non vectorized: 27ms 
g++ -O3 -msse4.2 non vectorized: 25ms 
g++ -O3 -mavx vectorized: 24ms 

Answer 2

希望最好是：

for (int x=0;x<w/2;++x) { 
    std::swap(data[x], data[w-i-x]);  
} 

如果你不喜歡使用標準模板庫功能，減少作業和局部變量的數目如下：

• 刪除3當地變量與您的實施相比
• 刪除了3個額外的分配操作

for (int x=0;x<w/2;++x) { type_copy l = data[x]; data[x] = data[w-1-x]; data[w-l-x] = l; }

Answer 3

你的代碼不能並行很好的原因是因爲有數據之間的相關性：

for (int x=0;x<w/2;++x) { 
    int il =  x; 
    int ir = w-1-x; 
    type_copy l = data[il]; 
    type_copy r = data[ir]; 
    data[il] = r; 
    data[ir] = l; 
} 

有3個操作位置：compute l/r indexes，read from array，write to array。它們中的每一個都依賴於先前操作的結果，因此它們不能並行完成。注意我在同一類別下向左或向右分組操作。

要做的第一件事就是嘗試制動依賴。

而不是在同一週期閱讀廣告寫入嘗試讀取數據的迭代N和寫入數據迭代N - 1;這可以在同一個循環中完成。

int il = 0; 
int ir = w-1; 
type_copy l = data[il]; 
type_copy r = data[ir]; 

for (int x=0;x<w/2;++x) { 
    data[il] = r; 
    data[ir] = l; 
    il =  x; 
    ir = w-1-x; 
    l = data[il]; 
    r = data[ir];  
} 

甚至更​​好，預先計算用於讀取以及指標：

int il_0 = 0; 
int ir_0 = w-1; 
int il_1 = 1; 
int ir_1 = w-2; 
type_copy l = data[il_0]; 
type_copy r = data[ir_0]; 

for (int x=0;x<w/2;++x) { 
    data[il_0] = r; 
    data[ir_0] = l;  
    l = data[il_1]; 
    r = data[ir_1]; 
    il_0 = il_1; 
    ir_0 = ir_1;  
    il_1 = il_1++; 
    ir_1 = ir_1--; 
} 

的另一件事值得嘗試的是複製一個以上的數據樣本;例如在同一個週期中讀取/寫入2,4，...等樣本。這應該會改善您的代碼的並行性。

Answer 4

該代碼當然可以優化，但這樣做可能取決於平臺。例如，AMD64繼承了x86 SSE的一些有用指令，包括PSHUFD或VPPERM，它們可以在矢量內任意重新排序單詞，MASKMOVDQU可以組合部分寫入。