Code Effizienz

Danny92

@Arcoth
Das läuft allerdings nochmal um einiges schneller, allerdings ist die Ausgabe noch nicht so schön in Tabellenform, und vor allem kommen da bei mir bei hinreichend großer grenze>10000 nur noch kryptische Zeichen in der Primes.txt.

Columbo

manni66 schrieb:

vector<bool> ist eine spezielle platzsparende Implementation, dürfte aber langsamer als "normale" vectoren xein.

Wie kommst du darauf?

Columbo

Danny92 schrieb:

@Arcoth
Das läuft allerdings nochmal um einiges schneller, allerdings ist die Ausgabe noch nicht so schön in Tabellenform, und vor allem kommen da bei mir bei hinreichend großer grenze>10000 nur noch kryptische Zeichen in der Primes.txt.

Kann ich nicht nachvollziehen. Hört sich auch merkwürdig an.

Danny92

@Arcoth
Ist aber leider so. Bis 1259 funktionierts, ab grenze>=1260 kommt bei mir leider sowas:
′″‵‷ㄱㄠ″㜱ㄠ‹㌲㈠‹ㄳ㌠‷ㄴ㐠″㜴㔠″㤵㘠‱㜶㜠 .............

Danny92 schrieb:

Ja in der Konsole mit:
g++ -std=c++11 -Wall -o main main.cpp

Ja, da hast du ja deinen Grund. Ohne Optimizer wird das nichts. Benutze -O (das ist ein großes Oh)!

Arcoth schrieb:

Der naivste Blödsinn läuft mehr acht mal schneller als dein Pascal Program (1.2s, Clang -O4 -march=native )

Ohne Vergleich eurer PCs macht diese Angabe wenig Sinn.

Arcoth schrieb:

manni66 schrieb:

vector<bool> ist eine spezielle platzsparende Implementation, dürfte aber langsamer als "normale" vectoren xein.

Wie kommst du darauf?

Wenigstens das Platzsparend stimmt. Geschwindigkeit mag ich ohne vorherigen Test nichts zu sagen. Könnte mir aber schon vorstellen das es langsamer ist (shiften der Bits an die richtige Stelle, alte Daten lesen, Bits maskieren und das richtige Bit löschen, Daten zurück schreiben)

Columbo

sebi707 schrieb:

Arcoth schrieb:

Der naivste Blödsinn läuft mehr acht mal schneller als dein Pascal Program (1.2s, Clang -O4 -march=native )

Ohne Vergleich eurer PCs macht diese Angabe wenig Sinn.

Ich habe eine HDD und einen relativ alten i7 (2013). Sollte also nicht schneller als sein System sein.

Könnte mir aber schon vorstellen das es langsamer ist (shiften der Bits an die richtige Stelle, alte Daten lesen, Bits maskieren und das richtige Bit löschen, Daten zurück schreiben)

Was ist mit Caching? Jedenfalls läuft vector<bool> etwa 3/4 mal so lang wie vector<char> .

Danny92 schrieb:

@Arcoth
Ist aber leider so. Bis 1259 funktionierts, ab grenze>=1260 kommt bei mir leider sowas:
′″‵‷ㄱㄠ″㜱ㄠ‹㌲㈠‹ㄳ㌠‷ㄴ㐠″㜴㔠″㤵㘠‱㜶㜠 .............

Was passiert, wenn du dir das ganze parallel auf der Konsole ausgeben lässt?

SeppJ

sebi707 schrieb:

Wenigstens das Platzsparend stimmt. Geschwindigkeit mag ich ohne vorherigen Test nichts zu sagen. Könnte mir aber schon vorstellen das es langsamer ist (shiften der Bits an die richtige Stelle, alte Daten lesen, Bits maskieren und das richtige Bit löschen, Daten zurück schreiben)

Wir hatten hier im Forum auch schon öfters Programmbeispiele, bei denen die bessere Platzeffizienz (-> Weniger Hauptspeicherzugriffe!) dies mehr als wett macht. Und natürlich auch Beispiel für den von dir beschriebenen Effekt. Kann man so pauschal also nicht behaupten, dass eines unbedingt schneller wäre.

Danny92

