[CPP in VS] Array auslagern und vorkompilieren

knivil

Man darf eine includierte Datei anscheinend nicht zum Projekt hinzufügen

Plonk

Microsofts Projektmanagement war mir schon immer ein Buch mit vielen Siegeln.

Doppelplonk

#include "blubb.asm" tut es nicht, der MASM fühlt sich davon nicht angesprochen

...

Ich habe KEINE Ahnung was MFC, etc. bedeutet. Wie ich schon sagte - Hochsprachen sind nicht so meins.

Ich werde mal folgenden Plan verfolgen: das Array in die Sort-Funktion einfügen, die ASM-Datei generieren, die DATA-Definition des Arrays in ein Makro auslagern und als array.inc oder array.lib einbinden.

Bashar

devcon schrieb:

Also habe ich mir kurzerhand eine txt-Datei mit 40x2000 zufallsgenerierten INT-Werten in Array-Syntax vollschreiben lassen, um eine messbare Ausführzeit des Sortier-Algos zu erhalten. Problem an der Sache: der olle VS-Compiler doktort 7 Minuten an dem Array herum, obwohl er beim Kompilieren lediglich eine gigantische Folge von MOV-Befehlen aneinanderreihen muss. Das sollte inkl. Adressberechnung normalerweise in unter 10 Sekunden erledigt sein.

Der gcc macht das in einer Sekunde. Wahrscheinlich auch der VC, ich zweifle deine Aussage an, bis das jemand anders bestätigt. Dazu sind mir zuviele unlogische Ungereimtheiten in deinem Posting: Sortieren ausschließlich in Registern? 80000 Elemente = fett? Man muss unbedingt 999mal dasselbe Array sortieren, eine neue Kopie des Originals machen geht nicht? Man muss unbedingt alles vordefinieren, per Zufall zur Laufzeit erzeugen geht nicht? etc.

Das Array selbst liegt natürlich nicht in den Registern sondern im RAM aber sämtliche Variablen, die per default im RAM liegen, habe ich in Register ausgelagert. Bringt immerhin doppelte Geschwindigkeit.

Für die Ungläubigen:

Main-File mit 80k-Array: http://pastebin.com/91ZLBNvA
Sort-File für ein 80k-Array: http://pastebin.com/raXyAr5w

VS2012 braucht dafür gut 7 Minuten.

Um Bashars Fragen zu beantworten: nein, nein, nein und nein. Wie ich oben schon schrieb, muss der Algorithmus die ganze Zeit sortieren. Es gilt, den Algorithmus auf Assembler-Ebene zu optimieren (Register-Renaming, Loop-Unrolling, Pipelining, etc.) Das Array nach dem sortieren immer wieder neu zu füllen ginge theoretisch auch aber praktisch ist clock() einfach zu langsam für kleine Arrays. Bei 2000 Elementen kriege ich eine Sortier-Laufzeit von 0. Es muss also ein großes Array her.

knivil

Da wir hier bei C++ sind, wie sieht den die Laufzeit gegenueber std::sort aus? Btw. Optimierung anschalten.

80k-Array ... VS2012 braucht dafür gut 7 Minuten.

Du machst garantiert was falsch. Dein Algorithmus sieht eher nach Bubblesort aus.

Ist aber Selectionsort Mein Algo steht hier aber auch nicht zur Debatte.

Das mit der Optimierung probiere ich mal, hoffentlich kann man die auch auf 1 Datei (in meinem Falle die main.cpp) beschränken, da ich die ASM-Datei manuell optimieren soll.

knivil

Mein Algo steht hier aber auch nicht zur Debatte.

Noe, es bringt nur nichts, eine Algorithmus mit O(n^2) auf Assemblerebene zu optimieren, wenn sortieren in O(n log n) geloest werden kann. Manche wuerde zu deinem Vorhaben sagen: dumm. Genau wie viele andere deiner Bemerkungen. Trolle gibt es hier genug.

