- "Inside STL: The deque, design" by Raymond Chen - 1 Update
- Sieb des Eratosthenes - 1 Update
| gazelle@shell.xmission.com (Kenny McCormack): Aug 12 12:59PM In article <ub3nef$hbb3$1@dont-email.me>, >"All three of the major implementations of the C++ standard library use >the same basic structure for a deque, but they vary in both policy and >implementation details." I'm sorry. Your C++ question is? -- The book "1984" used to be a cautionary tale; Now it is a "how-to" manual. |
| Bonita Montero <Bonita.Montero@gmail.com>: Aug 12 09:50AM +0200 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. |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment