Großer Zweidimensionaler Vector braucht ewig zur Freigabe
-
Moin moin
Ich habe ein kleines Problem in C++. Und zwar mache ich momentan eine FFT mit Bildern, d.h. ich transformiere die Pixelwerte eines Bildes in Schwingungen und wieder zurück. Dafür verwende ich das Library FFTW.
Bei der ganzen Sache kommt es nun dazu, dass ich mit sehr großen Vektoren arbeiten muss. Z.B. habe ich ein Ausgangsbild mit 14.000.000 Pixeln, was in einem Vektor mit genauso vielen Elementen bzw. Frequenzen resultiert. Der Vektor ist allerdings zweidimensional (vector<vector<double>>), da es sich um Komplexe Zahlen handelt (Realteil und Imaginärteil).
Der Algorithmus an sich funktioniert wunderbar, es wird alles richtig transformiert und am Ende kommt auch wieder mein Ausgangsbild raus. Das Problem ist nur, dass das Programm dann wenn es eigentlich terminieren sollte, nicht terminiert. Zumindest dauert es seeeehr lange Zeit, bis es das tut. Der Algorithmus an sich ist schon abgearbeitet, doch anscheinend braucht das Freigeben der Vektoren so lange. Woher ich das weiß? Ich habe das Programm während der Ausführung mal in Visual Studio pausiert, und in der Quelle geschaut, wo er gerade ist.
Zudem kann man in dieser Zeit geradezu im Taskmanager nachverfolgen, die der Speicher der von diesem Programm belegt wird kontinuierlich sinkt. Allerdings nur sehr langsam, das ganze dauert wesentlich länger, als die FFT an sich.Die komische Sache dabei: wenn ich das Programm in dieser Zeit in der es den Speicher freizugeben scheint per Klick auf das 'X' schließe, so terminiert es augenblicklich, und auch der belegte Speicher ist wieder freigegeben.
Das Problem besteht wohl hauptsächlich darin, dass ich, dadurch dass ich einen "zweidimensionalen" Vektor habe, insgesamt eine Unmenge an einzelnen Vektor-Objekten habe, die alle wieder zerstört werden müssen. Dies zeigt sich schon daran, dass das Erzeugen & Zerstören eines eindimensionalen Vektors mit 50 Millionen double-Werten kaum eine wahrnehmbare Zeit in Anspruch nimmt, aber das Erzeugen & Zerstören eines Vektors mit 100.000 Elementen, die jedoch wiederum je einen Vektor mit 2 Elementen enthalten, mehr als 10 Sekunden dauert.
Gibt es eine Möglichkeit das irgendwie zu beschleunigen, oder einen anderen Datentyp, der sich besser für den Inhalt (der immer aus genau 2 Elementen besteht) eignen würde?
-
Glücklicherweise enthält die C++-Standardlibrary exakt das, was du suchst!
Die Klasse complex dient zum arbeiten mit komplexen Zahlen, alle Operatoren sind bereits fertig überladen.
http://www.cplusplus.com/reference/std/complex/
-
Hey danke, werde ich sobald ich Zeit habe, also morgen, mal ausprobieren. Werde zwar wahrscheinlich so einige Funktionen umschreiben müssen, aber da kann man wohl nix machen
Was mir da gerade einfällt, es gab doch mal die STL-Klasse Pair, das ist doch fast das gleiche, nur ohne die Funktionen speziell für komplexe Zahlen.Hab mal kurz den Schnell-Test gemacht, geht anscheinend wirklich schneller. In das eigentliche Programm baue ich's dann demnächst mal ein, und berichte, ob sich die Situation verbessert hat.
-
Für lediglich zwei Elemente ist std::vector totaler Overkill.
Entweder Du nimmst float[2] oder Du befolgst Π14s Rat und nimmst std::complex; je nachdem ob Du schon alle benötigten Operatoren (effizient) implementiert hast, bzw. dir die von std::complex bereitgestellten behilflich sind.
-
Pair gibt es natürlich immer noch, allerdings denke ich, dass sich complex aufgrund der bereits vorhandenen Operationen besser eignet.
Übrigens ist es vermutlich deswegen schneller, weil std::vector intern selbst nochmal ein paar Byte per new alloziert. Bei complex<double> sind es 2 doubles, und das auf dem Stack. Stackallokationen sind viel schneller als Heapallokationen
-
14.000.000 complex auf dem Stack?
Sportlich!
-
314159265358979 schrieb:
Übrigens ist es vermutlich deswegen schneller, weil std::vector intern selbst nochmal ein paar Byte per new alloziert. Bei complex<double> sind es 2 doubles, und das auf dem Stack. Stackallokationen sind viel schneller als Heapallokationen
Wo die hinterher liegen, ist ja wohl Sache, wie die Variable an sich angelegt wurde. Wichtig ist der Unterschied, dass beim std::vector eine weitere Indirektion dazu kommt, die dem vector seine dynamischen Eigenschaften gibt. Und die bezahlt man hier, obwohl man die Dynamik gar nicht nutzt.
-
Caligulaminus schrieb:
14.000.000 complex auf dem Stack?
Sportlich!Wenn du sie in einen vector<> packst, landen sie trotzdem auf dem Heap - aber das Zerstören eines complex geht wesentlich schneller als das Zerstören eines (Unter)vector<>s
-
Im Großen und Ganzen genau das, was ich sagen wollte.
Ich maulfauler, ich...
-
CStoll schrieb:
Caligulaminus schrieb:
14.000.000 complex auf dem Stack?
Sportlich!Wenn du sie in einen vector<> packst, landen sie trotzdem auf dem Heap - aber das Zerstören eines complex geht wesentlich schneller als das Zerstören eines (Unter)vector<>s
Argh, natürlich. Kleiner Denkfehler
-
CStoll schrieb:
Caligulaminus schrieb:
14.000.000 complex auf dem Stack?
Sportlich!Wenn du sie in einen vector<> packst, landen sie trotzdem auf dem Heap - aber das Zerstören eines complex geht wesentlich schneller als das Zerstören eines (Unter)vector<>s
Vor allem als das Zerstören eines nicht-leeren (Unter)vector<>s.
Dann heisst es nämlich 14 Mio. mal "delete", und das kostet (dauert).
-
So, ich hab jetzt das komplette Programm umgeschrieben. Und es ist wundervoll, das Problem ist praktisch nicht mehr vorhanden. Und der Code erschließt sich sogar noch leichter, weil man sieht, dass mit komplexen Zahlen gerechnet wird.
Übrigens handelt es sich bei der ganzen Sache um ein Projekt hier an der Uni (Bauhaus Uni Weimar) an dem ich beteiligt bin. Und zwar geht es darum, gute analoge Photos mit guten digitalen Photos zu vergleichen, besonders in Bezug auf Auflösung in verschiedenen 'krummen' Abtastrichtungen (soll heißen, bei digitalen Bildern erreicht man nur bei horizontalen und vertikalen Signalen die volle Abtastung, schräge Linien etc. werden auf einer Koordinate viel geringer gesampled).
Und daher haben wir große Bilddateien, die Fourrier-transformiert werden. Momentan arbeite ich mit ersten Testbildern, am Ende kann's sein, dass wir Bilder mit 50 Millionen Bildpunkten haben. Da sollte das Programm schon einigermaßen performant sein^^
Die FFT mit den 14M Pixeln macht mein Laptop jetzt in 1,5min, das ist akzeptabel (jetzt wo die Dreiviertelstunde Vektor-wieder-freigeben wegfällt)
lg
Bastian
-
Das heißt, du machst professionelle Numerik und hast die FFT selber programmiert?
-
SeppJ schrieb:
Das heißt, du machst professionelle Numerik und hast die FFT selber programmiert?
Wenn ich es richtig verstanden habe benützt er die FFTW-Lib http://fftw.org/
-
VS braucht ewig um Speicher freizugeben, wenn man den Debug-Modus verwendet.
Also nur um sicher zu gehen: Auf "Release" kompiliert? Programm mit Strg+F5 gestartet ("ohne Debugging")?
-
Ja, das Programm lief schon im Release Modus.
Und nein, ich hab die FFT nicht selbst programmiert. Ich benutze das Library FFTW. Chen, ein Masterstudent mit dem ich im Rahmen dieses Projektes Kontakt hatte, der hat DFT, DCT und Wavelettransformation selbst programmiert. Mal schauen, vllt. kommt sowas auch mich auch noch irgenwann zu...
-
wronglyNeo schrieb:
Ja, das Programm lief schon im Release Modus.
Und nein, ich hab die FFT nicht selbst programmiert. Ich benutze das Library FFTW. Chen, ein Masterstudent mit dem ich im Rahmen dieses Projektes Kontakt hatte, der hat DFT, DCT und Wavelettransformation selbst programmiert. Mal schauen, vllt. kommt sowas auch mich auch noch irgenwann zu...
Meine Antwort wäre eher gewesen, dass es keinen guten Grund gibt, FFT selber zu programmieren und man dabei wahrscheinlich nur einen minderwertigen Abklatsch von FFTW & Konsorten bekommt.
-
wronglyNeo schrieb:
Ja, das Programm lief schon im Release Modus.
Bitte beide Fragen mit "ja" beantworten. Auch im Release Modus gibt es noch einen riesigen Unterschied zwischen "Starten" (F5) und "Starten ohne Debugging" (Strg+F5).
-
Hey, cool, das geht wirklich nochmal deutlich schneller. Die Transformation hat jetzt in ca. 20 Sekunden geklappt.
