5

I was asked to profile (using some tool, such as YourKit or JVisualVM) a couple of implementations of the Traveling Salesman Problem (find the minimum path that visits all the given set of cities), in the context of a Algorithms Analysis and Design graduate course.

Taking in consideration the brute force approach of the algorithm, I'm wondering, though, how to best use the tools (for instance, JVisualVM) to analyze the spatial and temporal complexities of the algorithm. If I'm not in error the algorithm has spatial complexity of O(n), as it basically grows linearly with the number of cities, while it is O(n!) in temporal complexity.

The math isn't the issue here.

After playing for a bit with both the referred tools, I'm having some hard time understanding how can they be of any use to my problem.

Sure I can see which methods are being used the most and which % of the time is being used in each one of them, and what is the actual memory footprint, so that can be all be regarded as hints where to optimize.

But other than that, and other than seeing the % of the CPU which is actually being used (or IO accesses, which never occur in this program), I can't see how can I actually learn something about the algorithm with these tools than the math before referred didn't.

What should be my main concerns when using profilers to the analysis of algorithms? Also, I've put basic time recording capabilities embedded in my program. Maybe I could use the profiling tools to better do that job?

Thanks

devoured elysium
  • 592
  • 1
  • 5
  • 17
  • 1
    Welcome to profiling. If they tell you anything, they don't tell you much. If you can single-step the program at the statement or instruction level, you will get a much clearer idea of how it might be made to go faster. You will be able to see exactly how it wastes time, because it will be wasting *your* time. – Mike Dunlavey Feb 22 '12 at 22:41
  • 1
    @MikeDunlavey: That's fine if you know where to look, but profiling is what tells you where to start when you have no idea where the bottleneck is (especially when it only occurs under specific circumstances). – TMN Feb 23 '12 at 01:11
  • You complexity analysis is wrong: The [traveling salesman problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem) is [NP complete](https://en.wikipedia.org/wiki/NP-complete) - not only O(n). – Martin Schröder Feb 23 '12 at 07:49
  • @TMN: I was referring to the OP's traveling salesman algorithm. For big software you're right, single-stepping won't work. Profilers won't either - try it. *[Here are PDF slides showing why.](http://sourceforge.net/projects/randompausedemo/files/)* – Mike Dunlavey Feb 23 '12 at 13:06

1 Answers1

2

I typically use the Performance Diagnostic Model (PDM) approach as taught by Kirk Pepperdine (he's a world leading expert on Java performance). One of the things it teaches is that the profiler is a scalpel you use once you've diagnosed the general nature of the performance problem / analysis you want to do. You typically start with looking at who the dominant consumer of the CPU is. This can be:

  1. System (i.e. Operating System/Hardware)
  2. User (which in turn splits into JVM or the Application)
  3. No dominator (which generally means CPU starvation)

So my question is - What question are you trying to answer in analysing these implementations? Is it their performance? If so then the profiler is actually the wrong place to start (starting with the profiler is common misconception that's taught).

Martijn Verburg
  • 22,006
  • 1
  • 49
  • 81
  • "So my question is - What question are you trying to answer in analysing these implementations? Is it their performance?" That's the main issue. I'm not really sure. I think my professor's idea would be to see how much the reality is in touch with theory (spatial / temporal complexity). – devoured elysium Feb 22 '12 at 23:10
  • 1
    I'd seek some clarification in that case :-). Spatial/Temporal complexity can be looked at via profilers, however they can also be analysed in other ways. You can also run some micro benchmarks using n inputs and see what the call stack is like in the profiler – Martijn Verburg Feb 22 '12 at 23:26