[] vs. vector<>

Sorry volkard, aber als "Katzensprung" würde ich das nicht bezeichnen :|
(Mit der folgenden Frage krieg ich bestimmt wieder Haue...)

@volkard: Nun habe ich noch ein Problem: wenn ich deine Klasse nehme und z.B. folgende Klassenmethode (abgekürzt) habe:

void f(const FastArray2d<float>& feld){
    anderes_feld[0][0] = feld[0][0];
}

... dann kommt folgender Compiler-Fehler:

feld.cpp: passing `const FastArray2d<float>' as `this' argument of `FastArray2d<T>::Proxy FastArray2d<T>::operator[](unsigned int) [with T = float]

Dabei sei anderes_feld ein Attribut der Klasse, ebenfalls als FastArray2d<float> realisiert.

Vielleicht ist's ja ein einfacher Fehler, aber ich kann damit nichts anfangen - habe zwar schon versucht herauszufinden was denn das Problem ist, komme aber selbst nach langem Überlegen nicht drauf
Macht der mit der Referenz Probleme? Wäre für mich das Naheliegendste, aber wie kann man das dann als Referenz realisieren?

Danke für alles, Matze

volkard

Guest1 schrieb:

Vielleicht ist's ja ein einfacher Fehler, aber ich kann damit nichts anfangen - habe zwar schon versucht herauszufinden was denn das Problem ist, komme aber selbst nach langem Überlegen nicht drauf

das liegt am const.

meine klasse ist noch gar nicht fertig.
und zwar muß eine funktion als const deklariert werden, wenn sie auf const-objekte aufrufbar sein soll. das const-deklarieren der funktion verspricht, daß man das objekt nicht ändern kann.
ich mach zuerst nur Array korrekt, damit die hopser überschaubar bleiben.

template<typename T>
class Array{
private:
    T* data;
    Array(Array const&);
    Array& operator=(Array const&);
public:
    Array(size_t size){
        data=new T[size];
    }
    ~Array(){
        delete[] data;
    }
    T& operator[](size_t index) const{
        return data[index];
    }
};

so, jetzt kann man ein const Array benutzen und damoit den op[] aufrufen.
aber moment mal, das ist ja unfug. dann bringt return data[index]; auch nur ne referenz auf const T und da müßte es nen compilerfehler geben.
und der anwender darf ja auch nicht

const Array<int> a(10);
a[5]=7;

schreiben.

ich mach die rückgabe auch mal const.

template<typename T>
class Array{
private:
    T* data;
    Array(Array const&);
    Array& operator=(Array const&);
public:
    Array(size_t size){
        data=new T[size];
    }
    ~Array(){
        delete[] data;
    }
    T const& operator[](size_t index) const{
        return data[index];
    }
};

so, jetzt geht's.

const Array<int> a(10);
a[5]=7;//fehler
cout<<a[5];//ok

aber toll wäre es, wenn die alte funktionalität auch da wäre. und das geht sogar. man bietet einfach beide versionen des op[] an.

template<typename T>
class Array{
private:
    T* data;
    Array(Array const&);
    Array& operator=(Array const&);
public:
    Array(size_t size){
        data=new T[size];
    }
    ~Array(){
        delete[] data;
    }
    T const& operator[](size_t index) const{
        return data[index];
    }
    T& operator[](size_t index){
        return data[index];
    }
};

jetzt liefert der op[] entweder T& oder T const&, je nachdem, ob man ein Array oder const Array verwendet hat.

und den rest stelle ich mir so vor:

template<typename T>
class FastArray2d{
private:
    size_t shift;
    Array<T> data;
public:
    FastArray2d(size_t sizey,size_t sizex):
        shift(roundedUpLog2(sizex)),
        data(sizey<<shift){
    }
    struct ProxyConst{
        FastArray2d const* array;
        size_t y;
        ProxyConst(FastArray2d const* _array,size_t _y):
        array(_array),
        y(_y){
        }
        T const& operator[](size_t x){
            return array->at(x,y);
        }
    };
    ProxyConst operator[] const(size_t y){
        return ProxyConst(this,y);
    }
    T const& at const(size_t y,size_t x){
        return data[(y<<shift)+x];
    }
    struct Proxy{
        FastArray2d* array;
        size_t y;
        Proxy(FastArray2d* _array,size_t _y):
        array(_array),
        y(_y){
        }
        T& operator[](size_t x){
            return array->at(x,y);
        }
    };
    Proxy operator[](size_t y){
        return Proxy(this,y);
    }
    T& at(size_t y,size_t x){
        return data[(y<<shift)+x];
    }
};

ist aber ganz ungetestet. wenn was nicht geht, und der fehler sich dir nicht zeigt, frag wieder, dann hab ich mich bestimmt vertippt.

Ok, die Klasse funzt, vielen vielen Dank...
Du hattest bloß bei den const-Methoden für operator[] und at() das const vor statt nach dem Funktionsnamen geschrieben, ansonsten war alles ok. Achja: der Compiler meckert beim Copy-Konstruktor für Array, dass er private ist. Hab erstmal auskommentiert, dürfte in diesem Kontext nichts machen.

