last day (15 days later) » 

10:42 PM
1
Q: prime number below 2 billion - usage of std::list hinders performance

Apoorva RajuProblem Statement is to find prime number below 2 billion in timeframe < 20 sec. I followed below approaches. Divide the number n with list of number k ( k < sqrt(n)) - took 20 sec Divide the number n with list of prime number below sqrt(n).In this scenario I stored prime numbers in std::list ...

 
Try std::vector.
 
@tkausl Although it may improve performance, it doesn't answer OP's question because both variations use list.
 
@tkausl Could be useful, but only if one remembers to reserve a suitable number of elements beforehand. It also won't help much with the big problem which is most likely the iteration and what's done inside the loop in check_prime.
 
Get the compiler to do it. Implement with metaprogramming and constant expression programming. O(1) at runtime. Nice.
 
What exceptions are you expecting to be thrown by your code? And if you're not doing anything special when you catch one, by catch it at all? Removing the try ... catch could possibly improve both your examples.
 
10:42 PM
@Someprogrammerdude my code crashes due to some issue .. so had that catch for debugging purpose will update/remove it
@Bathsheba thanks a lot let me try these approach
 
@ApoorvaRaju: Actually I'm being facetious. What you really want to do it to use a sieve to establish primality up to and including the square root of 2 billion, then use broadly your second approach for the check. You could use the compiler for the former, but that's probably against the spirit of the problem. See stoppels.blog/posts/compile-time-primes
@ApoorvaRaju: Also have a look at the mathematics behind probable primes. That's something you can check for first, but of course that actually adds overhead for some cases. So for a blunt tool that always works fast for any number it might not be an appropriate technique.
 
For time critical applications, don't use STL or smart-pointers, they are heavy, although they ease development process. Use bit level manipulation or even asm modules for extra speed boost.
 
A cache miss list is pretty much never something you actually want to be using. Insertion and rotation are faster with one in theory but iteration speed is just cripplingly slow. On my machine register access is pretty much free, an L1 fetch takes ~3 cycles where as an L3 cache miss (ram fetch) is ~200-300 cycles.
 
@seccpur "For time critical applications, don't use STL or smart-pointers, they are heavy" if this was true c++ would be crap
 
10:42 PM
@Bathsheba the sqrt of 2 bil is so small (44721) it really shouldn't matter whether you use the sieve or trial division by primes / odds up to its sqrt (211) to find the primes below it.
 
@WillNess: That would need benchmarking - I'm not sure I agree with that. Mind you if I had to do this in production and from scratch for some reason, I'd use the compiler to generate the "square root set".
 
Why are you checking if even numbers are prime? ;)
 
@Bathsheba FYI a test at ideone completely contradicts the claims made in this question.
@Someprogrammerdude FYI a test at ideone completely contradicts the claims made in this question.
@ApoorvaRaju so could you please clarify the situation? Do you stand by your claims? Have you re-run your tests carefully and got the same - or the completely opposite - results? Can you share a link to a live code site , with a test which supports your claims in the question, or was it in fact an error?
@MattTimmermans FYI a test at ideone completely contradicts the claims made in this question.
 
@WillNess I executed it on my VisualStudio 2015 in my local system and used clock_t library to calculate time taken . I am really not sure if this is right way to calculate time taken but with this approach it took me more time
 
As you can see on the ideone entry, it is the right way to measure time as it corresponds very well with the times that it reports. the question is, whether you are absolutely sure you used the same parameter - 2000000000 - for both tests, and whether you used the same compiler option for the both tests. Could you re-run your tests to be sure there wasn't a simple mistake in that regard, please? Can you repeat your observations, at all? First thing we learn about scientific method is that tests must be repeatable. Please clarify.
 

last day (15 days later) »