Naja spielt eigentlich keine Rolle, da beide Codes bei mir auf demselben Rechner laufen. Da kann ich sie dann hinsichtlich der Effizienz schon vergleichen und feststellen, dass C++ bis jetzt keineswegs schneller ist als Pascal.^^

SeppJ

Hast du denn inzwischen mal mit aktivierten Optimierungen übersetzt (O2 oder höher)? Niemanden interessiert, wie schnell unoptimierter Code läuft.

Danny92

Das Einzige was ich bis jetzt geändert habe, ist die Verwendung der Indizes Vector[] statt Vector.at(). Ich bin in C++ nicht so erfahren um zu sehen, ob/wo noch weitere Schwachstellen im Code stehen.

Columbo

Danny92 schrieb:

Das Einzige was ich bis jetzt geändert habe, ist die Verwendung der Indizes Vector[] statt Vector.at().

Dein Code ist kompletter Müll, es ist nicht im Geringsten überraschend dass er langsam läuft. Bitte vergleich nicht das Optimierungsvermögen zweier Sprachen anhand unqualitativer "Übersetzungen".

Danny92

@Arcoth
Dann sei doch so gut, und belehre mich aus dem Fundus deiner reichhaltigen Erfahrung. Denn in meinen Augen ist es 1 zu 1 übersetzt; die gleichen Datentypen, die gleichen Schleifen, die gleichen Algorithmen.

g++ -O3 -std=c++11 -Wall -o main main.cpp

Ist doch nicht so schwer.

Columbo

Danny92 schrieb:

@Arcoth
Dann sei doch so gut, und belehre mich aus dem Fundus deiner reichhaltigen Erfahrung.

Nimm meine harsche Art nicht persönlich. Du triffst halt einen wunden Punkt, wenn du eine Sprache, in deren Erlernung viel Fleiß gesteckt wurde, dermaßen falsch verwendest und dich dann über ihre angepriesenen Vorteile mockierst. C++ Implementierungen führen sehr clevere Optimierungen durch, damit deine Verantwortung auf algorithmische Optimierung reduziert wird. Du schmeisst aber einfach irgendwelche Befehle hin, bis der Code kompiliert und funktioniert. Das ist auch der Grund für die extrem schlechte Performance.

Die Konsolenausgabe hast du ebenfalls nicht gepostet, daher kann ich die kuriose Ausgabe in der Datei nach wie vor nur als Fehler deines Systems abstempeln.

Das größte Bottleneck könnte das Verwenden von string s sein, welche dynamisch Speicher allozieren. to_string impliziert einen Aufruf an vsnprintf . Etc.
Es besteht überhaupt kein Grund dazu, die Zeile vorher zwischen zu speichern. Schreib einfach direkt in den Stream. So werden etliche Aufrufe von new / delete (und anderem Zeug) impliziert, was möglicherweise durch SSO (small string optimization) gemildert wird.

Ohne Optimierungen wird des weiteren bspw. sqrt(grenze) nicht gehoisted (das wäre via loop invariant code motion möglich, welches sqrt als pure function betrachtet), CSE wird die identischen Ausdrücke nicht optimieren, usw.
Dann könnte noch dein ohnehin ungerechtfertigter Einsatz von globalen Variablen die Performance subtil schädigen: Zugriff auf globale Variablen kann etwas teurer sein (wird mittels effective addressing gelöst, was deine Implementierung nicht zwangsläufig durchführt, e.g. wenn die ABI kein RIP Register liefert). Ist hier aber wahrscheinlich nicht zutreffend.

Diese Kleinigkeiten können eben in extrem heißen Teilen viel ausmachen, vor allem wenn sie alle zusammen kommen.

Edit: Schau dir meinen Code an und versuche, den Fehler zu beheben und den Code dann auf dein Program auszuweiten. Kompiliere mit -O3 -march=native . Und hör auf mit diesem open / close Blödsinn. Nimm den Konstruktor. close wird im Destruktor aufgerufen. (Wenn du auf Fehler prüfen würdest, wäre der close Aufruf noch gerechtfertigt. Ahh... @SeppJ: Wann haste denn endlich mal Zeit?!)

Danny92

Ok Danke, ich werde mich damit mal genauer beschäftigen und Bescheid geben.