abgeleitete Objekte dynamisch in einen Vector speichern

Finnegan

@wob sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

@mawashi sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

@Finnegan : Ja genau, das wäre natürlich ein Traum, wenn man diese Vektor-/Matrixarithmetik so formulieren könnte wie man es händisch aufschreibt.

Schau dir vielleicht mal eine der LinAlg-Bibliotheken an, z.B. Eigen oder blaze oder oder...

Meines wissens sind die "grossen " Libs für Lineare Algebra auf riesige Matrizen dynamischer Größe ausgelegt, die vergleichbar mit einem std::vector im Speicher abgelegt sind. Für geometrische Probleme in 2D/3D braucht man aber meist nur Vektoren mit 2-4 Elementen und fast nur quadratische Matrizen in ebenfalls diesen Dimensionen. Diese Bibliotheken bringen daher für diesen Anwendungsfall wahrscheinlich eine Menge Performance-Overhead mit. Ich kann mir nicht vorstellen, dass Algorithmen, die für 1000x1000-Matrizen auf dem Heap optimiert sind, ihre Vorteile voll ausspielen können, wenn man die nur auf 4x4-Matrizen loslässt, die man mit nur einer handvoll SIMD-Operationen multiplizieren könnte.

Ich würde eine simplere Bibliothek mit flachen Vektoren und Matrizen (wie ein std::array) empfehlen. Ich kenne da nur GLM (ich selbst verwende für sowas eine eigene Implementierung). Das ist wahrscheinlich erstmal der bessere Ansatz, falls die "grossen" Libs das nicht auch als Extra unterstützen (denke aber eher nicht).

Eigen oder Blaze würde ich dann eventuell zusätzlich mit reinnehmen, wenn geometrische Probleme z.B. die Lösung von großen Gleichungssystemen erfordern oder die riesigen Matrizen anderweitig Sinn machen (z.B. wenn man auf einem Mesh in Adjazenzmatrix-Repräsentation arbeiten will).

TL;DR: BLAS et al. sind gut, aber für jedes Problem das passende Werkzeug. Für die hier im Thread geschilderten Probleme eher GLM, für weitere dann eventuell BLAS und Verwandte - wenn gerechtfertigt.

Schlangenmensch

@Finnegan Eigen behauptet zumindest, dass hinreichend kleine Vektoren / Matritzen intern einfache Arrays seien.

When should one use fixed sizes (e.g. Matrix4f), and when should one prefer dynamic sizes (e.g. MatrixXf)? The simple answer is: use fixed sizes for very small sizes where you can, and use dynamic sizes for larger sizes or where you have to. For small sizes, especially for sizes smaller than (roughly) 16, using fixed sizes is hugely beneficial to performance, as it allows Eigen to avoid dynamic memory allocation and to unroll loops. Internally, a fixed-size Eigen matrix is just a plain array,

wob

@Finnegan sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

Meines wissens sind die "grossen " Libs für Lineare Algebra auf riesige Matrizen dynamischer Größe ausgelegt

Natürlich, aber selbstverständlich auch für kleine!

Beispiel Eigen http://eigen.tuxfamily.org/dox/classEigen_1_1Matrix.html#fixedsize

Fixed-size versus dynamic-size:
Fixed-size means that the numbers of rows and columns are known are compile-time. In this case, Eigen allocates the array of coefficients as a fixed-size array, as a class member. This makes sense for very small matrices, typically up to 4x4, sometimes up to 16x16. Larger matrices should be declared as dynamic-size even if one happens to know their size at compile-time.

Dynamic-size means that the numbers of rows or columns are not necessarily known at compile-time. In this case they are runtime variables, and the array of coefficients is allocated dynamically on the heap.

Beispiel Blaze: https://bitbucket.org/blaze-lib/blaze/wiki/Vector Types

The blaze::StaticVector class template is the representation of a fixed size vector with statically allocated elements of arbitrary type.

Finnegan

@wob @Schlangenmensch Jo cool. Das war mir nicht bekannt. Schon was länger her dass ich mir diese Bibliotheken angesehen habe, und das waren auch nicht Eigen und Blaze.

In dem Fall gibts natürlich nichts daran auszusetzen, außer dass die Bibliothek je nach Anwendung eventuell etwas Overkill ist. Wichtig ist jedenfalls, dass nicht bei jeder kleinen Matrix eine zusätzliche Pointer-Indirektion stattfindet und man nicht die Algorithmen für die fetten Matrizen auf den Kleinen laufen lässt. Das sind schon andere Optimierungen die man hier braucht.

mawashi

Danke noch einmal für die Hinweise.
@wob : Du hast Recht was Python angeht. Ich hatte vergessen, dass die oft verwendete numpy-Bibliothek eben eine Bibliothek ist und nicht intrinsisch mitgeliefert wird.

Eigentlich dachte ich, dass ich mein Programm jetzt fertig habe. Leider klappt der (nun hoffentlich) letzte Schritt nicht... war ja auch nicht anders zu erwarten.
Ich möchte nämlich ein Objekt rve vom Typ RVE<2> an eine Funktion übergeben, die dann prüft ob Punkte innerhalb oder außerhalb der in rve liegen. Diese Punkte sind nur in dieser test_function verfügbar. Mein Versuch lautet dann wie folgt:

