1

If you have a function being called in another function, do you figure out the runtime for the being called and then "add" that to function you wish to analyze the runtime for?

Function to be analyzed:

for (i = 0, i > n, ++i)
{
    if (function.call() > 0)
    {
        \\something
    }
}

Function called:

Call
{
   for (i = 0, i > n, ++i)
    {
        \\return something
    }
}
  • Your second example is trivial and just increments bar exactly once (provided n > 0). Are you sure that's intended? – Rufflewind Sep 14 '14 at 18:58
  • Hmm. It's not really meant to be relevant. I'll edit to the question for more clarity. – RandomPleb Sep 14 '14 at 19:07
  • @Rufflewind Ha, I saw what you meant as I was editing. Good catch. Fixed. – RandomPleb Sep 14 '14 at 19:10
  • It is called profiling; on Linux in C consider gprof and oprofile (you may need to compile with gcc -pg) – Basile Starynkevitch Sep 14 '14 at 19:13
  • 3
    usually when profile you'll get two times for each function, in python these are called 'total' time (the time actually spent in this function, that isn't counted anywhere else), and 'cumulative' time, which is the total time spend in this function including time spent in children. the two together tell you different things. the second tells you more globally what your program is spending time on (e.g. reading a text file); the first tells you which low-level functions to focus on first (e.g. parsing a specific big number field from that text field that is inefficiently implemented). – Corley Brigman Sep 15 '14 at 13:49
1

Think of it as some kind of accounting.

The inclusive time of a function is:

  • The elapsed time between the entrance and the exit of this function,
  • MINUS pure overhead (if known; zero if negligible or undetermined)
  • PLUS total elapsed time spent on other CPU cores or OS threads due to any work that is delegated by this function. (In other words, external work that is "billable" to this function.)

The exclusive time of a function is:

  • The inclusive time of the function,
  • MINUS the total inclusive time of all children of that function.
    • The definition of "children" is up to the profiler designer.
    • For example, child functions which have been completely inlined into the parent function are usually no longer considered to be a separate item, and thus will not be subtracted.
    • On the other hand, any use of "source-based" profiler frameworks will impede the inlining optimization by the compiler, to the point that any functions marked for instrumentation will never be inlined anyway.
| improve this answer | |
0

@Rufflewind had it right in the comments, you have to substitute the function call - think closer to copy/pasting the subfunction into the main function. This can get a bit nasty when you have recursive calls, as you might guess.

One important thing to keep in mind is the "what" of your analysis. Usually big-O style runtime analysis picks a certain number of operations to measure - swaps, additions, multiplications, etc. You may have cases where the subfunction does work, but none of the operations being measured, in which case it should drop out of analysis.

So it looks like in your example that the outer loop would be O(N) if the subfunction did "no work", but when you substitute it, you'll end up with some O(N^2) type of operation.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.