Fish tank with Puck the Fish Fish tank with Puck the Fish Water on the floor spelling Fish
 

I Didn’t Order That, So Why Is It On My Bill, Episode 1

June 22nd, 2009

C++ was designed to ensure you "only pay for what you use," and at that it is mostly successful. But it’s not entirely successful, and I thought it might be interesting to explore some counterexamples: C++ features you don’t use but still negatively impact performance, and ways in which other languages avoid those issues.

So here’s the first episode of I Didn’t Order That, So Why Is It On My Bill, to be continued until I can’t think of any more.

Inline Functions

The C++ standard says this:

A static local variable in an extern inline function always refers to the same object.

In other words, static variables in inline functions work just like static variables in any function. That’s reasonable, because that’s probably what you want. That’s what statics are for, after all.

But wait, it also says this:

An inline function with external linkage shall have the same address in all translation units.

That’s borderline silly. Who cares what the address of the function is? When’s the last time you used the function pointer address for anything except calling it? Dollars to donuts says never. You aren’t using a function pointer as a hash table key. You aren’t comparing the same function via pointers from different files. And if you did, you’d probably have the good sense to ensure the functions are defined exactly once (i.e. not inline). You can easily live without this feature.

So hopefully I’ve established that you don’t use this feature. Now I have to show how you’re paying for it anyways. Well, this feature complicates linking. Ordinarily, there should be only one copy of a function, and if the linker finds more than one it gives you a multiple definition error. But with inline functions, the compiler is expected to generates multiple copies of the code and it’s up to the linker to sort it out. See vague linkage.

So the linker has more work to do, and link time is increased. Again, who cares? Linking occurs after compilation, and I promised you a runtime cost. But ah – link time is runtime when we’re using dynamic libraries!

Every time you start up a program, the linker has to make sure that your implementation of vector<int>::capacity() has the same address as the vector<int>::capacity() defined in libWhoGivesAHoot.dylib just in case you decide to go and compare their function pointers.

And it gets a little worse. You know how class templates have to live in header files? The function definition goes right there in the class declaration, and that makes them inline automatically. So nearly every function in a template gets this inline uniquing treatment. Every template function in a class that cannot or should not be inlined – because its address is taken, because it is recursive, because you’re optimizing for size, or simply because it’s too darn big and inlining is counterproductive – will incur a launch time cost.

The situation is dire enough that gcc added a "-fvisibility-inlines-hidden" flag. This is a minor violation of the C++ standard, but will improve launch time in cases with a lot of dynamic libraries. In other words, this flag says: I’m not using this feature, please take it off my bill.

C does not have this problem. Why not? C (in the C99 standard) has very different semantics for inline functions. To oversimplify a bit, a C99 inline function acts as sort of an alias for a real function, which must be defined once and only once. Furthermore, inline functions can’t have static variables, or have their addresses taken. This approach is more limiting, but doesn’t require the linker to bend over backwards, and so avoids the performance penalty of the C++ approach.

Programming
Comment
Entry feed
Trackback from your site
 

The Internet!

π = 3.2860203432

Rubrick

It’s great to see you posting again. I’d figured you were gone for good.

Rubrick

BTW, the E-Mail field claims to be Optional, but is in fact required (and somewhat bizarrely results in a site login sheet if omitted).

Anonymous

Why does the linker need to ensure anything about &vector::capacity if you never take the address of that method? (And if you do take the address of it, you’re asking for the additional complexity.)

Enzo90910

Just wanted to send thanks for a very interesting blog.

CQuestioner

What about strong/weak function linkage?

Don Hersey

I haven’t programmed in awhile, so go easy on me, I’ve been busy with other things, unfortunately. Is the intent here to protect memory-mapped I/O (ie volatile paramed fns)? Or if the fn has something equivalent to a ‘how many times have I been called’ counter? What, in your opinion, is the motivation for having things this way?

david

great post, concise and interesting. however, who is exporting vector::* anyway? does this happen in any dylibs shipped in OSX?

Ross

(i just wanted to see what pi is so far, because i read the ‘what’s this’ link after reading the article.)

good article! can’t wait for the next ones..

DogCow

Glad to see you’re updating the blog again!

Someone

I do not understand why -fvisibility-inlines-hidden would have to break “An inline function with external linkage shall have the same address in all translation units”. Couldn’t a compiler:
- in code that never takes the address of a function f:
– call an invisible copy of an inline function
– not generate a copy with external linkage
- in code that does takes the address of f:
– generate a copy with external linkage
– use that copy’s address as address of f (so that the linker has to do work to guarantee that all translation units get the same value for its address)

Technically, that would be in conflict with the standard, but how could a conforming program tell? If not, what is wrong?

Pierre Lebeaupin

Well, if you read about symbol resolution in the Mach-O runtime (or for that matter, ELF), you realise that even in C some work needs to be done to ensure pointers to the same function always compare equal, e.g. one consequence is that a function from a dylib cannot be resolved lazily in a module where its address is taken (the address of the stub function cannot be taken as then it wouldn’t compare equal to the function pointer address taken from within the dylib, or one taken from another module). Some time after reading in these docs the care that needs to be taken to ensure that, I was thinking about how to implement a feature (in code that needs to be so cross-platform it’s not even funny – think embedded RT OSes), and while it could make sense for it to rely on function pointer equality (long story), I thought “Hmm, I read about how Mach-O does this, it’s not trivial, perhaps other systems screw this up…” and decided the feature would query the function instead of comparing the function pointers (the feature has yet to be implemented, though). It’s only later that I learned that, on Windows, not only can two function pointers to the same function, but taken from different sides of a DLL boundary, compare different (learned from experimenting with a test case), but in fact two different functions can end up in the same address (and have function pointers compare equal) if they do the same thing (learned from the Old New Thing, of course, and confirmed experimentally)! Of course, the latter (and perhaps the former) can be prevented if you specify some “OMG be super respectful of all C semantics” flag, but how can you trust everyone who ever compiles your code to always set such a flag?…

Pierre Lebeaupin

(I was not answering “Someone” with my post, btw.)

rmn

Well, you said you were going to say how we’re paying for this at runtime – but you haven’t. I wouldn’t consider the time it takes to load shared libraries as “runtime” since, well, it is not the run time of your own code. For the same reasoning you could say that context switches are part of your runtime and are somehow related to C++, but that would not make a valid point imo.
Nice read though.

Phil

rmn: This is a runtime cost. Consider a program that is run very often, and takes very little time. The linking can come to be the dominant term in total execution time. Consider also programs that can load dynamic libraries as plugins, or interpreters for some other language with a foreign function interface. We pay the cost at each load there, too.

Xo Wang

This blog is fantastic! I’m student who has been using C++ for about 3 years now, and I’ve noticed that what I’ve learned with each project were features and quirks of C++, and how or why *not* to use them. This little column introduced me to a new facet of the language—features I don’t need but still pay for.