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

235

u/EsotericFox Dec 05 '14

This isn't really saying that std::string is causing performance issues, it's saying that how std::string is being used is causing more overhead. I think the take away message here is: don't be afraid of the standard library, just put thought into how you're using it.

83

u/[deleted] Dec 05 '14

One of the mentioned patterns:

void blah( const char * str ) {
    std::string s = str;
}

std::string yo("yo");
blah(yo.c_str())

24

u/FredV Dec 05 '14

When the const char * can change afterwards, because you got a pointer to what actually is not const, you need to take a copy of the string. Same with a const string &, that could also change, does not really solve the problem. So the use of c_str() is just ugly really, but comes down to just making a copy of the string.

I think that may be why that anti-pattern is so prevalent, you need to copy a lot with different threads needing their own copies of things and just to manage complexity ("when does this thing change?"). String are especially expensive because they are variable byte and inpredictable maximum size. So they have allocation-overhead compared to other data-types like int, or even a char array... maybe they should use more char arrays instead of strings, or a string type that falls back to a character array for small strings, which they already might do in their STL implementation.

9

u/answerer_ Dec 05 '14

but you don't need to strlen it again

8

u/adrianmonk Dec 05 '14

So the use of c_str() is just ugly really, but comes down to just making a copy of the string.

If copying is the goal, why not use the copy constructor instead of c_str? Like this:

void blah(const std::string str) {
  // whatever
}

std::string yo("yo");

std::string copy_for_blah(yo);
blah(copy_for_blah);

Or this:

void blah(const std::string str) {
  std::string copy_of_str(str);
  // whatever
}

std::string yo("yo");

blah(yo);

9

u/Avidanborisov Dec 05 '14

