4 ms·
I'd like to see static analysis that shows the call graph with number of nested loops at each level. Perhaps a way to show the loop lines themselves to make it
by phkahler 4y ago
I'd like to see static analysis that shows the call graph with number of nested loops at each level. Perhaps a way to show the loop lines themselves to make it easy to estimate O(nmk) by looking at the output. Obviously more detailed complexity analysis would involve a person going through the code manually.
We have a number of algorithms in Solvespace that are O(n*2) some of them accidentally because certain list operations are O(n). One of the worst offenders was accidentally O(n*4) because an n*2 size input was handed to an O(n*2) algorithm. I wrote a smarter algorithm to avoid that inner call entirely.
TLDR it shouldn't be hard for tooling to produce useful time complexity estimates. Can we get this please?
- hinkley 4y agoThere's a pretty simple workaround for this that I discovered fairly early on: Create a deterministic test for your code, write down the expected call counts for each function, and then look at the actual call counts. You can spend all week shaving 15% off of an inner loop function or you can notice that it's being called 3x as much as you expected, fix that problem, and get a 60% performance improvement without changing a single line of that function.