Code Effizienz



  • 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



  • 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.


  • Mod

    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.



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



  • @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. 😮


  • Mod

    manni66 schrieb:

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

    Wie kommst du darauf?


  • Mod

    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.



  • @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)


  • Mod

    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?


  • Mod

    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.



  • 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.^^


  • Mod

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



  • 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.


  • Mod

    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".



  • @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.


  • Mod

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



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


Anmelden zum Antworten