Doubt regarding C++

I was going through this blog which explains how to check whether a number is prime or not in O(1) runtime complexity.
In the comments I found a piece of code which compares the time taken to check for prime numbers using the conventional runtime sieve and the explained compile-time evaluated sieve.

My doubt lies in the slow_is_prime() function on line no. 31.
What does the statement: (Sieve<MAXN>{}).is_prime[n] mean?
I understand that MAXN is the parameter passed to the Sieve struct, which is what we would have done while creating a variable of its type as well, but what significance does the {} braces have?

How is it different from:
Sieve<MAXN> a;
return a.is_prime[n]; ?

Also, if you tweak the code a little bit and rather than what is given, if you replace the contents of the slow_is_prime function with:
Sieve<MAXN> a;
return a.is_prime[n];
there is a considerable difference in the runtimes.

I would be grateful to know your views and/or inputs.

1 Like

My knowledge of C++ is not deep so I am not able to give a convincing answer.

Regarding the empty bracket you mention it’s just sending no parameter to the constructor of the structure, like if you call vector<int>{}. Try for example: cout << (vector<int>{}).size() and see the output is 0 but if you call cout << (vector<int>{7}).size() you obtain 1.

My intuition about the differences in running times is that when you call (Sieve<MAXN>{}).is_prime[n] a new instance of the object is created and therefore the sieve is recalculated. It may be the case when you change that to:

Sieve<MAXN> a;
return a.is_prime[n];

the compiler use the fact that “a” never changes and refere to the same instance in every call to the function. Maybe it depends on the optimization flags.

I’m not sure if what I say is correct, so don’t take it as confirmed truth.

2 Likes

Aren’t constructors called like other functions, using parentheses --> () ?
And if the {} mean that we are creating an object, then the runtime reasoning seems to make sense.
Thank you for the inputs!

check this: https://ideone.com/GiGvRj

(Sieve<MAXN>{}).is_prime[n] 

means invoke the default constructor, then the returned object is set to empty. So it involves an additional operation. Think of it as invoking constructor like below

vector<int> vec = {};

Now consider this alternative invocation written below

(Sieve<MAXN>()).is_prime[n] 

means invoke the default constructor, then use the returned object. Think of it as invoking constructor like below

 vector<int> vec;

Hence, (Sieve()).is_prime[n] performs slightly better than (Sieve{}).is_prime[n]

Regarding your next question why explicit description improves the performance even when not declared as a static constexpr.

    Sieve<MAXN> dynamic;
    return dynamic.is_prime[n];

this translates to “dynamic” is constructed as a sieve and is being used by the function. Seeing that instruction is to repeatedly create and destroy the object ‘dynamic’ after doing a return, compiler optimises it and doesn’t construct and destroy s again and again.

If someone knows better, they can add.

Thank you for your response!

This is not what I meant by the second part of my question.
A few articles suggested that an enum declared as constexpr is always evaluated at compile time( functions may or may not be). So whether we declare dynamic as a constexpr or not does not really make a difference.

Well…you can take a while reading about that:

Aggregate_initialization

And a couple of Stackoverflow discussions:

First Link

Second Link

1 Like

These articles combined with @dardev’s explanation, clarifies the doubt.
Thanks you guys!

This trick isn’t particularly useful I think. If you try it on larger numbers the judge will throw you an error. But yes the power of C++ is the ability to use an O(N Log^2n) solution in a problem that expects an O(NlogN) solution.

1 Like