3 ms·

A good tree will have something like log(n) depth so normal recursion should be fine. Apart from recursive algorithms, stack size can be determined by static a

A good tree will have something like log(n) depth so normal recursion should be fine. Apart from recursive algorithms, stack size can be determined by static analysis. Which reminds me: what is a good tool for analyzing / viewing a C++ programs call tree?

dllthomas 5y ago
> A good tree will have something like log(n) depth so normal recursion should be fine. But in many contexts you have to be robust against a bad tree. > Apart from recursive algorithms, stack size can be determined by static analysis. Not always, in the presence of dynamically sized arrays (or alloca and friends).
xfer 5y ago
https://llvm.org/docs/Passes.html#dot-callgraph-print-call-graph-to-dot-file https://llvm.org/docs/Passes.html#dot-callgraph-print-call-g...
AnimalMuppet 5y ago
Yeah. You won't be able to fit the tree in memory long before you overflow the stack while recursing down the tree.
stncls 5y ago
> A good tree will have something like log(n) depth so normal recursion should be fine. Yes, this is true for comparison/search/sort/bucketing algorithms. But in other applications (e.g. graph theory, networks, sparse matrices) a depth of n, for n elements, can be perfectly legitimate. Or it can even be an edge case, but one you don't want to handle by just segfaulting. > Which reminds me: what is a good tool for analyzing / viewing a C++ programs call tree? Linux perf can collect the necessary data. Then for frontends, I am not sure. KDAB's "hotspot" ( https://www.kdab.com/tag/perf/ https://www.kdab.com/tag/perf/ ) can do flamegraphs, but this may be more performance-oriented than what you're looking for. Edit: perf can collect the data statistically. It will miss many calls, the ones that are the least time-consuming.
wallstprog 5y ago
> Which reminds me: what is a good tool for analyzing / viewing a C++ programs call tree? As already mentioned, perf can capture call stacks, but those are statistical samples, so not necessarily complete. callgrind (https://www.valgrind.org/docs/manual/cl-manual.html https://www.valgrind.org/docs/manual/cl-manual.html) by contrast can capture all call-stacks. kCacheGrind/qCacheGrind (https://kcachegrind.github.io/html/Home.html https://kcachegrind.github.io/html/Home.html) can be used to view the output from either perf or callgrind. Sources for kcachegrind, including converters from perf, oprofile, etc., can be found at https://github.com/KDE/kcachegrind https://github.com/KDE/kcachegrind

dllthomas 5y ago

> A good tree will have something like log(n) depth so normal recursion should be fine. But in many contexts you have to be robust against a bad tree. > Apart from recursive algorithms, stack size can be determined by static analysis. Not always, in the presence of dynamically sized arrays (or alloca and friends).

xfer 5y ago

https://llvm.org/docs/Passes.html#dot-callgraph-print-call-graph-to-dot-file https://llvm.org/docs/Passes.html#dot-callgraph-print-call-g...

AnimalMuppet 5y ago

Yeah. You won't be able to fit the tree in memory long before you overflow the stack while recursing down the tree.

stncls 5y ago

> A good tree will have something like log(n) depth so normal recursion should be fine. Yes, this is true for comparison/search/sort/bucketing algorithms. But in other applications (e.g. graph theory, networks, sparse matrices) a depth of n, for n elements, can be perfectly legitimate. Or it can even be an edge case, but one you don't want to handle by just segfaulting. > Which reminds me: what is a good tool for analyzing / viewing a C++ programs call tree? Linux perf can collect the necessary data. Then for frontends, I am not sure. KDAB's "hotspot" ( https://www.kdab.com/tag/perf/ https://www.kdab.com/tag/perf/ ) can do flamegraphs, but this may be more performance-oriented than what you're looking for. Edit: perf can collect the data statistically. It will miss many calls, the ones that are the least time-consuming.

wallstprog 5y ago

> Which reminds me: what is a good tool for analyzing / viewing a C++ programs call tree? As already mentioned, perf can capture call stacks, but those are statistical samples, so not necessarily complete. callgrind (https://www.valgrind.org/docs/manual/cl-manual.html https://www.valgrind.org/docs/manual/cl-manual.html) by contrast can capture all call-stacks. kCacheGrind/qCacheGrind (https://kcachegrind.github.io/html/Home.html https://kcachegrind.github.io/html/Home.html) can be used to view the output from either perf or callgrind. Sources for kcachegrind, including converters from perf, oprofile, etc., can be found at https://github.com/KDE/kcachegrind https://github.com/KDE/kcachegrind