A.3. Профилирование.

Теперь, когда мы знаем, как искать ошибки в программах, настало время разобраться, как ускорить выполнение программы. Профайлер gprof позволяет определить, какие функции требуют наибольших вычислительных ресурсов и тем самым являются кандидатами на оптимизацию. Профилирование полезно также при отладке, поскольку с помощью этого метода можно установить, какие функции вызываются чаще, чем нужно.

Для получения профильной информации необходимо следовать такому алгоритму.

1. Скомпилируйте и скомпонуйте программу с опциями профилирования.

2. Запустите программу, чтобы сгенерировать профильные данные.

3. Вызовите утилиту gprof для отображения и анализа профильных данных.

А.3.1. Простейший калькулятор.

Для иллюстрации методики профилирования мы напишем простейшую программу- калькулятор. Чтобы программа выполнялась нетривиальным образом, заставим ее работать с унарными числами, чего не встречается в реальных калькуляторах. Код программы приведен в конце приложения.

Значение унарного числа представляется аналогичным количеством символов. Например, число 1 — это "x", 2 — "xx", 3 — "xxx" и т.д. Вместо символов "x" программа использует связный список, количество элементов которого соответствует значению числа. В файле number.c содержатся функции, позволяющие создавать число 0, добавлять единицу к числу, вычитать единицу из числа, а также складывать, вычитать и умножать числа. Есть функция, которая преобразует строку, содержащую неотрицательное десятичное число, в унарное число. Другая функция преобразует унарное число в значение типа int. Сложение реализуется путем последовательного добавления единицы, вычитание — путем последовательного отнимания единицы, а умножение — путем многократного сложения. Функции even() и odd() возвращают унарный эквивалент единицы тогда и только тогда, когда их единственный операнд является соответственно четным или нечетным числом. В противном случае возвращается унарный эквивалент нуля. Обе функции взаимно рекурсивны. Например, число является четным, если оно равно нулю или если число, на единицу меньшее, является нечетным.

Калькулятор принимает однострочные постфиксные выражения[40] и отображает значение каждого выражения:

% ./calculator.

Please enter a postfix expression:

2 3 +

5.

Please enter a postfix expression:

2 3 + 4 -

1.

Калькулятор, реализованный в файле calculator.c, читает каждое выражение и сохраняет промежуточные результаты в стеке унарных чисел, реализованном в файле stack.c. Унарные числа представляются в стеке в виде связных списков.

А.3.2. Сбор профильной информации.

Первый этап профилирования заключается в настройке исполняемого файла на сбор профильной информации. Для этого при компиляции и компоновке объектных файлов необходимо указывать флаг -pg. Рассмотрим, к примеру, такую последовательность команд:

% gcc -pg -c -o calculator.o calculator.c.

% gcc -pg -c -o stack.o stack.c.

% gcc -pg -c -o number.o number.c.

% gcc -pg calculator.o stack.o number.o -o calculator.

Здесь разрешается сбор информации о вызовах функций и времени их выполнения. Чтобы получать сведения о каждой выполняемой строке программы, укажите флаг -g. При наличии флага -a будет подсчитываться количество итераций циклов.

На втором этапе требуется запустить программу. В процессе ее выполнения профильные данные накапливаются в файле gmon.out. Исследуются только те участки программы, которые действительно выполняются. Чтобы профильный файл был записан, программа должна завершиться нормальным образом.

А.3.3. Отображение профильных данных.

Получив имя исполняемого файла, утилита gprof проверяет файл gmon.out и отображает информацию о том, сколько времени заняло выполнение каждой функции. Давайте проанализируем ход выполнения операции 1787 × 13 - 1918 в нашей программе-калькуляторе, создав простой профиль.

Flat profile:

Each sample counts as 0.01 seconds.

% cumulative    self            self    total.

Time seconds seconds    calls ms/call ms/call name.

26.07   1.76    1.76 20795463    0.00    0.00 decrement_number.

24.44   3.41    1.65     1787    0.92    1.72 add.

19.85   4.75    1.34 62413059    0.00    0.00 zerop.

15.11   5.77    1.02     1792    0.57    2.05 destroy_number.

14.37   6.74    0.97 20795463    0.00    0.00 add_one.

 0.15   6.75    0.01     1788    0.01    0.01 copy_number.

 0.00   6.75    0.00     1792    0.00    0.00 make_zero.

 0.00   6.75    0.00       11    0.00    0.00 empty_stack.

Вычисление функции decrement_number() и всех вызываемых в ней функций заняло 26,07% общего времени выполнения программы. Эта функция вызывалась 20795463 раза. Каждый вызов выполнялся 0,00 с, т.е. столь малое время, что его не удалось замерить. Функция add() вызывалась 1787 раз, очевидно для вычисления произведения. Каждый проход по функции занимал 0,92 секунды. Функция copy_number() вызывалась почти столько же раз — 1788, но на ее выполнение ушло всего 0.15% общего времени работы программы. Иногда в отчете присутствуют функции mcount() и profil(), используемые профайлером.

В простом профиле отражается время, затраченное на выполнение каждой функции. Утилита gprof умеет также создавать схему вызовов, где показывается время, проведенное не только в каждой функции, но и во всех вызываемых в ее контексте дочерних функциях.

Index % time  self children called name.

                                      <spontaneous>

[1]     100.0 0.00 6.75              main [1].

              0.00 6.75     2/2       apply_binary_function [2].

              0.00 0.00     1/1792    destroy_number [4].

              0.00 0.00     1/1       number_to_unsigned_int [10].

              0.00 0.00     3/3       string_to_number [12].

              0.00 0.00     3/5       push_stack [16].

              0.00 0.00     1/1       create_stack [16].

              0.00 0.00     1/11      empty_stack [14].

              0.00 0.00     1/5       pop_stack [15].

              0.00 0.00     1/1       clear_stack [17].

--------------------------------------

              0.00 6.75     2/2       main [1].

[2]     100.0 0.00 6.75     2        apply_binary_function [2].

              0.00 6.74     1/1       product [3).

              0.00 0.01     4/1792    destroy_number [4].

              0.00 0.00     1/1       subtract [11].

              0.00 0.00     4/11      empty_stack [14].

              0.00 0.00     4/5       pop_stack [15].

              0.00 0.00     2/5       push_stack [16].

--------------------------------------

              0.00 6.74     1/1       apply_binary_function [2].

[3]      99.6 0.00 6.74     1        product [3].

              1.02 2.65 1767/1792     destroy_number [4].

              1.65 1.43 1767/1767     add [5].

              0.00 0.00 1760/62413059 zerop [7].

              0.00 0.00    1/1792     make_zero [13].

В первой секции сообщается о том, что на выполнение функции main() и всех ее дочерних функций ушло 100% времени (6.75 секунд). Функцию main() вызвал некто <spontaneous>: это означает, что профайлер не смог определить, как был осуществлен вызов. В функции main() дважды вызывалась функция apply_binary_function() (всего таких вызовов в программе было тоже два). В третьей секции сообщается о том, что выполнение функции product() и ее дочерних функций заняло 98% времени. Эта функция вызывалась только один раз из функции apply_binary_function().

По схеме вызовов несложно определить время работы той или иной функции. Однако рекурсивные функции требуют особого подхода. Например, функция even() вызывает функцию odd(), а та — снова функцию even(). Самому длинному из таких циклов присваивается номер и выделяется отдельная секция отчета. Следующий фрагмент профильных данных получен в результате проверки того, является ли результат операции 1787 × 13 × 3 четным:

--------------------------------------

              0.00 0.02    1/1        main [1].

[9]       0.1 0.00 0.02    1         apply_unary_function [9].

              0.01 0.00    1/1        even <cycle 1> [13].

              0.00 0.00    1/1806     destroy_number [5].

              0.00 0.00    1/13       empty_stack [17].

              0.00 0.00    1/6        pop_stack [16].

              0.00 0.00    1/6        push_stack [19].

--------------------------------------

[10]       0.1 0.01 0.00   1+69993   <cycle 1 as a whole> [10].

               0.00 0.00 34647        even <cycle 1> [13].

--------------------------------------

                         34847        even <cycle 1> [13].

[11]       0.1 0.01 0.00 34847       odd <cycle 1> [11].

               0.00 0.00 34847/186997954 zerop [7].

               0.00 0.00   1/1806     make_zero [16].

                         34846        even <cycle 1> [13].

Выражение 1+69693 в секции 10 сообщает о том что цикл 1 выполнялся один раз и в нем насчитывается 69693 обращений к функциям. Первой в цикле вызывалась функция even(), а из нее — функция odd. Обе функции вызывались по 34847 раз.

Утилита gprof располагает рядом полезных опций.

■ При задании опции -s будут суммироваться результаты нескольких запусков программы.

■ С помощью опции -c можно узнать, какие дочерние функции могли быть, но так и не были вызваны.

■ При задании опции -l отображается построчная профильная информация.

■ При задании опции -A будет отображен исходный текст программы, сопровождаемый процентными показателями времени выполнения.

А.3.4. Как работает утилита gprof.

