10.2 Using the profiler gprof

The GNU profiler gprof is a useful tool for measuring the performance of a program--it records the number of calls to each function and the amount of time spent there, on a per-function basis. Functions which consume a large fraction of the run-time can be identified easily from the output of gprof. Efforts to speed up a program should concentrate first on those functions which dominate the total run-time.

We will use gprof to examine the performance of a small numerical program which computes the lengths of sequences occurring in the unsolved Collatz conjecture in mathematics.⁽³⁴⁾ The Collatz conjecture involves sequences defined by the rule:

x_{n+1}  <=    x_{n} / 2  if x_{n} is even
             3 x_{n} + 1  if x_{n} is odd

The sequence is iterated from an initial value x_0 until it terminates with the value 1. According to the conjecture, all sequences do terminate eventually--the program below displays the longest sequences as x_0 increases. The source file 'collatz.c' contains three functions: main, nseq and step:

#include <stdio.h>

/* Computes the length of Collatz sequences */

unsigned int
step (unsigned int x)
{
  if (x % 2 == 0)
    {
      return (x / 2);
    }
  else
    {
      return (3 * x + 1);
    }
}

unsigned int
nseq (unsigned int x0)
{
  unsigned int i = 1, x;
  
  if (x0 == 1 || x0 == 0)
    return i;

  x = step (x0);

  while (x != 1 && x != 0)
    {
      x = step (x);
      i++;
    }

  return i;
}

int
main (void)
{
  unsigned int i, m = 0, im = 0;

  for (i = 1; i < 500000; i++)
    {
      unsigned int k = nseq (i);

      if (k > m)
        {
          m = k;
          im = i;
          printf ("sequence length = %u for %u\n", m, im);
        }
    }

  return 0;
}

To use profiling, the program must be compiled and linked with the -pg profiling option:

$ gcc -Wall -c -pg collatz.c
$ gcc -Wall -pg collatz.o

This creates an instrumented executable which contains additional instructions that record the time spent in each function.

If the program consists of more than one source file then the -pg option should be used when compiling each source file, and used again when linking the object files to create the final executable (as shown above). Forgetting to link with the option -pg is a common error, which prevents profiling from recording any useful information.

The executable must be run to create the profiling data:

$ ./a.out
(normal program output is displayed)

While running the instrumented executable, profiling data is silently written to a file 'gmon.out' in the current directory. It can be analyzed with gprof by giving the name of the executable as an argument:

$ gprof a.out 
Flat profile:
Each sample counts as 0.01 seconds.
 %     cumul.    self             self   total           
time  seconds seconds    calls us/call us/call name    
68.59    2.14    2.14 62135400    0.03    0.03 step
31.09    3.11    0.97   499999    1.94    6.22 nseq
 0.32    3.12    0.01                          main

The first column of the data shows that the program spends most of its time (almost 70%) in the function step, and 30% in nseq. Consequently efforts to decrease the run-time of the program should concentrate on the former. In comparison, the time spent within the main function itself is completely negligible (less than 1%).

The other columns in the output provide information on the total number of function calls made, and the time spent in each function. Additional output breaking down the run-time further is also produced by gprof but not shown here. Full details can be found in the manual "GNU gprof--The GNU Profiler", by Jay Fenlason and Richard Stallman.