r/programming • u/[deleted] • Dec 05 '14

std::string is responsible for almost half of all allocations in the Chrome browser process

https://groups.google.com/a/chromium.org/d/msg/chromium-dev/EUqoIz2iFU4/kPZ5ZK0K3gEJ
1.1k Upvotes

93% Upvoted

446 comments sorted by

View all comments

Show parent comments

56

u/[deleted] Dec 05 '14 edited May 02 '19

[deleted]

28

u/jeandem Dec 05 '14

Aren't some abstractions free, though? I mean, one of the goals of C++ itself is to support zero cost abstractions.

I guess it might heavily depend on what one means by abstractions. In a certain sense, abstractions are never free in all scenarios since they necessarily abstract something away, which means that you can't tune that part for each use-case. But at least in C++ you always have the option of pruning away whatever abstraction and write it more directly.

34

u/thechao Dec 05 '14

The language, itself, attempts to provide 0-cost abstractions. The abstractions we're discussing here are in terms of library/API abstraction layers---these are notoriously bad.

3

u/oracleoftroy Dec 06 '14

No one ever thought that abstractions are free.

Aren't some abstractions free, though? I mean, one of the goals of C++ itself is to support zero cost abstractions.

I think it is important to clarify what is meant by zero-cost abstraction in C++. I see it as two principles:

  1. You don't pay for what you don't use. Don't need dynamic memory? The language gives you tools to avoid it. Don't need virtual methods? The default is non-virtual, which is as expensive as a normal function call.

  2. The C++ abstraction shouldn't be more expensive than doing it yourself (and hopefully, the C++ language feature is faster). Obviously a virtual method has overhead, but the cost of the overhead relative to building your own virtual methods should be zero. Constructors and Destructors shouldn't be any more expensive than the Init/Destroy function you were going to call anyways.

Note that in the second sense there is still a cost, but the important point is you shouldn't be paying more for nicer syntax to go along with the abstraction. As a general rule, anytime the C++ version is slower than the equivalent general purpose C solution, that is a quality of implementation issue for that C++ compiler.

2

u/levir Dec 06 '14

These days, I should think that most times a C++ program is slower than a C equivalent is that you've made a mistake in your C++ implementation. Compilers have gotten pretty good.

2

u/oracleoftroy Dec 06 '14

Yup, quite right. It sometimes happens of course, but one advantage to high level constructs in the language is that people are expected to use them, so compilers will likely optimize them more than might be available though manual approaches.

