Инструмент для генерации рекурсивного дерева вызовов во время выполнения

Question

Существует ли простой инструмент для генерации дерева вызовов времени выполнения для рекурсивного алгоритма? Например, следующий для вычисления числа Фибоначчи:

Более конкретно, что если алгоритм реализован на C / C ++?

РЕДАКТИРОВАТЬ: я хочу, чтобы это дерево анализировало сложность рекурсивного алгоритма. Я знаю, как создать дерево в руке. Ранее я просто добавлял «cout» в файл soure, генерировал файл точек и использовал graphviz для генерации дерева. Но я хочу знать, есть ли какие-нибудь хорошие инструменты, чтобы сэкономить время написания кода.

РЕДАКТИРОВАТЬ: пример кода для числа Фибоначчи

//fib.cpp
#include<iostream>
typedef int Int;

Int fib(Int n)
{
  if (n==0)
    return 1;
  else if (n==1)
    return 1;
  else
    return fib(n-2)+fib(n-1);
}

int main()
{
  std::cout<<fib(5)<<std::endl;
  return 0;
}

Я пробовал valgrind для этого простого кода, но не могу найти, как получить график. Я использовал следующую команду:

g++ fib.cpp
valgrind --tool=callgrind ./a.out
kcachegrind callgrind.out.4343

Я пропустил некоторые варианты или что?

Answer 1

Используйте callgrind (cmdline) и затем kcachegrind (gui) для визуализации деревьев вызовов.Это один из инструментов из набора 'valgrind'.

Callgrind - это инструмент профилирования, который также позволяет увидеть полное дерево вызовов.Вы собираете информацию о профилировании, запустив ее в своей программе, затем анализируете вывод информации callgrind с помощью kcachegrind.

Дополнительное редактирование: К сожалению, как я только что узнал, это будет работать только частично для рекурсивных вызовов, которые в этом случае будут выглядеть как заглушка, вызывающая себя несколько раз.Несмотря на то, что callgrind создаст динамический граф вызовов, он не сможет показать переданные и возвращенные значения.Инструмент статического callgraph будет иметь тот же вывод (без количества вызванных вызовов).

Это будет выглядеть так, а не то, что вы хотите:

Я предполагаю, что единственный способ выяснить, в какой последовательности и с какими параметрами и возвращаемыми значениями была вызвана рекурсивная функция, - это выполнить backtrace (функцию gdb или backtrace ()) и визуализировать этот вывод (через graphviz).Для этого есть инструменты, но, насколько я знаю, они не находятся в свободном доступе / с открытым исходным кодом.

Answer 2

Я не думаю, что есть инструмент как таковой, но вы можете вручную создать дерево (и затем распечатать его так, как вам нравится. Для этого конкретного алгоритма узел дерева будет выглядеть примерно так:

struct node {
   int value;
   int result;
   node *left;
   node *right;
   node( int value ) : value(value), result(), left(), right() {}
};

И затем вы можете изменить функцию, чтобы позволить ей построить дерево:

int fibo( int value, node*& ptr )
{
   ptr = new node( value );
   ptr->result = fibo( value-1, ptr->left ) + fibo( value-2, ptr->right );
   return ptr->result;
}

По сути, называйте это как:

node* tree;
fibo( 5, tree );

А затем поработайте над деревом, которое вы построили.

Answer 3

Что вы подразумеваете под "получить дерево вызовов во время выполнения"?Вы хотите получить список вызовов в некотором массиве?

Если вы хотите получить список всех вызовов во время выполнения, вы можете просто создать эти функции и напечатать что-нибудь в каждом из них (или добавить в векторили что угодно), например:

int fib(int i) {
  int ret;
  printf("fib(%d)\n",i);
  if (i>2) ret=fib(i-2)+fib(i-1);
  else ret=i;
  printf("fib-end(%d)\n",i);
}

Если вы хотите получить что-то подобное, но во время компиляции, вы можете попробовать следующий подход:

template <int i>
inline int fib() {
  //do something
  return fib<i-2>()+fib<i-1>();
}

template <>
inline int fib<0>() {return 0;}

tempalte <>
inline int fib<1>() {return 1;}

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

Answer 4

Вы можете реализовать дерево и сохранить ссылку на активный лист.