Silly program takes a very long time to get compiled

[Arjen_Markus]

At the Fortran discourse site (https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/13) there is a discussion about the possibility to use compile-time computation. I wrote a small program to meet a challenge that was posted, getting a list of prime numbers at run-time. While hardly the right tool of course, for more serious purposes, it is short and it causes an amazing problem it seems for the compiler. The Intel Fortran oneAPI compiler has been running for more than 4 hours (as has the gfortran compiler).

Here is the code:

! primesieve.f90 --
!     Is it possible t obuild a prime sieve using compile-time computation?
!
program primesieve
    implicit none

    integer, parameter :: N = 1000
    integer            :: i, j
    integer, parameter :: candidates(*) = [(i, i=2,N)]
    integer, parameter :: multiples(*)  = [(( i*j, i=2,N), j=2,N)]
    integer, parameter :: primes(*)     = pack( candidates, [(all(candidates(i) /= multiples), i = 1,size(candidates))] )

    write(*,*) primes

end program primesieve

[Ron_Green]

Now that is an interesting test!  Our compiler has had issues with the speed of initializations.  I had a bug open against IFX on this general topic.  Not this example, but rather a source file with 80,000 or so lines of code with DATA statements.  Or was is simple initializations?  In either case, IFX was slower than IFORT but a substantial factor ( 3-5x or so slower).   We improved IFX and got it 'roughly' the same as IFORT but it was non-trivial.  Sounds easy, right?  Sometimes those 'easy' code fixes worm throughout the code and end up taking weeks to get right.  With all the problems to solve in a compiler, compile time data initialization speed and efficiency just isn't the top of the priorities.

I might scale this down to something that compilers in 10minutes or so and see where IFX is wrt to IFORT wrt gfortran 11.  A Friday diversion.  Thanks.

ron

[Arjen_Markus]

While the programs I work on are hardly of the complexity level of a compiler, I know the feeling ;). The reason I mention it, is not to urge you to do something about it, but to report it as one of those faits divers that you can sometimes do little about. Being aware of the problem is at least a bit better than getting surprised.

We recently found that the results of one of our programs changed subtly when we added a new feature. The changes caused a number of tests to fail because they tested a rather sensitive module. There was no direct connection with the code change, as far we could see. We suspected all manner of complicated issues, but in the end we solved it by using a double precision variable to do a summation over a handful of values. The search for the bug (if you can call it that) was systematic at first and in the wrong place. As nothing untoward revealed itself we were getting desperate ... One saliant detail: the debug version was okay, the release version showed the failing tests. I am not sure anymore how we found out what the cause was.

[Ron_Green]

This was a fun Friday diversion.  With N=100

gfortran ~ 5secs

IFX and IFORT ~48secs 

We do know we have some issues with compile-time initialization.  This is a textbook case for it.  I'll put this on our 'to do' list (feature request) for some future date. 

[mecej4]

Here is a modified version of Arjen_Markus's program, which the current versions of IFort and IFx compile in less than 1 second even for N = 1000, while retaining the computing-at-compile-time attribute. The modifications exploit two properties of the calculation:

• No need to consider even integers (other than 2) as candidate prime numbers
• No need to insert entries larger than N in the multiples array.

Here is the code:

program primesieve
    implicit none

    integer, parameter :: N = 1000
    integer, parameter :: rtN = 31 ! isqrt(N)
    integer            :: i, j
    integer, parameter :: candidates(*) = [2,(i, i=3,N-1,2)]
    integer, parameter :: multiples(*)  = [(( i*j, i=j,N/j,2), j=3,rtN,2)]
    integer, parameter :: primes(*)     = pack( candidates, [(all(candidates(i) /= multiples), i = 1,size(candidates))] )

    write(*,'(10I8)') primes
    print *
    write(*,*) size(multiples),size(primes)

end program primesieve

[JNichols]

Nice modifications,

I had a look at the compile times for increasing N.  