Trotzdem scheint die Klasse noch langsam zu sein. Schreibe ich nativ mit zwei Zeigern auf float, dann ist's halt unschlagbar schnell. Das Problem ist: auch wenn ich das Ganze gern objektorientiert machen wöllte kommt es eigentlich primär auf Geschwindigkeit an - daher ist es am Ende vielleicht doch das Beste float** zu lassen, auch wenn es nicht sehr schönen Code ergibt.

Ich würde es ja gern anders machen nur wenn's dann halt viel langsamer ist nützt die ganze schöne Implementierung nichts...

volkard

Guest1 schrieb:

Trotzdem scheint die Klasse noch langsam zu sein.

um wieviel langsamer genau?

und hast du auch bestimmt die optimierungen im compiler angemacht?

Schreibe ich nativ mit zwei Zeigern auf float, dann ist's halt unschlagbar schnell.

ich kenne den rest des programms nicht. ich weiß nicht, wie die zugriffe verteilt sind. unschalgbar ist sehr selten.

Das Problem ist: auch wenn ich das Ganze gern objektorientiert machen wöllte kommt es eigentlich primär auf Geschwindigkeit an

das ist in c++ kein problem. man kann total abstrahieren und zahlt null kosten dafür. ich bevorzuge speed auch, und zwar so schlimm, daß ich auch mal vier wochen meiner freizeit opfere, nur um eine schnelle datenstruktur zu schreiben.

- daher ist es am Ende vielleicht doch das Beste float** zu lassen, auch wenn es nicht sehr schönen Code ergibt.

kann nicht sein.

Ich würde es ja gern anders machen nur wenn's dann halt viel langsamer ist nützt die ganze schöne Implementierung nichts...

es wird zeit, daß ich deinen code sehe.

wo wir gerade so fein dran sindm erinnere ich nochmal an
[quote=volkard]und wenn die auch lahmer ist als rohe float**, dann packen wir einfach mal die float** in die Matrix-klasse und besorgen uns damit wenigstens das schöne automatische delete und müssen nicht mehr immer ** schreiben. [/quote]
und schreibe

template<typename T>
class FastArray2d{
private:
    T** data;
	size_t sizey;
	FastArray(FastArray const&);
	FastArray operator=(FastArray const&);
public:
    FastArray2d(size_t sizey,size_t sizex):
		sizey(_sizey){
		for(size_t y=0;y<sizey;++y)
			data[y]=new T[x];
    }
	~FastArray2d(){
		for(size_t y=0;y<sizey;++y)
			data[y]=new T[x];
	}
	//Proxys unverändert
    T& at(size_t y,size_t x){
        return data[y][x];
    }
    T const& at(size_t y,size_t x) const{
        return data[y][x];
    }
};

du jetzt die möglichkeit, alle varianten, die dir so einfallen, auszuprobieren. und so ein einfacher wrapper um float** kostet auch null performance, weil alles inline ist und der compiler das alles wegoptimiert, so daß am ende nur ein float** übrigbleibt.

Sieht mir nach nem Copy&Paste-Fehler im Destruktor aus, oder?
Ich werde das mit der Klasse über float** trotzdem mal probieren, dass soviel Speed verloren geht kann da eigentlich nicht sein...
Ich probier's erstmal aus, mal schauen wenn ich fertig bin.

Bis dann und danke nochmals, Matze

@volkard: die Geschwindigkeit mit Hilfe deiner Klasse (mit Array<T>) im Gegensatz zu vorher ist immernoch um 300% langsamer als wenn man gleich als Klassenattribut im Neuronalen Netz float** nimmt. Der Hauptgrund dürfte wohl auch sein dass ich eine Instanz der 2D-Matrix-Klasse als Zeiger definieren muss, weil es als Klassenattribut nicht geht. Grund dafür sind die Dimensionen des Neuronalen Netzes, welche den Konstruktoren nicht immer als Parameter übergeben werden können, sondern z.B. in den Konstruktoren erst gelesen werden (z.B. von Datei).

Stimmst du mir zu, dass darin das Problem begründet ist? Schließlich muss ich ja auch bei jedem Zugriff auf ein Matrixelement eine Dereferenzierung machen, z.B. mit "(*matrix)[i][j]"...

float** in ne eigene Klasse zu packen habe ich noch nicht ausprobiert, es dürfte aber nicht viel bringen IMHO.

Btw: du hattest oben bei der Implementierung von FastArray2d einen kleinen Fehler drin. Beim Aufruf von at() in Proxy hast du die Parameter x und y vertauscht. Ist mir nur beim näheren Hingucken und nach ein paar unschönen Abstürzen aufgefallen

volkard

Guest1 schrieb:

@volkard: die Geschwindigkeit mit Hilfe deiner Klasse (mit Array<T>) im Gegensatz zu vorher ist immernoch um 300% langsamer als wenn man gleich als Klassenattribut im Neuronalen Netz float** nimmt. Der Hauptgrund dürfte wohl auch sein dass ich eine Instanz der 2D-Matrix-Klasse als Zeiger definieren muss, weil es als Klassenattribut nicht geht.

