Compile Time Computing

[mecej4]

Modern Fortran provides many features to enable one to write programs in which a surprising amount of work can be completed at compile time, using Initialization Expressions and Array Constructors.

Two years ago, this feature was discussed in the thread Computing at Compile Time in the fortran-lang.discourse.group. Arjen Markus (forum participant here and author of Modern Fortran in Practice, 2012, Camb. Univ. Press) . In that thread, Ivan Pribec wrote, "I’d be extremely impressed if someone could write a compile time prime-sieve." Arjen responded with "I could not resist the challenge", and offered the following solution (CTS0) and opened my eyes to the concept of "compile-time-computing". In his book, Arjen applies these ideas to a range of problems, for example, Quicksort.

program primesieve
implicit none

integer, parameter :: N = 100
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

Note that all calculations are done before the EXE has been produced or run, and that the only executable statement is the WRITE statement. Compilers that know Fortran 2008 and above (or older versions, with extensions) can compile this program in a few seconds, at most, and the run time is negligible.

Arjen tried raising N to 1000, but gave up after waiting for the compilers to finish for about 15 minutes. In a later post, he noted that Gfortran finished compiling after over five hours. A NAG staffer ("Themos" Theodore-Thomas Tsikas) reported that the NAG Fortran compiled the program (with N=1000) in 3.4 seconds.

Note that we normally do not expect compilation time to be affected by our changing a single literal constant in the program source code!

The topic and the comments posted in that thread aroused my interest, and I posted the following improved version CTS1 (by excluding even numbers as candidate primes, etc., the MULTIPLES array was reduced in size from over a million to 563).

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

end program primesieve

This version could be compiled (in March 2022) by Ifort and IFX in less than a second and by Gfortran in about 3 seconds. Various forum posts followed, exploring program behavior with N = 100,000 and higher. "Themos" admonished us that "The compiler is not required to do anything, except somehow produce the correct output", and reported that the NAG compiler took 28 minutes for CTS1 with N = 1 million. I then posted the following version CTS2, in which the list of primes is built up in multiple stages (all at compilation time).

program primesieve
implicit none

integer, parameter :: rtrtN = 31, rtN = 1000, N = 1000000
integer :: i, np
integer, parameter :: candidates1(*) = [(i, i=rtrtN,rtN-1,2)]
integer, parameter :: primes0(*) = [2,3,5,7,11,13,17,19,23,29,31] ! 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,N-1,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 NAG compiler compiles CTS2 in about 3 seconds. The others, including IFX/IFort, did not finish within 5 minutes, and I aborted their compilations.

In a recent thread that he started in this forum, Arjen applied the same methods to a slightly different problem -- finding Ramanujan numbers. I found that a simplified version of Arjen's program, with three lines of declaration and one executable statement (WRITE the result(s)) could not be compiled by IFX 2024.1 in one minute. Ron Green posted an encouraging response, noting that Intel is aware of the slow processing of complicated initializations in Ifort/IFX, and may explore ways to make improvements.

The current situation provides Intel Fortran users an opportunity to give input into the process. Here are a couple of questions to get you started:

   1. Does your work involve code that contains complicated or long initializations?

   2. How do you compensate for the compiler's sluggishness in this aspect of compiling?

   3. Is it worth devoting developers' time into this topic?

[jimdempseyatthecove]

Interesting.

FWIW - If I were to run into a similar situation, (excessive compile times), I would rewrite the code to perform runtime initialization.

While we cannot make a parameter out of a variable, we can make it intent(in).

Jim Dempsey

[mecej4]

What makes this topic intriguing is that the compile times are rather unpredictable. In a recent thread, I displayed an example with about ten lines of code in which the initialize-at-runtime version takes a minute to compile whereas the compile-time-compute version finishes in about a second.

[Ron_Green · Accepted solution]

I do think these 3 and those on the other thread are exposing the same bug. Nevertheless, I opened a unique bug report for these 3 CMPLRLLVM-57647