Code Effizienz

[Danny92]

Hallo. Ich rätsel seit ein paar Tagen, warum die Ausführung des folgenden Codes so verhältnismäßig langsam ist.

#include <iostream>
#include <vector>
#include <cmath>
#include <math.h>
#include <fstream>
#include <string>

std::vector<bool> Zahl;
int primecount,FileCount=0;
bool Done=false;
int indi=1;

void SchreibeDatei()
{
	std::ofstream F;
	std::string zeile="";
	unsigned int i=indi;
	int rowcounter=0;
	F.open("Tabelle"+std::to_string((long long)FileCount)+".txt");
	while ((i<Zahl.size()) && (primecount<5000000))
	{
		if (!Zahl.at(i))
		{
			rowcounter++;
			zeile+=std::to_string((long long)i+1)+(char)9;
		}
		if (rowcounter==10)
		{
			zeile=zeile.substr(0,zeile.size()-1);
			primecount+=10;
			F<<zeile<<'\n';
			zeile="";
			rowcounter=0;
		}
		i++;
	}
	if (primecount<5000000)
	{
		if (!(zeile==""))
		{
			zeile=zeile.substr(0,zeile.size()-1);
			F<<zeile<<'\n';
			if (i==Zahl.size())
				Done=true;
		}
		else
		{
			if (i==Zahl.size())
				Done=true;
		}
	}
	else
	{
		indi=i;
		primecount=0;
		if (i==Zahl.size())
			Done=true;
	}
	F.close();
}

int main()
{
	int grenze, currprimeindex, vielfaches;
	std::cout<<"Grenze: ";
	std::cin>>grenze;
	Zahl.resize(grenze,false);
	Zahl.at(0)=true;
	currprimeindex=1;
	while (currprimeindex<=int(std::sqrt((double)grenze)))
	{
		while (Zahl.at(currprimeindex-1))
			currprimeindex++;
		vielfaches=1;
		while ((vielfaches+1)*(currprimeindex)-1<grenze)
		{
			vielfaches++;
			if (!Zahl.at(vielfaches*(currprimeindex)-1))
				Zahl.at(vielfaches*(currprimeindex)-1)=true;
		}
		currprimeindex++;
	}
	std::cout<<"Schreibe in Datei...\n";
	while (!Done)
	{
		FileCount++;
		SchreibeDatei();
	}
	FileCount=0;
	Done=false;
	primecount=0;
	indi=1;
	std::cout<<"Done!\n";
	return 0;
}

Ich habe diesen Code schon einmal in Pascal in Delphi geschrieben und genau diesen Algorithmus 1:1 in C++ übersetzt. Allerdings ist dieser in Pascal um ein Vielfaches schneller! Warum?
Dieses Programm erstellt mir die Liste von Primzahlen bis zur vom Nutzer eingegebenen (Ober)grenze. Gibt man beispielsweise 100 000 000 ein, so braucht dieser Code bei mir schon ca. 54 Sekunden in C++! In Pascal nur knapp 10 Sekunden.
Kaum zu glauben, dass C++ als "schnell" gelten soll. Hier hab ich im Vergleich nochmal den äquivalenten Code in Pascal:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, Math;

type
  TForm1 = class(TForm)
    Edit1: TEdit;
    Label1: TLabel;
    Button1: TButton;
    Label2: TLabel;
    procedure Edit1KeyPress(Sender: TObject; var Key: Char);
    procedure Edit1Enter(Sender: TObject);
    procedure Edit1Exit(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    procedure SchreibeDatei;
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;
  Zahl: array of boolean;
  primecount: integer = 0;
  Done: boolean = False;
  FileCount: byte = 0;
  indi: integer = 1;

implementation

{$R *.dfm}

procedure TForm1.SchreibeDatei;
var
  F: TextFile;
  zeile: string;
  i: integer;
  rowcounter: byte;

begin
  AssignFile(F,ExtractFilePath(Application.ExeName)+'Tabelle'+IntToStr(FileCount)+'.txt');
  try
    Rewrite(F);
    zeile:='';
    rowcounter:=0;
    i:=indi;
    while (i<=high(Zahl)) and (primecount<5000000) do
    begin
      if not Zahl[i] then
      begin
        Inc(rowcounter);
        zeile:=zeile+Format('%3.0n',[i+1/1])+#9
      end;
      if rowcounter=10 then
      begin
        zeile:=Copy(zeile,1,Length(zeile)-1);
        Inc(primecount,10);
        WriteLn(F,zeile);
        zeile:='';
        rowcounter:=0
      end;
      Inc(i)
    end;
    if primecount<5000000
    then
      if not (zeile='') then
      begin
        zeile:=Copy(zeile,1,Length(zeile)-1);
        writeln(F,zeile);
        if i-1=high(zahl)
        then Done:=True
      end else
      begin
        if i-1=high(zahl)
        then Done:=True
      end
    else
      begin
        indi:=i; primecount:=0;
        if i-1=high(zahl) then Done:=True
      end
  finally
    CloseFile(F)
  end
end;

procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: Char);
begin
  if not (Key in ['0'..'9',Char(VK_BACK),Char(VK_RETURN)]) then Key:=#0
  else if Key=Char(VK_RETURN) then Button1.Click
