Primzahlenberechnung - Sieb des Eratosthenes - Was kann noch optimiert werden?

ichbineinnoob

redrew99 schrieb:

Eigentlich müßte es doch auch möglich sein, die Ausgabe auf der Konsole anstelle einer separaten Schleife jeweils dann zu tätigen, wenn i zum nächsten Wert(z.B. i*i) springt bzw. gesprungen ist, da alle Zahlen dazwischen, die nicht gestrichen wurden, Primzahlen sein müssen.

Ja, ab i abwärts ist die Liste "fertig"

hustbaer

ichbineinnoob schrieb:

Die geraden Zahlen lässt man tatsächlich aus. Aber das geht in vector<bool> wohl nicht.

Wieso sollte das mit vector<bool> nicht gehen? Einfach den Index halbieren...

vector<bool> ist eine Spezialisierung von vector, um pro Bool-Wert auch tatsächlich nur ein Bit zu verwenden. Theoretisch könnte ein vector<char> schneller sein. Praktisch muss man es nachmessen.

EOutOfResources

manni66 schrieb:

Theoretisch könnte ein vector<char> schneller sein.

Wegen was? Der Bitmaske?

SeppJ

EOutOfResources schrieb:

manni66 schrieb:

Theoretisch könnte ein vector<char> schneller sein.

Wegen was? Der Bitmaske?

Weil vector<bool> eine unnötig komplizierte Spezialisierung ist, während ein vector<char> der übliche schnelle vector wäre.

SeppJ

SeppJ schrieb:

EOutOfResources schrieb:

manni66 schrieb:

Theoretisch könnte ein vector<char> schneller sein.

Wegen was? Der Bitmaske?

Weil vector<bool> eine unnötig komplizierte Spezialisierung ist, während ein vector<char> der übliche schnelle vector wäre.

Was noch wichtig ist: Solche Überlegungen müssen nicht stimmen. Man kann zum Beispiel leicht vergessen, dass ein vector<bool> viel bessere Lokalität hat. Wenn der ganze vector (oder große Teile) in den CPU-Cache passen, dann ist das ein gewaltiger Vorteil. Ich hab's mal ausprobiert:

#include <vector>
#include <iostream>
#include <cstddef>

using namespace std;

typedef vector<bool> container;  // Hier entsprechend auf char oder bool setzen

int main()
{
  const size_t max_n = 100000000;
  container numbers(max_n, 1);
  for (unsigned n=2; n<max_n; ++n)
    if (numbers[n])
      for (unsigned i=2*n; i<max_n; i+=n)
        numbers[i]=0;
  unsigned long anti_optimizer = 0;
  for (unsigned n=2; n<max_n; ++n)
    if (numbers[n])
      anti_optimizer += n;
  cout<<"Summe aller Primzahlen bis "<<max_n<<" ist "<<anti_optimizer<<".\n";
}

Die vector<char> Version rechnet bei mir (Core 2, g++, -O3 -xHOST) knapp 8 Sekunden, der vector<bool> etwas über 5 Sekunden. Also ganz klarer Sieg für den kleinen, aber komplizierten, Datentyp.

volkard

SeppJ schrieb:

Wenn der ganze vector (oder große Teile) in den CPU-Cache passen, dann ist das ein gewaltiger Vorteil.
...
Die vector<char> Version rechnet bei mir (Core 2, g++, -O3 -xHOST) knapp 8 Sekunden, der vector<bool> etwas über 5 Sekunden. Also ganz klarer Sieg für den kleinen, aber komplizierten, Datentyp.

Jup. Der vector paßt wohl gerade rein? Rein interessehalber ie steht's bei max_n=1e9?

*Rewind*

SeppJ schrieb:

Die vector<char> Version rechnet bei mir (Core 2, g++, -O3 -xHOST) knapp 8 Sekunden, der vector<bool> etwas über 5 Sekunden. Also ganz klarer Sieg für den kleinen, aber komplizierten, Datentyp.

