### 11.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.40 The Collatz conjecture involves sequences defined by the rule:

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.

#### Footnotes

##### (40)

American Mathematical Monthly, Volume 92 (1985), 3–23