end;

procedure TForm1.Edit1Enter(Sender: TObject);
begin
  if Edit1.Text='Suche bis...' then
  begin
    Edit1.Font.Style:=[];
    Edit1.Font.Color:=clBlack;
    Edit1.Clear
  end
end;

procedure TForm1.Edit1Exit(Sender: TObject);
begin
  if Edit1.Text='' then
  begin
    Edit1.Font.Style:=[fsItalic];
    Edit1.Font.Color:=clGray;
    Edit1.Text:='Suche bis...'
  end
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  grenze, currprimeindex, vielfaches: integer;

begin
  try
    grenze:=StrToInt(Edit1.Text)
  except
    on E: EConvertError do Exit
  end;
  try
    if grenze/Power(2,20)>512 then
      if MessageDlg('Diese Variable wird etwa '+IntToStr(Trunc(grenze/Power(2,20)))+' MB RAM benötigen. Möchten Sie fortfahren?',mtConfirmation,[mbYes,mbNo],0)=mrYes
      then SetLength(Zahl,grenze)
      else Exit
    else SetLength(Zahl,grenze)
  except
    on E: EOutOfMemory do
    begin
      MessageDlg('Zu wenig Ram! Bitte wählen Sie eine kleinere Zahl.',mtError,[mbOk],0);
      Exit
    end
  end;
  Zahl[0]:=True;
  currprimeindex:=1;
  while currprimeindex+1<=Trunc(Sqrt(grenze)) do
  begin
    while Zahl[currprimeindex] do
    Inc(currprimeindex);
    vielfaches:=1;
    while (vielfaches+1)*(currprimeindex+1)-1<=grenze do
    begin
      Inc(vielfaches);
      if not Zahl[vielfaches*(currprimeindex+1)-1]
      then Zahl[vielfaches*(currprimeindex+1)-1]:=True
    end;
    Inc(currprimeindex)
  end;
  Label2.Caption:='Schreibe in Datei...';
  while not done do
  begin
    Inc(FileCount);
    SchreibeDatei
  end;
  FileCount:=0;
  Done:=False;
  primecount:=0;
  indi:=1;
  Label2.Caption:='Done!'
end;

end.

Kann mir jemand Verbesserungsvorschläge geben oder sagen, warum der Code in C++ so langsam läuft und was den Code so ausbremst? Das wäre mega!
Schon mal Danke.
PS: Compiliert habe ich das mit dem Compiler MinGW g++ C++11 Standard

[manni66]

Mit -O übersetzt?
Wenn man schnell will, sicher nicht at sondern Index.
vector<bool> ist eine spezielle platzsparende Implementation, dürfte aber langsamer als "normale" vectoren xein.

[Columbo]

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

#include <vector>
#include <cmath>

std::vector<bool> createPrimeTable( std::vector<bool>::size_type max ) {
	std::vector<bool> prime(max, true);
	prime[0] = prime[1] = false;
	auto sqrt = std::sqrt(max);

	for( std::vector<bool>::size_type div = 2;; ) {
		for (std::vector<bool>::size_type s = 2*div; s < max; s += div)
			prime[s] = false;

		for (auto next = div;;) {
			if (++next > sqrt) return prime;
			if (prime[next]) { div = next; break; }
		}
	}
}

#include <iostream>
#include <fstream>

int main() {
	std::ofstream stream("Primes.txt", std::ios::trunc);
	std::size_t c = 0;
	auto table = createPrimeTable(100'000'000);
	for (std::size_t i = 2; i < table.size(); ++i)
		if (table[i]) {
			stream << i << ' ';
			++c;
		}

	std::cout << c << " written";
}

Keine Ahnung was du verbockt hast, aber C++ ist nicht langsam.

[Danny92]

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

Danke, der Zugriff mit den direkten Indizes ist es schon ein paar Sekunden schneller.
Allerdings braucht die Methode SchreibeDatei() noch relativ lange...

Was genau meinst du mit "normale" Vektoren?
Danke nochmals!

[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:
′″‵‷ㄱㄠ″㜱ㄠ‹㌲㈠‹ㄳ㌠‷ㄴ㐠″㜴㔠″㤵㘠‱㜶㜠 .............

[manni66]

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)!

[sebi707]

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.

[asdfghjkhg]

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.