- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
Link Copied
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
@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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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?
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
@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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
@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]
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
@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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
Bug ID CMPLRLLVM-36328
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
@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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
@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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
>>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

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page