优化康威在C++中的生命博弈

Question

我怎样才能进一步优化康威生命游戏的实现？你会怎么批评我目前的策略？我正在上C++优化课，截止日期已经过了，我的作业已经提交了。我们应该使用以下选项进行编译：g++ me.cpp -std=c++11 -O3 -march=native -o me。

在像这样执行real之后，我正在尝试最小化它的时间：time ./me 0 1000 0。我的程序的第一个参数是随机种子，第二个参数是迭代次数，最后一个参数是1或0，意思是打印或不打印。我不想在计时的时候打印。随机种子和迭代次数可以是任意值。

是如何工作的

我遍历活的细胞，而不是板上的所有空间。我手动展开迭代，遍历包含每个活细胞的所有9个瓷砖。活的邻居，包括中央活细胞，变得积极地增加。活细胞的死邻居会衰老。

这意味着在encode函数之后，死瓷砖上的值为-3，这意味着有3个活的邻居，因此该瓷砖应该是活的。1是不可能的，因为活的细胞至少增加一次。正数2表示没有活邻居，3表示活邻居1，4代表活邻居2，5表示活邻居3，等等。

根据规则，有3种情况下单元格可以存活，但我的living_cipher数组包含第4种活动状态。这是因为在decode方法中，代码值为1意味着我已经确定单元格是活的，现在我应该忽略这个块。因为应该忽略1，所以counter_cipher在该条目处有一个零。这种方法将从-8到10之间的代码转换为1或0，表示活着或死亡。增加并重复所需的迭代次数。

我使用宏作为优化，因为常量变量比较慢。我没有尝试内联函数。

#include <iostream>

using namespace std;

#define HEIGHT ((1 << 10) + 2)
#define WIDTH ((1 << 11) + 2)
#define MAX_Y (HEIGHT - 1)
#define MAX_X (WIDTH - 1)
#define NEXT_ROW (WIDTH - 2)
#define AREA (HEIGHT * WIDTH)

constexpr signed char offset_living_cipher[19] = {
    0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0
};
constexpr signed char offset_counter_cipher[19] = {
    0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0
};

class Matthew_Conway{
private:
    bool print;
    signed char * board;
    signed char ** cells, ** next_cells;
    unsigned long total_cells;

    void make_cells(){
        unsigned long next_total_cells = 0;
        cells = new signed char * [AREA];
        next_cells = new signed char * [AREA];

        for (unsigned long row = 1; row <= HEIGHT - 2; ++row){
            for(unsigned long column = 1; column <= WIDTH - 2; ++column){
                unsigned long index = row * WIDTH + column;
                signed char cell = rand() % 2 == 0;
                board[index] = cell;
                cells[next_total_cells] = board + index;
                next_total_cells += cell;
            }
        }
        total_cells = next_total_cells;
    }

public:
    unsigned long iterations;

    Matthew_Conway(char ** argv){
        unsigned random_seed = (unsigned) atoi(argv[1]);
        srand(random_seed);
        iterations = (unsigned long) atoi(argv[2]);
        print = (bool) atoi(argv[3]);
        board = (signed char*) calloc(AREA, sizeof(signed char));
        make_cells();
    }

    void print_board(){
        if (!print) 
            return; 
        for (unsigned long row = 1; row <= HEIGHT - 2; ++row){
            for (unsigned long column = 1; column <= WIDTH - 2; ++column){
                signed char value = board[row * WIDTH + column];
                cout << (int) value;
            }
            cout << endl;
        }
    }

