Programmier\u00fcbung:
\nArray Verallgemeinerung von 1D zu 2D zu ND. Interessant wird es die Indizierung zu programmierten, da die Anzahl der Dimensionen variabel, aber zur Compilezeit bekannten ist.
\nDer Index f\u00fcr ein 2D Array berechnet sich einfach: idx1D = dimsize[0]*j + i Das Muster wiederholt sich einfach. F\u00fcr 3D ist es idx = dimsize[1]*dimsize[0]*k + dimsize[0]*j + j
\nDer Term dimsize[1]*dimsize[0] l\u00e4sst sich bei der Initialisierung des Arrays vorraus berechnen, so dass einige Multiplikationen beim Arrayzugiff gespart werden.<\/p>\n
Mit template parameter pack sollte das alles gut funktionieren. Hier ist meine erste Version:<\/p>\n
\r\ntemplate<typename T, size_t dimensionen, typename ValArray=std::vector<T> >\r\nstruct ArrayND : ValArray {\r\n using Base = ValArray;\r\n\r\n using const_reference = typename Base::const_reference;\r\n\r\n std::array<int, dimensionen> muldimsizes;\r\n\r\n \/\/\/ \\todo replace with std::reduce as soon it is supported by GCC\r\n auto helper(const std::array<int, dimensionen>& dims) {\r\n int size = 1;\r\n for(size_t i=0; i < dimensionen; ++i) {\r\n size *= dims[i];\r\n }\r\n return size;\r\n }\r\n\r\n ArrayND(const std::array<int, dimensionen>& dims)\r\n : Base(helper(dims))\r\n {\r\n muldimsizes.back() = dims.back();\r\n for(size_t i=dimensionen-1; i > 0; --i) {\r\n muldimsizes[i-1] = muldimsizes[i]*dims[i-1];\r\n }\r\n }\r\n\r\n template<typename Int>\r\n auto pos2idx(const std::array<Int,dimensionen>& pos) const {\r\n int idx = pos.back();\r\n for(size_t i=0; i < dimensionen-1; ++i) {\r\n idx += muldimsizes[i+1]*pos[i];\r\n }\r\n return idx;\r\n }\r\n\r\n template<typename...Ints>\r\n const_reference operator()(const Ints&...pos) const {\r\n static_assert(sizeof...(Ints) == dimensionen, "Given position array must be same size as this matrix dimensions");\r\n \/\/ It's a fold expression\r\n static_assert((std::is_integral_v<Ints> and ...), "All given positions must be integral type");\r\n return (*this) [pos2idx(std::array{pos...})];\r\n }\r\n};\r\n<\/pre>\nSo funktioniert das schonmal. Wie sieht der erzeugte Assembler Code aus?<\/p>\n
1D std::vector<\/h1>\n
Zum Vergleich der Assembler Code bei einem normalen Zugriff \u00fcber std::vector<\/p>\n
\r\nauto func( std::vector<double> &arr, int idx) {\r\n return arr[idx];\r\n}\r\n\r\nfunc(std::vector<double, std::allocator<double> >&, int):\r\n movslq %esi, %rsi # convert int32 to int64\r\n movq (%rdi), %rax\r\n movsd (%rax,%rsi,8), %xmm0 # xmm0 is return register of the double value\r\n ret\r\n<\/pre>\nDrei mov Instruktionen. Die erste Instruktion ist eine Konvertierung von int zu size_t. Besser geht es eigentlich nicht.<\/p>\n
1D ArrayND<\/h1>\n
Nun der 1D Fall f\u00fcr Array1D. Es muss im Prinzip der selbe Assembler Code erzeugt werden, wenn nicht sogar identischer! Da im Prinzip bei 1D keine Index Umrechnung statt findet.<\/p>\n
\r\nauto func1D( ArrayND<double,1> &arr, int idx) {\r\n return arr(idx);\r\n}\r\n\r\nfunc1D(ArrayND<double, 1ul, std::vector<double, std::allocator<double> > >&, int):\r\n movslq %esi, %rsi\r\n movq (%rdi), %rax\r\n movsd (%rax,%rsi,8), %xmm0\r\n ret\r\n<\/pre>\nHA! Identisch! Wenn das kein guter Start ist.<\/p>\n
2D ArrayND<\/h1>\n
F\u00fcr 2D m\u00fcsste theoretisch nur eine Multiplikation und eine Addition dazu kommen.<\/p>\n
\r\nauto func2D( ArrayND<double,2> &arr, int idx1, int idx2) {\r\n return arr(idx1,idx2);\r\n}\r\n\r\nfunc2D(ArrayND<double, 2ul, std::vector<double, std::allocator<double> > >&, int, int):\r\n imull 28(%rdi), %esi\r\n addl %edx, %esi\r\n movslq %esi, %rsi\r\n movq (%rdi), %rax\r\n movsd (%rax,%rsi,8), %xmm0\r\n ret\r\n<\/pre>\nJa, best\u00e4tigt.<\/p>\n
4D ArrayND<\/h1>\n
F\u00fcr jede weitere Dimension kommt wohl nur genau eine Multiplikation und eine Addition hinzu. Springen wir gleich zu 4D.<\/p>\n
\r\nauto func4D( ArrayND<double,4> &arr, int idx1, int idx2, int idx3, int idx4) {\r\n return arr(idx1,idx2,idx3,idx4);\r\n}\r\n\r\nfunc4D(ArrayND<double, 4ul, std::vector<double, std::allocator<double> > >&, int, int, int, int):\r\n imull 28(%rdi), %esi\r\n addl %r8d, %esi\r\n imull 32(%rdi), %edx\r\n addl %esi, %edx\r\n imull 36(%rdi), %ecx\r\n addl %edx, %ecx\r\n movslq %ecx, %rcx\r\n movq (%rdi), %rax\r\n movsd (%rax,%rcx,8), %xmm0\r\n ret\r\n<\/pre>\nDrei Kopien, drei Multiplikationen und drei Additionen.<\/p>\n
ArrayND ready to use ;)<\/p>\n","protected":false},"excerpt":{"rendered":"
Programmier\u00fcbung: Array Verallgemeinerung von 1D zu 2D zu ND. Interessant wird es die Indizierung zu programmierten, da die Anzahl der Dimensionen variabel, aber zur Compilezeit bekannten ist. Der Index f\u00fcr ein 2D Array berechnet sich einfach: idx1D = dimsize[0]*j + i Das Muster wiederholt sich einfach. F\u00fcr 3D ist es idx = dimsize[1]*dimsize[0]*k + dimsize[0]*j […]<\/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-3576","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\/3576","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=3576"}],"version-history":[{"count":5,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3576\/revisions"}],"predecessor-version":[{"id":3581,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3576\/revisions\/3581"}],"wp:attachment":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3576"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3576"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3576"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}