# Computing at compile time

**URL:** <https://fortran-lang.discourse.group/t/computing-at-compile-time/3044>\
**Category:** Uncategorized\
**Created:** [March 24, 2022, 8:26pm UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044 "2022-03-24T20:26:06Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![certik](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/certik/32/4_2.png) [@certik](https://fortran-lang.discourse.group/u/certik)\
**Post date:** [March 24, 2022, 8:26pm UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/1 "2022-03-24T20:26:06Z")

</div>

This [discussion](https://github.com/j3-fortran/fortran_proposals/issues/253) 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:

```fortran
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:

```auto
 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.

---

<div class="post-metadata">

**Author:** ![Beliavsky](https://avatars.discourse-cdn.com/v4/letter/b/ba8739/32.png) [@Beliavsky](https://fortran-lang.discourse.group/u/Beliavsky)\
**Post date:** [March 24, 2022, 8:58pm UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/2 "2022-03-24T20:58:45Z")

</div>

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

```auto
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.

---

<div class="post-metadata">

**Author:** ![ivanpribec](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/ivanpribec/32/3290_2.png) [@ivanpribec](https://fortran-lang.discourse.group/u/ivanpribec)\
**Post date:** [March 24, 2022, 10:11pm UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/3 "2022-03-24T22:11:25Z")

</div>

There was a very nice talk on this topic by @mfurquan at FortranCon 2021: [Some adventures with compile time evaluation](https://tcevents.chem.uzh.ch/event/14/contributions/76/)

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.

---

<div class="post-metadata">

**Author:** ![everythingfunctional](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/everythingfunctional/32/176_2.png) [@everythingfunctional](https://fortran-lang.discourse.group/u/everythingfunctional)\
**Post date:** [March 24, 2022, 10:26pm UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/4 "2022-03-24T22:26:30Z")

</div>

> [@Beliavsky](#):
>
> Intel Fortran on Windows takes more than 30 seconds to compile the code on my PC.

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.

---

<div class="post-metadata">

**Author:** ![Beliavsky](https://avatars.discourse-cdn.com/v4/letter/b/ba8739/32.png) [@Beliavsky](https://fortran-lang.discourse.group/u/Beliavsky)\
**Post date:** [March 24, 2022, 10:33pm UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/5 "2022-03-24T22:33:31Z")

</div>

> [@everythingfunctional](#):
>
> > [@Beliavsky](#):
> >
> > Intel Fortran on Windows takes more than 30 seconds to compile the code on my PC.
> 
> 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.

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.

---

<div class="post-metadata">

**Author:** ![everythingfunctional](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/everythingfunctional/32/176_2.png) [@everythingfunctional](https://fortran-lang.discourse.group/u/everythingfunctional)\
**Post date:** [March 25, 2022, 12:59am UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/6 "2022-03-25T00:59:23Z")

</div>

> [@Beliavsky](#):
>
> 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.

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

---

<div class="post-metadata">

**Author:** ![Arjen](https://avatars.discourse-cdn.com/v4/letter/a/b9bd4f/32.png) [@Arjen](https://fortran-lang.discourse.group/u/Arjen)\
**Post date:** [March 25, 2022, 8:57am UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/7 "2022-03-25T08:57:51Z")

</div>

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:

```auto
! 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.

---

<div class="post-metadata">

**Author:** ![Arjen](https://avatars.discourse-cdn.com/v4/letter/a/b9bd4f/32.png) [@Arjen](https://fortran-lang.discourse.group/u/Arjen)\
**Post date:** [March 25, 2022, 9:33am UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/8 "2022-03-25T09:33:14Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![gnikit](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/gnikit/32/1213_2.png) [@gnikit](https://fortran-lang.discourse.group/u/gnikit)\
**Post date:** [March 25, 2022, 10:45am UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/9 "2022-03-25T10:45:39Z")

</div>

> [@Arjen](#):
>
> gfortran and Intel Fortran have now taken more than 15 minutes to compile

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

---

<div class="post-metadata">

**Author:** ![Arjen](https://avatars.discourse-cdn.com/v4/letter/a/b9bd4f/32.png) [@Arjen](https://fortran-lang.discourse.group/u/Arjen)\
**Post date:** [March 25, 2022, 10:52am UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/10 "2022-03-25T10:52:07Z")

</div>

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)

---

<div class="post-metadata">

**Author:** ![cmaapic](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/cmaapic/32/659_2.png) [@cmaapic](https://fortran-lang.discourse.group/u/cmaapic)\
**Post date:** [March 25, 2022, 11:09am UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/11 "2022-03-25T11:09:45Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![themos](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/themos/32/521_2.png) [@themos](https://fortran-lang.discourse.group/u/themos)\
**Post date:** [March 25, 2022, 11:23am UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/12 "2022-03-25T11:23:15Z")

</div>

> > 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).

---

<div class="post-metadata">

**Author:** ![Arjen](https://avatars.discourse-cdn.com/v4/letter/a/b9bd4f/32.png) [@Arjen](https://fortran-lang.discourse.group/u/Arjen)\
**Post date:** [March 25, 2022, 12:48pm UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/13 "2022-03-25T12:48:25Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Arjen](https://avatars.discourse-cdn.com/v4/letter/a/b9bd4f/32.png) [@Arjen](https://fortran-lang.discourse.group/u/Arjen)\
**Post date:** [March 25, 2022, 2:21pm UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/14 "2022-03-25T14:21:00Z")

</div>

gfortran has finished: it five hours and sixteen minutes.

Intel Fortran oneAPI still going strong …

---

<div class="post-metadata">

**Author:** ![themos](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/themos/32/521_2.png) [@themos](https://fortran-lang.discourse.group/u/themos)\
**Post date:** [March 25, 2022, 2:37pm UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/15 "2022-03-25T14:37:47Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Arjen](https://avatars.discourse-cdn.com/v4/letter/a/b9bd4f/32.png) [@Arjen](https://fortran-lang.discourse.group/u/Arjen)\
**Post date:** [March 25, 2022, 2:55pm UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/17 "2022-03-25T14:55:40Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Arjen](https://avatars.discourse-cdn.com/v4/letter/a/b9bd4f/32.png) [@Arjen](https://fortran-lang.discourse.group/u/Arjen)\
**Post date:** [March 25, 2022, 4:06pm UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/19 "2022-03-25T16:06:13Z")

</div>

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)

---

<div class="post-metadata">

**Author:** ![cmaapic](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/cmaapic/32/659_2.png) [@cmaapic](https://fortran-lang.discourse.group/u/cmaapic)\
**Post date:** [March 25, 2022, 4:07pm UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/20 "2022-03-25T16:07:26Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mecej4](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/mecej4/32/855_2.png) [@mecej4](https://fortran-lang.discourse.group/u/mecej4)\
**Post date:** [March 26, 2022, 1:23am UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/22 "2022-03-26T01:23:28Z")

</div>

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.

```auto
! 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!

---

<div class="post-metadata">

**Author:** ![certik](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/certik/32/4_2.png) [@certik](https://fortran-lang.discourse.group/u/certik)\
**Post date:** [March 26, 2022, 2:04am UTC](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044/23 "2022-03-26T02:04:59Z")

</div>

> [@ivanpribec](#):
>
> Edit: I’d be extremely impressed if someone could write a compile time prime-sieve.

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

[Next page](https://fortran-lang.discourse.group/t/computing-at-compile-time/3044.md?page=2)