disturbance_is_created's blog

By disturbance_is_created, 5 weeks ago, In English,

I used const int mod and int mod and they both had a different execution time.

int mod = 1e9 + 7 execution time : more than 1 sec code : https://cses.fi/problemset/result/651565/

int const mod = 1e9 + 7 execution time 0.58 sec code : https://cses.fi/problemset/result/651564/

can anyone explain why there is such a huge difference?

on codeforces the above code executes in less than 1 sec.

 
 
 
 
  • Vote: I like it
  • +54
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +97 Vote: I do not like it

This is a good question. The answer is that compiler can optimize constant modulo because it doesn't change. In the first case it would be possible for you to change modulo anytime, compiler doesn't bother to verify whether you do i guess. But in the second case it knows that it's a constant and it can apply stuff like Barrett reduction.

»
5 weeks ago, # |
  Vote: I like it +56 Vote: I do not like it

constexpr is even better than const. It guarantees that things are evaluated at compile time which can allow more optimizations.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    looking at you submissions i think you love to use it. thnks man i will also use it.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Right, constexpr is the most appropriate keyword for defining constants like mentioned one.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What about #define mod 100000007 ? Will it be faster or slower?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      It certainly won't be faster, and in general you should prefer constexpr to macros. It makes your intent more clear to the compiler so it can do more optimizations and error checking.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    const int automatically makes it constexpr whenever possible. e.g.

    const int N = int(acos(-1));
    int a[N];
    

    compiles okay, as N here is implicitly constexpr. But:

    const int N = __gcd(6, 9);
    int a[N];
    

    results in error: size of array ‘a’ is not an integral constant-expression

    More info here.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      I think you are wrong. If const keyword automatically makes its object constexpr then there is no reason to introduce a new keyword, right?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I meant to say, const int variable makes it constexpr int whenever possible as stated in this stackoverflow answer. constexpr has many other uses, e.g. if constexpr int is a function's return type, the function can be used to declare global array, this can't be done by const int:

        constexpr int fib(int n) {
            return n<=2 ? 1 : fib(n-1)+fib(n-2);
        }
        
        int a[fib(35)];
        
    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      std::acos isn't required to be constexpr so it may be evaluated at runtime. If you have constexpr int a = (int)acos(-1), you know for sure that if it compiles, it is evaluated at compile time. (I'm not completely sure about that so I could be wrong.) In general it's better to give the compiler as much information as possible by making things const and constexpr so it can optimize and error check as much as possible. Also constexpr is more readable.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

A compiler can optimize usages of a variable depending on its linkage. You can write static int mod = 1e9 + 7; and get same result as for const int mod = 1e9 + 7; because of internal linkage.

Add: In addition, you can write extern const int mod;, define mod in another file and get same result as for int mod = 1e9 + 7; despite the fact that the mod is defined as const.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    The const still matters sometimes. This:

    #include <array>
    using namespace std;
    
    int main()
    {
    	static int a = 5;
    	array<int, a> foo;
    }
    

    Won't compile even though the value of a can be deduced at compile time because a is not a constant expression as defined by the standard.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sure. However I wanted to say that optimization capability is based not on the fact a variable is defined as constant as kostia244 said.