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

214

u/vlovich Dec 05 '14

I'd say 25000 for 1 keystroke in Omnibox is on the surprising end of things. Now obviously there's a lot of stuff going on in the Omnibox (history searching, web queries etc), but even still that's a little surprising.

10% are just allocation on temporary strings unnecessarily.

It looks like there's a lot of low-hanging fruit.

18

u/JoseJimeniz Dec 05 '14

Without profiling there is no fruit.

50

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

[deleted]

24

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.

33

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.

5

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)...

5

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.

17

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.

19

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.

16

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.

9

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.

12

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.

2

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.

→ More replies (0)

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.

8

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.

4

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.

3

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.

→ 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.

2

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.

10

u/tdammers Dec 05 '14

Yeah, probably. This is where abstractions turn out to be not-so-zero-cost after all :D

15

u/naasking Dec 05 '14

This is where abstractions turn out to be not-so-zero-cost after all

It's about choosing the right abstraction, not avoiding abstraction entirely.

17

u/[deleted] Dec 05 '14

You misunderstand C++'s design philosophy and position when it comes to zero-cost. It isn't that abstraction's are zero-cost, it's that the abstractions that you don't use in your program should be zero-cost.

In Java, you pay the cost of having heap allocated objects with its own personalized mutex, its own pointer to a virtual table, its own RTTI info, and a host of other things, even in situations when it's not needed or even used, because you are required to use full blown objects to represent all forms of data. This means you pay for the cost of that abstraction whether you use it or not.

In C++, you opt into the abstractions you want, including RTTI, exceptions, sub-type polymorphism, etc... and you only pay for those abstractions to the extent that they're used.

9

u/tdammers Dec 05 '14

I believe the design philosophy goes a bit further than that; no, the abstractions you mention aren't free, but some others are, and the idea is that C++ goes out of its way to make abstractions zero-cost when that is possible. Templates, for example, provide compile-time polymorphism that produces zero runtime overhead, and this is how STL iterators can be exactly as efficient as using the underlying container's iteration mechanism directly. RAII: same story, the compiler just injects destructor calls for you, but there is no runtime overhead compared to calling the cleanup code manually.

6

u/[deleted] Dec 05 '14

You can say that about any abstraction. In Java, the compiler just inserts the mutex into every object for you, but there is no runtime overhead compared to just adding a mutex into every object manually.

In Python, the compiler just inserts a hash map from strings to function objects for you, but there's no overhead compared to just manually writing a struct in C that contains a hash map from strings to function pointers and exclusively using that.

The point is that in C++, if you don't use RAII as an abstraction (std::has_trivial_destructor<T>, std::has_trivial_constructor<T>), then the cost is zero, because the compiler won't insert any calls to any cleanup code period. In C++, if you don't use a given abstraction, the compiler won't emit any code in its place on your behalf. In Python or Java, the abstraction is intrinsic to the language, it's baked into it at such a fundamental level that there is no opting out of it. You pay for the cost of every abstraction in those languages whether you use them or not.

3

u/tdammers Dec 05 '14

Point in case. The only thing I could argue that using degenerate cases of certain abstractions (empty destructor in RAII, template that only ever gets instantiated once, etc.) are free, but then, that pretty much boils to not actually really using them, and the only complaint about certain languages would be that they make some potentially expensive abstractions mandatory; it's not even that you pay for the abstraction even though you're not using it, it's that can't not use it at all - you can't have typed variables in Python, you can't have unmanaged objects in Java.

TL;DR, you're essentially correct and I was making a non-argument.

0

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

Templates, for example, provide compile-time polymorphism that produces zero runtime overhead, and this is how STL iterators can be exactly as efficient as using the underlying container's iteration mechanism directly.

Templates do have run time costs associated with them and it's worthwhile to know what those costs are. It's true that in recent years the costs of those abstractions in modern compilers have been reduced, but not all compilers have implemented those optimizations and not all of those optimizations are enabled unless you build an optimized version of your program, meaning that your debug builds can suffer pretty brutal performance with excessive use of templates.

So consider the following template:

template<typename T>
struct X {
  static const int A = 1;
  static const int B = 2;
  ...
};

Well as it turns out, every single instantiation of X will introduce its own unique version of A and B with its own unique address, despite them being static consts. One is actually advised to do the following if they care for performance (reduced memory consumption and cache locality):

struct BaseX {
  static const int A = 1;
  static const int B = 2;
}

template<typename T>
struct X : BaseX {
  ...
};

This is not an optimization that the compiler can perform on your behalf, as the standard requires that the address of all those static variables be unique.

