The hidden cost of C++ (2009)
rachelslabnotes.com
rachelslabnotes.com
Will that function call be inlined? Does it have side-effects? Are the arguments constant, so that it might even be evaluated at compile-time? Can it be hoisted out of a loop? Do its pointer args alias, preventing many of these operations? Is it big enough to blow the cache, or will it all fit in L1 and benefit from really fast memory accesses? Can branch-prediction operate effectively on its loops, or does it have an unpredictable pattern that will flush the pipeline many times?
I've heard that the best way to get your program to run fast is to get it into a compiler benchmark suite, so that compiler-writers account for it when writing optimizations. Failing that, it's all about profiling so you can measure the actual cost rather than relying on what you think you know about the programming language.
As a trivial example, objc_msgSend(). This is a C function, but it's also the entry point for objective-C's message sending (e.g. dynamic dispatch).
Basically, what I'm trying to say is, focusing on the cost of the function call itself is useless if you don't know the cost of the function implementation.
Can't we just agree that you can't predict the performance of an arbitrary program without measuring it? (You can predict the performance of some programs quite accurately, but that has nothing to do with language choice and everything to do with coding standards that bound execution time.)
What we can agree on is that knowing these things is just a small part of what affects performance and that performance can be rather unintuitive.
And, I know some other guys who do hard core embedded C programming and they are migrating to C++. They love it compared to C and can't wait until every line of their C code has been reimplemented in C++.
C++ will be around for decades to come and many folks actually enjoy writing it, they just don't advertise that fact.
Except that I also enjoy some Lisp from time to time.
Your operating system is written in C. Why learn C++? The return of investment of learning just C is much much higher than learning C++. Been there, done that.
I've been concentrating too much on C++ I think. This thread has prompted me to go back and spend some time writing some C.
1. http://ridiculousfish.com/blog/posts/i-didnt-order-that-so-w...
2. http://ridiculousfish.com/blog/posts/i-didnt-order-that-so-w...
Thankfully one of C++11's requirements was to not introduce any new functionality that had penalties even if you aren't using it. Too bad that wasn't a requirement for the original design of the language.
So saying it's not C++ because it's standard library is at best a misunderstanding, at worst it's disingenuous. The C++ spec is the cause of this fundamental problem with any attempt at doing COW optimization of std::string.
The second article is pretty much obsolete with C++11, which makes copy-on-write string implementations impractical.
For example, consider the following function:
char f(string &s)
{
const string &t = s;
const char &ch = t[1];
s[2] = 'x';
return ch;
}
As far as I know there isn't a proper solution to this problem without changing the return type of `std::string::operator[](size_type) const' in some non-standard way.
No, libstdc++ specifically DOES NOT unshare the string buffer when calling the CONST version of operator[] (really, go look it up). That's the whole point of CoW: to only copy when the string is written (or at least, when you have to pessimistically assume it will be, because somebody has gotten a non-const reference to its contents).
You could "fix" the issue by unsharing the buffer whenever a const iterator/reference to the string is returned, but then you lose most of the performance benefit of sharing the buffer in the first place, because most strings that are constructed are read at some point.
Because of these difficulties we'll see standard library implementations move away from copy-on-write implementations and then the whole issues doesn't exist. That is to say: the performance of the test case the blog author describes will be consistently “bad” because std::string will behave pretty much like a std::deque/std::vector.
The first link is a reasonable example of paying a cost for something you might not use. However, I disagree with the article when it says there's no good reason for it. People really do compare function pointers for equality. A common example is when different functions implement different "strategies" (to use the GOF term.) A simulation might customize the behavior of simulation objects using pointers to different strategy functions, and you might compare the pointers to find all the simulation objects that follow a particular strategy, or to check whether two objects use the same strategy. Since implementations are free to inline functions that are not declared "inline," there would be no valid way to compare function pointers if an inlined function could have different addresses in different translation units.
Adding performance at the expense of sanity should be voluntary, not the default behavior. (It definitely counts as insanity if comparing &my_handy_function and &my_handy_function for equality returns false in a language where function pointers are the only way to treat a function as data.) Anyone who is picky enough about performance to be concerned about link time is on intimate terms with their implementation(s) anyway, so I think it's perfectly acceptable for such an optimization to be available through non-standard flags. Although, if any language were to standardize insanity, perhaps it would be appropriate for it to be C++.
You can write non-performant code in any language you'd like, and obscure it in non-trivial ways. That's not the fault of the language.
Most of the argument revolves around objects. There are two ways you can run into "hidden" surprises with objects in C++ that the author is pointing out. One involves failing to use the language features given, the other involves writing some seriously odd code.
class C {
public:
/*explicit*/ C( int ); // Adding explicit avoids hidden costs
// This combination (or something like it) is lethal.
C( int, double );
operator bool() const;
};
Don't get me wrong, you can hide costs pretty easily in C++ and write some atrocious code. But usually this issue is alleviated by following basic best practices. The hard part is knowing what those best practices are.
I do agree that C++ is a complex and hodgepodge language, but I am not sure there are acceptable alternatives yet. It would be great if JVM had native support for value types, i.e., a way to use manual memory management, bypass bounds checks, or call native code without incurring serialization costs.
Yes, I am aware that C# does this (and I like C# and F# a great deal as languages), but a) I am not deploying Windows in production b) Mono is not yet a viable high performance server side platform (it does look promising for desktop and mobile application or for simpler ASP.NET webapps).
C is a beautiful and simple language (one I have strong affinity for) but manually implementing vtables is a bit painful (see a large pure C project for an example of that), nor is there any support for type-safe generic programming (which is an issue I have with Go as well -- even though I fully understand their reasons for omitting generics).
Then again, the reverse isn't true. There are languages (or more precisely their implementations) that just are slow.
Furthermore, good asymptotic complexity doesn't always correlate with faster code for values of n you actually encounter. Linear search is much faster than binary search, because of cache behavior, up to a surprisingly large n on many architectures.
I have had a few experiences of simply porting something rather directly to C++ and seeing 10X speed and memory improvements. The 'hidden costs' in other languages are loads of unavoidable heap allocations and pointer indirection that really don't happen with C++. And C++ compilers do a ton of very smart optimization these days.
With the generic programming constructs and static polymorphism approaches in C++ you can often get really big performance increases over what's practical in C or Java. std::sort in C++, for example, has often been found a few times faster than stdlib.h qsort. It's because of compile time optimizations that languages like C and Java can't do.
The mental effort you have to make to determine the overhead of an expression by looking at the call site is greater in C++ than it is in C.
That's an undeniable consequence of features like operator overloading, constructors, destructors, virtual functions, etc. It has nothing to do with how well you understand the language. The information just isn't there at the call site for you to see.
The question is a different one. It's whether that fact is compensated for by the power and reduced mental effort these features enable elsewhere. Constructors and destructors make RAII possible. That arguably makes memory management a lot easier than in C.
Isn't this just a specific example of saying "the mental effort you have to make to determine the overhead of an expression by looking at the call site is greater in higher-level languages than in lower-level ones"?
It's true, precisely because you are using higher-level abstractions. I'd be more interested in seeing an example where this wasn't true.
The only good reason to use C++ is because you (1) need a level of abstraction that C doesn't give you, (2) need level of performance that no garbage collected language can give you (even compiled ones), and (3) can't even use C + Lua (or some other scripting language), probably because you need the abstraction and the performance in the same place.
(This is an awfully narrow application domain, compared to what C++ is actually used for)
At that point, the performance characteristics of your programs have become part of the specs. You do not want to hide them under the carpet like you would do with a garbage collected language. Yet C++ does. It wouldn't hurt if it syntactically distinguished initializations, casts, calls by reference and so on.
Or take reference parameters. In C++, if you pass an object to a function you cannot know by looking at the call site if the object is going to be copied or not. The parameter could be defined as a reference, but you have to look at the function definition to find out. In C#, in Java, in Python and in C you know it by looking at the call site. These other languages are all over the place in terms of any high/low level categorization.
If you're writing, let's say, scenegraph traversal, it's really tempting to get it working on the PPU and then port it to run on an SPU. A vtable dereference to main memory will crash your SPU job and it is not always obvious why. Obviously, you can't use static analysis tools to make sure the right instructions are transferred, so you have to do it by hand. A modern PS3 game has on the order of low hundreds f different SPU jobs...not much fun. Even discounting that, SPUs will work best when fed branchless parallelized jobs, I wouldn't be surprised to see an order of magnitude difference between a vtable call on a pointer array and a static call on an object array.
Keeping pointers to objects in a polymorphic array is a games performance anti-pattern because of the dereferencing cost, but it's necessary to call virtual functions...there's a hidden cost right there.
Which loop is faster, by eyeballing, and by how much?
void load(Assets* a) {
for (int j=0; j<m_numAssets; j++) {
loadAsset(a[j]);
m_numLoadedAssets++;
}
}
void load(Assets* a) {
int numLoadedAssets=0;
for (int j=0; j<m_numAssets; j++) {
loadAsset(a[j]);
numLoadedAssets++;
}
m_numLoadedAssets = numLoadedAssets;
}
I don't think that all the author's points are spot on...Koenig lookup is Byzantine but IDEs do a good job of it, ditto source-level reasoning about dispatch. The underlying theme, that C++ is not a good fit for modern game development, shouldn't be so trivially dismissed.
It depends where *this is allocated. In the worst case, it is allocated in main memory while you wanted to stay in the graphic memory, or something.
A naive compiler would then access memory (or the cache) instead of using registers. A Sufficiently Advanced Compiler would guess that calling ++ many times is the same as incrementing in one go, and hoist that out of the loop, but apparently this one is a bit cruder.
Now the same could be said about m_numAssets, but this one isn't written to, so the compiler only have to put a copy in a register, which I guess is a simpler optimization to do.
To answer your question, that particular situation would be better in any language that forces you to explicit the reference to "this" (or "self"). Imagine how we could modify C++:
void member_function() {
int local_variable++;
local_variable++; // This is okay
member_variable++; // That should not be allowed
this->member_variable++; // This should be written instead
}
void load(Assets* a) {
for (int j=0; j<this->m_numAssets; j++) {
loadAsset(a[j]);
this->m_numLoadedAssets++;
}
}
void load(Assets* a) {
for (int j=0; j<m_numAssets; j++) {
loadAsset(a[j]);
}
m_numLoadedAssets += j; // Increment once, out of the loop
}I explained that here: http://news.ycombinator.com/item?id=4540107 I did not get the Load Hit Store problem, but I did sense there was a problem with the repeated read access to memory.
By the way, it looks like your problem is a bit more subtle than the textbook Load Hit Store: you don't read the location you just wrote to. I guess the write access dirties more than one word (at least a cache line, maybe more).
If I remember correctly somewhere further down in that particular Linus rant he was saying that you can look at a call site and tell what's going on, the same argument the poster here is making, but do we honestly believe Linus never uses function pointers? And the argument about the name of the function giving us a rough estimate of the overhead does not sound valid to me.
As a C programmer and former C++ programmer I can see a valid argument hidden in these types of posts but I think we'd be better off with a little less attitude and a little more useful guidelines.
ObjectiveC has a much smaller call site complexity penalty.
I believe a beginning programmer will be best off using fixed arrays at first, then reimplementing a basic version of std::vector when the need for it arises (which it inevitably will) and then use whatever vector datatype his chosen language offers him. This will give the programmer an understanding of what is actually going on and why the array is suddenly resizeable/resizes itself. That's the sort of attention to detail that separates a good programmer from a great one.
> do we honestly believe Linus never uses function pointers
Actually, they're all over the place in the kernel. They're used all the time when writing device drivers. I use them myself in every bit of quasi-polymorphic C code I write (although I'm not a kernel hacker). I think they're quite nifty actually although they can obscure things. Here we come back to how we're using constructs a language gives us. Used correctly, specifying well documented interfaces, they give birth to hardly any problems. Executed the wrong way, they give birth to all sorts of bugs and weird behaviour and obscure the code.
> the argument about the name of the function giving us a rough estimate of the overhead does not sound valid to me. It only will if you know the function, yes. Otherwise it's a weird argument.
I think your opinion is just as valid as Linus' is. I think, larger languages open the flood gates for decisions which can come at a cost for performance or maintainability. Programmers should be aware of that and useful guidelines would definitely help.
x = foo(bar(), baz());
I guess this is the trade-off with using a high level language. Expressivity vs transparency.
What's especially nice is that TRUE is defined as -1 in that source, not 1, which could easily confuse someone who isn't intimately familiar with C's boolean operators and conditional expressions (since something like if((a < b) == TRUE) { ... } would actually be incorrect).
Even with that in mind, it would still be nice to have a "safer to use" systems language than C++ generally available. Perhaps Go or D can fill that role (though good luck making that happen for game development on Windows...)
She also has a followup where she explores the "pressure points" of writing games in C++:
http://www.rachelslabnotes.com/2009/11/there-are-never-enoug...
I can count on one hand the number of times that I thought that changing the function signature of a few methods was going to impact whole application performance. Every time, it was in a low-level function that was called all over the place. Or, more to the point, I dug into function signatures when evidence pointed me there.
I can't even begin to list all of the other problems I worry about that actually do impact whole application performance on a regular basis.
One of the most important aspects of balancing productivity with performance is knowing which parts of code are crucial to performance and should be written with that in mind. That's one of the toughest parts as well. Usually one is better off profiling than guessing but I believe an educated guess can go a long way nevertheless.