Computing at compile time

1

This discussion got me the idea to see how much you can compute at compile time. For example this program computes \int_a^b \sin(x) dx at compile time:

program compile_time
implicit none
integer, parameter :: N = 65535
integer, parameter :: sp = kind(1.0)
integer, parameter :: dp = kind(1.d0)
real(dp), parameter :: pi = 2*asin(1._dp)
real(dp), parameter :: a = 0, b = pi
real(dp), parameter :: dx = (b-a)/N
integer :: i
real(dp), parameter :: X(*) = [(sin(a+(b-a)*i/N), i = 1, N)]
real(dp), parameter :: S = sum(X)*dx
logical, parameter :: l = S < 2
real(kind=merge(sp, dp, l)) :: y
if (kind(y) == sp) then
    print *, "true"
else
    print *, "false"
end if
print *, S
end program

It prints:

 true
   1.9999999996170159

The value in S must be known at compile time, because it is used to determine the kind of the variable y, which must be known at compile time.

It looks like one can already do loops, if statements, etc.

9 Likes
2

Neat, thanks. Compiling implied do loops can be slow. For the slightly modified code

program compile_time
implicit none
integer , parameter :: N = 65535
integer , parameter :: wp = kind(1.0d0)
real(wp), parameter :: pi = 2*asin(1._wp), a = 0, b = pi, &
                       dx = (b-a)/N
integer             :: i
real(wp), parameter :: X(*) = [(sin(a+(b-a)*i/N), i = 1, N)]
real(wp), parameter :: S = sum(X)*dx
print*,S ! 1.9999983550656624 gfortran, ifort 1.99999999961702
end program compile_time

Intel Fortran on Windows takes more than 30 seconds to compile the code on my PC.

6 Likes
3

There was a very nice talk on this topic by @mfurquan at FortranCon 2021: Some adventures with compile time evaluation

If I remember correctly the last slide was an analogy with vortexes in a flowing fluid, similar to how the fluid is stretched and folded, we can use packing/unpacking, or generating/reshaping to evaluate the desired expression.

Edit: Iā€™d be extremely impressed if someone could write a compile time prime-sieve.

3 Likes
4

Is doing 65,535 calculations of sin, so that would make sense. Iā€™d guess the equivalent program would take a similar amount of time in many interpreted languages.

1 Like
5

Gfortran only takes 2 seconds to compile it, though, so the speed of compile time calculations across compilers seems to vary more than run-time speed.

6

Does this mean we should start benchmarking the compile time computation speed of different compilers? :stuck_out_tongue:

1 Like
7

Well, I could not resist the challenge, and I must confess it is not a true prime sieve, more a brute force approach, but here is one solution to computing a list of primes at compile-time:

! primesieve.f90 --
!     Is it possible t obuild a prime sieve using compile-time computation?
!
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

I first tried with N = 1000, but then gfortran choked, gaspng that I should use -fmax-array-constructor. When I tried that, my patience was exhausted. May try again later on.

The program in this state does get compiled by both gfortran and Intel Fortran, even in a reasonable time, though Intel Fortran is slower and compiling takes, eh, a bit longer than you would expect from so tiny a program. But they both give executables that do their job.

5 Likes
8

Update: with N=1000 both gfortran and Intel Fortran have now taken more than 15 minutes to compile the program and there is no indication that they are about to complete the task.

Conclusion: if you want a list of primes, you are probably better off computing it in run-time.

4 Likes
9

I stopped my compilations at 1.5h, not sure if the compiler was doing any work or it was simply stuck.

10

Me neither, I intend to let them run in the background, until I turn off the laptop. Just curious to see what the result is (not the list of primes, the compile time)

11

Iā€™ve hit problems with a variety of compilers doing compile time initialisation of variables. Got some very interesting replies from some vendors.

12

time (nagfor /tmp/primes_ct.f90 ; ./a.out )
NAG Fortran Compiler Release 7.1(Hanzomon) Build 7106
[NAG Fortran Compiler normal termination]
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997

real 0m3.394s
user 0m3.323s
sys 0m0.016s

The N=2000 case takes about 24 seconds, looks like O(N**3).

4 Likes
13

That sounds right: quadratic to fill the array of multiples and then the loop over all the candidates to see if any occur within that list of multiples.

1 Like
14

gfortran has finished: it five hours and sixteen minutes.

Intel Fortran oneAPI still going strong ā€¦

4 Likes
15

For added insight, comment out the WRITE statement and compare the times.

17

As I said in a post to the Intel forum about it, it is a silly program :slight_smile: And I appreciate gfortran offering a remedy right away for the limit.

1 Like
19

That is several orders of magnitude more memory than I would as a naĆÆve programmer expect!

(The Intel compiler is still considering my program and it takes 1 GB of memory. I have no idea how much it usually takes, as compilation is usually quick and so I would not even bother to find out)

20

I have a teaching example which uses a 375,000+ word dictionary. The overall best way to get the ā€˜wordsā€™ into a data structure is reading the file. In Fortran I read into an array and use a binary search algorithm. In C# and C++ I use sets and set membership, but with both of these too I read the data in. Worst case scenario is 375,000+ lines of source code. Not worth trying to ā€˜computeā€™ at compile time in my opinion.

22

I hereby nominate Arjen as Leader of the PACK Intrinsic (is groepsleider better?).

Here is a slight modification of his program, with two speed-ups:

  1. Avoid even numbers in candidates, except for 2.

  2. Avoid putting numbers larger than N in the multiples array.

! primesieve.f90 --
!     Is it possible to build a prime sieve using compile-time computation?
!
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 should work with more compilers, while retaining the attribute of ā€œall calculations done at compile timeā€.

This version, with N equal to 1000, compiled with GFortran 12 (Windows Cygwin64) in less than 3 s (i7-10710U CPU). Intelā€™s Ifort and Ifx compilers took less than 1 second to compile and run. For this value of N, the size of the multiples array in this version is 563, whereas Arjenā€™s original version had it at nearly one million!

7 Likes
23

So now when this is done, whatā€™s the next challenge for compile time computing?