    void encode() {
        #define INCREMENT *board_address += 2 * (*board_address > 0) - 1;
        unsigned long next_total_cells = 0;

        for (unsigned long cell_i = 0; cell_i < total_cells; ++cell_i) {
            signed char * cell = cells[next_total_cells] = cells[cell_i];
            unsigned long index = cell - board;
            unsigned long y = index / WIDTH;
            unsigned long x = index % WIDTH;
            if (x == 0 || x == MAX_X || y == 0 || y == MAX_Y){
                continue;
            }
            ++next_total_cells;

            signed char * board_address = cell - WIDTH - 1; // Upper Left
            INCREMENT;
            ++board_address; // Upper Middle
            INCREMENT;
            ++board_address; // Upper Right
            INCREMENT;
            board_address += NEXT_ROW; // Middle Left
            INCREMENT;
            ++board_address; // Center
            ++*board_address;
            ++board_address; // Middle Right
            INCREMENT;
            board_address += NEXT_ROW; // Lower Left
            INCREMENT;
            ++board_address; // Lower Middle
            INCREMENT;
            ++board_address; // Lower Right
            INCREMENT;
        }
        total_cells = next_total_cells;
    }

    void decode() {
        #define LIVING_CIPHER (offset_living_cipher + 8)
        #define COUNTER_CIPHER (offset_counter_cipher + 8)
        #define DECIPHER { \
            code = *board_address; \
            *board_address = LIVING_CIPHER[code]; \
            next_cells[next_total_cells] = board_address; \
            next_total_cells += COUNTER_CIPHER[code]; \
        }
        signed char code;
        unsigned long next_total_cells = 0;

        for (unsigned long cell_i = 0; cell_i < total_cells; ++cell_i) {
            signed char * cell = cells[cell_i];

            signed char * board_address = cell - WIDTH - 1; // Upper Left
            DECIPHER;
            ++board_address; // Upper Middle
            DECIPHER;
            ++board_address; // Upper Right
            DECIPHER;
            board_address += NEXT_ROW; // Middle Left
            DECIPHER;
            ++board_address; // Center
            DECIPHER;
            ++board_address; // Middle Right
            DECIPHER;
            board_address += NEXT_ROW; // Lower Left
            DECIPHER;
            ++board_address; // Lower Middle
            DECIPHER;
            ++board_address; // Lower Right
            DECIPHER;
        }
        total_cells = next_total_cells;
        swap(cells, next_cells);
    }
};

int main(int argc, char ** argv){
    if (argc != 4){
        cout << "usage game-of-life <seed> <generations> <0:don't print, 1:print>" << endl;
        return 1;
    }
    Matthew_Conway conway(argv);
    conway.print_board();
    for (unsigned long i = 0; i < conway.iterations; ++i){
        conway.encode();
        conway.decode();
    }
    conway.print_board();
    return 0;
}

Answer 1

代码可能已经被过度优化，添加额外的优化只会使读取和维护代码变得更加困难，但这说明：

缺失优化

• 当打印更喜欢'\n'而不是std::endl，因为std::endl调用一个系统函数来刷新输出时，'\n'只是插入一个新行。
• 将检查放到函数print_board()之外打印，这样函数甚至不会被调用。这节省了将所有内容推送到堆栈和更改执行流程的时间成本。
• 在print_board()和make_cells()中使用迭代器或指针，而不是索引。用-O3编译可能会为您做到这一点，但是直接寻址将比索引更快。
• 取决于处理器和指令集是否包括auto decrement and test，可以通过在for循环中计数而不是计数来提高指令性能。
• 检查生成的程序集代码，并知道正在使用的处理器的指令集。
• 使用处理器的自然字号，而不是指定字长。在代码中，这意味着使用unsigned而不是unsigned long。在大多数当前处理器上，您将被保证至少32位的字大小，可能是64位的字大小。
• 使不更改成员值的成员函数const。void print_board() const {.}

幻数

有一些数值常量应该移除或更改为符号常量。数值常量有时被称为幻数，因为它不清楚这些值代表什么。在堆栈过流上对此进行了讨论。

在比较4的argc中的main值和在这两个声明中的值19是示例：

constexpr signed char offset_living_cipher[19] =
{
    0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0
};

constexpr signed char offset_counter_cipher[19] = 
{
    0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0
};

前两个声明中的数字19并不是必需的，因为这些声明将由编译器计算。

constexpr signed char offset_living_cipher[] =
{
    0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0
};

