C++Guns – RoboBlog

11.07.2018

C++ Guns: ArrayND multidimensionaler Container

Filed under: Allgemein — Tags: — Thomas @ 13:07

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 ;)

No Comments

No comments yet.

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress