CODEWITHSUNDEEP
c++methodsbig-oexecution
user827992
user827992

Reputation: 1753

Locate the most costly methods and evaluate/profile them

I would like to know if there is a technique or a tool available that can tell you how much time is required to execute a particular method.

Something similar to the big O notation in math/computer science that can give you an idea about the complexity of an algorithm, I wonder if there is something similar for code analysis.

Upvotes: 2

Views: 125

Answers (4)

titus
titus

Reputation: 5784

You should try running your code with callgrind started, it will record what functions are called, how many times, but the code will run 20X slower or such. After you get your callgrind output you should open it with kcachegrind to view the tree structure of the calls. There you can browse around and see where do you have bottlenecks

Useful links:
kcachegrind http://kcachegrind.sourceforge.net/html/Home.html
callgrind documentation http://valgrind.org/docs/manual/cl-manual.html
(valgrind is the framework, callgrind is a component)
how to start callgrind if the program spawns processes and you want to profile those too (replace sage bench.py with your program) https://github.com/titusnicolae/pynac-callgrind/blob/master/run.sh
edit: "--instr-atstart=no" should be removed from the parameter list if you don't plan on enabling the instrumentation later

Upvotes: 1

Jon Purdy
Jon Purdy

Reputation: 55059

Profiling is a means of analysing a program to determine the relative amount of time spent in particular functions or methods. It is useful for discovering performance issues in a program empirically. Using GCC, for example, you can:

  • Compile the program with the -pg option to enable profiling.

  • Run the executable to produce a file called gmon.out, which contains information about the runtime characteristics of your program as it actually ran.

  • Run gprof to display the information generated by the instrumented executable.

Generally speaking, human analysis is the only way to discover the asymptotic (i.e., big-O) complexity of a particular algorithm—there is, so far as I know, no mechanical way to do it.

Upvotes: 4

Ben Voigt
Ben Voigt

Reputation: 283793

How is this different from the halting problem?

Please note that I can trivially solve the halting problem using your automatic complexity analyzer -- your problem is HARDER. And the halting problem is already undecidable.

Upvotes: 0

Steve Jessop
Steve Jessop

Reputation: 279345

If you want to know how much time is spent in a function, use a so-called "profiler".

Complexity analysis is outside the scope of a profiler, though, since a profiler tells you what happens when you run a program once, whereas complexity tells you the limit behavior of what happens when you run an infinite sequence of programs with bigger and bigger input.

So: do you want to know which functions are most costly in your program (in which case find a profiler for your C++ implementation and follow its documentation), or do you want to know about time complexity (in which case you pretty much need a human to analyze your code)?

Upvotes: 2

Related Questions