constexpr signed char offset_counter_cipher[] = 
{
    0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0
};

对这些声明进行评论也可能是好的，因为这里不清楚正在做什么。

最好是include <cstdlib>，并在return语句中使用main中系统定义的符号常量EXIT_FAILURE和EXIT_SUCCESS。

不要混合内存分配方法

在构造函数中，调用C编程内存分配函数calloc()，但在函数make_cells()中有两个对new的调用。这里有几个问题，第一个问题是没有检查对calloc()的调用结果。如果没有分配由calloc()分配的数组(calloc返回NULL或nullptr)，那么第一次使用board将导致程序终止，但是，如果new失败，则会引发异常。在这种情况下，由于没有try {} catch {}块，程序也将终止，但如果存在try {} catch {}块，如果calloc()失败，程序仍将终止。最好与内存分配保持一致，最好还是坚持使用new而不是calloc()。

避免使用名称空间std

如果您是专业编写代码的，您可能应该戒掉使用using namespace std;指令的习惯。代码将更清楚地定义cout和其他标识符来自何处(std::cin、std::cout)。当您开始在代码中使用名称空间时，最好确定每个函数的来源，因为可能会有来自不同名称空间的函数名称冲突。您可以在您自己的类中重写的对象cout。本堆栈溢出问题将对此进行更详细的讨论。

Answer 2

为性能编写代码并不意味着您应该编写不可维护的代码。请记住，开发人员的时间也是宝贵的:任何花费在跟踪可避免的bug的时间都是您可能花在调整程序性能上的时间。一些可以在不影响性能的情况下得到改进的特殊事情：

• 包括我们使用的标准标识符的标头(std::swap需要<utility>；std::atoi和std::calloc需要<cstdlib>)。
• 避免using namespace std;
• 更喜欢正确类型的constexpr值，而不是预处理宏(我不相信这会使代码变慢--我得到了完全相同的汇编代码)。这些值应该是(私有的)静态成员，而不是全局成员。
• C++内存分配优于<cstdlib>分配(malloc()和家庭)。这使得错误检查更加简单(异常而不是返回值检查)。
• 使用std::vector而不是原始new[]；这样可以防止内存泄漏。
• 将参数解析排除在核心逻辑之外，并使其更健壮(例如，使用std::stoul()转换为unsigned long)。
• 初始化构造函数初始化程序列表中的成员。
• 如果你真的需要短期的宏，那么在使用后对它们进行#undef。

一旦我们有了可维护的代码，我们就可以对算法进行研究。我们在存储方面效率很低(造成数据局部性差，从而不必要地破坏缓存)。我们有两个指针数组，每个数组与board相同，但在sizeof (unsigned char *)大于1的平台上要大得多。指针都指向board，因此我们可以存储索引；更好的是，存储单独的x和y坐标，这样就不必进行除法了。

考虑到我们的任务是最小化实时，我们应该尽可能多地并行化。在多核处理器上，生命游戏自然地与每个线程并行，每个线程编写自己的下一个状态，所有线程共享对旧状态的读取访问。如果处理器有支持(例如NEON或AVX)，那么每个线程内的SIMD并行化也是可能的。

Answer 3

利用稀疏性是一个不错的技巧，尽管不如哈希姆 (它属于自己的类)。撇开哈希生活不说，有一些简单的方法可以在实际的计算机上很好地工作，不是通过算法聪明，而是通过对计算机友好。与一个完全简单的方法相比，你的方法肯定更好。但它并没有真正挖掘现代CPU的潜力。

例如，在我的个人电脑上(使用4770 K，所以不再很新)，你的基准测试大约需要2.85秒，但是如果我使用一些非常简单的不使用技巧的AVX2实现(所以不使用稀疏或任何其他聪明的)的“生命游戏”，那大约需要0.38秒。但是工作不是时间，SIMD很擅长在短时间内处理大量的工作，特别是当你使用8位类型的时候。