Схема работы утилиты gprof выглядит следующим образом. Когда в ходе выполнения программы происходит вызов функции, счётчик обращений к функции увеличивается на единицу. Утилита периодически прерывает программу, чтобы выяснить, какая функция выполняется в данный момент. На основании этих '"выборок" и определяется время выполнения. В Linux тактовые импульсы генерируются с интервалом 0,01 с, следовательно, это наименьший промежуток между прерываниями. Таким образом, профильные данные о слишком быстро выполняющихся функциях могут оказаться неточными. Во избежание погрешностей рекомендуется запускать программу на длительные периоды времени или суммировать профильные данные по результатам нескольких запусков (это делается с помощью опции -s).

А.3.5. Исходные тексты программы-калькулятора.

В листинге А.3 показан текст программы, вычисляющей значения постфиксных выражений.

Листинг А.3. (calculator.c) Основная часть программы-калькулятора.

/* Вычисления в унарном формате. */

/* На вход программы подаются однострочные выражения.

   в обратной польской (постфиксной) записи, например:

   602 7 5 - 3 * +

   Вводимые числа должны быть неотрицательными.

   десятичными числами. Поддерживаются операторы.

   "+", "-" и "*". Унарные операторы "even" и "odd".

   возвращают значение 1 в том случае, когда операнд.

   является четным или нечетным соответственно.

   Лексемы разделяются пробелами. Отрицательные числа.

   не поддерживаются. */

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <ctype.h>

#include "definitions.h".

/* Эта функция выполняет указанную бинарную операцию над.

   операндами, извлекаемыми из стека, помещая результат.

   обратно в стек, в случае успеха возвращается.

   ненулевое значение. */

Int apply_binary_function(number (*function)(number, number),

 Stack* stack) {

 number operand1, operand2;

 if (empty_stack(*stack)).

  return 0;

 operand2 = pop_stack(stack);

 if (empty_stack(*stack)).

  return 0;

 operand1 = pop_stack(stack);

 push_stack(stack, (*function)(operand1, operand2));

 destroy_number(operand1);

 destroy_number(operand2);

 return 1;

}

/* Эта функция выполняет указанную унарную операцию над.

   операндом, извлекаемым из стека, помещая результат.

   обратно в стек. В случае успеха возвращается.

   ненулевое значение. */

Int apply_unary_function(number (*function)(number), Stack* stack) {

 number operand;

 if (empty_stack(*stack)).

  return 0;

 operand = pop_stack(stack);

 push_stack(stack, (*function)(operand));

 destroy_number(operand);

 return 1;

}

Int main() {

 char command_line[1000];

 char* command_to_parse;

 char* token;

 Stack number_stack = create_stack();

 while (1) {

  printf("Please enter a postfix expression:\n");

  command_to_parse =

   fgets(command_line, sizeof (command_line), stdin);

  if (command_to_parse = NULL).

   return 0;

  token = strtok(command_to_parse, " \t\n");

  command_to_parse = 0;

  while (token != 0) {

   if (isdigit(token[0])).

    push_stack(&number_stack, string_to_number(token));

   else if (((strcmp(token, "+ ") == 0) &&

    !apply_binary_function(&add, &number_stack)) ||

    ((strcmp(token, "-") == 0) &&

    !apply_binary_function(&subtract, &number_stack)) ||

    ((strcmp(token, "*") == 0) &&

    !apply_binary_function(&product, &number_stack)) ||

    ((strcmp(token, "even") == 0) &&

    !apply_unary_function(&even, &number_stack)) ||

    ((strcmp(token, "odd") == 0) &&

    !apply_unary_function(&odd, &number_stack))).

    return 1;

   token = strtok(command_to_parse, " \t\n");

  }

  if (empty_stack(number_stack)).

   return 1;

  else {

   number answer = pop_stack(number_stack);

   printf("%u\n", number_to_unsigned_int(answer));

   destroy_number(answer);

   clear_stack(&number_stack);

  }

 }

 return 0;

}

Функции, приведенные в листинге А.4 выполняют операции над унарными числами, представленными в виде связных списков.

Листинг А.4. (number.c) Арифметика унарных чисел.

/* Операции над унарными числами */

#include <assert.h>

#include <stdlib.h>

#include <limits.h>

#include "definitions.h".

/* Создание числа, равного нулю. */

Number make_zero() {

 return 0;

}

/* Эта функция возвращает ненулевое значение,

   если аргумент равен нулю. */

Int zerop(number n) {

 return n == 0;

}

/* Уменьшение числа на единицу. */

Number decrement_number(number n) {

 number answer;

 assert(!zerop(n));

 answer = n->one_less_;

 free(n);

 return answer;

}

/* Добавление единицы к числу. */

Number add_one(number n) {

 number answer = malloc(sizeof(struct LinkedListNumber));

 answer->one_less_ = n;

 return answer;

}

/* Удаление числа. */

Void destroy_number(number n) {

 while (!zerop(n)).

 n = decrement_number(n);

}

