Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #91466
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c++ |
| Subject | Re: What is visitor pattern? |
| Date | 2023-08-29 19:27 +0200 |
| Organization | A noiseless patient Spider |
| Message-ID | <ucl9qd$2bhvr$1@dont-email.me> (permalink) |
| References | <331cb164-e6b3-4f9b-af8d-ee933abd79b7n@googlegroups.com> |
I think that's my final solution. Currently I store the bits in
size_ts and I look up the next set bit with countr_zero which maps
to TZCNT on x64 and according to some small code on godbolt ARM
also has a proper instruction for that.
Resettig the bits for the composites is done by a rotating bit-mask.
If the prime is less than size_t * 8 there's a special case optimi-
zation.
#include <iostream>
#include <vector>
#include <charconv>
#include <string_view>
#include <algorithm>
#include <fstream>
#include <cctype>
#include <cstring>
#include <bit>
#if defined(_MSC_VER)
#pragma warning(disable: 26495) // uninitialized member
#endif
#if defined(__llvm__)
#pragma clang diagnostic ignored "-Wdangling-else"
#endif
using namespace std;
int main( int argc, char **argv )
{
constexpr size_t BUF_SIZE = 0x100000;
try
{
size_t end;
if( argc < 2 )
return EXIT_FAILURE;
char const *sizeStr = argv[1];
bool hex = sizeStr[0] == '0' && (sizeStr[1] == 'x' || sizeStr[1] == 'X');
sizeStr += 2 * hex;
if( from_chars_result fcr = from_chars( sizeStr, sizeStr + strlen(
sizeStr ), end, !hex ? 10 : 16 ); (bool)fcr.ec || *fcr.ptr )
return EXIT_FAILURE;
if( !++end )
throw bad_alloc();
using word_t = size_t;
constexpr size_t BITS = sizeof(word_t) * 8;
size_t bEnd = (end + BITS - 1) & -(ptrdiff_t)BITS;
if( bEnd < end )
throw bad_alloc();
union ndi_word_t { word_t w; ndi_word_t( word_t w ) : w( w ) {} };
using bit_vec = vector<ndi_word_t>;
using bit_it = bit_vec::iterator;
bit_vec sieve( (end + BITS - 1) / BITS, (word_t)0xAAAAAAAAAAAAAAAAu );
ofstream ofs;
union ndi_t { char c; ndi_t() {} };
using ndi_vec = vector<ndi_t>;
constexpr size_t AHEAD = 32;
ndi_vec printBuf;
ndi_vec::iterator bufBegin, bufEnd, bufFlush;
if( argc < 3 || *argv[2] )
{
ofs.exceptions( ofstream::failbit | ofstream::badbit );
ofs.open( argc >= 3 ? argv[2] : "primes.txt", ofstream::trunc );
printBuf.resize( BUF_SIZE + AHEAD - 1 );
bufBegin = printBuf.begin();
bufEnd = bufBegin;
bufFlush = bufBegin + BUF_SIZE;
}
auto print = [&]() { ofs << string_view( &to_address( bufBegin )->c,
&to_address( bufEnd )->c ); };
bit_it const pSieveEnd = sieve.end();
size_t sqr = (ptrdiff_t)ceil( sqrt( (ptrdiff_t)end ) );
for( size_t p = 2; p < end; )
{
if( ofs.is_open() )
{
auto [ptr, ec] = to_chars( &bufEnd->c, &to_address( bufEnd + (AHEAD
- 1) )->c, p );
if( (bool)ec ) [[unlikely]]
throw system_error( (int)ec, generic_category(), "converson failed" );
bufEnd = ptr - &bufBegin->c + bufBegin; // NOP
bufEnd++->c = '\n';
if( bufEnd >= bufFlush )
ofs << string_view( &to_address( bufBegin )->c, &to_address( bufEnd
)->c ),
bufEnd = bufBegin;
}
if( ++p == end ) [[unlikely]]
break;
for( bit_it pSieve = sieve.begin() + p / BITS; ; )
{
size_t g = countr_zero( pSieve->w & (word_t)-1 << p % BITS );
p = (p & -(ptrdiff_t)BITS) + g;
if( g != BITS )
break;
if( ++pSieve == pSieveEnd )
goto end;
}
bit_it pSieve = sieve.begin();
if( size_t m = p * p; p < sqr )
if( p >= BITS ) [[likely]]
{
word_t mask = rotl( (word_t)-2, m % BITS );
do
pSieve[m / BITS].w &= mask,
mask = rotl( mask, (int)p % BITS ),
m += p;
while( m < end );
}
else
{
pSieve += m / BITS;
word_t mask = rotl( (word_t)-2, m % BITS );
do
{
word_t punch = -1, oldMask;
do
punch &= mask,
oldMask = mask,
mask = rotl( mask, (int)p );
while( mask < oldMask );
pSieve->w &= punch;
} while( ++pSieve != pSieveEnd );
}
}
end:
if( ofs.is_open() )
print();
return EXIT_SUCCESS;
}
catch( bad_alloc const & )
{
cout << "out of memory" << endl;
}
catch( ios_base::failure const & )
{
cout << "I/O error" << endl;
}
catch( system_error const &se )
{
cout << se.what() << endl;
}
}
Back to comp.lang.c++ | Previous | Next — Previous in thread | Find similar | Unroll thread
What is visitor pattern? wij <wyniijj5@gmail.com> - 2023-08-20 06:55 -0700
Re: What is visitor pattern? Öö Tiib <ootiib@hot.ee> - 2023-08-20 07:22 -0700
Re: What is visitor pattern? wij <wyniijj5@gmail.com> - 2023-08-20 19:24 -0700
Re: What is visitor pattern? wij <wyniijj5@gmail.com> - 2023-08-27 13:13 -0700
Re: What is visitor pattern? Öö Tiib <ootiib@hot.ee> - 2023-08-28 00:13 -0700
Re: What is visitor pattern? wij <wyniijj5@gmail.com> - 2023-08-28 23:18 -0700
Re: What is visitor pattern? Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2023-08-20 14:12 -0400
Re: What is visitor pattern? Öö Tiib <ootiib@hot.ee> - 2023-08-20 13:34 -0700
Re: What is visitor pattern? Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2023-08-20 18:01 -0400
Re: What is visitor pattern? Öö Tiib <ootiib@hot.ee> - 2023-08-20 21:12 -0700
Re: What is visitor pattern? Muttley@dastardlyhq.com - 2023-08-21 06:53 +0000
Re: What is visitor pattern? Öö Tiib <ootiib@hot.ee> - 2023-08-21 00:10 -0700
Re: What is visitor pattern? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-08-26 21:26 -0700
Re: What is visitor pattern? Öö Tiib <ootiib@hot.ee> - 2023-08-26 22:57 -0700
Re: What is visitor pattern? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-08-28 15:07 -0700
Re: What is visitor pattern? Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2023-08-21 22:55 -0400
Re: What is visitor pattern? Öö Tiib <ootiib@hot.ee> - 2023-08-21 21:56 -0700
Re: What is visitor pattern? Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2023-08-24 01:38 -0400
Re: What is visitor pattern? Öö Tiib <ootiib@hot.ee> - 2023-08-24 04:45 -0700
Re: What is visitor pattern? Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2023-08-24 23:11 -0400
Re: What is visitor pattern? Öö Tiib <ootiib@hot.ee> - 2023-08-25 07:52 -0700
Re: What is visitor pattern? Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2023-08-26 00:55 -0400
Re: What is visitor pattern? Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-21 06:18 +0200
Re: What is visitor pattern? Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2023-08-21 23:28 -0400
Re: What is visitor pattern? Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 05:47 +0200
Re: What is visitor pattern? Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2023-08-22 00:11 -0400
Re: What is visitor pattern? Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 14:30 +0200
Re: What is visitor pattern? Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2023-08-24 01:56 -0400
Re: What is visitor pattern? Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-24 09:15 +0200
Re: What is visitor pattern? Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2023-08-24 20:02 -0400
Re: What is visitor pattern? Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-25 05:13 +0200
Re: What is visitor pattern? Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2023-08-26 01:05 -0400
Re: What is visitor pattern? Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-26 09:24 +0200
Re: What is visitor pattern? Muttley@dastardlyhq.com - 2023-08-26 08:01 +0000
Re: What is visitor pattern? Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-26 11:29 +0200
Re: What is visitor pattern? Muttley@dastardlyhq.com - 2023-08-26 15:00 +0000
Re: What is visitor pattern? Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-26 17:08 +0200
Re: What is visitor pattern? Muttley@dastardlyhq.com - 2023-08-26 15:15 +0000
Re: What is visitor pattern? Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-26 17:24 +0200
Re: What is visitor pattern? Muttley@dastardlyhq.com - 2023-08-26 15:36 +0000
Re: What is visitor pattern? Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-26 17:39 +0200
Re: What is visitor pattern? Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-26 17:26 +0200
Re: What is visitor pattern? Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2023-08-29 21:44 -0400
Re: What is visitor pattern? Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2023-08-29 22:14 -0400
Re: What is visitor pattern? Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-30 06:13 +0200
Re: What is visitor pattern? Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2023-08-30 23:18 -0400
Re: What is visitor pattern? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-21 01:17 +0200
Re: What is visitor pattern? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-21 01:24 +0200
Re: What is visitor pattern? Michael S <already5chosen@yahoo.com> - 2023-08-25 05:21 -0700
Re: What is visitor pattern? Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-25 14:33 +0200
Re: What is visitor pattern? Öö Tiib <ootiib@hot.ee> - 2023-08-25 08:28 -0700
Re: What is visitor pattern? Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2023-08-26 01:17 -0400
Re: What is visitor pattern? Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-29 19:27 +0200
csiph-web