I have a C++ application, running on Linux, which I'm in the process of optimizing. How can I pinpoint which areas of my code are running slowly?
C++ – How to profile C++ code running on Linux
clinuxprofiling
Related Solutions
I use this to split string by a delimiter. The first puts the results in a pre-constructed vector, the second returns a new vector.
#include <string>
#include <sstream>
#include <vector>
#include <iterator>
template <typename Out>
void split(const std::string &s, char delim, Out result) {
std::istringstream iss(s);
std::string item;
while (std::getline(iss, item, delim)) {
*result++ = item;
}
}
std::vector<std::string> split(const std::string &s, char delim) {
std::vector<std::string> elems;
split(s, delim, std::back_inserter(elems));
return elems;
}
Note that this solution does not skip empty tokens, so the following will find 4 items, one of which is empty:
std::vector<std::string> x = split("one:two::three", ':');
static_cast
is the first cast you should attempt to use. It does things like implicit conversions between types (such as int
to float
, or pointer to void*
), and it can also call explicit conversion functions (or implicit ones). In many cases, explicitly stating static_cast
isn't necessary, but it's important to note that the T(something)
syntax is equivalent to (T)something
and should be avoided (more on that later). A T(something, something_else)
is safe, however, and guaranteed to call the constructor.
static_cast
can also cast through inheritance hierarchies. It is unnecessary when casting upwards (towards a base class), but when casting downwards it can be used as long as it doesn't cast through virtual
inheritance. It does not do checking, however, and it is undefined behavior to static_cast
down a hierarchy to a type that isn't actually the type of the object.
const_cast
can be used to remove or add const
to a variable; no other C++ cast is capable of removing it (not even reinterpret_cast
). It is important to note that modifying a formerly const
value is only undefined if the original variable is const
; if you use it to take the const
off a reference to something that wasn't declared with const
, it is safe. This can be useful when overloading member functions based on const
, for instance. It can also be used to add const
to an object, such as to call a member function overload.
const_cast
also works similarly on volatile
, though that's less common.
dynamic_cast
is exclusively used for handling polymorphism. You can cast a pointer or reference to any polymorphic type to any other class type (a polymorphic type has at least one virtual function, declared or inherited). You can use it for more than just casting downwards – you can cast sideways or even up another chain. The dynamic_cast
will seek out the desired object and return it if possible. If it can't, it will return nullptr
in the case of a pointer, or throw std::bad_cast
in the case of a reference.
dynamic_cast
has some limitations, though. It doesn't work if there are multiple objects of the same type in the inheritance hierarchy (the so-called 'dreaded diamond') and you aren't using virtual
inheritance. It also can only go through public inheritance - it will always fail to travel through protected
or private
inheritance. This is rarely an issue, however, as such forms of inheritance are rare.
reinterpret_cast
is the most dangerous cast, and should be used very sparingly. It turns one type directly into another — such as casting the value from one pointer to another, or storing a pointer in an int
, or all sorts of other nasty things. Largely, the only guarantee you get with reinterpret_cast
is that normally if you cast the result back to the original type, you will get the exact same value (but not if the intermediate type is smaller than the original type). There are a number of conversions that reinterpret_cast
cannot do, too. It's used primarily for particularly weird conversions and bit manipulations, like turning a raw data stream into actual data, or storing data in the low bits of a pointer to aligned data.
C-style cast and function-style cast are casts using (type)object
or type(object)
, respectively, and are functionally equivalent. They are defined as the first of the following which succeeds:
const_cast
static_cast
(though ignoring access restrictions)static_cast
(see above), thenconst_cast
reinterpret_cast
reinterpret_cast
, thenconst_cast
It can therefore be used as a replacement for other casts in some instances, but can be extremely dangerous because of the ability to devolve into a reinterpret_cast
, and the latter should be preferred when explicit casting is needed, unless you are sure static_cast
will succeed or reinterpret_cast
will fail. Even then, consider the longer, more explicit option.
C-style casts also ignore access control when performing a static_cast
, which means that they have the ability to perform an operation that no other cast can. This is mostly a kludge, though, and in my mind is just another reason to avoid C-style casts.
Related Topic
- C++ – The Definitive C++ Book Guide and List
- Python – How to you profile a Python script
- Linux – How to change permissions for a folder and its subfolders/files in one step
- Node.js – How to update NodeJS and NPM to the next versions
- Linux – How to use grep to show just filenames on Linux
- Linux – How to kill a process running on particular port in Linux
- Linux – How to find all files containing specific text on Linux
Best Answer
If your goal is to use a profiler, use one of the suggested ones.
However, if you're in a hurry and you can manually interrupt your program under the debugger while it's being subjectively slow, there's a simple way to find performance problems.
Just halt it several times, and each time look at the call stack. If there is some code that is wasting some percentage of the time, 20% or 50% or whatever, that is the probability that you will catch it in the act on each sample. So, that is roughly the percentage of samples on which you will see it. There is no educated guesswork required. If you do have a guess as to what the problem is, this will prove or disprove it.
You may have multiple performance problems of different sizes. If you clean out any one of them, the remaining ones will take a larger percentage, and be easier to spot, on subsequent passes. This magnification effect, when compounded over multiple problems, can lead to truly massive speedup factors.
Caveat: Programmers tend to be skeptical of this technique unless they've used it themselves. They will say that profilers give you this information, but that is only true if they sample the entire call stack, and then let you examine a random set of samples. (The summaries are where the insight is lost.) Call graphs don't give you the same information, because
They will also say it only works on toy programs, when actually it works on any program, and it seems to work better on bigger programs, because they tend to have more problems to find. They will say it sometimes finds things that aren't problems, but that is only true if you see something once. If you see a problem on more than one sample, it is real.
P.S. This can also be done on multi-thread programs if there is a way to collect call-stack samples of the thread pool at a point in time, as there is in Java.
P.P.S As a rough generality, the more layers of abstraction you have in your software, the more likely you are to find that that is the cause of performance problems (and the opportunity to get speedup).
Added: It might not be obvious, but the stack sampling technique works equally well in the presence of recursion. The reason is that the time that would be saved by removal of an instruction is approximated by the fraction of samples containing it, regardless of the number of times it may occur within a sample.
Another objection I often hear is: "It will stop someplace random, and it will miss the real problem". This comes from having a prior concept of what the real problem is. A key property of performance problems is that they defy expectations. Sampling tells you something is a problem, and your first reaction is disbelief. That is natural, but you can be sure if it finds a problem it is real, and vice-versa.
Added: Let me make a Bayesian explanation of how it works. Suppose there is some instruction
I
(call or otherwise) which is on the call stack some fractionf
of the time (and thus costs that much). For simplicity, suppose we don't know whatf
is, but assume it is either 0.1, 0.2, 0.3, ... 0.9, 1.0, and the prior probability of each of these possibilities is 0.1, so all of these costs are equally likely a-priori.Then suppose we take just 2 stack samples, and we see instruction
I
on both samples, designated observationo=2/2
. This gives us new estimates of the frequencyf
ofI
, according to this:The last column says that, for example, the probability that
f
>= 0.5 is 92%, up from the prior assumption of 60%.Suppose the prior assumptions are different. Suppose we assume
P(f=0.1)
is .991 (nearly certain), and all the other possibilities are almost impossible (0.001). In other words, our prior certainty is thatI
is cheap. Then we get:Now it says
P(f >= 0.5)
is 26%, up from the prior assumption of 0.6%. So Bayes allows us to update our estimate of the probable cost ofI
. If the amount of data is small, it doesn't tell us accurately what the cost is, only that it is big enough to be worth fixing.Yet another way to look at it is called the Rule Of Succession. If you flip a coin 2 times, and it comes up heads both times, what does that tell you about the probable weighting of the coin? The respected way to answer is to say that it's a Beta distribution, with average value
(number of hits + 1) / (number of tries + 2) = (2+1)/(2+2) = 75%
.(The key is that we see
I
more than once. If we only see it once, that doesn't tell us much except thatf
> 0.)So, even a very small number of samples can tell us a lot about the cost of instructions that it sees. (And it will see them with a frequency, on average, proportional to their cost. If
n
samples are taken, andf
is the cost, thenI
will appear onnf+/-sqrt(nf(1-f))
samples. Example,n=10
,f=0.3
, that is3+/-1.4
samples.)Added: To give an intuitive feel for the difference between measuring and random stack sampling:
There are profilers now that sample the stack, even on wall-clock time, but what comes out is measurements (or hot path, or hot spot, from which a "bottleneck" can easily hide). What they don't show you (and they easily could) is the actual samples themselves. And if your goal is to find the bottleneck, the number of them you need to see is, on average, 2 divided by the fraction of time it takes. So if it takes 30% of time, 2/.3 = 6.7 samples, on average, will show it, and the chance that 20 samples will show it is 99.2%.
Here is an off-the-cuff illustration of the difference between examining measurements and examining stack samples. The bottleneck could be one big blob like this, or numerous small ones, it makes no difference.
Measurement is horizontal; it tells you what fraction of time specific routines take. Sampling is vertical. If there is any way to avoid what the whole program is doing at that moment, and if you see it on a second sample, you've found the bottleneck. That's what makes the difference - seeing the whole reason for the time being spent, not just how much.