merano

devcon schrieb:

Das Array nach dem sortieren immer wieder neu zu füllen ginge theoretisch auch aber praktisch ist clock() einfach zu langsam für kleine Arrays. Bei 2000 Elementen kriege ich eine Sortier-Laufzeit von 0. Es muss also ein großes Array her.

Ein Feld mit memcopy zu kopieren sollte kein Problem sein ..

Tatsächlich tut sich Visual-Studio schwer Code mit so einem riesigen
lokalen Variablenfeld zu linken. Muss das lokal sein ?

Nach dem kompilieren wird es direkt vom Virenscanner (F-Secure) einkassiert.
Besser abschalten; beim Messen könnte er ohnehin stören.

Wenn die Zeitmessung genauer sein soll würde ich einen Systemaufruf statt
einem (ANSI-) Bibliotheksaufruf verwenden.

Unter Windows z.B.

http://msdn.microsoft.com/en-us/library/windows/desktop/ms644904.aspx

Ich würde zudem auch empfehlen die Prozess und Thread Priorität deutlich zu erhöhen.

Als Ergebnis im Release-Mode (in der Konsole gestartet) kommt bei mir nun

"Die Zeit fuer 80.000 Elemente betraegt: 1.783840 sec."

Bei Deiner Version mit clock kommt dagegen nur 1 sek raus.

Bemerkung zur Ausgabe:

thou  = (time2-time1) * 1000 / CLOCKS_PER_SEC;
	sec   = thou / 1000;
	thou -= sec * 1000;
	printf ("\nDie Zeit fuer 80.000 Elemente betraegt: %ld.%09ld sec.\n\n", sec, thou,"\n");

Mit der integer Division kommt offensichtlich nicht das richtige Ergebnis raus.

Zudem ist es nicht üblich einen "int" mit %ld auszugeben.

Das zusätzliche "\n" am Ende des printf Aufrufs auch ist Unsinn.

Warum nicht double ?

double sec2  = (double)(time2-time1) / CLOCKS_PER_SEC;
	printf ("\nDie Zeit fuer 80.000 Elemente betraegt: %f sec.\n", sec2);

Das Ergebnis ist dann ähnlich zu meiner Version.

knivil schrieb:

Mein Algo steht hier aber auch nicht zur Debatte.

Noe, es bringt nur nichts, eine Algorithmus mit O(n^2) auf Assemblerebene zu optimieren, wenn sortieren in O(n log n) geloest werden kann. Manche wuerde zu deinem Vorhaben sagen: dumm. Genau wie viele andere deiner Bemerkungen. Trolle gibt es hier genug.

Und trotzdem lautet so die Aufgabenstellung - ob wir es toll finden oder nicht, ich muss es erledigen. Hierbei geht es auch nicht darum, den Algorithmus mathematisch zu optimieren sondern um die Assembler-Kniffe und Dinge wie Loop-unrolling und Pipeline-Optimierung (erstes fällt bei meinem Code natürlich flach). Nächstes mal bin ich mit Details sparsamer, ist ja kaum auszuhalten ...

@merano danke für den Hinweis, werde ich mich morgen mal ransetzen! *thumbup*

merano schrieb:

devcon schrieb:

Das Array nach dem sortieren immer wieder neu zu füllen ginge theoretisch auch aber praktisch ist clock() einfach zu langsam für kleine Arrays. Bei 2000 Elementen kriege ich eine Sortier-Laufzeit von 0. Es muss also ein großes Array her.

Ein Feld mit memcopy zu kopieren sollte kein Problem sein ..

Doch weil ich ja das Feld vorm erneuten Betreten des Algorithmus neu schreiben müsste. Die gemessene (Gesamt)Zeit darf aber ausschließlich die Laufzeit des Algorithmus beinhalten, keine weiteren Befehle, die nicht zum Algorithmus gehören.