Ähnliche Funktionen - Designfrage

Mechanics

Ist hier tatsächlich jede Nanosekunde wichtig? Das musst du schon wirklich wissen, bevor du mit Mikrooptimierungen anfängst.
Ansonsten kannst dir natürlich auch Zeiger auf die Felder übergeben, den Offset berechnet dir der Compiler.

Nexus

ThomasT schrieb:

Das Problem ist dass ich zwei rel. komplexe Funktionen habe, die fast völlig identisch arbeiten. Aber einmal mit den Datenfeld A und einmal mit B.
Beide völlig unabhängig und auch anders hinsichtlich des Ablaufs innerhalb der Funktion (mehrere Verzweigungen). Ein Zusammenfassen ist also nicht möglich.

Das widerspricht sich. Arbeiten sie nun fast identisch oder nicht? Kannst du ein Codebeispiel machen, das dein Problem repräsentiert (das in deinem ersten Post scheint es ja nicht zu tun)?

Grundsätzlich besteht natürlich auch die Möglichkeit darin, verschiedene Verhalten an die Funktion zu übergeben. Das kann klassisch über Strategy-Pattern implementiert werden, oder modern über std::function .

ThomasT schrieb:

Ich hatte erst alles mit STL-Containern gelöst und jetzt in ein Datenstruct-Array umgewandelt, was mittels Placement New erzeugt wird. (Geschwindigkeitssteigerung ca. Faktor 1000!!!)

Klingt so, als ob du die STL falsch angewendet hast oder im Debug-Modus gemessen hast. Wenn du std::vector nimmst und mit einer Grösse konstruierst, hast du im schlimmsten Fall ein paar Defaultkonstruktor-Aufrufe (damit diese Faktor 1000 ausmachen, muss ganz viel passieren). Wenn du aber reserve() benutzt, hast du das nicht. push_back() ist zwar auch nicht ganz gratis, aber bei Vorallokierung so gut wie.

Nexus schrieb:

ThomasT schrieb:

Ich hatte erst alles mit STL-Containern gelöst und jetzt in ein Datenstruct-Array umgewandelt, was mittels Placement New erzeugt wird. (Geschwindigkeitssteigerung ca. Faktor 1000!!!)

Klingt so, als ob du die STL falsch angewendet hast oder im Debug-Modus gemessen hast.

Er sagt placement new. Kann dann schon sein, da der ganze Memory-Overhead wegfällt.

@ThomasT: Darfst du C++11 verwenden? Dann wandle den Vorschlag von Mechanics in

template <typename F>
void processX(F f)
{
  //viel code
  f(xyz);
  //noch mehr code
}