ich weiß nicht mit welchem Code du getestet hast, aber ich hab's mal mit deinem probiert (max_n = 100000000;). Ergebnis:

vector<char> container; -> 9s
vector<bool> container; -> 19s

Edit: hab die Angaben korrigiert.

camper

Auf meinem Rechner (Atom 330) mit n=100000000:
char: 10.35s
bool: 12.75s

Die Lokalität mit bool ist nicht von besonders großem Vorteil, wenn man bedenkt, dass bool für jeden einzelnen Wert sowohl eine Lese- als auch eine Schreibvorgang impliziert. Wärend mit char nur geschrieben wird - hier könnte man ggf. auch low-level optimieren, z.B. mit unsigned arbeiten und ungeordnet schreiben.

volkard

[Rewind] schrieb:

probiert (max_n = 1000000;). Ergebnis:
vector<char> container; -> 2-3s
vector<bool> container; -> 32-33s

Naja, -O3 muß schon sein. Am besten auch -march=native.
So lahm kann Dein Rechner gar nicht sein.

Bei mir:
Bis 1e5
bool: 0.0014
char: 0.0015

Bis 1e6
bool: 0.14
char: 0.18

Bis 1e7
bool: 1.08
char: 1.84

Bis 1e8
bool: 13.77
char: 21.11

Und der Prozessor ist nicht neu. AMD Sempron 3000+ @ 1800MhZ.

SeppJ

[Rewind] schrieb:

ich weiß nicht mit welchem Code du getestet hast, aber ich hab's mal mit deinem probiert (max_n = 1000000;). Ergebnis:

vector<char> container; -> 2-3s
vector<bool> container; -> 32-33s

Das widerspricht sich ja auch nicht. Je nach Compiler und System können schon so große Unterschiede auftauchen. Anscheinend hat deine Standardbib einen sehr schlechten vector<bool>, meine einen sehr guten. Darf ich fragen, welcher Compiler?

volkard schrieb:

Jup. Der vector paßt wohl gerade rein? Rein interessehalber ie steht's bei max_n=1e9?

Eigentlich nicht, der Prozessor müsste irgendwie so um 2-4MB Cache haben. Der vector müsste aber mindestens 12.5 MB groß sein.

Abgesehen davon, dass ich gerade an einem anderen Rechner sitze, dürfte mein Core2 Rechner jedoch Probleme mit 1 Milliarde char bekommen, von der RAM-Größe her, daher unvergleichbar.

Ich sitze gerade an einem i7 mit viel mehr RAM und vergleichbar großem Cache, da probiere ich mal (gleicher Compiler wie oben) mit 1 Milliarde:
vector<bool>: gut 24 Sekunden
vector<char>: knapp 26 Sekunden

Sehr interessant. Ich lasse mal im Hintergrund mit 8 Milliarden laufen und melde mich in 10-20 Minuten mit den Ergebnissen.

edit: Ach, dazu habe ich nicht die Geduld. Dafür die Ergebnisse von dem i7 Rechner mit 100 Millionen:
bool: 1.75 Sekunden
char: 2 Sekunden

Da das auch ungefähr das gleiche ist wie bei 1 Milliarde, breche ich mal den 8 Milliarden test ab, da wird sicherlich nichts großarti anderes rauskommen.

*Rewind*

Wie bereits in der letzten Antwort dazugeschrieben, die Zeitangaben habe ich korrigiert (9s für char und 19s für bool mit n=100mil). Ich verwende momentan VS2008 PE.

SeppJ

Was mir gerade auffällt: Wenn man sich mal Zwischenergebnisse ausgeben lässt, sieht man, dass ein sehr großer Teil der Zeit für das Erstellen des vectors draufgeht. Kein Wunder, dass der vector<bool> so gut abschneidet, denn das geht natürlich deutlich schneller wenn man weniger Speicher braucht.

Auch wieder so ein Aspekt, an den man gar nicht gedacht hätte, ohne dass man es ausprobiert. War wohl doch nicht die Lokalität.

