{"id":4065,"date":"2019-01-23T18:24:40","date_gmt":"2019-01-23T17:24:40","guid":{"rendered":"http:\/\/roboblog.fatal-fury.de\/?p=4065"},"modified":"2019-09-15T12:57:40","modified_gmt":"2019-09-15T11:57:40","slug":"c-guns-acpl-conways-game-of-life","status":"publish","type":"post","link":"http:\/\/roboblog.fatal-fury.de\/?p=4065","title":{"rendered":"C++ Guns: ACPL: Conway's Game of Life"},"content":{"rendered":"

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

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

GO: 1.9
\ng++ -O1: 0.61
\ng++ -O2: 0.60
\ng++ -O3: 0.30<\/p>\n

Da bleibt nichts mehr \u00fcbrig. Mal das Spielfeld und die Anzahl der Iterationen jeweils um Faktor 10 vergr\u00f6\u00dfern. 1000x1000 mit 10000 Iterationen.<\/p>\n

GO: 32m6
\ng++ -O1: 498.3 (8m18)
\ng++ -O2: 493.3 (8m13)
\ng++ -O3: 191.5 (3m11)<\/p>\n

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

g++ -O1: 366.6 (6m6)
\ng++ -O2: 341.1 (5m41)
\ng++ -O3: 210.0 (3m30)<\/p>\n

Die Kaffeepause wird immer k\u00fcrzer. 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!
\nAnbei der Quellcode. Ist ja wirklich nicht viel. Zu beachten ist, dass der rechte Index der schnell laufende Index ist. Gedanklich l\u00e4uft man die Zeile entlang und spring dann runter zur n\u00e4chsten Zeile. Daher werden die Koordinaten in y,x \u00fcbergeben. In dieser Reihenfolge. Das k\u00f6nnte man in der n\u00e4chsten ACPL<\/a> Version auch weg optimieren und ein NDArray-Index benutzen.<\/p>\n

Update 15.09.2019
\nSch\u00f6neren Code hochgeladen<\/p>\n

\r\n#include <iostream>\r\n#include <chrono>\r\n#include <thread>\r\n\r\n#include <core\/util\/ArrayND.hpp>\r\n\r\nusing std::cout;\r\nusing namespace std::chrono_literals;\r\n\r\n\/\/ Torusartiger Spielraum. Wrap around.\r\nstruct Spielfeld : acpl::Array2D<bool>\r\n{\r\n    using Base = acpl::Array2D<bool>;\r\n    using Base::Base;\r\n\r\n    \/\/ If the x or y coordinates are outside the field boundaries they are wrapped\r\n    \/\/ toroidally. For instance, an x value of -1 is treated as width-1.\r\n    bool isAlive(int y, int x) const {\r\n        x += nCols();\r\n        x %= nCols();\r\n        y += nRows();\r\n        y %= nRows();\r\n        return operator()(y,x);\r\n    }\r\n\r\n    bool next(int y, int x) const {\r\n        \/\/ Count the adjacent cells that are alive.\r\n        int alive = 0;\r\n        if(isAlive(y-1,x-1)) alive++;\r\n        if(isAlive(y-1,  x)) alive++;\r\n        if(isAlive(y-1,x+1)) alive++;\r\n\r\n        if(isAlive(y, x-1)) alive++;\r\n        if(isAlive(y, x+1)) alive++;\r\n\r\n        if(isAlive(y+1, x-1)) alive++;\r\n        if(isAlive(y+1, x))   alive++;\r\n        if(isAlive(y+1, x+1)) alive++;\r\n\r\n        \/\/ Return next state according to the game rules:\r\n        \/\/   exactly 3 neighbors: on,\r\n        \/\/   exactly 2 neighbors: maintain current state,\r\n        \/\/   otherwise: off.\r\n        return alive==3 or (alive==2 and isAlive(y,x));\r\n    }\r\n};\r\n\r\nstruct ConwayGameOfLife {\r\n    Spielfeld a,b;\r\n\r\n    ConwayGameOfLife(unsigned int w, unsigned int h)\r\n        : a({h,w}), b({h,w})\r\n    {\r\n        for(unsigned int i=0; i<(w*h\/4); i++) {\r\n            a(rand()%h, rand()%w) = true;\r\n        }\r\n    }\r\n\r\n    void step() {\r\n        for(unsigned int y=0;y < a.nRows(); y++) {\r\n            for(unsigned int x=0; x < a.nCols(); x++) {\r\n                b(y,x) = a.next(y,x);\r\n            }\r\n        }\r\n\r\n        std::swap(a,b);\r\n    }\r\n\r\n    auto width() const {\r\n        return a.nCols();\r\n    }\r\n\r\n    auto height() const {\r\n        return a.nRows();\r\n    }\r\n};\r\n\r\nstd::ostream& operator<<(std::ostream& s, const ConwayGameOfLife& game) {\r\n    for(unsigned int x=0; x < game.width()+2; x++) {\r\n        s << '-';\r\n    }\r\n    s << '\\n';\r\n    for(unsigned int y=0;y < game.height(); y++) {\r\n        s << "|";\r\n        for(unsigned int x=0; x < game.width(); x++) {\r\n            if(game.a.isAlive(y,x)) {\r\n                s << '*';\r\n            } else {\r\n                s << ' ';\r\n            }\r\n        }\r\n        s << "|\\n";\r\n    }\r\n\r\n    for(unsigned int x=0; x < game.width()+2; x++) {\r\n        s << '-';\r\n    }\r\n    s << "\\n";\r\n\r\n    return s;\r\n}\r\n\r\nint main() {\r\n    srand(2);\r\n    auto start = std::chrono::high_resolution_clock::now();\r\n\r\n    int maxIter = 220;\r\n    ConwayGameOfLife game(60,30);\r\n    for(int i=0; i < maxIter; i++) {\r\n        game.step();\r\n\r\n        system("clear");\r\n        std::cout << i << " \/ " << maxIter << "\\n";\r\n        std::cout << game;\r\n        std::this_thread::sleep_for(0.2s);\r\n    }\r\n\r\n    auto end = std::chrono::high_resolution_clock::now();\r\n    std::chrono::duration<double> elapsed = end-start;\r\n    std::cout << elapsed.count() << " seconds\\n";\r\n\r\n    \/\/std::cout << game << "\\n\\n\\n";\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
In den Heise Kommentaren (Ja ich schau da ab und zu rein) gab es letztens ein Vergleich zum Spa\u00df von Conway's Game of Life einmal in C++ und GO. Nat\u00fcrlich 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 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[17],"class_list":["post-4065","post","type-post","status-publish","format-standard","hentry","category-allgemein","tag-cpp"],"_links":{"self":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/4065","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4065"}],"version-history":[{"count":10,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/4065\/revisions"}],"predecessor-version":[{"id":4526,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/4065\/revisions\/4526"}],"wp:attachment":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4065"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4065"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4065"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}