N      Time(s)           sqrt(N)       Time(s)   log(time)
1000	2		31.6227766	2	0.301029996
2000	9		44.72135955	9	0.954242509
3000	31		54.77225575	31	1.491361694
4000	85		63.2455532	85	1.929418926
5000	190		70.71067812	190	2.278753601
6000	435		77.45966692	435	2.638489257
7000	740		83.66600265	740	2.86923172
8000	1030		89.4427191	1030	3.012837225
9000	1240		94.86832981	1240	3.093421685

A quick look suggested that to do N == 100000 that we are looking at centuries of time, but I will do a few more cycles to see if it bends over.  

[mecej4]

I suspect that you will get a better fit if you curve-fit the relation

     log(t_compile) = a + b log(N) + c loglog(N)

at least for the smaller ranges of N. For large N, the compile time evaluation may be significantly affected by the memory caches.

[JNichols]

18000 has an out of memory error on 64 bit debug build on a core i7.  And theoretically 18000 will take 6 hours to compile.  At 5 hours it crashed.  

Ideas to solve that one?  I have to solve a bridge problem.  

[mecej4]

@JNichols: "And theoretically 18000 will take 6 hours to compile.  At 5 hours it crashed."

On another forum, a NAG software engineer reported that the NAG 7.1 compiler gave the following results for compilation times:

     N=100,000 in 8 14 seconds.
     N=200,000 in 32 58 seconds.

P.S.: timings revised, the earlier reported timings were for a version of the program that had a bug.

[Arjen_Markus]

Odd, I stopped the compiler after it had been trying to build an N=1000 version for two days and two hours. That was not a debug build though, just a plain compile and link without specific options.

[mecej4]

Here is an improved version that can be built and run with Ifort, Ifx and Gfortran in a few seconds.

program primesieve
    implicit none

    integer, parameter :: rtrtN = 10, rtN = 100, N = 10000
    integer            :: i, np
    integer, parameter :: candidates1(*) = [(i, i=rtrtN+1+mod(rtrtN,2),rtN-1-mod(rtN,2),2)]
    integer, parameter :: primes0(*)  = [2,3,5,7] ! primes <= rtrtN, used to seed calculation
    integer, parameter :: primes1(*) = &
       pack( candidates1, [(all(mod(candidates1(i),primes0) /= 0), &
          i = 1,size(candidates1))] )  ! newly identified primes < rtN
    integer, parameter :: candidates2(*) = [(i,i=rtN+1+mod(rtN,2),N-1-mod(N,2),2)]
    integer, parameter :: primes01(*) = [primes0, primes1]        ! primes <= rtN
    integer, parameter :: primes2(*) = pack(candidates2,[(all(mod(candidates2(i),primes01) /=0), &
                   i = 1,size(candidates2))])

    np = size(primes2)
    write(*,'(i5,A10,i4)') size(primes01),' primes < ',rtN
    write(*,'(i5,A10,i7)') size(primes01)+size(primes2),' primes < ',N
    print *
    print *,' Last 10 primes < ',N,' :'
    write(*,'(10I8)') primes2(np-9:np)

end program primesieve

The expected output:

   25 primes <  100
 1229 primes <   10000

  Last 10 primes <  10000  :
    9887    9901    9907    9923    9929    9931    9941    9949    9967    9973

A useful resource for checking such output: How many primes are there? 

[JNichols]

25 prime numbers from 1 to 100

This is the statement that really gets up my wick.  There are 25 primes from 1 to 97.  100 is just a decimal number in the stretch to the next  prime at 101, it is not even in the middle of the stretch. The famous equation from 19th century predicts the mid point of the non-prime stretches, but the other function of interest,  is the one that predicts the 97, 101 as an upper limit.

It is not that great a predictor. 

[JNichols]

@mecej4  - I have 40 years of experimental data collection. I set up a new solution file in Intel, added you code and then hand timed the runs.  In the end I used Alexa to set an alarm to then follow the run.   Here is the zip file of the solution - you can run it on any computer.  It includes the Excel file.  