Immer schön vorsichtig sein, bei der Mikrooptimierung.

camper

volkard schrieb:

Bis 1e8
bool: 13.77
char: 21.11

Und der Prozessor ist nicht neu. AMD Sempron 3000+ @ 1800MhZ.

Dass ist langsamer als mein atom 330 (1.6GHz) - sollte eigentlich nicht passieren. Sind denn auch alle Checks deaktiviert? Visual C++ hat da ja eine Menge standardmäßig aktiv.

volkard

camper schrieb:

volkard schrieb:

Bis 1e8
bool: 13.77
char: 21.11

Und der Prozessor ist nicht neu. AMD Sempron 3000+ @ 1800MhZ.

Dass ist langsamer als mein atom 330 (1.6GHz) - sollte eigentlich nicht passieren. Sind denn auch alle Checks deaktiviert? Visual C++ hat da ja eine Menge standardmäßig aktiv.

Ja. NDEBUG ist definiert, und -O3 -march=native.
gcc 4.5.0 (MinGW).

SeppJ hat eine wichtige Optimierung vergessen, die im ersten Beispiel
von redrew99 noch drin war: Die Quadratwurzel als Grenze.
Der folgende Code ist noch schneller:

#include <vector>
#include <iostream>
#include <cstddef>
#include <cmath>
using namespace std;
#define NDEBUG

typedef vector<bool> container;  // Hier entsprechend auf char oder bool setzen

int main()
{
   const size_t max_n = 100000000;

   container numbers(max_n, 1);
   size_t grenze = sqrt(max_n); // impliziter cast

   for (unsigned n=2; n<grenze; ++n)     // geaendert!
      if (numbers[n])
         for (unsigned i=2*n; i<max_n; i+=n)
            numbers[i]=0;

   unsigned long anti_optimizer = 0;
   for (unsigned n=2; n<max_n; ++n)
      if (numbers[n])
         anti_optimizer += n;
   cout<<"Summe aller Primzahlen bis "<< max_n
       << " (ausschließlich)  ist "<<anti_optimizer<<".\n";
}

DocShoe

Du musst aber schon gegen sqrt( max_n ) +1 laufen (oder zumindest gegen ceil( sqrt( max_n ) ) ), sonst fehlen dir ein paar Überprüfungen.

Edit:
Ist im Original aber drin.

Michael E.

DocShoe schrieb:

Du musst aber schon gegen sqrt( max_n ) +1 laufen (oder zumindest gegen ceil( sqrt( max_n ) ) ), sonst fehlen dir ein paar Überprüfungen.

Edit:
Ist im Original aber drin.

Nö, floor(sqrt(max_n)) reicht. Außer wenn der sqrt-Algorithmus Mist baut und die Rechenungenauigkeit dazu führt, dass floor(sqrt(max_n)) ungleich der "richtigen Wurzel" von max_n (abgerundet) ist.

Jockelx

Michael E. schrieb:

DocShoe schrieb:

Du musst aber schon gegen sqrt( max_n ) +1 laufen (oder zumindest gegen ceil( sqrt( max_n ) ) ), sonst fehlen dir ein paar Überprüfungen.

Edit:
Ist im Original aber drin.

Nö, floor(sqrt(max_n)) reicht. Außer wenn der sqrt-Algorithmus Mist baut und die Rechenungenauigkeit dazu führt, dass floor(sqrt(max_n)) ungleich der "richtigen Wurzel" von max_n (abgerundet) ist.

Nö, es wird ja auf echt kleiner abgefragt.
Für max_n=5 ist grenze=2 und die Schleife wird überhaupt nicht durchlaufen und 4 somit als Primzahl erkannt.

Michael E.

Jockelx schrieb:

Nö, es wird ja auf echt kleiner abgefragt.

Da hast du Recht. Ich hab mir den Code gar nicht durchgelesen. Wer prüft auch schon mit strikt kleiner?