wie gesagt, ich habe deinen code noch nicht gesehen und muss raten, was effizient aussieht.

Grund dafür sind die Dimensionen des Neuronalen Netzes, welche den Konstruktoren nicht immer als Parameter übergeben werden können, sondern z.B. in den Konstruktoren erst gelesen werden (z.B. von Datei).

man kriegt sowas auch hin. wird aber kompliziert. oder man schaufelt eine nachlässigkeit zur anderen und macht statt des konstruktors der array-klasse eine init-funktion. oder man baut nen default-ctor. jo, warum nicht?

FastArray2d():
		sizey(0),
		data(0){
    }
    FastArray2d(size_t sizey,size_t sizex):
		sizey(_sizey),
		data(new (*T)[_sizey]){
		for(size_t y=0;y<sizey;++y)
			data[y]=new T[x];
    }

hmm. nen zuweisungsoperator und nen kopierkonstruktor braucht der mensch dann auch noch.

Stimmst du mir zu, dass darin das Problem begründet ist?

nein. und das werde ich auch so schnell nicht. objektorientierung mit c++ erzeugt keinen overhead gegenüber c ohne oo.

was mich wundert, ist daß eine dereferenzierung so teuer ist. immerhin hast du in [][] bereits zwei davon.

Schließlich muss ich ja auch bei jedem Zugriff auf ein Matrixelement eine Dereferenzierung machen, z.B. mit "(*matrix)[i][j]"...

jo, das sind schlimme kosten.

float** in ne eigene Klasse zu packen habe ich noch nicht ausprobiert, es dürfte aber nicht viel bringen IMHO.

stimmt. außer mit obiger anpassung.

Btw: du hattest oben bei der Implementierung von FastArray2d einen kleinen Fehler drin. Beim Aufruf von at() in Proxy hast du die Parameter x und y vertauscht. Ist mir nur beim näheren Hingucken und nach ein paar unschönen Abstürzen aufgefallen

*grins*. war keine absicht.

Danke für den Tipp mit dem Default-Konstruktor und Zuweisungsoperator. Habe jetzt die Version mit T** so implementiert, das Ergebnis ist trotzdem nicht befriedigend.

Statt 18s wie bei float** braucht der Algorithmus 50s - das ist zwar schneller als mit slices/valarrays, aber immer noch bedeutend langsamer. So langsam vergeht mir die Lust zu grübeln woran es liegt, Im Moment nehme ich mir einfach Zeit dafür, die ich eigentlich gar nicht habe und wenn dann nichts dabei rauskommt ist es noch frustrierender...

Ich frage mich zwar immernoch, wo diese Zeit liegen gelassen wird, doch das kann ich wohl erst durch Profiling klären - vielleicht lässt sich dann mehr erkennen...

Bevor du Tage lang im Dunkeln stocherst solltest du dir im klaren sein
wo dein Performance-Problem liegt, alles andere ist sinnlos.

Hier gibts nen guten Profiler für 21 Tage zum Ausprobieren:
http://www.glowcode.com/eval.htm
allerdings Windows only !!

@Redhead: hatte doch eben geschrieben, dass ich Profiling machen werde.

Und das habe ich auf die Schnelle auch mal gemacht.
Das Ergebnis bestätigt für mich, dass die Geschwindigkeit durch die Matrix-Klasse verloren geht.

Und zwar sieht es so aus: in der Funktion Backprop() findet das Anlernen des Neuronalen Netzes statt (zum Teil).
In dieser Funktion wird nichts weiter gemacht als ein paar arithmetische Operationen mit Matrizen und Vektoren (*/+-).

Profiling mit float** erbrachte, dass das Programm 66% der Zeit in dieser Funktion verbracht hat und dabei 11s verbraucht wurden.
Bei Verwendung von "Fast2DArray" mit T** und "Array" brauchte das Programm 79% seiner Zeit für Backprop() und 39s!

Ein ganz schön niederschmetterndes Ergebnis wie ich finde, aber ich verstehe immernoch nicht WARUM es zu diesen Unterschieden kommt.

Bei Bedarf/Interesse kann ich den Code von Backprop() oder Bilder des Profilings mal posten.

volkard

Guest1 schrieb:

Danke für den Tipp mit dem Default-Konstruktor und Zuweisungsoperator. Habe jetzt die Version mit T** so implementiert, das Ergebnis ist trotzdem nicht befriedigend.

Statt 18s wie bei float** braucht der Algorithmus 50s

du mißt falsch. das ist hiermit sicher. da komme ich mir doch veralbert vor.

ich sag nix mehr, bis ich deinen falschen messcode hab.

b7f7

@Guest nur mal so, du kompilierst auch release?

Was heißt denn hier "falscher Messcode"? Ich komme mir ja selber vom DevCpp veralbert vor, dass er so lange mit der Klasse und so kurz mit float** braucht - da kann ich auch nix für!

Kompiliert natürlich als release...

[] vs. vector&lt;&gt;

[] vs. vector<>