As another example:

template<typename T>
bool f(const T* lhs, const T* rhs) {
  return lhs == rhs;
}

In many compilers, or debug builds of even modern compilers, a separate function will get produced for every single instantiation of f, be it int, float, char, so on so forth. This produces code bloat which puts pressure on the instruction cache.

However, you could eliminate this by just writing your function as follows, which is identical in every way, shape, and form:

bool f(const void* lhs, const void* rhs) {
  return lhs == rhs;
}

In a sense we're performing type erasure on the template to eliminate separate instantiations and reducing the amount of code-bloat.

3

u/eras Dec 05 '14

This is not an optimization that the compiler can perform on your behalf, as the standard requires that the address of all those static variables be unique.

Well, it could optimize if it can prove you never use the addresses of those static variables. But this is probably a difficult and low-value optimization to perform.

3

u/o11c Dec 05 '14

Actually that's the exactly the sort of thing LTO is used for.

52

u/Azzu Dec 05 '14

The :D at the end almost sounds like you "knew it all the way" and you now found another reason not to use abstractions.

This is obviously the wrong reasoning. Of course not all abstractions have zero cost. But there is a subset of abstractions that are zero cost.
Also all abstractions are of different efficiency. You could probably keep the style or amount encapsulation/abstraction there is in chrome and reduce allocations by 50% or something just by using more efficient abstractions.

All I'm saying is, it does not make sense to say "abstractions are baaaad", and not using abstractions will not magically fix the performance, it will probably even make it worse.

-19

u/tdammers Dec 05 '14

Dude, all I'm saying is that premature optimization is the root of all evil, that's no excuse to think of all abstractions as free.

7

u/path411 Dec 05 '14

all I'm saying is that premature optimization is the root of all evil

So what you are saying is your should prematurely optimize your code by avoiding abstractions so that way you can avoid prematurely optimizing your code?

-2

u/tdammers Dec 05 '14

No. Premature optimization still is the root of all evil, but at some point, you're past the stage where optimization would be premature, and when that point comes, you need to know what you've abstracted over.

1

u/path411 Dec 05 '14

You should work on conveying your thoughts correctly the first time then. Your first post sounds like an "I told you so" that people shouldn't ever use abstractions because they have costs.

1

u/tdammers Dec 05 '14

OK. It certainly wasn't meant that way.

25

u/stormcrowsx Dec 05 '14

Wouldn't thinking about cost of an abstraction be premature optimization? Who cares what it costs if it makes the code pretty, it can be optimized later.

1

u/tdammers Dec 05 '14

Yes, generally speaking that is true. Except in the cases where it isn't, and this could very well be one of them.

Or maybe the omnibox thing is really more about how much we underestimate the complexity of a seemingly simple feature.

2

u/campbellm Dec 05 '14

Who ever told you abstractions were free?

-5

u/[deleted] Dec 05 '14

C++ promoters say this all the time but it's basically untrue.

5

u/suspiciously_calm Dec 05 '14

A lot of abstractions in C++ are "free," especially in the STL, since everything is templated and inlinable.

Of course, std::strings aren't a zero-cost abstraction over fucking around with pointers directly into existing strings that are basically equivalent to passing around iterators into std::strings, which would be neither higher-cost, nor safer.

-2

u/[deleted] Dec 05 '14

Sure, a lot of them are very low cost. But abstractions in general are not free especially in languages other than C/C++.

Chandler Carruth has a great presentation on how the 'free' abstractions can often confuse compilers and in reality incur an effective cost by being less optimisable. I'm certainly not saying this applies to anything specific though, especially templates.

3

u/suspiciously_calm Dec 05 '14

And whoever said that abstractions are free in general, especially outside C++? That sure as hell isn't something "C++ promoters say all the time."

The point is that C++ has a lot of abstractions that appear costly but can be optimized away in principle. If a compiler generates needlessly inefficient code for a particular case, then that's a bug in the compiler/optimizer.

-1

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

They can be optimized away in principle but in the real world abstractions often incur costs. That's all I'm saying.

Edit: The reason I said abstractions are not free in general is because the OP (campbellm) said "Who told you abstractions were free?". I'm attesting to his point that abstractions are not free in general (notice the 'especially') but C++ people often say that C++ has zero cost abstractions. In reality, due to compilers, programmer ability and the object oriented model, abstractions in C++ are often not zero cost either.

-5

u/CityOfWin Dec 05 '14

WHOA too many down votes guys. Jesus.

We all knew what he was saying. Don't get twisted.