Previous Up Next

Chapter 9  Средства анализа программ

9.1  Введение

Средства анализа программ предоставляют дополнительную информацию, по сравнению с компилятором или компоновщиком. Часть этих средств реализуют статический анализ. То есть они анализирую (в виде исходного кода или синтаксического дерева) и определяют различные свойства кода, такие как зависимости между модулями или возможные исключения. Другие средства проводят динамический анализ, то есть изучают программы во время ее выполнения. Такие средства полезны, в случае когда необходимо знать сколько раз была вызвана определенная функция, какие аргументы были ей переданы или время, затраченное на выполнение части кода программы. Такие средства анализа могут быть интерактивными, как например отладчик программ. В этом случае выполнение программы изменяется, для того чтобы реагировать на команды пользователя, который может установить контрольные точки чтобы просмотреть значения или перезапустить программу с новыми аргументами.

В дистрибутив Objective CAML входят подобные средства. Некоторые из них имеют не часто встречающиеся характеристики, связанные со статической типизацией. Такая типизация гарантирует, что во время выполнения кода, не произойдет ошибок типа и используется компилятором для того чтобы генерировать эффективный код небольшого размера. Часть информации о типе созданных значений теряется и из–за этой особенности нельзя просмотреть аргументы полиморфных функций.

9.2  План главы

В этой короткой главе представляются средства анализа входящие в дистрибутив Objective CAML. В первой части описывается команда ocamldep, которая определяет зависимости множества файлов Objective CAML принадлежащих одной и той же программе. Во второй части представляются средства отладки, как например результаты применения функций или стандартное средство отладки — ocamldebug для операционных систем Unix. В третьей части мы рассмотрим профайлер. Он анализирует программы и результат этого анализа может быть использован для оптимизации этой программы.

Вычисление зависимостей между файлами интерфейса и реализации имеет двойную цель. Первая — получить глобальное видение зависимостей между модулями? Вторая — использовать данную информацию для того чтобы компилировать лишь необходимый минимум при изменении некоторых файлов.

Команда ocamldep анализирует файлы .ml и .mli и выводит зависимости файлов в формате Makefile1.

Зависимости появляются при глобальной декларации других модулей, либо используя синтаксис с точкой (пример: M1.f), либо открывая модуль (пример: open M1).

Предположим, что имеются файлы dp.ml:

let print_vect v = for i = 0 to Array.length v do Printf.printf "%f " v.(i) done; print_newline();;

и d1.ml:

let init n e = let v = Array.create 4 3.14 in Dp.print_vect v; v;;

При вызове команды ocamldep с указанием файлов, получим следующий результат:

$ ocamldep dp.ml d1.ml array.ml array.mli printf.ml printf.mli dp.cmo: array.cmi printf.cmi dp.cmx: array.cmx printf.cmx d1.cmo: array.cmi dp.cmo d1.cmx: array.cmx dp.cmx array.cmo: array.cmi array.cmx: array.cmi printf.cmo: printf.cmi printf.cmx: printf.cmi

Зависимости вычисляются для байт–код и нативных компиляторов. Поясним полученный результат: компиляция файла dp.cmo зависит от файлов array.cmi и printf.cmi. Файлы с расширением .cmi зависят от файлов с таким же именем, но с расширением .mli. Аналогичное правило распоространяется на файлы .ml с .cmo и .cmx.

Объкетные файлы дистирбитува отсутствуют в списке зависимостей. В действительности, если команда ocamldep не найдет их в текущем каталоге, то они будут найдены в каталоге библиотек дистрибутива и выдаст следующий результат:

$ ocamldep dp.ml d1.ml d1.cmo: dp.cmo d1.cmx: dp.cmx

Для того, чтобы указать командe ocamldep дополнительные каталоги для поиска файлов, используйте опцию -I каталог.

9.3  Средства отладки

Существует два типа средств для отладки программ. Первый тип это трассировка глобальных функций, интерактивного интерпретатора. Второе средство это отладчик, который не используется в нормальном интерактивном интерпретаторе. После первичного выполнения программы, отладчик позволяет вернуться к контрольным точкам, просмотреть определенные значения или перезапустить функции с новыми параметрами. Данный отладчик доступен лишь в среде Unix, потому что он использует вызов fork для создания процесса программы.

9.3.1  Trace

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

#trace имя_функциитрассировать указанную функцию
#untrace имя_функциипрекратить трассировку указанной функции
#untrace_allпрекратить все трассировки

В следующем примере, определим функцию:

