C++Guns – RoboBlog

In den Heise Kommentaren (Ja ich schau da ab und zu rein) gab es letztens ein Vergleich zum Spaß von Conway's Game of Life einmal in C++ und GO. Natürlich war GO furchtbar langsam. Aber der C++ Code sah auch nicht sehr sinnvoll aus. Es ist an der Zeit es mit meinem ACPL Framework und den 2D Array auch mal zu probieren.

Hier die Laufzeiten [sec] ganz grob zum vergleichen. Intel i7-2640M GCC 8.1 go1.6.2 linux/amd64

GO: 1.9
g++ -O1: 0.61
g++ -O2: 0.60
g++ -O3: 0.30

Da bleibt nichts mehr übrig. Mal das Spielfeld und die Anzahl der Iterationen jeweils um Faktor 10 vergrößern. 1000x1000 mit 10000 Iterationen.

GO: 32m6
g++ -O1: 498.3 (8m18)
g++ -O2: 493.3 (8m13)
g++ -O3: 191.5 (3m11)

Jetzt sieht man erst, das GO total unbenutzbar ist. Mit C++ ist man noch mit einer Kaffeepause dabei.
Bei meiner Variante habe ich schon einmal die zwei 3er Schleifen von Hand ausgerollt. Das ist ja trivial. Ansonsten als Container nur acpl::ArrayND benutzt mit 2 Dimensionen und bool Werte. Folgende Zeiten haben sich ergeben:

g++ -O1: 366.6 (6m6)
g++ -O2: 341.1 (5m41)
g++ -O3: 210.0 (3m30)

Die Kaffeepause wird immer kürzer. Sehr interessant, dass bei Optimierung O3 die Laufzeit schlechter wurde. Dies betrifft das Schleifenausrollen. Das kann der Compiler wohl besser als ich. So soll es auch sein!
Anbei der Quellcode. Ist ja wirklich nicht viel. Zu beachten ist, dass der rechte Index der schnell laufende Index ist. Gedanklich läuft man die Zeile entlang und spring dann runter zur nächsten Zeile. Daher werden die Koordinaten in y,x übergeben. In dieser Reihenfolge. Das könnte man in der nächsten ACPL Version auch weg optimieren und ein NDArray-Index benutzen.

Update 15.09.2019
Schöneren Code hochgeladen

#include <iostream>
#include <chrono>
#include <thread>

#include <core/util/ArrayND.hpp>

using std::cout;
using namespace std::chrono_literals;

// Torusartiger Spielraum. Wrap around.
struct Spielfeld : acpl::Array2D<bool>
{
    using Base = acpl::Array2D<bool>;
    using Base::Base;

    // If the x or y coordinates are outside the field boundaries they are wrapped
    // toroidally. For instance, an x value of -1 is treated as width-1.
    bool isAlive(int y, int x) const {
        x += nCols();
        x %= nCols();
        y += nRows();
        y %= nRows();
        return operator()(y,x);
    }

    bool next(int y, int x) const {
        // Count the adjacent cells that are alive.
        int alive = 0;
        if(isAlive(y-1,x-1)) alive++;
        if(isAlive(y-1,  x)) alive++;
        if(isAlive(y-1,x+1)) alive++;

        if(isAlive(y, x-1)) alive++;
        if(isAlive(y, x+1)) alive++;

        if(isAlive(y+1, x-1)) alive++;
        if(isAlive(y+1, x))   alive++;
        if(isAlive(y+1, x+1)) alive++;

        // Return next state according to the game rules:
        //   exactly 3 neighbors: on,
        //   exactly 2 neighbors: maintain current state,
        //   otherwise: off.
        return alive==3 or (alive==2 and isAlive(y,x));
    }
};

struct ConwayGameOfLife {
    Spielfeld a,b;

    ConwayGameOfLife(unsigned int w, unsigned int h)
        : a({h,w}), b({h,w})
    {
        for(unsigned int i=0; i<(w*h/4); i++) {
            a(rand()%h, rand()%w) = true;
        }
    }

    void step() {
        for(unsigned int y=0;y < a.nRows(); y++) {
            for(unsigned int x=0; x < a.nCols(); x++) {
                b(y,x) = a.next(y,x);
            }
        }

        std::swap(a,b);
    }

    auto width() const {
        return a.nCols();
    }

    auto height() const {
        return a.nRows();
    }
};

std::ostream& operator<<(std::ostream& s, const ConwayGameOfLife& game) {
    for(unsigned int x=0; x < game.width()+2; x++) {
        s << '-';
    }
    s << '\n';
    for(unsigned int y=0;y < game.height(); y++) {
        s << "|";
        for(unsigned int x=0; x < game.width(); x++) {
            if(game.a.isAlive(y,x)) {
                s << '*';
            } else {
                s << ' ';
            }
        }
        s << "|\n";
    }

    for(unsigned int x=0; x < game.width()+2; x++) {
        s << '-';
    }
    s << "\n";

    return s;
}

int main() {
    srand(2);
    auto start = std::chrono::high_resolution_clock::now();

    int maxIter = 220;
    ConwayGameOfLife game(60,30);
    for(int i=0; i < maxIter; i++) {
        game.step();

        system("clear");
        std::cout << i << " / " << maxIter << "\n";
        std::cout << game;
        std::this_thread::sleep_for(0.2s);
    }

    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed = end-start;
    std::cout << elapsed.count() << " seconds\n";

    //std::cout << game << "\n\n\n";
}