Doubts on constexpr and virtual memory

1
  1. CodeChef: Practical coding for everyone
  2. CodeChef: Practical coding for everyone
    They are the exact same code with only one difference.
    In code 1 “mod” variable is declared as constexpr long long int
    In code 2 “mod” variable is declared as long long int
    In both the “mod” variable is initialised with value 1e9+7

But their runtime is very different.
code 1=> 0.26 sec
code 2=> 0.62 sec

So, the first question is why this happened?

I know a thing that using constexpr we can tell compiler a part to execute during compile time. So, that the time will not be considered in Runtime. I may be wrong, if so then please tell correct thing.

So, I tried to fill an array of factorial and its modular inverse in another array during compile time.
In custom test only it gave virtual memory exceeded. The size of both array each was 5e5.
But if I will store same thing during runtime it will run and it’s proof is above two codes.

So, second question is what is this virtual memory? How virtual memory exceeded different from memory limit exceeded (which generally gives SIGSEGV ).

Please Help.

2

llvm generates basically identical code to the constexpr case if you use const instead, so it’s more about “inlining a constant value” (instead of having to fetch the value of mod every time it’s used) than “compute something at compile-time”.

I was a bit puzzled as to why the compiler wasn’t detecting, in the case where mod is not declared constexpr nor const, the fact it was never changed and inlining it anyway, but then I noticed that mod is extern: in this case, if the compiler isn’t aware that the executable being compiled is a stand-alone one, it might assume that mod is being changed in some other source file, and so not deduce that it is const and so not inline it.

Putting mod in an unnamed namespace (effectively giving it internal linkage) then makes llvm generate basically identical code to the const and constexpr case.

1 Like
3

It means the performance enhanced due to inlining of mod, if I got it right. Thanks for explaining.

1 Like
4

@ssjgz Are you trying to compare mod as it is without const/constexpr in the unnamed namespace with const/constexpr mod declared globally? I tried to do so and compiled with g++ 7.5.0 and the resultant codes were pretty different. Did I do anything wrong or is clang really that different? :thinking:

1 Like
5

Yep:

using namespace std;
constexpr ll mod = 1000000007;

template<typename T, typename U>
void operator %=(T& a, const U& m) { if (abs(a) >= m)a %= m; if (a < 0)a += m; }

vs

using namespace std;

namespace {
   ll mod = 1000000007;
}
template<typename T, typename U>
void operator %=(T& a, const U& m) { if (abs(a) >= m)a %= m; if (a < 0)a += m; }

I only looked at the LLVM IR, so maybe I’ve made a mistake somewhere - you should probably double-check :slight_smile:

Edit:

Command used:

clang++ skywarrior-SUBSFREQ-constexpr.cpp -S -emit-llvm -o skywarrior-SUBSFREQ-constexpr.S -O3  -c

and similar for const, normal, internal etc.

1 Like
6

I stored the two respectively in prog1.cpp and prog2.cpp and did this:

❯ g++ prog1.cpp prog2.cpp -std=c++14 -S
❯ wc prog1.s && wc prog2.s
 11822  26819 322022 prog1.s
 11860  26931 323637 prog2.s

Since I don’t have clang, I was looking at the GNU Assembly. The diff logs are pretty messy because of the variable names but I did notice some differences in the numbers in the assemblies. In theory, there shouldn’t be any difference other than in the variable names. Maybe this is a bug in gcc? I didn’t find any difference other than changes in variable names for diluted examples. :slight_smile:

1 Like
7

Ah yes - now I try with gcc, the results are quite different - specially at -O3. No idea why - probably not so much “a bug” as, perhaps, a missed optimisation opportunity? Dunno :slight_smile: :man_shrugging:

1 Like
8

Can you please explain me this problem an what is inlining of mod/constexpr??