My Fortran sieve drastically slows when the array exceeds 800,000,000

Question

I am a physicist, and recently I worked a lot with Fortran. Initially, I used Java extensively for recreation, because it was the first language I learned, but I abandoned it for Fortran and C ++. I have an amateur passion for primes, so I created a simple sieve. I was able to find all primes up to 2 ^ 31 in 15 seconds. This is the maximum array size for Java, so this is the end. I carefully ported the code (I mean ATTENTIVELY, I was so upset that my code was slow, and that I could not find an error, that I ported my Fortran code to Java to make sure that it was not my error, and then ported it back to Fortran, erasing every iteration!). The problem is that about 800 million Fortran will stop. Until that moment, he beat Java, but after that he was insanely slow. I spent several hours on the graph and curve fitting. It slows down exponentially and can take hundreds of years to solve down to the Javas level. I asked many people to no avail. Why is this happening to me?!?! Are there any wise fortran coders that can help me? I launch the Macbook Pro at the end of 2013 i5. My code is below.

program sieve integer(4),allocatable:: prime(:) integer(4)::a,max,b,primeCount write(*,*)"Welcome to the slow prime number sieve!" write(*,*)"--------------------------------------------" write(*,*)"Up to what numbers do you need to find primes for?" write(*,*)"Enter a number below 2^(32-1)" read*, max primeCount=0 allocate(prime(max)) prime(1)=1 do a=2,int(sqrt(real(max))) !the main loop if(prime(a)==0)then !if the number is marked as prime procede do b=2*a,max,a !eliminate all the numbers that are multiples of the number if(prime(b)==0)then !but only spend time eliminating if the number is still marked prime prime(b)=1 end if end do end if end do do a=1,max if(prime(a)==0)then primeCount=primeCount+1 end if end do print*, primeCount end program 

EDIT: My machine has 4 gigabits installed.

Answer 1

I can see a few things you could do to speed up the code, although none of them seem to explain the sharp drop in performance you are experiencing. The most likely culprit, apparently, is the limitation of RAM, as suggested by Alexander Vogt.

The first thing you need to do is change the prime from integer to logical . This reduces memory requirements and also speeds up the evaluation of if (prime(a)==0) .

The relevant parts of the code are as follows

 logical(1),allocatable:: prime(:) primeCount=0 allocate(prime(max)) prime = .false. prime(1)=.true. do a=2,int(sqrt(real(max))) !the main loop if(.not. prime(a))then !if the number is marked as prime procede do b=2*a,max,a !eliminate all the numbers that are multiples of the number if(.not. prime(b))then !but only spend time eliminating if the number is still marked prime prime(b)=.true. end if end do end if end do do a=1,max if(.not. prime(a))then primeCount=primeCount+1 end if end do 

I am not programming Java, but in Matlab, if you declare prime(1:max)=0 , and then only change the values ​​of bewteen 0 and 1 . I think Matlab treats the array as a logical array. Java can do the same. This may explain why your Java code does not suffer from performance degradation (assuming the RAM limitation is indeed a problem).

EDIT: I did some experiments.

On my machine (Debian Linux 64bit, i3, 16GB RAM, ifort 14 with default flags max=800 million (8E8) it took 22 seconds for max=800 million (8E8) . max=2E9 took 60 seconds. This is not the watch that was reported in the question. Also, in each case, the prime array was initialized to zero.

In addition, using integer(1) will run the program 33% faster than using integer(4) . With logical(1) it runs less than 5% faster than with integer(1) . This behavior is probably associated with better use of cash, since each prime element takes up less memory space, so the processor can perform more iterations when the data currently in cash goes through the cycles much faster.

The conclusions that I would like to draw from this would be that the culprit was the lack of RAM, as Alexander Vogt noted, and that there is a fair likelihood that the author's experience was not affected by the lack of initialization of the prime array (although that definitely should not have been happen) as HighPerformanceMark pointed out. Further, I suspect that Java declared prime as a logical array, and therefore the problem did not arise there. (Although 2 ^ 31 in 15 seconds in Java? The Fortran code used here doesn't come close to this. Was the same code mapped?)

Answer 2

This is more of an extended version of my previous comment than an answer. I think your mistake that you do not set all prime elements to 0 affects the execution time of the code, although initially my initial assessment was that it makes it faster.

The source code does not set 0 all primes elements. It is very likely that when these statements are first met:

 do a=2,int(sqrt(real(max))) !the main loop if(prime(a)==0)then !if the number is marked as prime procede 

prime(2) not 0 , so your algorithm cannot mark 2 and its multiplicity as prime. And it gets worse! If prime elements are not initialized to 0 , then prime(a) never be guaranteed to be 0 , and your program can run until completion without marking the number as prime. I would expect this error to make your code faster, since it will not go into the inner loop, and not by accident.

Faster, perhaps, but so broken that you should not evaluate its performance.

Answer 3

You can only store odd numbers in the prime(a) array. This would reduce the size of the prime array to half and the size of the loop. Also make sure that you are using the optimal optimization for your compiler.