C: analyze bottleneck of C programs

Question

My C program is efficiency critical. Some functions are called millions of times, so I would like to know how much time is spent on each function, giving me sth like this:

Total time: 100s
forward(): 20s;
align(): 15s;
...
others: 1s.

Is there any debugger can perform such analysis? I am using Eclipse CDT on Ubuntu, and using gdb to debug. Some guy suggested Valgrind, but I did not find any suitable. I found there are some questions talking about c# or php or perl profiling, any suggestions for C? Thanks.

===========================================

Follow up: thanks very much for all help, gprof seems really nice. Here is a manual link: http://www.cs.utah.edu/dept/old/texinfo/as/gprof_toc.html.

A question about interpreting the summary:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 61.29      9.18     9.18                             bwa_print_sam_SQ
 21.96     12.47     3.29                             bwt_sa
  4.01     13.07     0.60                             bns_coor_pac2real
  3.87     13.65     0.58                             bwt_match_exact_alt
  2.60     14.04     0.39                             bwa_read_seq
  1.00     14.19     0.15                             bwt_match_gap
  0.80     14.45     0.12                             seq_reverse

If I am not wrong, it says the function bwa_print_sam_SQ takes 61.29% of the total time. But my program runs for 96.24 seconds, this function should run around 60 seconds. Why the column "cumulative" seconds is only 9.18? The manual says:

cumulative seconds
    This is the cumulative total number of seconds the computer spent executing this functions, plus the time spent in all the functions above this one in this table. 

And I use the parameter

"gprof -f pe_sai2sam_se_core -f bwa_print_sam_SQ -f seq_reverse ./peta > gprof", 

where function "pe_sai2sam_se_core" calls "bwa_print_sam_SQ" in a big while loop. Why the report says:

index % time    self  children    called     name
                                                 <spontaneous>
[1]     61.3    9.18    0.00                 bwa_print_sam_SQ [1]
-----------------------------------------------
                                                 <spontaneous>
[8]      0.8    0.12    0.00                 seq_reverse [8]
-----------------------------------------------

It did not say anything about pe_sai2sam_se_core... Why?

Answer 1

You don't need a debugger. What you need is called a profiler. Since you mention Ubuntu, you probably want to start with gprof.

Here's how you can use gprof:

• Disable all compiler optimizations for your program (-O0) - optional of course
• Add the -g and the -pg flags
• Rebuild and run the program as usual
• At this point your program should have produced a gmon.out file in the cwd

• Use gprof to inspect data:

  gprof ./your_program > prof
  

Now you can view the prof file. It begins with the flat profile which simply tells you how much time it's spending in various functions.