Ich hab gestern mal jemanden im IRC erzählt, dass ich mir einen AMD
16-Kerner gegönnt habe. Der meinte darauf, dass ich dessen Performance
ja mal testen könnte indem ich das Sieb des Eratosthenes als Bash-Script
laufen lasse. Ich darauf, dass man dann doch mehr die Perfomrmance des
Interpreters teste als das eigentliche Problem zu benchmarken.
Ich mein solche Benchmarks sind schon unsinnig genug, da wollte ich der
Unsinnigkeit noch eins drauf setzen und habe das Sieb des Eratosthenes
als C++20-Programm geschrieben, und zwar wirklich so effizient wie mög-
lich. Letztlich bearbeite ich mehrfach einen Vektor aus vorab auf true
bools und lösche die Vielfachen von bisher bekannten Primzahlen und su-
che darauf die nächste Primzahl und fange wieder mit deren Vielfachen
an.
In C++ ist ein bool üblicherweise ein Byte das einfach auf Null oder
Eins gesetzt ist. Dementsprechend wäre ein vector<bool> ein Vektor aus
Bytes. In C++ lassen sich aber einzelne gernerische Klassen für Sonder-
fälle, bezogen auf bestimmte Typen, spezialisieren, und das ist auch
für den vector<bool> so, der dann jedes bool einfach als ein Bit spei-
chert. Das macht, dass der Vektor eben kompakter gespeichert wird und
das wirkt sich dann eben positiv auf die Performance aus.
Am Ende werden die Primzahlen dann alle noch in eine Datei ausgegeben.
Ich mein das könnte ich in C wie in C++ über irgendwelche ASCII-Streams
tun, aber die sind meiner Erfahung nach alle ziemlich ineffizient.
Es gibt seit C++20 die Funktion to_chars, die eine Zahl ähnlich wie bei
sprintf in einen Stück Speicher ausgeben kann. Bei der gehe ich davon
aus, dass die wirklich maximal effizient arbeitet (vor allem muss hier
ein Format-String geparst werden). Damit printe ich die Primzahlen fort-
laufend in ein char-Array, hänge ein Newline an und hänge das Ganze dann
an einen dynamisch wachsenden C++-string an.
Die C++-Strings haben wie die Vektoren die Eigenschaft, dass der allo-
kierte Speicher nicht für jedes Größenwachstum neu um-allokiert wird,
sondern nur dann wenn dessen Kapazitäts-Grenzen gebrochen werden. C++
hat für Vektoren und Strings nämlich die Eigenschaft des "amortisiert
konstanten" Overheads für jedes Einfügen oder Anhängen an einen String
oder Vektor, d.h. der Aufwand für jedes Anfügen ist konstant, egal
welche Größe der Vektor zuvor hatte. Um das umsetzen zu können muss
der Container in seiner Kapazität immer um einen konstanten Faktor
wachsen. Bei Visual C++ wächst der Container in seiner Kapazität dann
immer um 50% seiner vorherigen Größe, bei libstdc++ (g++) und libc++
(clang++) wächst er immer um 100% (is performanter da seltener reallo-
kiert wird als bei MSVC, braucht aber mehr Speicher).
Ich hatte anfänglich damit gerechnet, dass die Reallokationen den Code
maßgeblich verlangsamen. Daher habe ich die Ausgabeschleife als Funk-
tion in der Funktion, also als so genanntes Lambda, geschrieben und
diese Funktion kriegt an zwei Stellen ein unterschiedliches Funktions-
objekt übergeben, das an erster Stelle nur die Länge der Zeilen mit
den Primzahlen aufsummiert und an zweiter Stelle das dann in einen
entsprechend vor-allokierten String kopiert. Da das Lambda für jedes
dieser Übergebenen Funktionsobjekte zweimal kompiliert wird habe ich
so wirklich die maximale Performance beim Durchzählen und bei der Aus-
gabe.
Interessanterweise haut das Durchzählen bzgl. der CPU-Zeit mehr rein
als das mit logarithmisch zur Größe des Ausgabe-Strings häufigen Re-
allokieren und Umkopieren des Strings. Daher hab ich das Durchzählen
zuletzt auskommentiert.
Wenn ich alle Primzahlen im Zahlenbereich von >= 2 bis < 0x1000000000
durchrechnen lasse braucht das Ganze dann nur ca 10s auf meinem AMD
7950X. Was ich auch interessant finde ist, dass das Generieren der
Datei aus dem berechneten Array daran nur ca. 0,5s Anteil hat.

#include <iostream>
#include <vector>
#include <charconv>
#include <string_view>
#include <algorithm>
#include <fstream>
#include <cctype>

using namespace std;

int main( int argc, char **argv )
{ constexpr bool USE_CHAR = true;
using bool_t = conditional_t<!USE_CHAR, bool, char>;
size_t max = 10000;
if( argc >= 2 )
{
char const* sizeParam = argv[1];
bool hex = argv[1][0] == '0' && tolower( argv[1][1] ) == 'x';
sizeParam += 2 * hex;
if( from_chars_result fcr = from_chars( sizeParam, sizeParam + strlen(
sizeParam ), max ); (bool)fcr.ec || *fcr.ptr )
return EXIT_FAILURE;
}
vector<bool_t> sieve( max, true );
for( size_t m = 2; m < max; )
{
for( size_t i = 2 * m; i < max; i += m )
sieve[i] = false;
do
if( ++m == max )
goto finished;
while( !sieve[m] );
}
finished:
auto format = [&]( auto fn )
{
for( size_t i = 2; i != max; ++i )
if( sieve[i] )
{
char append[32];
to_chars_result tcr = to_chars( append, append + sizeof append, i );
*tcr.ptr++ = '\n';
fn( string_view( append, tcr.ptr ) );
}
};
size_t outLength = 0;
//format( [&]( string_view const &append ) { outLength +=
append.length(); } );
string print;
print.reserve( outLength );
format( [&]( string_view const &append ) { print.append( append ); } );
ofstream ofs;
ofs.exceptions( ofstream::failbit | ofstream::badbit );
ofs.open( argc >= 3 ? argv[2] : "primes.txt", ofstream::trunc );
ofs << print << endl;
}

Mich würde an der Stelle der Performance-Vergleich zu anderen
Implementationen interessieren. Freiwillige vor.