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
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.
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.
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.
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
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.
@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:
8 14 seconds.
32 58 seconds.
P.S.: timings revised, the earlier reported timings were for a version of the program that had a bug.
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?
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.
@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 , 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.
@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.
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.
>>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.