#include <iostream>

#include <numeric>
#include <vector>
#include <array>
#include <memory>

#include <math.h>
// HEADER
template<unsigned int spacedim>
class AbstractShape{
    public:
        std::array<double,spacedim> m;
        AbstractShape(std::array<double,spacedim> m); 
        // use virtual to make this function overloadable for every derived class/object
        // use keyword const to declare the return value not to be altered
        // use &-sign to give back a reference (avoid copying)
        // use keyword const at the end to indicate that this function cannot change a member variable of the class
        //     and makes it a compiler error if it would do so
        virtual const bool inside(const std::array<double,spacedim>& x) const = 0; 
        virtual const std::string& getType() const = 0;
        // use deconstructor to avoid problems connected to destroyed classes with pointers to the base class
        virtual ~AbstractShape() = default;
};

template<unsigned int spacedim>
class Circle : public AbstractShape<spacedim>{
    public:
        double r;
        Circle(std::array<double,spacedim> m,double r);
        // use keyword override to tell the compiler that we excpect to override a virtual method 
        // (this is just a safety feature that throws a compiler error if we are not overriding a virtual method at that stage)
        const std::string& getType() const override;
        const bool inside(const std::array<double,spacedim>& x) const override;
};

template<unsigned int spacedim>
class RVE{ // representative volume element with shapes
    public:
        std::vector<std::unique_ptr<AbstractShape<spacedim>>> shapes;
        void add_shape( std::unique_ptr<AbstractShape<spacedim>> shape );
        // const std::vector<unsigned int> indicator_arr( const std::array<double,spacedim>&  x ) const;
        const bool indicator_bool( const std::array<double,spacedim>&  x) const;
    private:
        
};

// DEFINITIONS
template<unsigned int spacedim>
AbstractShape<spacedim>::AbstractShape(std::array<double,spacedim> m){
    for(unsigned int i=0;i<spacedim;i++){
        this->m[i] = m[i];
    }
};

template<unsigned int spacedim>
Circle<spacedim>::Circle(std::array<double,spacedim> m,double r):AbstractShape<spacedim>(m){
    this->r=r;
};

template<unsigned int spacedim>
const std::string& Circle<spacedim>::getType() const{
    // use the keyword static to maintain this variable throughout the entire life of the objects life
    // Der wichtigere Punkt war, dass nicht jede Instanz diesen String hält, der eh immer gleich ist und nie geändert werden darf.
    static std::string s = "Circle";
    return s;
};

template<unsigned int spacedim>
const bool Circle<spacedim>::inside(const std::array<double,spacedim>& x) const{
    bool inside_flag;
    inside_flag = (this->m[0]-x[0])*(this->m[0]-x[0]) 
                 +(this->m[1]-x[1])*(this->m[1]-x[1]) - this->r*this->r <0.;
    return inside_flag;
};

template <unsigned int spacedim>
void RVE<spacedim>::add_shape( std::unique_ptr<AbstractShape<spacedim>> shape ){
    this->shapes.push_back( std::move(shape) );
}

template <unsigned int spacedim>
const bool RVE<spacedim>::indicator_bool(const std::array<double, spacedim>& x) const
{
    for (unsigned int i=0;i<this->shapes.size();i++){
        if (this->shapes[i]->inside(x)){
            return true;
        }
    }
    return false;
};

// MAIN-PROGRAMM
template<int spacedim>
void test_function( RVE<spacedim> rve ){
    std::cout << rve.shapes.size() << "\n";
}

int main(){
    const unsigned int dim=2;
    double r1 = 0.25;
    std::array<double,dim> m1{0.0,0.0};
    std::vector<std::vector<double>> points{ {-0.03,0.06}, 
                                             { 0.5,0.45 } };
    RVE<dim> rve;
    rve.add_shape( std::make_unique<Circle<dim>>( std::array<double,dim>{0.0,0.0} ,r1) );
    rve.add_shape( std::make_unique<Circle<dim>>( std::array<double,dim>{0.1,0.1} ,r1) );
    test_function( rve );
};

Zeile 108 macht hier Probleme, wobei ich denke, dass das Problem in der ursprünglichen Funktionsdefinition liegt. Habt ihr Vorschläge?

Th69

Verwende unsigned int spacedim als Template-Parameter.
Außerdem verwende const RVE<spacedim> &rve als Parameter der Funktion (damit keine Kopie erforderlich ist).

mawashi

@ Th69 : danke! das mit dem unsigned int spacedim war ein unnötiger Fehler Aber warum zur Hölle wird das & benötigt? Das ein Programm bei Übergabe von lediglich der Referenz und nicht einer Kopie effizienter läuft leuchtet mir ein. Aber warum ist es hier an dieser Stelle notwendig?

Finnegan

@mawashi sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

@ Th69 : danke! das mit dem unsigned int spacedim war ein unnötiger Fehler Aber warum zur Hölle wird das & benötigt? Das ein Programm bei Übergabe von lediglich der Referenz und nicht einer Kopie effizienter läuft leuchtet mir ein. Aber warum ist es hier an dieser Stelle notwendig?

