Tuesday, February 13, 2024

Digest for comp.lang.c++@googlegroups.com - 3 updates in 2 topics

wij <wyniijj5@gmail.com>: Feb 14 12:15AM +0800

On Sun, 2023-12-10 at 10:46 +0100, Bonita Montero wrote:
> cpuId( 0x80000006u );
> return ((unsigned)regs[2] >> 16) * 1024;
> }
 
I just wrote a class PrimeTab to test prime numbers. It took 73s to
complete.
0.1s is too unbelievable. Something must be wrong.
 
------------- PrimeTab.h
#include <Wy.stdlib.h>
#include <CSCall/VLInt.h> // Very Large Integer
 
// [Syn] PrimeTab is a table for prime numbers
//
class PrimeTab {
typedef uint64_t NumType;
WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
Wy::VLInt m_ptab;
NumType m_maxn;
 
// [Syn] Get the bit position storing info. for n
// 0= pos for n (n is composite) is not available
//
size_t bpos(NumType n) {
switch(n%6) {
case 1: return 2*(n/6);
case 5: return 2*(n/6)+1;
default: return 0;
}
};
 
public:
WY_DECL_REPLY;
PrimeTab() : m_ptab(), m_maxn(0) {};
PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn)
{};
PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),
m_maxn(s.m_maxn) {};
 
// [Syn] Create prime table for numbers<=maxn
//
explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) {
for(NumType n=2; n<=m_maxn; ++n) {
size_t p= bpos(n);
if(p==0) {
continue; // composite number
}
if(m_ptab.bit(p)) {
continue; // composite number
}
for(NumType m=n+n; m<=m_maxn; m+=n) {
Wy::Errno r=m_ptab.set_bit(bpos(m),true);
if(r!=Wy::Ok) {
WY_THROW( Reply(r) );
}
}
};
};
NumType max_num() const { return m_maxn; };
bool is_prime(NumType n) {
if(n>m_maxn) {
WY_THROW( Reply(EINVAL) );
}
if(n<=6) {
switch(n) {
case 1: // FALLTHROUGH
case 2: // FALLTHROUGH
case 3: // FALLTHROUGH
case 5: return true;
default: return false;
}
}
size_t p= bpos(n);
if(p==0) {
return false;
}
return !m_ptab.bit(p);
};
void swap(PrimeTab& ano) {
m_ptab.swap(ano.m_ptab);
Wy::swap(m_maxn, ano.m_maxn);
};
void reset() {
m_ptab.reset();
};
Wy::Errno reset(NumType maxn) try {
PrimeTab tmp(maxn);
Wy::swap(tmp);
return Wy::Ok;
}
catch(const Wy::Errno& e) {
WY_RETURN(e);
};
Wy::Errno reset(const PrimeTab& rhs) {
WY_RETURN(m_ptab.reset(rhs.m_ptab));
};
PrimeTab& operator=(const PrimeTab& rhs) {
Wy::Errno r=m_ptab.reset(rhs.m_ptab);
if(r!=Wy::Ok) {
WY_THROW( Reply(r) );
}
return *this;
};
};
 
-------------- chk_primetab.cpp
#include <Wy.stdio.h>
#include "PrimeTab.h"
 
using namespace Wy;
 
void ck1() {
size_t cnt;
PrimeTab ptab(1LL<<32);
cnt=0;
for(size_t n=0; n<ptab.max_num(); ++n) {
if(ptab.is_prime(n)) {
++cnt;
// cout << n << WY_ENDL;
}
}
cout << "cnt=" << cnt << WY_ENDL;
};
 
int main()
try {
cout << "Check PrimeTab.h ..." WY_ENDL;
ck1();
cout << "OK" WY_ENDL;
return 0;
}
catch(const Errno& e) {
cerr << wrd(e) << WY_ENDL;
return -1;
}
catch(...) {
cerr << "main caught(...)" WY_ENDL;
return -1;
};
 
-------------
[]$ g++ chk_primetab.cpp -lwy -O2
[]$ time ./a.out
Check PrimeTab.h ...
cnt=203280222
OK
 
real 1m13.716s
user 1m13.180s
sys 0m0.168s
Bonita Montero <Bonita.Montero@gmail.com>: Feb 13 07:08PM +0100

Am 13.02.2024 um 17:15 schrieb wij:
 
> I just wrote a class PrimeTab to test prime numbers. It took 73s to
> complete.
> 0.1s is too unbelievable. Something must be wrong.
 
There's nothing wrong with that. I'm storing the bits as a bitmap and
I'm using a segmented sieve and I partition the part beyond the square
root in chunks which are according to the logical number of CPUs and
these are further divided into chunks which fit into the L2-cache.
And the sequential lookup inside the bitmap below the square root
is done with countl_zero, which maps to a single CPU-instruction
on most computers.
The naive single-threeaded approach without cache-partititioning is
for sure magnitudes slower.
Bonita Montero <Bonita.Montero@gmail.com>: Feb 13 12:07PM +0100

If you initialize a function<>-object with a reference_wrapper it
is guaranteed that the function<>-object references an external
function-object without any memory allocation. libstdc++ and libc++
don't allocate any memory with such function<>-objects according
to the standard, but MSVC does allocate external memory.
 
#include <iostream>
#include <functional>
 
using namespace std;
 
void *operator new( size_t n )
{
cout << "alloc" << endl;
void *p = malloc( n );
if( !p )
throw bad_alloc();
return p;
}
 
void operator delete( void *p )
{
free( p );
}
 
int main()
{
function<void ()> fn;
string str( "hello word" );
auto lam = [str = str]() { cout << str << endl; };
fn = ref( lam );
fn();
}
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.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)