Running on a stock standard CORE7 with a Samsung 970 SSD, 8 GB memory and the latest Windows 11 Preview and VS 2022 and the latest Intel oneapi.  

I use one Fortran compiler, I have used MS through to Intel since 1988, I do not play with other compilers, and LINUX is a pain in the ear to run.  

I measured most of them twice to make sure and they follow a pretty good regression, I did not have the time for your suggestion, but it will be close to a fourth order polynomial.  

Al Hill identified a slow down in Windows 11, but according to MAX PC that was solved last year.  They have never published anything I have found to be incorrect that I was interested in,  

It is not a perfect machine, but it is not that slow, I did not run anything else whilst I was doing the runs.  

[AlHill]

@JNichols "Al Hill identified a slow down in Windows 11".    Highly unlikely this is related, John.

Doc (not an Intel employee or contractor)
[Maybe Windows 12 will be better]

[JNichols]

@AlHill , I know, but I just wanted you to know I had thought about it.  

There is no real Windows 11 - IMHO , it is just an extension of 10, all the internal product numbers code as 10.  They are doing some interesting things as well on the front end.  I had to play with UBUNTU for a week and it gave me headaches, you need a lifetime to understand that little OS.  

@mecej4  can you load you latest program as a.f90 file, I cannot get opera to copy your code, it just does not copy.  I have rebooted and sworn at the Titans and it does not work.  I am refusing the Minoan method to solve a problem. 

[Ron_Green · Accepted solution]

Bug ID CMPLRLLVM-36328

[JNichols]

Ron:

I absolutely cannot copy anything from this website at the moment.  I select the text and when I try to copy the selected text looses the highlight.  

Any ideas

John

[mecej4]

@JNichols wrote, "I select the text and when I try to copy the selected text looses the highlight.  Any ideas"

Yes. Click-drag to select text with the mouse, but don't let up on the mouse yet. With the other hand (usually left hand) press down the control key, and have another finger ready to press the C key. Let go of the mouse and press the C, in quick succession. Then, let up on the control key. The text will have been copied to the clipboard.

[JNichols]

@mecej4 , thanks, you are a useful gold mine, much like D. Callum in the book Winter Holiday.  If you have not read it and you have a young grandchild 8 to 12 get it for them it will teach them scientific method without pain. 

[JNichols]

And God works in mysterious ways, I am using an Intel Fortran program as a data collection device.  I take this computer into the field to collect data with a friend and the blasted battery goes flat on the friend.  Data collection can be quite interesting in terms of problems.  So I buy a new battery, fit it to the machine, which has the smallest screws I have seen outside a watch.  Then boot manager starts throwing errors, unknown equipment,  it is a blasted battery why would it even know the difference.  

Finally after using tricks to keep it working BSOD this morning.  Wipe hard drive, install windows, it installs Windows 11 Home with a pro key.   Renter a pro key into activation point, says good to go. Restart and there is home still.  You have to go the Microsoft store and tell it to upgrade.  

As I am installing VS 2022, there is a note to say 2022 Preview is out for the next edition, next screen tells me support for VS 2017 has stopped.  

Lastly why do they not put the 32 bit version of MKL in the main base install.  It would save 20 wasted minutes and it is only about 32 MB. 

Why does Opera use Oslo as the base city for weather on a clean install?  That is a weird choice.  

Back to install. 

Then again it only takes a few hours and not a day as for Windows 7.  

[jimdempseyatthecove]

>>Then boot manager starts throwing errors, unknown equipment,  it is a blasted battery why would it even know the difference.

This might be one of those "features" that equipment manufactures are using for force users to ship their equipment to their repair sites.

IOW the batteries have serial numbers mated to the firmware. 

See: Unplugging the battery BRICKS this device; you MUST go back to the manufacturer 

Jim Dempsey