如何优化C++ for loops/if语句？

Question

有没有办法让c++代码运行得更快，我正在尝试优化我的代码中最慢的部分，比如：

    void removeTrail ( char floor[][SIZEX],int trail[][SIZEX])
{
    for (int y=1; y < SIZEY-1; y++)                                         
        for (int x=1; x < SIZEX-1; x++)
        {   if (trail [y][x] <= SLIMELIFE && trail [y][x] > 0)  
            {   trail [y][x] --;                                        
                if (trail [y][x] == 0)                                  
                    floor [y][x] = NONE;                                    
            }
        }
}

我在网上找到的大多数指南都是针对更复杂的C++的。

Answer 1

这真的取决于你在寻求什么样的优化。在我看来，您谈论的是一种更“低级”的优化，它可以通过更改嵌套循环的顺序、更改if语句的放置位置、在递归和迭代方法之间进行选择等技术，结合编译标志来实现。

然而，最有效的优化是那些针对算法的优化，这意味着您正在改变例程的复杂性，因此通常会将执行时间减少几个数量级。例如，当您决定实现Quicksort而不是Selection Sort时，就是这种情况。从O(n^2)到O(n lg n)算法的优化几乎不会被任何微观优化所击败。

在本例中，我看到您试图在元素达到某个特定值时从矩阵中“移除”这些元素。根据这些值是如何变化的，简单地跟踪它们何时达到那个值并将它们添加到queue中进行删除，而不是总是检查整个矩阵，可能会做到这一点：

trail[y][x]--; // In some part of your code, this happens
if (trail[y][x] == 0) { //add for removal
    removalQueueY[yQueueTail++] = y;
    removalQueueX[xQueueTail++] = x;
}

//Then, instead of checking for removal as you currently do:
while (yQueueHead < yQueueTail) {
    //Remove the current element and advance the heads
    floor[removalQueueY[yQueueHead]][removalQueueX[xQueueHead]] = NONE;
    yQueueHead++, xQueueHead++;
}

根据这些值是如何变化的(如果它不是一个简单的trail[y][x]--)，另一个数据结构可能更有用。例如，您可以尝试使用heap或std::set、std::priority_queue等。归根结底，算法必须支持哪些操作，以及哪些数据结构允许您尽可能高效地执行这些操作(根据您的优先级和需求，考虑内存和执行时间)。

Answer 2

要做的第一件事是打开编译器优化。我所知道的最强大的优化是配置文件导引优化。对于gcc：

1) g++ -fprofile-Generated....-o my_program

2)运行my_program (典型负载)

3) g++ -fprofile-使用-O3 ... -o optimized_program

使用profile O3确实很有意义。

下一步是执行算法优化，就像在Renato_Ferreira answer中一样。如果它不适用于您的情况，您可以使用矢量化将您的性能提高2到8倍。你的代码看起来是可矢量化的：

#include <cassert>
#include <emmintrin.h>
#include <iostream>

#define SIZEX 100 // SIZEX % 4 == 0
#define SIZEY 100
#define SLIMELIFE 100
#define NONE 0xFF

void removeTrail(char floor[][SIZEX], int trail[][SIZEX]) {
    // check if trail is 16 bytes alligned
    assert((((size_t)(&trail[0][0])) & (size_t)0xF) == 0);
    static const int lower_a[] = {0,0,0,0};
    static const int sub_a[] = {1,1,1,1};
    static const int floor_a[] = {1,1,1,1}; // will underflow after decrement
    static const int upper_a[] = {SLIMELIFE, SLIMELIFE, SLIMELIFE, SLIMELIFE};
    __m128i lower_v = *(__m128i*) lower_a;
    __m128i upper_v = *(__m128i*) upper_a;
    __m128i sub_v = *(__m128i*) sub_a;
    __m128i floor_v = *(__m128i*) floor_a;
    for (int i = 0; i < SIZEY; i++) {
        for (int j = 0; j < SIZEX; j += 4) { // only for SIZEX % 4 == 0
            __m128i x = *(__m128i*)(&trail[i][j]);

            __m128i floor_mask = _mm_cmpeq_epi32(x, floor_v); // 32-bit
            floor_mask = _mm_packs_epi32(floor_mask, floor_mask); // now 16-bit
            floor_mask = _mm_packs_epi16(floor_mask, floor_mask); // now 8-bit
            int32_t fl_mask[4];
            *(__m128i*)fl_mask = floor_mask;
            *(int32_t*)(&floor[i][j]) |= fl_mask[0]; 

            __m128i less_mask = _mm_cmplt_epi32(lower_v, x);
            __m128i upper_mask = _mm_cmplt_epi32(x, upper_v);
            __m128i mask = less_mask & upper_mask;
            *(__m128i*)(&trail[i][j]) = _mm_sub_epi32(x, mask & sub_v);
        }
    }   
}

int main()
{   
    int T[SIZEY][SIZEX];
    char F[SIZEY][SIZEX];
    for (int i = 0; i < SIZEY; i++) {
        for (int j = 0; j < SIZEX; j++) {
            F[i][j] = 0x0;
            T[i][j] = j-10;
        }
    }
    removeTrail(F, T);
    for (int j = 0; j < SIZEX; j++) {
        std::cout << (int) F[2][j] << " " << T[2][j] << '\n';
    }
    return 0;
}

看起来它做了它应该做的事情。没有if和迭代的4个值。仅在NONE = 0xFF时有效。可以为另一个人做，但这是困难的。