# let f x = x + 1;; val f : int -> int = <fun> # f 4;; - : int = 5

Теперь зададим директиву трассировки данной функции, после чего переданные аргументы и результат буду выведены на экран.

#trace f;; f is now traced. # f 4;; f <-- 4 f --> 5 - : int = 5

Передача аргумента 4 функции f выводится на экран, функция реализует вычисление и затем результат так же выводится на экран. Значения параметров вызова функции указываются стрелкой влево, а возвращаемое значение стрелкой вправо.

Функции с несколькими параметрами

Таким же образом можно трассировать функции с несколькими аргументами (или возвращающими замыкание). Каждая передача аргумента выводится на экран. Для того чтобы различить замыкания, символом '*' помечается число уже переданных замыканию аргументов. Пусть имеется функция verif_div с четырьмя аргументами a b c d, соответствующие целочисленному делению: a = bq + r.

# let verif_div a b q r = a = b*q + r;; val verif_div : int -> int -> int -> int -> bool = <fun> # verif_div 11 5 2 1;; - : bool = true

Трассировка данной функции выводит на экран передачу 4 аргумента:

#trace verif_div;; verif_div is now traced. # verif_div 11 5 2 1;; verif_div <-- 11 verif_div --> <fun> verif_div* <-- 5 verif_div* --> <fun> verif_div** <-- 2 verif_div** --> <fun> verif_div*** <-- 1 verif_div*** --> true - : bool = true

Рекурсивные функции

Трассировка дает ценную информацию о рекурсивных функциях. Можно с легкостью определить неверный критерий остановки рекурсии.

Определим функцию belongs_to, которая проверяет принадлежит ли число списку целых чисел:

# let rec belongs_to (e : int) l = match l with [] -> false | t::q -> (e = t) || belongs_to e q ;; val belongs_to : int -> int list -> bool = <fun> # belongs_to 4 [3;5;7] ;; - : bool = false # belongs_to 4 [1; 2; 3; 4; 5; 6; 7; 8] ;; - : bool = true

Трассировка вызова функции belongs_to 4 [3;5;7] выведет на экран передачу четырех аргументов и возвращенные результаты.

#trace belongs_to ;; belongs_to is now traced. # belongs_to 4 [3;5;7] ;; belongs_to <-- 4 belongs_to --> <fun> belongs_to* <-- [3; 5; 7] belongs_to <-- 4 belongs_to --> <fun> belongs_to* <-- [5; 7] belongs_to <-- 4 belongs_to --> <fun> belongs_to* <-- [7] belongs_to <-- 4 belongs_to --> <fun> belongs_to* <-- [] belongs_to* --> false belongs_to* --> false belongs_to* --> false belongs_to* --> false - : bool = false

При каждом вызове функции belongs_to ей передается аргумент 4 и тестируемый список. Когда передается пустой список, то функция возвращает false. Это значение передается каждому ожидающему рекурсивному вызову.

В следующем примере список пройден лишь частично, до того места где находится нужный элемент:

# belongs_to 4 [1; 2; 3; 4; 5; 6; 7; 8] ;; belongs_to <-- 4 belongs_to --> <fun> belongs_to* <-- [1; 2; 3; 4; 5; 6; 7; 8] belongs_to <-- 4 belongs_to --> <fun> belongs_to* <-- [2; 3; 4; 5; 6; 7; 8] belongs_to <-- 4 belongs_to --> <fun> belongs_to* <-- [3; 4; 5; 6; 7; 8] belongs_to <-- 4 belongs_to --> <fun> belongs_to* <-- [4; 5; 6; 7; 8] belongs_to* --> true belongs_to* --> true belongs_to* --> true belongs_to* --> true - : bool = true

Как только 4 оказывается в заголовке списка, функция возвращает значение true и оно возвращается всем ожидающим рекурсивным вызовам.

Если в функции belongs_to поменять порядок '||', то функция все так же будет возвращать правильный результат, но при этом она будет проверять список до конца.

# let rec belongs_to (e : int) = function [] -> false | t::q -> belongs_to e q || (e = t) ;; val belongs_to : int -> int list -> bool = <fun> #trace belongs_to ;; belongs_to is now traced. # belongs_to 3 [3;5;7] ;; belongs_to <-- 3 belongs_to --> <fun> belongs_to* <-- [3; 5; 7] belongs_to <-- 3 belongs_to --> <fun> belongs_to* <-- [5; 7] belongs_to <-- 3 belongs_to --> <fun> belongs_to* <-- [7] belongs_to <-- 3 belongs_to --> <fun> belongs_to* <-- [] belongs_to* --> false belongs_to* --> false belongs_to* --> false belongs_to* --> true - : bool = true