在一个具有更稀疏网格的基准测试中，SIMD方法不会做得那么好。即使在这个基准测试中，模拟更多的步骤也会降低加速比，在100000步中下降到~3.7倍。

AVX2是当今许多x86 CPU中可用的指令集扩展，例如Haswell和较新的英特尔处理器(包括i7-8565U，但分级服务器中的神秘Xeon可能支持AVX2，也可能不支持AVX2，这取决于它的年龄)，以及AMD挖掘机和Zen。如果使用支持这些指令的编译器，则在C++中将这些指令公开为内部函数。AVX2包括一次将一个操作应用于32个字节的指令，例如，在下面的代码中，我多次使用_mm256_add_epi8 (又名vpaddb)，每次执行32个添加，以同时对一行32个单元格的活邻居数进行汇总。

示例代码：

void step() {
#define INDEX(a, b) ((a) + (b) * WIDTH)
    for (size_t y = 0; y < HEIGHT; y++) {
        if (y == 0 || y == MAX_Y) {
            for (size_t x = 0; x < WIDTH; x++) {
                next_board[INDEX(x, y)] = board[INDEX(x, y)];
            }
        }
        else {
            next_board[INDEX(0, y)] = board[INDEX(0, y)];
            next_board[INDEX(MAX_X, y)] = board[INDEX(MAX_X, y)];
            size_t x = 1;
            for (; x < WIDTH - 33; x += 32) {
                __m256i n = _mm256_loadu_si256((__m256i*)&board[INDEX(x - 1, y - 1)]);
                n = _mm256_add_epi8(n, _mm256_loadu_si256((__m256i*)&board[INDEX(x, y - 1)]));
                n = _mm256_add_epi8(n, _mm256_loadu_si256((__m256i*)&board[INDEX(x + 1, y - 1)]));
                n = _mm256_add_epi8(n, _mm256_loadu_si256((__m256i*)&board[INDEX(x - 1, y)]));
                n = _mm256_add_epi8(n, _mm256_loadu_si256((__m256i*)&board[INDEX(x + 1, y)]));
                n = _mm256_add_epi8(n, _mm256_loadu_si256((__m256i*)&board[INDEX(x - 1, y + 1)]));
                n = _mm256_add_epi8(n, _mm256_loadu_si256((__m256i*)&board[INDEX(x, y + 1)]));
                n = _mm256_add_epi8(n, _mm256_loadu_si256((__m256i*)&board[INDEX(x + 1, y + 1)]));
                __m256i is3 = _mm256_cmpeq_epi8(n, _mm256_set1_epi8(3));
                __m256i is2 = _mm256_cmpeq_epi8(n, _mm256_set1_epi8(2));
                __m256i cellItself = _mm256_loadu_si256((__m256i*)&board[INDEX(x, y)]);
                __m256i isNextLive = _mm256_or_si256(is3, _mm256_and_si256(is2, cellItself));
                isNextLive = _mm256_abs_epi8(isNextLive);
                _mm256_storeu_si256((__m256i*)&next_board[INDEX(x, y)], isNextLive);
            }
            for (; x < WIDTH - 1; x++) {
                int n = board[INDEX(x - 1, y - 1)];
                n += board[INDEX(x, y - 1)];
                n += board[INDEX(x + 1, y - 1)];
                n += board[INDEX(x - 1, y)];
                n += board[INDEX(x + 1, y)];
                n += board[INDEX(x - 1, y + 1)];
                n += board[INDEX(x, y + 1)];
                n += board[INDEX(x + 1, y + 1)];
                next_board[INDEX(x, y)] = n == 3 || (n == 2 && board[INDEX(x, y)]);
            }
        }
    }

    swap(board, next_board);
}

有更巧妙地使用AVX2 2，例如，使用vpshufb实现自动机规则。

另一种流行的方法是对单元格进行位填充，然后使用按位操作来计算下一个状态，依赖于位并行操作的性质来加快计算速度。此页讨论了这个技巧和一些相关的历史。