/* Копирование числа. Эта функция необходима для того,

   чтобы при временных вычислениях не искажались.

   исходные операнды. */

Number copy_number(number n) {

 number answer = make_zero();

 while (!zerop(n)) {

  answer = add_one(answer);

  n = n->one_less_;

 }

 return answer;

}

/* Сложение двух чисел. */

Number add(number n1, number n2) {

 number answer = copy_number(n2);

 number addend = n1;

 while(!zerop(addend)) {

  answer = add_one(answer);

  addend = addend->one_less_;

 }

 return answer;

}

/* Вычитание одного числа из другого. */

Number subtract(number n1, number n2) {

 number answer = copy_number(n1);

 number subtrahend = n2;

 while(!zerop(subtrahend)) {

  assert(!zerop(answer));

  answer = decrement_number(answer);

  subtrahend = subtrahend->one_less_;

 }

 return answer;

}

/* Умножение двух чисел. */

Number product(number n1, number n2) {

 number answer = make_zero();

 number multiplicand = n1;

 while (!zerop(multiplicand)) {

  number answer2 = add(answer, n2);

  destroy_number(answer);

  answer = answer2;

  multiplicand = multiplicand >one_less_;

 }

 return answer;

}

/* Эта функция возвращает ненулевое значение, если.

   ее аргумент является четным числом. */

Number even(number n) {

 if (zerop(n)).

  return add_one(make_zero());

 else.

  return odd(n->one_less_);

}

/* Эта функция возвращает ненулевое значение, если.

   ее аргумент является нечетным числом. */

Number odd (number n) {

 if (zerop(n)).

  return make_zero();

 else.

  return even(n->one_less_);

}

/* Приведение строки, содержащей десятичное целое,

   к типу "number". */

Number string_to_number(char* char_number) {

 number answer = make_zero();

 int num = strtoul(char_number, (char **)0, 0);

 while (num != 0) {

  answer = add_one(answer);

  --num;

 }

 return answer;

}

/* Приведение значения типа "number".

   к типу "unsigned int". */

Unsigned number_to_unsigned_int (number n) {

 unsigned answer = 0;

 while (!zerop(n)) {

  n = n->one_less_;

  ++answer;

 }

 return answer;

}

Функции, приведенные в листинге A.5, реализуют стек унарных чисел, представленных в виде связных списков.

Листинг А.5. (stack.c) Стек унарных чисел.

/* Реализация стека значений типа "number". */

#include <assert.h>

#include <stdlib.h>

#include "definitions.h".

/* Создание пустого стека. */

Stack create_stack() {

 return 0;

}

/* Эта функция возвращает ненулевое значение,

   если стек пуст. */

Int empty_stack(Stack stack) {

 return stack == 0;

}

/* Удаление числа, находящегося на вершине стека.

   Если стек пуст, программа аварийно завершается. */

Number pop_stack(Stack* stack) {

 number answer;

 Stack rest_of_stack;

 assert(!empty_stack(*stack));

 answer = (*stack)->element_;

 rest_of_stack = (*stack)->next_;

 free(*stack);

 *stack = rest_of_stack;

 return answer;

}

/* Добавление числа в начало стека. */

Void push_stack(Stack* stack, number n) {

 Stack new_stack =

  malloc(sizeof(struct StackElement));

 new_stack->element_ = n;

 new_stack->next_ = *stack;

 *stack = new_stack;

}

/* Очистка стека. */

Void clear_stack(Stack* stack) {

 while(!empty_stack(*stack)) {

  number top = pop_stack (stack);

  destroy_number(top);

 }

}

В листинге А.6 показаны объявления типов данных и функций работы со стеком и унарными числами.

Листинг А.6. (definitions.h) Файл заголовков для файлов number.c и stack.c.

#ifndef DEFINITIONS_H.

#define DEFINITIONS_H 1.

/* Представление числа в виде связного списка. */

Struct LinkedListNumber {

 struct LinkedListNumber* one_less_;

};

Typedef struct LinkedListNumber* number;

/* Реализация стека чисел, представленных в виде.

   связных списков. Значение 0 соответствует.

   пустому стеку. */

Struct StackElement {

 number element_;

 struct StackElement* next_;

};

Typedef struct StackElement* Stack;

/* Операции над стеком. */

Stack create_stack();

Int empty_stack(Stack stack);

Number pop_stack Stack* stack);

Void push_stack(Stack* stack, number n);

Void clear_stack(Stack* stack);

/* Операции над числами */

Number make_zero();

Void destroy_number(number n);

Number add(number n1, number n2);

Number subtract(number n1, number n2);

Number product(number n1, number n2);

Number even(number n);

Number odd(number n);

Number string_to_number(char* char_number);

Unsigned number_to_unsigned_int(number n);

#endif /* DEFINITIONS_H */