最佳化 C++/程式碼最佳化/更快的操作

一些基本操作，即使在概念上與其他操作一樣簡單，對處理器來說也要快得多。聰明的程式設計師可以為任務選擇更快的指令。

不過，每個最佳化編譯器都能夠為目標處理器選擇最快的指令，因此一些技術在某些編譯器中毫無用處。

此外，一些技術甚至可能會在某些處理器上降低效能。

在本節中，介紹了一些可能在某些編譯器/處理器組合上提高效能的技術。

結構體欄位順序

以這樣的方式排列類和結構體的成員變數：最常用的變數位於前 128 個位元組中，然後按從最長的物件到最短的物件排序。

如果在以下結構體中，msg 成員僅用於錯誤訊息，而其他成員用於計算

struct {
    char msg[400];
    double d;
    int i;
};

可以透過用以下結構體替換結構體來加快計算速度

struct {
    double d;
    int i;
    char msg[400];
};

在某些處理器上，如果成員距離結構體開頭的距離小於 128 個位元組，則成員的定址效率更高。

在第一個示例中，要使用指向結構體開頭的指標來定址 d 和 i 欄位，需要至少 400 個位元組的偏移量。

相反，在第二個示例中，包含以不同順序排列的相同欄位，定址 d 和 i 的偏移量只有幾個位元組，這允許使用更緊湊的指令。

現在，假設您編寫了以下結構體

struct {
    bool b;
    double d;
    short s;
    int i;
};

由於欄位對齊，它通常佔用 1 (bool) + 7 (填充) + 8 (double) + 2 (short) + 2 (填充) + 4 (int) = 24 個位元組。

以下結構體是透過按從最長到最短的順序對欄位進行排序，從上一個結構體中獲得的

struct {
    double d;
    int i;
    short s;
    bool b;
};

它通常佔用 8 (double) + 4 (int) + 2 (short) + 1 (bool) + 1 (填充) = 16 個位元組。排序最小化了對齊要求導致的填充（或空洞），因此生成更緊湊的結構體。

浮點數到整數轉換

利用非標準例程將浮點數四捨五入為整數。

C++ 語言沒有提供將浮點數四捨五入為整數的原始操作。將浮點數 x 轉換為最接近的整數 n 的最簡單技術是以下語句

n = int(floor(x + 0.5f));

使用這種技術，如果 x 恰好位於兩個整數之間，則 n 將是較大的整數（例如，0.5 生成 1，1.5 生成 2，-0.5 生成 0，-1.5 生成 -1）。

不幸的是，在某些處理器（特別是 Pentium 系列）上，這種表示式在非常慢的機器程式碼中編譯。有些處理器有專門的指令來對數字進行四捨五入。

特別是，Pentium 系列有 fistp 指令，在以下程式碼中使用時，會生成更快但並不完全等效的程式碼

#if defined(__unix__) || defined(__GNUC__)
    // For 32-bit Linux, with Gnu/AT&T syntax
    __asm ("fldl %1 \n fistpl %0 " : "=m"(n) : "m"(x) : "memory" );
#else
    // For 32-bit Windows, with Intel/MASM syntax
    __asm fld qword ptr x;
    __asm fistp dword ptr n;
#endif

上面的程式碼將 x 四捨五入到最接近的整數，但如果 x 恰好位於兩個整數之間，則 n 將是最接近的偶數整數（例如，0.5 生成 0，1.5 生成 2，-0.5 生成 0，-1.5 生成 -2）。

如果這個結果是可以容忍的甚至想要的，並且您被允許使用嵌入式彙編，那麼請使用這段程式碼。顯然，它不能移植到其他處理器系列。

整數的位操作

利用您對其表示形式的瞭解來對整數的位進行操作。

您可以在這裡找到這類技巧的集合：http://www.graphics.stanford.edu/~seander/bithacks.html。其中一些技巧實際上已經被一些編譯器使用，另一些技巧用於解決罕見的問題，另一些技巧僅在某些平臺上才有用。

陣列單元大小

確保陣列或 vector 的非大型單元的大小（由 sizeof 運算子得出）是 2 的冪，而陣列或 vector 的大型單元的大小不是 2 的冪。

直接訪問陣列單元是透過將索引乘以單元大小（即一個常數）來執行的。如果此乘法的第二個因子是 2 的冪，則此操作會快得多，因為它被執行為位移。類似地，在多維陣列中，除第一個以外的所有大小都應該是 2 的冪。

這種大小是透過在結構體中新增未使用的欄位，並在陣列中新增未使用的單元來獲得的。例如，如果每個單元都是 float 物件的 3 元組，則只需在每個單元中新增第四個虛擬 float 物件即可。

但是，當訪問多維陣列的單元時，如果最後一維是足夠大的 2 的冪，您可能會遇到資料快取競爭現象（也稱為資料快取衝突），這可能會使計算速度降低 10 倍或更多。這種現象僅在陣列單元超過一定大小（取決於資料快取）時才會發生，但大約是 1 到 8 KB。因此，如果演算法必須處理一個單元大小為 2 的冪，並且大小大於或等於 1024 個位元組的陣列，首先，您應該檢測資料快取競爭是否發生，在這種情況下，您應該避免這種現象。