Несмотря на то, что число 3 находится в начале списка, он, список, проверяется до конца. Таким образом трассировка помогает анализировать эффективность рекурсивных функций.

Полиморфные функции

Трассировка аргументов полиморфной функции не выводит на экран значение параметризованного типа. Пусть функция belongs_to написана без явного указания типа.

# let rec belongs_to e l = match l with [] -> false | t::q -> (e = t) || belongs_to e q ;; val belongs_to : 'a -> 'a list -> bool = <fun>

Теперь, функция belongs_to стала полиморфная и в ее трассировке вывод значений аргументов заменен на <poly>.

#trace belongs_to ;; belongs_to is now traced. # belongs_to 3 [2;3;4] ;; belongs_to <-- <poly> belongs_to --> <fun> belongs_to* <-- [<poly>; <poly>; <poly>] belongs_to <-- <poly> belongs_to --> <fun> belongs_to* <-- [<poly>; <poly>] belongs_to* --> true belongs_to* --> true - : bool = true

Интерактивный интерпретатор умеет выводить на экран только значения мономорфных типов. К тому же он сохраняет лишь выведенный тип глобальных деклараций. То есть после компиляции выражения belongs_to 3 [2;3;4], интерактивный интерпретатор не располагает другой информацией о типе, кроме того, что тип функции belongs_to есть a -> 'a list -> bool. Типы (мономорфные) 3 и [2;3;4] утеряны, так как при статической типизации значения не хранят информацию о типе. Поэтому, трассировка программы ассоциирует значениям функции belongs_to полиморфные типы 'a и 'a list.

Из–за того что значения не сохраняют информацию о типе, мы не можем создать общую функцию print с типом a -> unit.

Локальные функции

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

# let belongs_to e l = let rec bel_aux l = match l with [] -> false | t::q -> (e = t) || (bel_aux q) in bel_aux l;; val belongs_to : 'a -> 'a list -> bool = <fun>

Глобальная функция лишь вызывает локальную, чтобы она выполнила необходимую задачу.

Замечания о трассировке

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

9.3.2  Отладка программ

Средством отладки программ или отладчик в Objective CAML является ocamldeb. Он позволяет пошаговое выполнение программы, вставлять контрольные точки, просмотреть или изменить значения окружения.

Сказать пошаговое выполнения, значить осознавать что такое в программе шаг. В императивном программировании это понятие соответствует инструкции языка. Однако подобное определение не имеет смысла в функциональном программировании. Здесь скорее говорят о событии (event) программы. Событием может быть применения, вход функции, сопоставление с образцом, условие, цикл, элемент последовательности.


Warning
Отладчик доступен только для систем Unix.

Компиляция для отладчика

При компиляции с опцией -g создается файл с расширением .cmo, что позволяет создать инструкции необходимые для отладки. Данная опция существует только для байт–код компилятора. При компиляции различных файлов программы, необходимо указать данную опцию. После того как получен исполняемый файл, необходимо запустить ocamldebug следующим образом:

ocamldebug [options] executable [arguments]

Пусть есть файл fact.ml со следующим кодом для вычисления факториала:

let fact n = let rec fact_aux p q n = if n = 0 then p else fact_aux (p+q) p (n-1) in fact_aux 1 1 n;;

Основная программа находится в файле main.ml, она запускает долгую рекурсию вызовом Fact.fact на -1.

let x = ref 4;; let go () = x := -1; Fact.fact !x;; go();;

Оба файла компилируются с опцией -g:

$ ocamlc -g -i -o fact.exe fact.ml main.ml val fact : int -> int val x : int ref val go : unit -> int

Запуск отладчика

После того как программа скомпилирована подобным образом, ее запуск в режиме отладчика происходит следующим образом:

$ ocamldebug fact.exe Objective Caml Debugger version 3.00 (ocd)

9.3.3  Контроль над выполнение программы

Контроль над выполнением реализуется при помощи событий программы. Можно либо продвинутся вперед или назад на n элементов программы, либо продвинутся вперед или назад до первой точки контроля (или на n точек). Точку контроля можно установить на функцию или элемент программы. Элемент языка можно выбрать по номеру линии, столбца или номера символа. Эти координаты могут быть определены по отношению к модулю.

В приведенном ниже примере, мы устанавливаем точку на четвертой строке модуля Main:

(ocd) step 0 Loading program... done. Time : 0 Beginning of program. (ocd) break @ Main 4 Breakpoint 1 at 4964 : file Main, line 4 column 3

Инициализация модуля происходит до самой программы. И по этой причине контрольная точка 4 находится после 4964 инструкций.

Перемещаться по программе можно либо по отношению к элементам программы либо по отношению к контрольным точкам. run и reverse выполняют программу до первой встретившейся точки. В первом случае выполнение происходит в нормальном направлении, а во втором в обратном порядке. По команде step выполняется один или n элементов программы входя в функции, а next не входя в функции. Соответственно команды backstep и previous выполняют программу в обратном порядке. И наконец команда finish завершает вызов текущей функции, а start возвращается к элементу стоящему перед вызовом функции.

В продолжении примера, продвинемся до контрольной точки, а затем выполним три элемента программы.

(ocd) run Time : 6 - pc : 4964 - module Main Breakpoint : 1 4 <|b|>Fact.fact !x;; (ocd) step Time : 7 - pc : 4860 - module Fact 2 <|b|>let rec fact_aux p q n = (ocd) step Time : 8 - pc : 4876 - module Fact 6 <|b|>fact_aux 1 1 n;; (ocd) step Time : 9 - pc : 4788 - module Fact 3 <|b|>if n = 0 then p

Просмотр значений

В контрольной точке можно просмотреть значения связанные с активным блоком. Команды print и display выводят в зависимости от глубины значения.

Выведем значение n, затем вернемся на три элемента назад и выведем значение x.

(ocd) print n n : int = -1 (ocd) backstep 3 Time : 6 - pc : 4964 - module Main Breakpoint : 1 4 <|b|>Fact.fact !x;; (ocd) print x x : int ref = {contents=-1}

Эти же команды позволяют вывести содержимое вектора или поле записи.

(ocd) print x.contents $1 : int = -1

Стек выполнения

Вложенные вызовы функций можно просмотреть в стеке выполнения. Для этого существует команда backtrace или bt, которая выводит порядок в котором вызывались функции. При помощи команд up down выбирается следующий или предыдущих активный блок. Для описания текущего блока используется команда frame.

9.4  Профайлер

С помощью профайлера можно получить определеную информацию о выполении программы: сколько раз была выполненя функция или структура контроля (условный, цикл или сопоставление с образцом). Эта информация сохраняется в файле, анализируя который, можно обнаружить алгоритмические ошибки или критические моменты, которые можно оптимизировать.

Для того, чтобы профайлер смог реализовать анализ, необходимо скомпилировать код со специальными опциями. Эти опции добавляют в код инструкции, необходимые для сбора данных. Существует две методики профайлинга: одна — для байт–код компилятора и другая — для нативного компилятора, плюс две комманды для представления результата. При анализе мащинного кода мы получим так же время затраченно на выполнение каждой функции.

Профайлинг программы состоит из трех этапов:

9.4.1  Комманды компиляции

Ниже приводятся комманды компиляции с опциями для профайлинга

Указанные компиляторы создают такие же типы файлов, что и обычные коммманды компиляции (6). В таблице 9.1 приведены различные опции компиляции.


fвызов функции
iответвления if
lцикл while и for
mответвления match
tответвления try
aвсе опции
Table 9.1: Опции команд профайлинга.

Данные комманды указывают, какие структуры контроля должны учитыватся профайлером. По умолчанию используются опции fm.

9.4.2  Выполнение программы

Байт–код компилятор

Пру успешном выполениние программы, которая была скомпилированна со специальными для профайлера опциями, мы получим файл ocamlprof.dump, который содержит желаемую информацию.

Вернемся к нашему примеру произведения элементов целочисленного списка. Пусть файл f1.ml содержит следующий код:

let rec interval a b = if b < a then [] else a::(interval (a+1) b);; exception Found_zero ;; let mult_list l = let rec mult_rec l = match l with [] -> 1 | 0::_ -> raise Found_zero | n::x -> n * (mult_rec x) in try mult_rec l with Found_zero -> 0 ;;

А так же файл f2.ml, в котором вызываются функции из f1.ml:

let l1 = F1.interval 1 30;; let l2 = F1.interval 31 60;; let l3 = l1 @ (0::l2);; print_int (F1.mult_list l1);; print_newline();; print_int (F1.mult_list l3);; print_newline();;

Компиляция файлов для профайлера осуществляется так:

ocamlcp -i -p a -c f1.ml val profile_f1_ : int array val interval : int -> int -> int list exception Found_zero val mult_list : int list -> int