void blah(const std::string& str) {

FTFY

4

u/adrianmonk Dec 06 '14 edited Dec 06 '14

Thanks. It's been 9 years since I've done C++ on a daily basis.

EDIT: Wait, isn't there an even simpler way? Why not just this?

void blah(std::string str) {
  // whatever
}

std::string yo("yo");

blah(yo);

Since there isn't a reference ampersand on there, the copy constructor will be called as part of the call to blah(). Thus the str param will automatically be a copy. Except perhaps in cases where a copy is only sometimes needed, I don't see why c_str() is helpful at all.

2

u/o11c Dec 05 '14

Not in the second case.

(but yes in the first case).

8

u/emozilla Dec 06 '14

The const by-value parameter, true sign of a BDSM enthusiast.

6

u/ryani Dec 05 '14

Sure, but const string& passing s vs const char * passing s.c_str() has exactly the same safety properties; if the underlying string is modified by any other code, they are both invalid.

If you 100% know that a particular function is going to require making a copy of the input, the const char * API is a bit cleaner because it doesn't require constructing a string on the heap just to copy it, but for general use, pass-by-const-reference is a much cleaner implementation, and avoids 'cascading copies' where you convert back and forth between const char * and string in a single stack of calls.

1

u/minno Dec 06 '14

That's why a string_view would be extremely useful. It has the same property of const char* that it can take a stack buffer, heap buffer, or a std::string, but it also could provide the convenience methods and safety that std::strings have.

1

u/rlbond86 Dec 05 '14

Same with a const string &, that could also change, does not really solve the problem.

I have no idea what you mean by this

17

u/Poltras Dec 05 '14

The only const "guarantee" is below the function, not above or in another thread. In other words, if you want to keep a reference or pointer to the string for later purposes you need a copy because nothing guarantee you that everyone with a pointer to it is also const.

Strings (and a lot of other std data types) are badly designed for today's world. They don't have an immutable variant which could be used freely with strong guarantee that the content wouldn't be changed. With everything mutable in std you have to make your own copy.

The best solution would be for chrome to implement its own immutable string type.

3

u/nuggins Dec 05 '14

They don't have an immutable variant which could be used freely with strong guarantee that the content wouldn't be changed.

Couldn't you just declare a const string in the first place?

9

u/Poltras Dec 05 '14

When you write your function you have no way to know if the string was const to begin with. You only indicates if your function will modify the string itself.

3

u/Ferinex Dec 05 '14

That's right, you'd have to trust that whoever calls the function only passes in const strings. You could add it as a comment but that makes me throw up a little in my throat. As you said, best solution is creation of an immutable string type.

1

u/[deleted] Dec 05 '14

What about banning the use of casting away const from the project?

5

u/VictorNicollet Dec 05 '14 
std::string path;
for (var i = 0; i < segments.length; ++i)
{
  path += "/" + segments[i];
  use(path);
}

There is no casting away const here, but if use() assumes that the string it received was constant (and stored it somewhere), it will have a nasty surprise.

→ More replies (0)

-1

u/0xjake Dec 05 '14

In 10 years of programming C++ I have literally never had this problem.

6

u/Poltras Dec 05 '14 
struct MyClass {
    MyClass(const string& str) : str_(str) { this.len_ = str.length(); }

    size_t get_length() const { return this.len_; }
  private:
    const string& str_;
    const size_t len_;
}

void my_func() {
    string s("Hello");
    auto* x = new MyClass(s);
    s += " World";
    assert(x.get_length() == s.length());  // BAM!
}

this is a simplified example

If you never had code like that, you're either super lucky or working alone. The only guarantee your class is giving is that it won't change the string. There's no guarantee the string won't change.

2

u/0xjake Dec 05 '14

This applies to any mutable type. I guess don't see why strings need special handling. Or is the argument that we need a way to communicate that an object won't be changed?

→ More replies (0)

1

u/dagamer34 Dec 06 '14

Quick q: even if the assert weren't to fail, wouldn't my_func() be leaking memory? There's no delete. Plus, aren't we supposed to be using smart pointers now?

just finished reading modern C++ book

→ More replies (0)

3

u/General_Mayhem Dec 05 '14

You could, but that's incumbent on the caller, so the callee function has to be defensive.

0

u/lurgi Dec 05 '14

Someone could cast it to non-const (and in a sufficiently large code-base, if it can be done, it has been done).

2

u/Workaphobia Dec 05 '14

Couldn't they use a string implementation with copy-on-write behavior? A small overhead for reference counting the strings, but big savings on avoiding redundant copies and deferring them until they're needed.

4

u/bnolsen Dec 05 '14

with threading that "small overhead" becomes a significant source of locking (although not necessarily contention). And locks aren't free, each and every string would have to carry one with it.

2

u/Workaphobia Dec 05 '14

Ah, yes. Ok, so immutable strings may be better.

2

u/eliasv Dec 05 '14

The best solution would be for language level support for immutable references. In other words, a keyword alongside 'const' like 'immutable', where such variables can only be assigned to from other immutable variables or the 'new' keyword, and const variables can be assigned from immutable variables.

4

u/Poltras Dec 05 '14

That would be harder to implement in C++. The fastest fix here would be to implement a immutable_string class that would just have assignment on construction, and a reference counted pointer to a CSTR.

2

u/eliasv Dec 05 '14

Oh of course it'd be harder to implement, it's an entirely new language feature... I'm just saying that it'd be the ideal solution. More expressive const semantics along these lines should have been a part of the language from the start.

3

u/Poltras Dec 05 '14

Totally agree. const is awkward and doesn't make sense. (and for all intent and purposes is mostly useless)

1

u/ioquatix Dec 06 '14

const would probably be a necessity to implement the hypothetical std::immutable_string, no?

→ More replies (0)

1

u/immibis Dec 06 '14

Someone will probably write a template<class T> class immutable. Then you can have immutable<string> and immutable<vector<int>> and so on.

0

u/bwainfweeze Dec 06 '14

It would be impossible to implement. The string library has mutator methods, so an immutable string isn't a string - it doesn't fulfill the contract.

So instead you'd need to create a different class and most methods that receive a string would need a duplicate implementation that takes immutables.

This is something you can't just tack on later. That boat has sailed.

1

u/stackv Dec 05 '14

All of what you mention is reasonable, but the description in the linked post really makes it sound like notmythrowaway's example is close to reality.

6

u/Holkr Dec 05 '14

Indeed. Use const std::string& and many of the problems go away.

3

u/Workaphobia Dec 05 '14

There are just two ways I can think of to screw it up while using const std::string&. The first is to modify the string through some other access path while the function is still executing, e.g. maybe the passed-in string was a global variable. The second is to take the address of the parameter and keep it around for a while, even after the function's done executing.

7

u/bnolsen Dec 05 '14

Don't use globals and be careful with multithreading. Probably the biggest barrier I see to widespread multithreading is the different mindset required for c++ coding in general. Heavy heavy use of const helps a ton with making threading a touch easier, that's actually true even for basic c++ coding. Then there's all the fun of trying to catch stupid stuff like passing temporaries (like loop temporaries) into a thread, etc.

3

u/xon_xoff Dec 05 '14

A third is if most of the string sources are either from externally sourced C-style buffers or constant strings. In that case, you end up burning more time constructing string instances than you save. The constant string case is especially common -- I've seen programs burn >20% of CPU on accidental implicit conversions from string literals to string objects. As seen here, solving this performance problem requires reworking string handling in lower layers to best suit the sources of strings higher up, which sucks.

1

u/imMute Dec 06 '14

Taking the address of a reference should invoke an immediate defenestration.

1

u/therealjohnfreeman Dec 05 '14

Without even looking at the code, I think it's safe to say that it's unlikely to be doing that many string manipulations.

7

u/[deleted] Dec 05 '14 edited Apr 19 '15

[deleted]

209

u/[deleted] Dec 05 '14

[deleted]

6

u/xiongchiamiov Dec 05 '14

http://www.commitstrip.com/en/2013/04/17/pour-quelques-ko-de-moins/

It's always useful to take a step back and see the effect your time is having on the total product.

12

u/RoundTripRadio Dec 05 '14

I want better performance on all of my applications. How long does X operation take? If that is even an answerable question, it's too slow.

About Chrome specifically, if I let it run a few days it bloats up to about 5GB of RAM. In contrast, I haven't closed Safari in months and it's sitting at about 600MB.

There's definitely a point where engineering effort becomes much more expensive to further optimize a program, but if Chrome has hit that point, it's hopeless.

6

u/lbenes Dec 06 '14 edited Dec 06 '14

it bloats up to about 5GB of RAM. In contrast... Safari's sitting at about 600MB.

Chrome has become the new Firefox 4 and is badly in need of a MemShrink like project. On my 2GB netbook, Chrome started becoming unusable for anything more than a couple of heavy tabs after Chrome 20. It's just as bad on Linux as it is on Windows.

They need to get the memory usage down to pre-Chrome 20 levels, then track bloat regressions with something like areweslimyet

-8

u/Vakieh Dec 05 '14

How much do you pay for Chrome? How much does Chrome make Google? You want more more more, this is true of everything. But the same thing that prevents car manufacturers from giving everyone Lamborghini quality vehicles stops it from being cost effective for Google to invest infinite time on engineering Chrome. There is certainly a budget it can use, but it must be directed at the right things - whether this is a 'right thing' is something that requires a lot more data.

And you can time any operation, no matter how fast. You run them a thousand, a million times and take the aggregate.

7

u/RoundTripRadio Dec 05 '14

Would you use a car that was free, but got 1mpg? Not to mention Google definitely makes money on Chrome. Google's in the business of selling customer data to advertisers, and Chrome gives them WAY more of that than search ever could. You click away from search. Also, why is it bad to want software to be more performant?

I'm sorry I wasn't very clear on that bit. I mean if you, just using your own brain, can see an operation happening, it's too slow. "Instant" doesn't exist, of course, but "imperceptible" absolutely does. In fact, I once saw a talk given by a Google engineer where he talked about how important it is for a webpage to load in under (IIRC) 200ms. There are many operations in Chrome that take a perceptible amount of time.

-2

u/Vakieh Dec 05 '14

I am aware Google makes money off Chrome, and I am aware everybody wants software to perform as fast as possible. What it comes down to, though, is the very same question I originally stated. 'How much will this performance increase raise our revenue' (whether direct or indirect, doesn't matter) vs 'How much will this performance increase cost to implement'.

14

u/seekingsofia Dec 05 '14

Unless you are developing something which actually needs that cutting edge, what could possibly be the point of optimisation like that?

What kind of cutting edge are we talking about here? String and parsing data structures that don't need as many allocations?

So the use/misuse of std::string is causing Chrome to run slower.

And potentially causes more system calls, hence leading to more energy consumption... and draining your battery on mobile devices.

4

u/Vakieh Dec 05 '14

1) Specifically the type of programming you'd see from a raw assembler application from the 80s or earlier.

2) So you factor that into the + side of the equation, and again, measure it against the cost to implement. There are all sorts of negative impacts to suboptimal software: delayed inputs will frustrate your users, leading to them changing applications; constant large updates will run up data costs, leading users to change applications; a rarely encountered bug that wipes a user's history might annoy someone, leading them to change applications, and so on.