um und rufe processX mit Lambda-Funktionen auf (z.B. processX([this](int a, int b){A[a] += b;});

Da Lambdas immer geinlined werden, sollte das genauso schnell sein wie dein ursprünglicher Code.

hustbaer

@ThomasT

ThomasT schrieb:

diese Idee spukte mir auch schon im Kopf rum: die getter-Methoden als function-pointer zu übergeben. Auch hier ist die Frage nach Performance wichtig. Kann ich nicht einschätzen.
Davon eine schmutzige Variante: Pointer auf Datenobjekt nehmen und Pointer auf konkretes Feld basteln. Und sozusagen den Offset übergehen.

Mach lieber die Funktion zu einem Template, und übergib den Teil mit den Unterschieden als Traits-Klasse:

struct ATraits
{
    static int GetAOrB(Foo& foo) { return foo.A; }
    static void CallFunction(Foo& foo) { foo.AFunction(); }
}

template <class TTraits>
void Foo::Fun()
{
   int x = TTraits::GetAOrB(this);
   if (x)
      TTraits::CallFunction(this);
}

Dadurch kann alles inline erweitert werden - Funktionszeiger und ähnliche Bremsen sind dann nicht notwendig.

hustbaer

statement placement schrieb:

Da Lambdas immer geinlined werden, sollte das genauso schnell sein wie dein ursprünglicher Code.

Krasse Behauptung. Glaub ich bloss nicht. Kannst du das belegen?

statement placement schrieb:

Er sagt placement new. Kann dann schon sein, da der ganze Memory-Overhead wegfällt.

Warum? Mit emplace() kannst du Objekte direkt in STL-Containern konstruieren. Wenn du dann noch 1000 Mal langsamer als Placement New bist, kannst du deine Standardbibliothek anzünden.

Nathan

ThomasT schrieb:

Hallo Nathan,

das geht schlecht. Ich habe ein Array von Daten-Objekten.

Ja, und?
Eines der unterschätztesten und fast nie angewendeten Features von C++ hilft hier: Zeiger auf Membervariablen:

#include <iostream>
using namespace std;

struct foo
{
	int a, b;
};

foo arr[3] = {foo{0, 1}, foo{0, 1}, foo{0, 1}};

void func(int foo::*member)
{
	for (auto el : arr)
		cout << el.*member << ' ';
}

int main() {
	func(&foo::a);
	cout << '\n';
	func(&foo::b);
}

http://ideone.com/NMHwXX
(Und sorry für die globale Variable. Kommt nicht wieder vor.)

Nathan schrieb:

Eines der unterschätztesten und fast nie angewendeten Features von C++ hilft hier: Zeiger auf Membervariablen:

Ist aber nicht sinnvoll im Bezug auf Datenkapselung. Du willst nicht von Implementierungsdetails wie Variablennamen (oder überhaupt deren Existenz) abhängig sein.

...wohl mit ein Grund, warum niemand Pointer-To-Member benutzt.

Nathan

OOPler schrieb:

Nathan schrieb:

Eines der unterschätztesten und fast nie angewendeten Features von C++ hilft hier: Zeiger auf Membervariablen:

Ist aber nicht sinnvoll im Bezug auf Datenkapselung. Du willst nicht von Implementierungsdetails wie Variablennamen (oder überhaupt deren Existenz) abhängig sein.
Ja

...wohl mit ein Grund, warum niemand Pointer-To-Member benutzt.

Das ist eher ein Grund sie zu benutzen!
Gut, da Variablen meistens eh private sein sollen, beschränk ich mich auf Funktionen.
Und da sind Pointer to Member nützlich.
Man muss nicht den Namen der Funktion wissen, sondern kann es einfach als Blackbox sehen, wo man Daten reinsteckt bzw. bekommt.
std::function abstrahiert das noch mehr.

ThomasT

Danke erstmal.

Ich denke die Version mit den Zeigern auf Member gefällt mir noch am besten.
Allerdings bastle ich noch, nicht so sehr quick, aber zumindeste dirty am Algorithmus selbst. So dass die saubere Implementierung noch warten wird ...

Zu STL-Design:

Ich bearbeite Bilder. Z.B. 1920x1080 Pixel groß.
Beim eigentlichen bearbeiten hatte ich die Infos in stl:maps gespeichert wobei der Key = x + y * Width ist. Infos waren mal floats, ints und structs.
Es werden nur ca. 5-10% aller Pixel überhaupt bearbeitet.
Dazu noch diverse std::vectors für z.B. Zwischenergebnisse.

Dann hatte ich radikal auf Arrays (von in int und float) von Width * Height Größe umgestellt. Schwubs ca. Faktor 1000. Nagelt mich nicht auf diesen Wert fest, aber was vorher mehrere Minuten gedauert hat, war nun innerhalb von weniger als einer Sekunde da.

Ich behaupte nicht die STL Lösung von oben wäre auch nur ansatzweise elegant oder hübsch gewesen. Es war dirty zum Algorithmus finden. Aber der Unterschied verblüffte dann doch. Momentan allokiere ich fast ein GB für die ganzen Ergebnisse.

Ich darf natürlich alles verwenden, da privat.
Hauptsache Visual C++. Unterstützt die neue Version schon C++11?
(Weil ich keine Lust habe später alles umzustricken, wenn daraus wieder ein Photoshop-Plugin wird oder Premiere-Plugin.)

Nexus

Was für Arrays? int i[1000] (statische) oder int* i = new int[1000] (dynamische)? Erstere sind äquivalent zum STL-Container std::array , letztere zum std::vector . Es gibt überhaupt keinen Grund, warum die STL langsamer sein sollte, wenn du richtige Szenarien vergleichst. Ich vermute, du hast irgendwas falsch angewandt oder z.B. im Debug-Modus getestet, wo die STL zur Fehlerfindung viele Laufzeitchecks (die Zeit kosten) durchführt.

Ich würde dir raten wieder die STL zu verwenden, da sie um einiges komfortabler und sicherer gegenüber Fehlern ist. Wie gesagt sollte sie nicht langsamer sein, im Gegenteil kannst du mit gezielter Containerwahl sogar Performance herausholen. Du kannst uns gerne den Code zeigen, vielleicht sehen wir eine falsche Anwendung darin. Und wie gesagt, stell sicher, dass du im Release-Modus kompilierst und allfällige Checks ausschaltest.

Ja, Visual Studio 2013 hat einen Grossteil der C++11-Features implementiert.

hustbaer

Was gefällt euch an der Template-Variante nicht? Ich würde hier nicht mit Member-Zeigern rummachen - schneller wird dadurch sicher nichts.

@Nexus
Wenn er 10% von 2 Mio. Pixeln in einer std::map verwaltet, dann wundert es mich gar nicht dass das langsam ist. Release hin oder her. Auch die Grössenordnung Faktor 1000 kann ich mir vorstellen.
Sollte doch irgendwo klar sein dass das sehr viel schneller geht wenn man einfach in ein Array reingreift (std::vector oder selbst verwaltet - egal), anstatt in einem Red-Black-Tree zu suchen. Und dann kommt natürlich noch der Aufwand für das Einfügen/Entfernen von Elementen dazu. Die ganzen dynamischen Speicheranforderungen (eine pro Pixel)... pfuh.

----

Was noch was bringen könnte - je nachdem wie das Zugriffsmuster des Algorithmus aussieht - wäre den Index anders zu berechnen. Also z.B.
index = (x & 31) + (y << 5) + ((x >> 5) * (Height << 5))
Die Spaltenbreite (32) ist jetzt einfach nur geraten - müsste man mit verschiedenen Werten probieren.