С опцией -p, компилятор добавляет новую функцию (profile_f1_) для инициализации счетчиков модуля F1.Это касается и файла f2.ml:

ocamlcp -i -p a -o f2.exe f1.cmo f2.ml val profile_f2_ : int array val l1 : int list val l2 : int list val l3 : int list

Нативный компилятор

Компиляция в машинный код выглядит следующим образом:

$ ocamlopt -i -p -c f1.ml val interval : int -> int -> int list exception Found_zero val mult_list : int list -> int $ ocamlopt -i -p -o f2nat.exe f1.cmx f2.ml

Здесь используется лишь опция -p без аргументов. После выполения f2.exe мы получим файл gmon.out. Формат данного файла распознается обычными средствами Unix (см. стр. 9.4.3).

9.4.3  Представление результата

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

Байт–код компилятор

Команда ocamlprof представляет анализ результата измерений профайлера. Для этого используется информация содержащаяся в файле camlprof.dump. Данная команда читает приведеный файл и затем, при помощи исходного кода, создает новый исходный код программы, содержащий желаемые данные в виде комментариев.

Для нашего примера получим следующее:

$ ocamlprof f1.ml
let rec interval a b = (* 62 *) if b < a then (* 2 *) [] else (* 60 *) a::(interval (a+1) b);; exception Found_zero ;; let mult_list l = (* 2 *) let rec mult_rec l = (* 62 *) match l with [] -> (* 1 *) 1 | 0::_ -> (* 1 *) raise Found_zero | n::x -> (* 60 *) n * (mult_rec x) in try mult_rec l with Found_zero -> (* 1 *) 0 ;;

Полученные счетчики отражают запрошенные в модуле F2 вычисления. Мы получили 2 вызова для list_mult и 62 для вспомогательной функции mult_rec. Анализ ответвлений match показывает что образец по умолчанию выполнялся 60 раз, образец [] выполнялся один раз в самом начале и образец с нулем в начале списка так же выполнялся один раз, возбуждая исключение. В строке с try указывается значение образца вызвавшее исключение.

У команды camlprof имеется две опции. При помощи опции -f файл можно указать файл, в котором содержатся измерения. Опцией -F строка можно добавить строку в комментарии структурам контроля.

Нативный компилятор

Чтобы получить время, затраченное на вызов функции умножения элементов списка, напишем следующий файл f3.ml:

let l1 = F1.interval 1 30;; let l2 = F1.interval 31 60;; let l3 = l1 @ (0::l2);; for i=0 to 100000 do F1.mult_list l1; F1.mult_list l3 done;; print_int (F1.mult_list l1);; print_newline();; print_int (F1.mult_list l3);; print_newline();;

Это такой же файл как и f3.ml с 100000 итерациями.

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

$ gprof f3nat.exe Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls us/call us/call name 92.31 0.36 0.36 200004 1.80 1.80 F1_mult_rec_45 7.69 0.39 0.03 200004 0.15 1.95 F1_mult_list_43 0.00 0.39 0.00 2690 0.00 0.00 oldify 0.00 0.39 0.00 302 0.00 0.00 darken 0.00 0.39 0.00 188 0.00 0.00 gc_message 0.00 0.39 0.00 174 0.00 0.00 aligned_malloc 0.00 0.39 0.00 173 0.00 0.00 alloc_shr 0.00 0.39 0.00 173 0.00 0.00 fl_allocate 0.00 0.39 0.00 34 0.00 0.00 caml_alloc3 0.00 0.39 0.00 30 0.00 0.00 caml_call_gc 0.00 0.39 0.00 30 0.00 0.00 garbage_collectio

Здесь наглядно видно, что почти все время выполнения затрачено на исполнение функции F1_mult_rec_45, которая соответствует функции F1.mult_rec из файла f1.ml. Мы так же видим, что вызывается много других функций. Первые из них, являются функциями стандартной библиотеки по управлению памятью(8).

9.5  Резюме

В данной главе мы ознакомились с различными вспомогательными инструментами разработки программ, которые входят в дистрибутив Objective CAML.

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

Другие средства предоставляют информацию о выполнении программы. Интерактивная среда предлагает трассировку выполнения, но, как мы видели, полиморфизм устанавливает достаточно серьезные ограничения на исследуемые значения. Нам “видны” лишь мономорфные глобальные обьявления, а так же моморфные параметры функции. С помощью этого мы все такие можем остлеживать выполнени рекурсивных функций.

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


1
Файлы Makefile используются командой make чтобы обновлять при необходимости файлы или программы

Previous Up Next