Streng "notwendig" ist es nicht, aber RVE hat doch den Member std::vector<std::unique_ptr<AbstractShape<spacedim>>> shapes. Der wird bei einer By Value-Übergabe komplett mitkopiert: n mal Speicher reservieren für die std::unique_ptr, dann für jedes AbstractShape je einmal Speicher reservieren für die Objekte, plus Objekte konstruieren... und am Ende alles nochmal rückwärts - n Destruktoren aufrufen, n mal Speicher freigeben und schliesslich den Speicher für die std::unique_ptr freigeben. Das würde ich aus dem Bauch schon als schwergewichtig genug einschätzen, um eine Referenz zu rechtfertigen

Bei den std::array<double, spacedim>-Parametern hast du schliesslich auch eine Referenz verwendet... und da wäre es nicht unbedingt nötig, die paar doubles machen da keinen Unterschied. Die werden je nach Compiler-Optimierungen wahrscheinlich sogar alle in einem (SIMD-) Register an die Funktion übergeben.

Natürlich kann man argumentieren, dass es "nur ne blöde Testfunktion" ist, aber es ist vielleicht nicht verkehrt, wenn man weiss, welches "Gewicht" die verschiedenen Typen haben und man bei Objekten einer gewissen Größe intuitiv zur Referenz greift.

wob

@Finnegan sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

Der wird bei einer By Value-Übergabe komplett mitkopiert: n mal Speicher reservieren für die std::unique_ptr (...) Das würde ich aus dem Bauch schon als schwergewichtig genug einschätzen, um eine Referenz zu rechtfertigen

Ich würde es vor allem deshalb als notwendig einschätzen, weil unique_ptr NICHT kopierbar sind. Ein unique_ptr hat schlicht keinen copy-Konstruktor. Dazu brauche ich keinen Bauch

mawashi

Danke für die Erklärung. Das bringt mir noch einmal einiges an Verständnis.
Tatsächlich ist das & nötig, da der Code sonst nicht kompiliert.

Ansonsten danke noch an Alle. Vorerst läuft mein Program, hauptsächlich getrieben durch eure Hilfe. Ohne euch hätte ich die Kniffe so wohl nicht herausgefunden.

Finnegan

@wob sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

Ich würde es vor allem deshalb als notwendig einschätzen, weil unique_ptr NICHT kopierbar sind. Ein unique_ptr hat schlicht keinen copy-Konstruktor. Dazu brauche ich keinen Bauch

Hah! Stimmt ja ... ist aber vielleicht angebracht irgendwann mal Kopieroperationen für RVE zu implementieren, je nachdem wie man die Klasse verwenden will. "Geometrie kopieren" kann ja durchaus nützlich sein. Und dann kann man sich wieder an meine Argumentation erinnern .

wob

@Finnegan sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

Hah! Stimmt ja ... ist aber vielleicht angebracht irgendwann mal Kopieroperationen für RVE zu implementieren, je nachdem wie man die Klasse verwenden will. "Geometrie kopieren" kann ja durchaus nützlich sein.

Stimmt, aber ob das immer tiefe Kopien sein müssen? Gerade wenn man viele Objekte hat, kann das schnell zu viel Speicherbedarf führen. Es kann durchaus eine gute Idee sein, die Objekte unveränderbar zu machen und bei Änderungen einfach neue Objekte zu erzeugen. Dann wird das Kopieren eine einefache Operation, weil man nur noch die Referenz / den Pointer kopieren muss.

Aber hängt sicher vom Problem und der Datenmenge ab.

Finnegan

@wob sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

@Finnegan sagte in abgeleitete Objekte dynamisch in einen Vector speichern:

Hah! Stimmt ja ... ist aber vielleicht angebracht irgendwann mal Kopieroperationen für RVE zu implementieren, je nachdem wie man die Klasse verwenden will. "Geometrie kopieren" kann ja durchaus nützlich sein.

Stimmt, aber ob das immer tiefe Kopien sein müssen? Gerade wenn man viele Objekte hat, kann das schnell zu viel Speicherbedarf führen.
[...]
Aber hängt sicher vom Problem und der Datenmenge ab.

Ja, stark problemabhängig. Mir schwebte eher sowas vor wie eine Editoroperation vor: Gruppe Kreise kopieren und die dann an eine andere Position verschieben. Radius und relative Positionen bleiben, aber es können nicht exakt die selben Objekte sein, da ihre absolute Position eine andere sein muss.

Es kann durchaus eine gute Idee sein, die Objekte unveränderbar zu machen und bei Änderungen einfach neue Objekte zu erzeugen. Dann wird das Kopieren eine einefache Operation, weil man nur noch die Referenz / den Pointer kopieren muss.

Das kann Sinn machen, wenn man allerdings so wie es derzeit mit unique_ptr umgesetzt istRVE überhaupt kopierbar machen will, dann ist natürlich als tiefe Kopie. Andernfalls vector<shared_ptr> oder (etwas haarig, aber auch eine Option, wenn man weiss was man tut) vector<reference_wrapper>.