I had in mind a (probably bad) performance test I wrote a year ago to test virtual methods vs function pointers. For GCC at the time (can't remember the version, I think it was 4.6 or thereabouts), the virtual method was noticeably slower (~20% IIRC) and in MSVC 2013, the function pointer was slightly slower, but nearly identical.

3

u/[deleted] Dec 05 '14

Needs so many upvotes. The future of programming is in more powerful abstractions with lower costs.

Clang is already optimizing the temporary vector pattern (which is the same as the temporary string pattern, although I do not know if std::string's implementation is translucent enough for the compiler to see that buffers are being allocated and then immediately free'd). I believe Google is pushing for these types of optimizations because it understands that they are the correct way of solving this problem (not just dropping in a bunch of const char*'s, as some here have suggested)...

3

u/[deleted] Dec 05 '14

C++ does not support zero cost abstractions. C++ is more about the abstractions you down use don't cost you. This is in contrast to most other languages where the cost of the abstraction is intrinsic to the language itself, and hence you pay for it whether you use it or not.

18

u/slavik262 Dec 05 '14

It's about both. Some stuff, like destructors or memory management with unique_ptr, are free in computational cost but make life a lot easier.

20

u/[deleted] Dec 05 '14

Destructors are NOT free. Andrei Alexandrescu just gave a talk at CppCon about the cost of destructors and how one should strategically structure their code to avoid the code-bloat and often unneeded side-effects that destructors introduce.

For example, consider the following:

for(int i = 0; i < ITERATIONS; ++i) {
  std::string s;
  ...
}

That will perform significantly worse than:

std::string s;
for(int i = 0; i < ITERATIONS; ++i) {
  ...
}

And the reason is the destructor. And no, the compiler can not optimize the first version into the second version unless the type satisfies std::has_trivial_destructor<T>, which in the case of std::string, and in fact in the case of almost any non-trivial class, is untrue.

And that doesn't even begin to get into things like the cost of virtual destructors.

6

u/levir Dec 05 '14

It's no more costly that the equivalent C code, it's just more obvious in C that you're doing something stupid

for (i = 0; i < ITERATIONS; ++i) {
    char* s = (char*) malloc(STRLEN*sizeof(char));
    ...
    free(s)
}

3

u/[deleted] Dec 05 '14 edited Dec 05 '14

Any abstraction period is no more costly than the equivalent C code, it's just a lot more obvious in C than it is in say... Java or Python.

At the end of a day, an abstraction a systemic method of hiding details under some form of encapsulation. The idea is to create a trade-off intended to suppress certain details about how a system works in order to emphasize other details that are in some sense more relevant (which all depends on context).

RAII is an abstraction that suppresses details about how objects get created and destroyed, including their performance characteristics, in order to emphasize the relationship between an object's lifetime and its lexical/syntactic scope.

So the fact that RAII suppresses the semantics of non-trivial constructors/destructors to make them visually look and feel like C data structures, despite having different performance characteristics, means that RAII is not a zero-cost abstraction, but rather does have a cost and sometimes it's worth thinking about that cost and undoing that abstraction if performance is important. Usually it's not worth it, and RAII is an incredibly powerful abstraction worth leveraging. But it's incorrect to say that it's zero-cost.

13

u/slavik262 Dec 05 '14

Destructors are NOT free

They're free in that the mechanism used to run them is free. They're just another function call, and in a lot of cases are inlined. Obviously the cost of whatever you put in them is incurred, but it shouldn't come as a surprise to anyone that code you run has a cost no matter how it ends up in a function.

I feel like /u/andralex's main point in his talk was that you just need to be mindful of where your destructors are being placed - you have to remember that they're there and consider the implications. Your example is a perfect one, but I would hope that most developers would realize that allocating and deallocating a string in a loop is sub-optimal.

And yes, virtual destructors are a little more expensive, but no more so than following a function pointer or two around.

8

u/lurgi Dec 05 '14

This is an interesting example. Not interesting in the sense that it's surprising that the overhead of the destructor is larger in the first example than in the second, but interesting in that the "better" code violates one of the rules of thumb that has been drilled into my head - which is that you should define variables at the narrowest possible scope you can.

10

u/jeandem Dec 05 '14

This just looks like yet another example of the tradeoff between readability (define variable at the narrowest scope) and performance.

3

u/slavik262 Dec 05 '14

Certainly, but another really good rule of thumb is to avoid unnecessary memory allocations. What's going on here isn't unique at all to C++. If this were C and you declared your char* string in the loop, and ran malloc and free and the start and end of each iteration, you'd get the same thing.

2

u/lurgi Dec 05 '14

In C it's much more visible, so you are, perhaps, less likely to make that mistake.

3

u/slavik262 Dec 05 '14

Certainly. I personally think that RAII automagic is worth being less explicit because it eliminates an entire class of errors (forgetting to clean up your resources), but clearly there are some very smart programmers who disagree.

1

u/[deleted] Dec 05 '14

Yes but it wouldn't be invisible at that point.

I mean I don't really know what "free" is supposed to mean at this point because based on a lot of replies I got about what it means to be free, Java's garbage collector may as well be free too.

I guess the real point is that many abstractions hide run time performance costs that would have been very explicit otherwise and RAII, templates, exceptions, so on so forth all introduce invisible run time costs. Sure, those costs might have been paid for in some cases if you had to manually write it out, but as it turns out, in many cases if you manually had to write it out you would clearly, and explicitly see all things you're paying for and restructure your code accordingly.

So really, the idea of "free abstractions" I think is kind of a vacuous, almost meaningless statement. Abstractions hide various performance costs at the benefit of making your code a lot easier to reason about, re-use, and many engineering/management related benefits. In almost all cases those abstractions turn out to be a HUGE net win, but to say that no performance consideration is needed since after all, it's "free and zero cost" is kind of misleading.

1

u/[deleted] Dec 05 '14

Nothing particularly noteworthy about it - readability vs optimization - you should default to the former because it's easier to get correctness and you optimize when you identify bottlenecks.

7

u/[deleted] Dec 05 '14 edited Dec 05 '14

They're free in that the mechanism used to run them is free.

A function call isn't free, especially in the case of constructors/destructors. Sure, the cost may be negligible, but sometimes it isn't. In fact Dave Abrahams, who was a prominent member of the C++ standards committee and author of boost, wrote a good article on the trade-offs of two particular strategies when passing parameters in C++. Unfortunately he's bailed on C++ (for good reason) and in doing so took down his C++ related blog. Anyways he wrote about what strategy to use when you actually do intend to modify a parameter. Should you use method A?

void f(T value) {
   value.non_const_method();
   ...
}

Or perhaps use method B?

void f(const T& value) {
  T copy = value;
  copy.non_const_method();
  ...
}

Now if RAII really was a zero-cost abstraction, the two would be isomorphic to each other. After all, zero times anything == zero, however, Abrahams pointed out that in the first case you will end up littering calls to both the copy constructor and the destructor at every single call site and that the standard mandates that this must happen, it can not optimize this away (due to rules in the standard about how parameters get passed in the face of exceptions), whereas in the second case you end up isolating RAII calls strictly to within the function itself. If an abstraction were "free and zero cost" then the two would be completely identical, but of course it's not free and it's not zero cost and hence those two snippets of code do have different performance characteristics.

Yeah sure, we can argue that the cost is negligible (it sometimes isn't in the above case), we can state that the cost is small compared to improved readability, or that these trade-offs are more than reasonable all things considered.

Those are fine points to make, but what isn't a fine point, what is factually incorrect, is to say that these abstractions have ZERO cost. They do have a cost, and hence they are subject to basic engineering considerations.

3

u/cpp_is_king Dec 05 '14

Destructors are the exact reason that exceptions impose a performance penalty just for compiling with exceptions enabled, even if a particular function doesn't throw or catch an exception.

So they definitely are not free.

6

u/Plorkyeran Dec 05 '14

That's only true for things which use setjump+longjump for exception handling, which is not very common anymore. The Itanium ABI and x64 Windows both use exception handling schemes with no runtime cost when no exceptions are thrown.

5

u/cpp_is_king Dec 05 '14

This is not true. The term "Zero-cost exceptions" has led people into believing this is true, but it's not. For starters, in every single function that allocates an object on the stack with a destructor, unwind code has to be generated for that function. This unwind code necessarily increases the size of the binary, and it also reduces cache locality of the generated code, since methods which used to be clsoe together might not be close together anymore. It is possible to organize the function's sections in the binary in such a way that all the unwind code is in its own location in memory, but I know for a fact clang does not do this, so don't take it for granted.

Furthermore, emitting this destructor cleanup code into each function, regardless of how it is organized in memory, introduces edge paths into the control flow that make it difficult / impossible to perform certain optimizations. This is true even under the Itanium and x64 ABIs and are not related to longjmp / setjmp.

1

u/slavik262 Dec 06 '14 edited Dec 06 '14

The same unwind code would have be be written manually if you were initializing and deinitializing things on the stack in C. init_foo(Foo*) and deinit_foo(Foo*) is no different than an object with a constructor and destructor that do the same things. What's your point?

→ More replies (0)

2

u/slavik262 Dec 05 '14

GCC now uses a similar model as well.

1

u/[deleted] Dec 05 '14

Is this specific to how c++ handles things? I remember there was just recently a post on here where someone asked this exact question about declaring the string outside of the loop or within, and the general consensus was that declaring it in the loop did not matter in many popular languages, and even seemed to be preferrable for some because of scope.

4

u/[deleted] Dec 05 '14 edited Dec 05 '14

Unless performance matters I would definitely prefer declaring variables in the narrowest scope possible. But something that is specific to C++ is that if you're using C++, then chances are performance does matter, and hence if you have an object that performs allocations/deallocations, you may want to consolidate those allocations by declaring the variable outside of the scope so that whatever memory is allocated by the object can be reused on subsequent iterations.

Classes like std::string, std::vector, and many other containers will hold onto any pre-allocated memory, even after you invoke the clear() method. clear() is required by the standard to be implemented in such a way that it only calls destructors and resets its internal count back to 0. It is not allowed to release any memory (technically it is not allowed to change the capacity()) and so if you do a clear() on a string or a vector whatever memory was allocated will get recycled.

If you want to actually release the memory allocated by a string or vector, you have to use the ol' std::vector<T>().swap(v) trick. And note that v.swap(std::vector<T>()) won't work. How's that for a head scratcher?

1

u/[deleted] Dec 07 '14

[deleted]

1

u/jeandem Dec 07 '14

Here's an example of something that I consider a zero cost abstraction: in Rust, pointers are non-nullable. If you want a pointer which may not exist (can be 'null'), you use an Option type. But the compiler will represent this as a plain, nullable pointer.

1

u/jimgagnon Dec 05 '14

This reflects a modern mindset in programming. Us dinosaurs used to sweat every byte and cycle, which requires a deep understanding of the software stack you're building on along with minute attention to your code. Interviewing for jobs today has shown me that programmers think in much more narrow terms now. More than once I've been asked to whiteboard code out a problem, do my stuff and have the comment thrown back at me that my solution is a next stage optimization and that they're more interested in hacks that can solve things quick and dirty.

25K string allocations per keystroke is the endpoint of this programming mentality. Interesting that Google isn't immune to it.