例如，一個 100 x 512 float 物件的矩陣是一個包含 100 個 512 float 陣列的陣列。一級陣列的每個單元的大小為 512 x 4 = 2048 個位元組，因此它有資料快取競爭的風險。

要檢測競爭，只需在每個最後一級陣列中新增一個基本單元（一個 float），但繼續處理與以前相同的單元，並測量處理時間是否大幅降低（至少 20%）。在這種情況下，您必須確保這種改進是穩定的。為了實現這個目標，您可以使用以下技術之一

在每個最後一級陣列的末尾新增一個或多個未使用的單元。例如，陣列 double a[100][1024] 可以變成 double a[100][1026]，即使計算將處理該陣列直到前一個大小。
保持陣列大小，但將其劃分為矩形塊，並一次處理一個塊中的所有單元。

字首運算子與字尾運算子

優先使用字首運算子而不是字尾運算子。

在處理基本型別時，字首和字尾算術運算的效能可能相同。但是，對於物件，字尾運算子會導致物件建立自己的副本以保留其初始狀態（作為操作結果返回），以及導致操作的副作用。請考慮以下示例

class IntegerIncreaser
{
    int m_Value;

public:
    /* Postfix operator. */
    IntegerIncreaser operator++ (int) {
        IntegerIncreaser tmp (*this);

        ++m_Value;
        return tmp;
    };

    /* Prefix operator. */
    IntegerIncreaser operator++ () {
        ++m_Value;
        return *this;
    };
};

由於字尾運算子需要返回被遞增（或遞減）的值的未更改版本——無論結果是否實際被使用——它們很可能會進行復制。STL 迭代器（例如）在使用字首運算子進行修改時效率更高。

顯式內聯

如果您不使用整個程式最佳化的編譯器選項，並且不允許編譯器內聯任何函式，請嘗試將瓶頸中呼叫的函式移至標頭檔案，並將其宣告為 inline。

如第 3.1 節中“行內函數”準則所述，每個行內函數都更快，但許多行內函數會減慢整個程式的速度。

嘗試一次宣告幾個 inline 函式，只要您在單個命令中獲得顯著的速度提升（至少 10%）。

與二的冪進行運算

如果必須選擇一個經常用於乘除的整數常量，請選擇二的冪。

如果第二個運算元是二的常數冪，則整數之間的乘法、除法和模運算會快得多，因為在這種情況下它們被實現為位移或位遮蔽。

整數除以常數

當您將一個整數（已知為正或零）除以一個常數時，將該整數轉換為unsigned。

如果s是一個signed整數，u是一個unsigned整數，C是一個常數整型表示式（正或負），則運算s / C比u / C慢，s % C比u % C慢。當C是二的冪時，這種情況最為顯著，但在所有情況下，在除法過程中都必須考慮符號。

但是，從signed到unsigned的轉換是免費的，因為它只是對相同位的重新解釋。因此，如果s是一個您知道為正或零的signed整數，您可以使用以下（等效）表示式來加速其除法：(unsigned)s / C和(unsigned)s % C。

具有縮減資料匯流排的處理器

如果目標處理器的資料匯流排小於處理器暫存器，如果可能，對除函式引數和最常用的區域性變數以外的所有變數使用不超過資料匯流排大小的整數型別。

型別int和unsigned int是最有效的，在它們被載入到處理器暫存器中之後。但是，對於某些處理器系列，它們可能不是在記憶體中訪問的最有效型別。

例如，有一些處理器具有 16 位暫存器，但具有 8 位資料匯流排，而其他處理器具有 32 位暫存器，但具有 16 位資料匯流排。對於資料匯流排小於內部暫存器的處理器，通常型別int和unsigned int與暫存器的大小相匹配。

對於這樣的系統，在記憶體中載入和儲存一個int物件所需的時間比不超過資料匯流排大小的整數所需的時間更長。

函式引數和最常用的區域性變數通常分配在暫存器中，因此不會導致記憶體訪問。

將結構陣列重新排列為多個數組

與其處理單個聚合物件陣列，不如並行處理兩個或多個具有相同長度的陣列。

例如，代替以下程式碼

const int n = 10000;
struct { double a, b, c; } s[n];
for (int i = 0; i < n; ++i) {
    s[i].a = s[i].b + s[i].c;
}

以下程式碼可能更快

const int n = 10000;
double a[n], b[n], c[n];
for (int i = 0; i < n; ++i) {
    a[i] = b[i] + c[i];
}

使用這種重新排列，“a”、“b”和“c”可以透過陣列處理指令進行處理，這些指令比標量指令快得多。這種最佳化可能會對某些（更簡單的）架構產生無效或不利的結果。

更好^{[需要引證]}是交錯陣列

const int n = 10000;
double interleaved[n * 3];
for (int i = 0; i < n; ++i) {
    const size_t idx = i * 3;
    interleaved[idx] = interleaved[idx + 1] + interleaved[idx + 2];
}

記住要測試所有內容！並且不要過早最佳化。