Reading the code profiler(gprof)

Question

I'm trying to implement someone's Quadtree system, but it's insanely slow, so I'm attempting to figure out why. I've done some tests, and it takes a staggering two seconds to query 1000 against 1000 with it. It's insanely faster to just iterate through the whole thing instead.

I used code::blocks code profiler to try to find out why, but there's quite alot in there I don't understand, namely the pthread things. I do use multithreadding for networking, but the Quadtree system never touches it, as far as I can tell.

Image of the readout below.

https://i.stack.imgur.com/iMwPy.jpg

I have a feeling I'm just using it wrong, but It doesn't hurt to learn what all those pthread and unwind things are. I've seen them often, but they've never been at the top so prominently before this quadtree thing.

Answer 1

You could learn some things about performance.

One is that there is code you can change (sometimes called "your code") and code you can't change, like library code including all this pthread and unwind stuff. The most the latter can do is maybe give you a distant clue about what in your code can be taking time. It is more likely to either leave you mystified or exploring a wrong path.

Another is that "self time" is seldom useful. In all but the simplest toy programs, the computer's instruction pointer does not go very far in your code before calling into a subroutine (function, method, whatever it is called). Then in that routine it doesn't go very far before calling yet another. So you're going to see that if there's much self time in any routine, it's not likely to be in your code.

Another is that accuracy of measurement doesn't really matter. If a program is some factor, like 100, slower than it will be after it is fixed, what does that mean? That means that typically only 1 out of 100 nanoseconds are spent progressing toward the finish line. The other 99 are doing something useless, that if you knew what it was, you would easily recognize it as useless, so you would get rid of it. SO, if you run the program under an IDE or debugger, and simply click the "pause" button to make it stop at a random time, what is the chance you will see it doing the useless thing? Practically certain - the chance that it's in the 1% is 1%. If you're not sure if it's in the 1%, do it again. What's the chance that it's again in the 1% - 1% squared or 0.0001. So the chance that you've seen the speed bug is almost certain. That's two samples, not thousands.

To generalize, suppose only 30% is being wasted. Then the number of samples, on average, needed to see the problem two times is 2 / 30% or 6.67 samples. Typically there are multiple problems, so each time you fix one you get a speedup factor, and the percent taken by the others grows by that factor. That means you eventually get to the ones that were small at first.

That's the principle behind random pausing, the method many people and I use, and it is very effective.