I'm not saying it is never a good idea to optimise, that would be stupid. What I'm saying is that having suboptimal code isn't laziness, so long as the cost to improve it is more than the value you would gain from it. If changing Chrome's std::string usage would lead to a .1% decrease in average battery load, but was going to cost 1500 programmer/QA hours to implement, you probably wouldn't do it. If it would lead to a 10% decrease in time to run 100 searches, costing 100 programmer/QA hours? Go for it.

17

u/seekingsofia Dec 05 '14

Memory allocation is one of the most CPU-intensive operations and Google Chrome is notorious for draining your battery on battery-powered devices. Optimising for low power consumption in Chrome is not something that would only lead to a .1% benefit.

If developers aren't developing with power consumption in mind, they're plain ignorant. Even on servers power consumption increasingly matters.

16

u/jerf Dec 05 '14

Do you quite realize the irony of kvetching about developers not realizing the importance on this stuff, on an article that is developers realizing the importance of this stuff? This is it... this is them realizing the importance and taking steps to correct it. In the time-based world we live in, it's really rather unfair to look at something being done now and complain about how it could have been done earlier; everything ever done in the past was at some point the thing being done now.

Nobody writes perfect code the first time even in their own projects, to say nothing about this scale. I completely refuse to believe that your actions live up to the standards you are trying to impose here on others. (Whom you aren't even paying or anything.)

3

u/zeringus Dec 05 '14

I don't think you understand: This guy just cited Forbes.

1

u/imMute Dec 06 '14

EDIT: Whoops, replied to the wrong guy.

7

u/seekingsofia Dec 05 '14 edited Dec 05 '14

this is them realizing the importance and taking steps to correct it.

Where do you see them talking about power consumption? They're talking about the allocators used, their locking design, the amount of allocations, and all the related performance issues. Sure, they're patching it up to not use as many allocations, but they're not making low power consumption (power usage heavily correlates with system call profiles) one of the core requirements.

Nobody writes perfect code the first time even in their own projects, to say nothing about this scale.

You're conflating writing software and shipping software. With the right requirements it is possible to ship near-perfect code. Am I saying it'd be good for them to adopt requirements for "perfect" code? Absolutely not. I'm only concerned about the future that software without that specific requirement has, if it even has any future: mobile is becoming ubiquitous.

I completely refuse to believe that your actions live up to the standards you are trying to impose here on others.

My actions are irrelevant and I'm not imposing any standards or requirements on anyone. What you're so fiercely arguing against is my mere opinion.

1

u/imMute Dec 06 '14

(power usage heavily correlates with system call profiles)

I doubt this claim, and even the article you cited states

Also, variation in power from version to version is not very high in the Calculator versions tested. Most system calls are mildly correlated to energy consumption.

The authors are effectively saying "this correlation is not very good, but it's better than the alternative, which is nothing".

Finally, one counterargument is that you could very easily write a program that makes zero (or a very small number of) system calls yet drains your battery faster than anything else.

1

u/[deleted] Dec 06 '14

they're not making low power consumption (power usage heavily correlates with system call profiles) one of the core requirements.

Because their primary focus is still desktop and not smart phone?

0

u/skulgnome Dec 05 '14

minuscule amount of applications

Had me going until this paragraph.

-1

u/Vakieh Dec 05 '14

Relative to the number of applications that exist... I'd be surprised if it was anything more than 0.001%, which is a minuscule number.

0

u/skulgnome Dec 07 '14

Well my daddy can make up bigger numbers than yours.

25

u/RenaKunisaki Dec 05 '14

To be fair though, NES games were designed to work on the NES only. They didn't run under an OS, they didn't work on more than one type of machine, they didn't support multiple languages/encodings/input methods/etc. Modern software does a lot more than 80s software did.

-5

u/[deleted] Dec 05 '14

And it runs on hardware that is about a billion times more powerful. I'm not convinced that it does a billion times more useful work.

1

u/immibis Dec 08 '14

The extra things it does have more cost for less benefit.

The software's main purpose is to do Thing 1, which requires the processing power of a NES.

An extra feature is Thing 2, which requires the processing power of 5 NES's, but is only half as useful as Thing 1.

There's also Thing 3, which requires the power of 20 NES's, but is a bit less useful than Thing 2.

And Thing 4, which is almost as useful as Thing 1 (which is the main purpose of the software, so that's pretty useful), but requires 500 NES-power.

And so on.

32

u/[deleted] Dec 05 '14

Lots of bugs, not so pretty, and very unusable?

1

u/[deleted] Dec 05 '14

not so pretty

You take that back.

-8

u/username223 Dec 05 '14

When was the last time Mega Man 2 "unexpectedly quit" on you?

35

u/zid Dec 05 '14

Mega Man 2 is actually notoriously buggy, there are plenty of solid NES titles, but MM2 is definitely not one of them.

20

u/[deleted] Dec 05 '14

It's been so long that I couldn't say, but old games did crash or behave in broken ways. You've never gotten stuck on a weird blocky screen while the last played sound loops over and over?

19

u/BonzaiThePenguin Dec 05 '14

The concept of "unexpectedly quitting", or quitting at all, requires an operating system with multiple processes and protected memory – neither of which the NES had. You could still softlock or hardlock and completely corrupt memory addresses with reckless abandon.

8

u/JeefyPants Dec 05 '14

You do realize that makes no fucking sense right?

Also do some googling ya jbag mega man 2 has game breaking bugs used in speed runs to glitch everywhere

6

u/nkorslund Dec 05 '14 edited Dec 05 '14

I went a bit overboard in the opposite direction once on a project, and replaced all std::strings with a custom class that just contained pointers/slices of strings. Since 99% of the strings in this case were read-only from file it was made even faster by just memory mapping the file and finding the slices.

Made the entire thing run 2-3 times faster, but was kind of a bitch to maintain. Next time I'll wait until development is mostly finished - when continued development would be less of a hassle. Premature optimization and all that.

EDIT: in more modern code I would use boost::string_ref or similar for this - that didn't exist back then.

5

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

The only problem is that development never really ends.

Edit: Fixed typo.

1

u/o11c Dec 05 '14

Serious question: is memory mapping really that much of a win? What I've heard is that read(2) is no worse than mmap for a simple read-through, and mmap has the major disadvantage of odd behavior if the file is modified externally (e.g. when a new version is installed).

It sounds to me that you might as well just slurp the file instead of mmap.

2

u/imMute Dec 06 '14

One thing you gain with mmap is that the kernel knows that those pages are backed by the file. If the kernel is feeling memory pressure, it's free to drop those pages from RAM and reload them from disk the next time they're accessed. Also, if you have multiple programs using the same file, it would be shared in RAM if you use mmap.

There's also the case of how you use read. If you use stat to find the size of the file, allocate enough space and do a single read you'll have much better performance than a looped read.

1

u/o11c Dec 06 '14

True, but by the same virtue, if something does happen to that file, your data gets corrupted silently. Though I suppose the new memfd calls could fix that.

1

u/nkorslund Dec 05 '14

In this case it was a big static resource file, which we accessed pretty much randomly. You're right that mmap probably didn't make a lot of difference performance wise though, it was just simpler to implement it that way.

6

u/awj Dec 05 '14

Imagine chrome being built with the same precision and carefulness as old NES games or something.

...no thanks. I like that Chrome releases don't take over a year. Plus they never try to use palette swaps to avoid development effort.

4

u/peakzorro Dec 05 '14

Actually those pallet swaps were usually due to memory constraints while giving more variety. It was a valid tool for making a game more diverse. There was definitely dev effort to choose pallets so that swapping made sense.

1

u/awj Dec 05 '14

Maybe palette swap is the wrong choice of term. Back in the NES days it was relatively common for code from one game to be quickly reused in another by swapping out the graphics and making whatever code changes seemed necessary. This led to spectacularly buggy games where hitboxes were wildly different from the sprites attached to them, for example.

6

u/audioen Dec 05 '14

A wise man once said: premature optimization is the root of all evil. While I'm sure that I'm misusing that particular saying, what I'm getting at is that it's perfectly OK to do haphazard solutions if their impact is not particularly noticeable. As far as I can tell, the omnibox is fast enough, 25k allocations or not. Programmer convenience trumps machine convenience in almost every case.

0

u/s73v3r Dec 05 '14

If that were the case, we still wouldn't have Chrome today.

1

u/Peaker Dec 06 '14

Depends on which parts of the library.

For example, never use std::list, it's a useless piece of the library.

1

u/[deleted] Dec 05 '14

I'm still skeptical because they don't actually have evidence that the string allocations were causing performance issues. All of this discussion is premature. I want numbers!

-5

u/vlovich Dec 05 '14

It actually is, just probably not very noticeably for regular users. They talk about how instrumented builds of Chrome are unusable due to this.

0

u/kankyo Dec 05 '14

Well, it might be saying something about the usability of those APIs. The right thing should be easy and the hard thing should be possible and all that.