Inline functions (Discussion on performance)

6 Likes

Check out the disadvantages of “inline” in this link. Specially 1st 2nd and 5th points…I think this will answer your question…:slight_smile:

2 Likes

In simple words, when you use an inline function, then the area where you call that function is equivalently replaced with the exact code written for that function; this is what the word inline implies.

It gives a performance boost when written for small pieces of code. Here what you’re doing:

  1. Inside an inline function (ModPow) calling another non-inline function (ModMultiply).
  2. Inside an inline function (Miller) calling both an inline function (ModPow) and a non-inline function (ModMultiply).

And inline functions fail to perform optimally in cases of recursion, or what you have done here.

Note: By writing inline before a function definition, we are just suggesting the compiler to use it in an inline manner, it is not guaranteed that it will be used so.

More readings here (SO discussion) and here (already mentioned by @kunal361)

To even force the compiler to use inline, you can use __attribute__ ((always_inline)) See here it gives TLE :slight_smile:

2 Likes

5th point I guess :slight_smile:

Are you saying, performance is boosted in case 1 and 2 i.e what I have done ?
And if both functions are inline then?
One more thing, recursion has not been used anywhere.

@bit_cracker007 >> Updated my answer

Editted back your answer(hope you won’t mind). Its tem<<=1 only.
Check the link again. Maybe that time by mistake it was there. Again go through the link and submit with inline. Check my two last submissions you will get it :slight_smile:

PS : Even in this solution where you got tle : http://www.codechef.com/viewsolution/2179437 , temp<<=1 is there.

Yes so now on the basis of last two submissions, lets take the one that is giving TLE, which is the same as mine using __attribute__ ((always_inline)) just that I am forcing the compiler for inline, so TLE is quite reasonable. Where is the problem now? Just estimate how many times ModMultiply() would be called inside ModPow(), all being inline there might be some error generated.

I think the problem’s reason is same as what enlisted in link provided by @kunal361 : point 5 of disadvantages. Please check and continue the discussion.

Checked again what? I mentioned that forcing inline was giving TLE as in my solution too. And, that point #5 might be a case, in the last comment I have mentioned the same thing that can you estimate how many calls to inline ModMultiply() will be there inside ModPow()? A lot many number of times.
The precise error (of what happened for the TLE) can be told by someone who is very well aware of the Codechef Judge (mechanisms) e.g @anton_lunyov or the @admin himself. http://www.codechef.com/viewsolution/2179437

Ofcourse many times. And I think that’s the reason we arrive at. But, I had studied that using inline makes the function act like a macro definition. Wondering using a macro so many times can cause tle?

I had a look on your’s submission. Couldnot figure out still properly.

Yes, depending on the situations, it might. And it is not actually correct that inline acts the same as macro. Rather what I have studied is we should prefer inline over macros for short code snippets. See the same link by @kunal361, in guidelines point #2. And please edit the question with corresponding links to AC and TLE solutions. The one currently given there says Page not found.

Actually an inline function is used when the function code is short(link text)check point no 5.But here you are not only using many inline functions but the code within the function is also large…:slight_smile:
This may help your code get trashed!!! ;)…And bring down your performance :slight_smile:

3 Likes

You were too fast to answer :stuck_out_tongue:

1 Like

@bit_cracker007:hehehe…I did not see the question dude…:slight_smile:

3 Likes