Programmierübung:
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ür ein 2D Array berechnet sich einfach: idx1D = dimsize[0]*j + i Das Muster wiederholt sich einfach. Für 3D ist es idx = dimsize[1]*dimsize[0]*k + dimsize[0]*j + j
Der Term dimsize[1]*dimsize[0] lässt sich bei der Initialisierung des Arrays vorraus berechnen, so dass einige Multiplikationen beim Arrayzugiff gespart werden.
Mit template parameter pack sollte das alles gut funktionieren. Hier ist meine erste Version:
template<typename T, size_t dimensionen, typename ValArray=std::vector<T> > struct ArrayND : ValArray { using Base = ValArray; using const_reference = typename Base::const_reference; std::array<int, dimensionen> muldimsizes; /// \todo replace with std::reduce as soon it is supported by GCC auto helper(const std::array<int, dimensionen>& dims) { int size = 1; for(size_t i=0; i < dimensionen; ++i) { size *= dims[i]; } return size; } ArrayND(const std::array<int, dimensionen>& dims) : Base(helper(dims)) { muldimsizes.back() = dims.back(); for(size_t i=dimensionen-1; i > 0; --i) { muldimsizes[i-1] = muldimsizes[i]*dims[i-1]; } } template<typename Int> auto pos2idx(const std::array<Int,dimensionen>& pos) const { int idx = pos.back(); for(size_t i=0; i < dimensionen-1; ++i) { idx += muldimsizes[i+1]*pos[i]; } return idx; } template<typename...Ints> const_reference operator()(const Ints&...pos) const { static_assert(sizeof...(Ints) == dimensionen, "Given position array must be same size as this matrix dimensions"); // It's a fold expression static_assert((std::is_integral_v<Ints> and ...), "All given positions must be integral type"); return (*this) [pos2idx(std::array{pos...})]; } };
So funktioniert das schonmal. Wie sieht der erzeugte Assembler Code aus?
1D std::vector
Zum Vergleich der Assembler Code bei einem normalen Zugriff über std::vector
auto func( std::vector<double> &arr, int idx) { return arr[idx]; } func(std::vector<double, std::allocator<double> >&, int): movslq %esi, %rsi # convert int32 to int64 movq (%rdi), %rax movsd (%rax,%rsi,8), %xmm0 # xmm0 is return register of the double value ret
Drei mov Instruktionen. Die erste Instruktion ist eine Konvertierung von int zu size_t. Besser geht es eigentlich nicht.
1D ArrayND
Nun der 1D Fall für 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.
auto func1D( ArrayND<double,1> &arr, int idx) { return arr(idx); } func1D(ArrayND<double, 1ul, std::vector<double, std::allocator<double> > >&, int): movslq %esi, %rsi movq (%rdi), %rax movsd (%rax,%rsi,8), %xmm0 ret
HA! Identisch! Wenn das kein guter Start ist.
2D ArrayND
Für 2D müsste theoretisch nur eine Multiplikation und eine Addition dazu kommen.
auto func2D( ArrayND<double,2> &arr, int idx1, int idx2) { return arr(idx1,idx2); } func2D(ArrayND<double, 2ul, std::vector<double, std::allocator<double> > >&, int, int): imull 28(%rdi), %esi addl %edx, %esi movslq %esi, %rsi movq (%rdi), %rax movsd (%rax,%rsi,8), %xmm0 ret
Ja, bestätigt.
4D ArrayND
Für jede weitere Dimension kommt wohl nur genau eine Multiplikation und eine Addition hinzu. Springen wir gleich zu 4D.
auto func4D( ArrayND<double,4> &arr, int idx1, int idx2, int idx3, int idx4) { return arr(idx1,idx2,idx3,idx4); } func4D(ArrayND<double, 4ul, std::vector<double, std::allocator<double> > >&, int, int, int, int): imull 28(%rdi), %esi addl %r8d, %esi imull 32(%rdi), %edx addl %esi, %edx imull 36(%rdi), %ecx addl %edx, %ecx movslq %ecx, %rcx movq (%rdi), %rax movsd (%rax,%rcx,8), %xmm0 ret
Drei Kopien, drei Multiplikationen und drei Additionen.
ArrayND ready to use ;)