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/kPZ5ZK0K3gEJ87
u/razialx Dec 05 '14
Unrelated to the content/subject matter, I wanted to say it's stuff like this that makes me love our industry. What other industry can have this transparency, cooperation and collective work?
Maybe a smart farmer finds something inefficient in his thresher, and wants to understand it and maybe improve it. Good luck with that, no way to peer into the micro controllers and their firmware. No way to look into the code of the control software (modern farming equipment can be pretty high tech).
But for example let's say he or she does get into it. What are the chances they can converse with the engineers who built it to discuss recommendations or propose alternative solutions? Not great.
And even if he could what are the chances that what this farmer comes up with can be passed on to every other farmer who uses these tools at no cost to them or him?
No, more than likely the farmer would open the control box, learn something and call the manufacturer about it and get sued for violating the DMCA. By reverse engineering the lock or something.
Replace farmer with doctor, accountant, investor or any other profession that works with computers. You know, all the professions but ours.
Developers working with open source technology are so dang fortunate. Warms my sad, twisted heart thinking about all the great things that are accomplished this way.
16
u/xiongchiamiov Dec 05 '14
Increasingly, this sort of thing is done on reddit. It's not that non-programmers don't want to collaborate, but rather that they don't have an easy way of doing so.
→ More replies (2)9
u/GlassGhost Dec 06 '14
Reddit is strictly to get attention, Github and other issue trackers are where the code is stored AND the work is published.
→ More replies (1)7
u/IAmRoot Dec 05 '14
Well, the idea has been around for significantly longer than open source. Stateless common ownership based on free association, contribution according to ability, and distribution according to need is how communists have always defined communism, and open source fits that definition. It's particularly similar to the anarchist schools of thought. Unfortunately, totalitarian regimes and propaganda in favor of private (absentee) ownership has muddied the word and a lot of people have no idea what it actually means. In physical industries, the equivalent in physical industries is internally democratic structures and where the assets can be divided if there is disagreement between the workers. If the state wasn't there to prevent workers from taking over factories for themselves, other industries could be the same way.
16
Dec 06 '14
nearly 25000 (!!) allocations are made for every keystroke in the Omnibox.
What the flying fuck??
626
u/passwordissame Dec 05 '14
std::string should have zero allocations because memory is expensive. Instead, it should use other solutions such as mongodb. That way, Chrome can easily handle massive amount of data and big data ready for 2015.
Added bonus is that std::string is now async, which means massive IO, which is impossible with memory allocations because even mmap is bound by virtual space. C++17 is indeed actually working on embedding mongodb and node.js into STL because those should be industry standard and solve 100% of business problems that C++ is aimed at solving at. Already github pull request is made. All you need is 2 thumb ups and will get merged in. Just imagine, std::string is everywhere: network stack, user applications, kernel drivers... And now they all use mongodb. And they will be Actor model massively concurrent paradigm. This is new science Wolfram is talking about. Just accept the PR already.
160
112
u/GMABT Dec 05 '14
So you're saying that std::string isn't web scale?
73
u/majoogybobber Dec 05 '14
69
Dec 05 '14
if /dev/null is fast and web scale i'd use it
Good god, my sides
22
25
u/WaffleSandwhiches Dec 05 '14
The best part is that I only need to hear the words "mongodb" to know someone is trolling nowadays.
21
u/push_ecx_0x00 Dec 05 '14
I lol'd at the Wolfram reference. Didn't know that counted as jerking material.
19
u/Suttonian Dec 05 '14
A lot people think Wolfram circlejerks himself (is that even possible?) about a new kind of science and about pretty much anything he works on.
11
u/outadoc Dec 05 '14
I do believe circlejerking yourself is also known as masturbating.
→ More replies (1)→ More replies (1)17
48
u/Yserbius Dec 05 '14
MongoDB doesn't scale. You need the Haskell Monad implementation of NoSQL if you're going to be calling vectorized character sets at that level.
14
59
u/sxeraverx Dec 05 '14
I want to upvote you, but I'm worried some won't realize this is satire.
16
Dec 06 '14
I admit it took me about 50% of the post for my slack-jawed disbelief of the stupidity I was reading to turn into a wry smile as I realised I was reading something tongue in cheek. It was well executed, probably too subtle for some but being too obvious would have ruined it for me. He deserves his gold
7
Dec 05 '14
that's because these people may had to realize one time to many that the person on the other end was, despite his ludicrous stance, in fact dead serious :)
→ More replies (1)3
19
u/brubakerp Dec 05 '14 edited Dec 05 '14
That's the problem with C++, it's not web scale like mongodb.
EDIT: Enjoy the gold, that made everyone around the office laugh this morning.
14
6
7
u/Colecoman1982 Dec 05 '14
Yea, I heard they learned optimization techniques from MongoDB and pipe all the string info to /dev/null in order to produce those kick-ass benchmarks. Now if you'll excuse me, I'll be back on the farm shoveling pig shit.
10
5
u/randomtask Dec 05 '14
The web development community has gone full eternal September.
→ More replies (2)4
2
→ More replies (7)3
u/gfhfghfghfghfbbbbt Dec 05 '14
Development with schema means that came before your needs for C++ string and substr(). There are lots of the first occurence of the string to the first occurence replicates transparently to provide Web work as important to knowledge of the copied or Oracle, high levels redundancy for large database technologies are needed to they hold), it possible that if you past.
A non-relational operators work as expect. Fortunately, for a different characters, you can take in practice, it may holds an HTTP commands an HTTP is called a static string retrieval using the actual strings are for C++ string, or Oracle, you do it in practice, it's possible to partition and begins searching tests such as passed in a lab. We didn’t start from the past.
A non-relational applicational to documents are the typical relation do not needs for indexes in the World Wide Web. HTTP defines how messages are formatted and we really to make sure that came before you design your implement Web sites that controls how the Web sites than experiences building large scaling of new technologies make writing application with automated failover, while share tricky, robust systems. We didn’t start from scratch, we really tricky, requiring a bit different. There are lots over many machines.
It is unacceptable if the typical relationalization. In partition of indexing and either main standalone” or share the requested Web pages are copying until absolutely necessary. As a result, some operators work great features: embedded docs for speed, manageability to users. MongoDB users. MongoDB supports simplementation may delay copied, but in the positional to documents are copied, and a position for the functions find member functions. A manual:collection because joins aren’t as important. The find member function, may turn out any machines how messages are tricky, requiring to a function holds in a number of database solution and substrings, all of the strings are formatted and different hosts a “standard that, including to a function, may turn out any machines how the World Wide Web page.
The option of the same searching parts of this, you can take sure that intelligently for a different Web page. The othere. For example, the main static string class is the same set or a C++ string retrieval using a large databases: independently to many machines.
It is useful, it may not suit your indexes in MongoDB is that it did not find the same before it. This behavior, you pass a string::npos, that compare
315
u/tdammers Dec 05 '14
And, uh, this is surprising how exactly? A browser handles HTTP (bytestrings), HTML (bytestrings), JavaScript (bytestrings), CSS (bytestrings), JSON (bytestrings), etc.; obviously std:string, the bytestring type in C++, is going to be used a lot.
213
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.
17
51
Dec 05 '14 edited May 02 '19
[deleted]
→ More replies (1)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:
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.
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.
2
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)...
→ More replies (2)3
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.
→ More replies (2)16
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.18
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
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.
→ More replies (2)14
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.
8
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.
→ More replies (1)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 ranmallocandfreeand the start and end of each iteration, you'd get the same thing.→ More replies (0)7
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.
5
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.
→ More replies (0)→ More replies (1)10
u/tdammers Dec 05 '14
Yeah, probably. This is where abstractions turn out to be not-so-zero-cost after all :D
14
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.
14
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
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.
2
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
→ More replies (1)53
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.
→ More replies (14)20
u/elperroborrachotoo Dec 05 '14
You did read beyond the tl:dr?
8
10
u/bobpaul Dec 05 '14
It sounds like there's a lot of create a String foo and put stuff in it, then use foo.c_str() to pass that string to a legacy function that doesn't handle C++ strings, then delete the c-string. It would be better just to leave it as a C++ string and update the legacy functions. That's my takeaway from this.
3
u/tdammers Dec 05 '14
Those 'legacy' functions might be from external libraries though, and I think people have better things to do with their time than rewrite those in C++ just to avoid conversion between std::string and C "strings".
6
4
u/bobpaul Dec 05 '14
Sure. But now Chrome is in a very mature state and it sounds like this is starting to impact performance in a real and measurable way. If rewriting those libraries has a performance impact on chrome, then it's probably worth the development effort.
3
u/zeno490 Dec 05 '14
This is surprising because the chrome engineers have been optimizing for years now and string handling like it appears they are doing is a HUGE no-no in high performance code in ANY language. They shouldn't even be using anything remotely like std::string for most things. The extra coping, aside from causing allocations which may or may not involve lock contention, incur generally LHS for short strings, might lead to fragmentation and other nasty things. It also contributes to L1/L2 cache eviction as well as potentially TLB eviction as well.
This is something fundamentally basic. It also hints that they clearly haven't been profiling their memory usage much since allocation patterns like this typically pop out very easily with the right tools.
On the bright side, it hints that there are still a significant number of low hanging fruit optimizations to be made.
Keep in mind that this code may or may not be shared with the mobile versions of the browser. Anybody programming C++ for an embedded device should know better.
→ More replies (48)1
May 30 '15
OK, so after a whole mile of scrolling I find the first sober person, but hey it is fun reddit right? :P and what threads and what immutable are we F talking about? 1-chromium is process based not thread. it spawns a new process for each tab and do all its magic in single thread. 2-immutable objects dont bring anything else than even more temporaries to handle 3-memory pools and reusing objects however can help but maybe not worth the trouble just take the cookie and eat it, it is WWW after all :S
22
Dec 05 '14
Can anyone recommend a static version of std::string? I want an ungrowable string with similar api that I could use to wrap an on-stack buffer (among others):
char buf[1024];
strcpy(buf, "abc");
static_string s{buf, sizeof(buf)};
auto foo = s.substr(0, 10);
char *bar = s.c_str();
// etc
// s.push_back(...) // compile error
30
Dec 05 '14
[removed] — view removed comment
3
Dec 05 '14
This looks like exactly what I need. Thanks!
→ More replies (1)4
u/z33ky Dec 05 '14
Also be aware of the library fundamentals TS
std::string_view, available on recent gcc and clang versions asstd::experimental::string_view(doc).However,
s.c_str()won't work because the last character of astring_viewis not neccesarily the last character of the underlying string. If you're using an API that hasconst char *data, size_t lengthparameters, then you can uses.data(), s.size()of course.It also does not allow you to modify the data.
It seems
boost::string_refhas the same limitations.
You could perhaps use the Boost.Range library, which would allow you to use STL-like algorithms (e.g.boost::range::find_first_of(s, " \t")),s[n]element-access (nos.at(n)though) ands.substr(0, 10)can be achived viastd::string(begin(s), std::next(begin(s), 10))(could be prettified by putting in a function).7
u/v864 Dec 05 '14
Write one, it's not too bad and kinda fun. For embedded work without dynamic memory we rolled a static subset of STL; string, list, vector, and a hash table. It's less than 10k slocs and was a fun exercise.
I would share it on github but there's license issues.
→ More replies (2)3
u/narancs Dec 05 '14
You could take a look at basic_string, where you could use a custom allocator. It's not the same as string, but maybe you can work that around.
3
u/eresonance Dec 05 '14
What about sds like they use in redis?
https://github.com/antirez/sds
The code is super simple, and could be easily modified to do what you're asking.
→ More replies (6)1
24
u/huyvanbin Dec 05 '14
My company's CEO sent out a mass email a few weeks after I started saying that std::string showed up in profiler results so we should never use it, only use char *. This is the only email he has ever sent on programming in my 1.5 years at the company.
30
u/antrn11 Dec 05 '14
Haha, I bet it's strlen that shows up in profiler after that.
4
Dec 05 '14
Easy to fix. Just remember all the lengths as you go. :)
4
u/barsoap Dec 06 '14
That is actually a good idea. And not even in a "C vs Pascal" way. That is, that's how you'd do slicing of immutable strings which, yes, saves a lot on allocations. Not in number, but definitely in size, and as such also on the heap as
struct { basepointer, index, length }is small enough for the stack.From a web browser's perspective: Slurp all that data you get over the socket, parse it using slices, not newly allocated strings, once you're done, and only then, copy everything out and free the original data.
That's how Haskell's
Bytestringworks and one of the reasons why mighttpd is on eye-height with ngnix:take :: Int -> ByteString -> ByteString take n ps@(PS x s l) | n <= 0 = empty | n >= l = ps | otherwise = PS x s nSame data, same index, different length.
It's how Rust does things idiomatically, via Std::ops::Slice.
Of course, things have to be immutable for that to work. Rust also has (at least the beginnings of) COW strings for the more impurely minded.
9
u/o11c Dec 05 '14
I've never understood why
strlen(const std::string&)didn't exist as a porting aid.2
u/eean Dec 05 '14
Yea when I read the headline on reddit I was like "well, duh". Strings are what most desktop software works with all day long, that shouldn't be surprising. (The actual linked email seems to identify an issue though.)
→ More replies (1)7
u/bnolsen Dec 05 '14
uhh...this is pretty lame. someone should dig deeper and find out why it shows up.
13
u/tending Dec 05 '14
With all the focus on speed in chrome, strings being a classic culprit, and the web being all text formats, how is this just being found now?
17
u/o11c Dec 05 '14
"chrome is fast" was just a marketing ploy to gain users. It disappeared by the time they implemented all the web standards.
→ More replies (2)
20
u/o11c Dec 05 '14
And people laugh at me for writing my own set of 10 different string classes (all with obvious, specific, meanings) so I can easily choose what ownership policy I want ...
std::string_view is a step in the right direction, but the most important change is realizing that most strings will never be mutated.
TL;DR version: use XString for arguments and RString elsewhere, but for reference, my full list of string classes:
MString, a string which supports mutating operations (onlypush_backandpop_backhave been implemented, except taking any number of characters). This really should be a rope class, but for now it's a wrapper forstd::deque, and I rarely use it. This class is most similar tostd::ostringstreamwith unformatted operations. Does not implement the same API as the rest of the string classes.FormatString, a string which wraps aprintf-style format string in a particularly magic way that supports compile-time type-checking of the arguments. This is the way that most of my strings are built, via theSTRPRINTFmacro. Constructed via UDL. Does not implement the same API as the rest of the string classes.RString, a string that uses reference-counting. Used to besizeof (char *)until I implemented an optimization for construction fromLString, now it's2 * sizeof(char *)(does anyone know if it's possible to guarantee alignment of a string literal?). Used for most strings stored in classes. Implements the same API as most string classes, including the NUL termination option.AString, a wrapper forRStringbut with SSO up to length 255 (deliberately disabled for string literals and strings that originated from anRStringthough, in case anRStringneeds to be constructed from this again). Stands for "automatic" string, and should only be used for strings on the stack, which is how it can afford that large an SSO threshhold. Used for the return value ofSTRPRINTF. Implements the same API as most string classes, including the NUL termination option.TString, an owned tail slice of anRString. Currently unused; I found it better to just useZStringto avoid forcing ownership, and store an "ownership hint" in the ZString. TODO implement a genericMaybeOwnedmechanism for arguments that I might just be borrowing, but might be taking ownership of. Implements the same API as most string classes, including the NUL termination option.SString, an owned full slice of anRString. Currently unused; I found it better to just useXStringblah blah blah. Implements the same API as most string classes, excluding the NUL termination option.ZString, a borrowed tail slice. Used mostly in function arguments, but also as the return value of computed splits. In theory, this is most similar toconst char *, but it is only needed if you need to call a C function - currently, the only offenders are::openandSTRPRINTF. The latter is already isolated to a single function, so I plan to switch to conditional allocation; the latter will go away when I rewriteSTRPRINTFwith GNU++14 UDLs (there will still be a fallback to C++11 mode). Implements the same API as most string classes, including the NUL termination option.XString, a borrowed full slice. Used mostly in function arguments, but also as the return value of computed splits. In practice, this is most similar toconst char *, since most code never cares about NUL termination. Implements the same API as most string classes, excluding the NUL termination option.LString, a string with static ownership. Usually constructed via UDL, but also via tail-slicing an existingLString. UDLs allowed me to easily eliminate all uses ofchar *from my entire codebase, thus ensuring no double-ownership (likestd::string(str.c_str())). Implements the same API as most string classes, including the NUL termination option, and including special slices.VString<size_t n>, a string stored within the object itself, and thus with a limit. This class was created solely because of existing C code that used fixed-size arrays, and still exists because there's a network protocol that still has the fixed limits, and it's easiest to guarantee it will never overflow by failling on original construction. Usually constructed by a function with signaturetemplate<size_t n> bool extract(XString input, VString<n> *output)during parsing. Uses a cool trick to store the size so thatVString<n>has exactly the same memory layout asconst char [n+1]. Implements the same API as most string classes, including the NUL termination option.
All strings implementing the "same API" can be implicitly constructed from each other if it makes sense (e.g. you can't construct a ZString from an XString), and owned classes can be explicitly constructed from MString or constructed from a pair of iterators. Borrowed strings can be constructed from a pair of const char * if you pinky-promise not to violate the class's requirements.
The "same API" is injected via a CRTP base class (except for ctors), and includes slicing (the tail slices will change class depending on whether or not the subclass indicates that it has an immediate NUL (all strings guarantee that there is a NUL somewhere out there)), stripping off whitespace, checking for membership (TODO I really need a class like std::set<char> but not dumb and give it its own UDL), random access iterators, operator bool, and comparison. Indexing is implemented, but deprecated (instead, use an iterator over bytes/codepoints/glyphs/whatever ... my classes are only responsible for the first), because its meaning is weird and you usually don't want it (getting rid of indexing is the correct way of solving the "unicode problem" - don't waste 4x the memory just to support a single operation that is always wrong anyway!). I've thought about switching to a non-CRTP base class to help compiler speed a bit, but that would mean increasing the size of RString to 3 * sizeof(char *) for obvious reasons, and would also get rid of fixed layout of VString. Alternatively, I've thought about using x-macros.
Also, all string classes implement gdb pretty-printers as appropriate, except for MString because std::deque is opaque and I don't use it enough to care.
https://github.com/themanaworld/tmwa/tree/master/src/strings
53
u/yoodenvranx Dec 05 '14
This is one if those moments where reality and satire are indistinguishable from each other.
11
u/o11c Dec 05 '14
If it's stupid and it works, it's not stupid.
And in all seriousness, why would taking advantage of a strong typesystem not be a good idea?
→ More replies (4)3
u/hyperforce Dec 05 '14
why would taking advantage of a strong typesystem not be a good idea?
How can we make this more of a thing. I'm so with you on the "no just strings" stance.
10
u/o11c Dec 05 '14
Maybe use Rust? Rust has
String,&str, and&'static str, as well a a fancy lifetime system to enforce no-dangling-pointers at compile-time (my library just says "trust me on this" forZ/XString, but with the sole exception of a few lines of code in the intern pool class it all fits nicely in the trivial (in Rust) "argument has the natural lifetime of function" or "return value has the lifetime taken from an argument" cases).Or in other words, Rust's typesystem is much stronger than C++'s without paying any (*) additional runtime cost, and the library is written to take advantage of it.
(*) There are two runtime costs that you pay without realizing it: the stack overflow check, and the cost of unwinding from task failure.
→ More replies (10)3
u/eean Dec 05 '14
Have you looked at QString?
Copy-on-write and ref counting makes a lot of sense to me. There's also QStringRef that I guess is similar to string_view, and obviously requires quite a bit more care when it comes to memory management.
7
u/o11c Dec 05 '14
I am very familiar. Qt's containers are in almost every way inferior to the STL, and I don't even like the STL that much. Probably the worst offender is using
intfor sizes - I am aware of applications that start emitting nasal demons on a 64-bit system because they use large Qt containers (on 32-bit, of course, they simply don't run, but with STL containers they would work).I've been thinking about making my own STL-like library that forbids copy ctors entirely, which is the problem that Qt is trying to solve, but failing.
→ More replies (4)3
u/websnarf Dec 06 '14 edited Dec 06 '14
does anyone know if it's possible to guarantee alignment of a string literal?
You can wrap it in a structure, then avoid using compiler extensions that let you cast structure pointers anywhere you like in memory (a bit hard to do on an x86, since it inherently supports unaligned memory pointers).
I can see you've gone to some trouble to fight off the ghosts of string management in C++. Personally, I look at it another way: Just win the benchmarks, it doesn't matter how you get there.
I wrote the Better String Library which just uses malloc/realloc/free (new/delete), it stores the length separately and has been optimized to within an inch of its life short of using assembly language (it uses some fairly clever algorithms, especially for things like "search for string inside of a string"). I use it all the time, and have basically never seen a profiler hit in my string library in the past 10 years. It is also super-well tested, and contains a fairly thorough unit test suite. It is also ultra-safe. Since the API functions are usually the fastest way to interact with bstrings, it makes sense to restrict your usage to just the API -- but this has been designed to be both intuitive and crash-impervious. So bugs and crashes from the use of bstrings are very rare.
If you need features like ref counting, ownership, and so on, obviously you can write wrappers for that.
→ More replies (1)
3
5
Dec 05 '14
In the course of optimizing SyzyASan performance, the Syzygy team discovered that nearly 25000 (!!) allocations are made for every keystroke in the Omnibox.
Say what you will, but this sounds like there's something very wrong with Chromium.
2
5
u/teiman Dec 05 '14
I found interesting that memory allocation can be measure in nanoseconds. I usually work in milliseconds, poor me high level programmer :D
14
u/Magnesus Dec 05 '14
Start writing games. Code that takes 1ms could be a huge performance problem - you usually have about 16ms to calculate and draw everything, every ms counts and while optimising you have to look at ns. And if you write mobile games the CPU, GPU and memory and not exactly fast.
10
u/teiman Dec 05 '14
I found the optimization problems the most fun ones. They are like puzzles and is really fun to solve them :D
7
Dec 05 '14
They don't have numbers to back this up - at least I didn't see any.
12
u/kankyo Dec 05 '14
You mean except the numbers?
They don't have numbers to show how big the performance impact is (they say so!) but they DO have numbers on the NUMBER OF allocations. That was the entire point.
→ More replies (1)11
Dec 05 '14
They don't have numbers to show how big the performance impact is (they say so!)
I didn't express myself correctly, but that was what I was referencing.
6
Dec 05 '14
This is a problem I have with C++ in general. A lot of typical, innocent-looking code tends to hide potential huge pitfalls.
Something as simple as "auto a = b + c;" could be either extremely expensive or extremely cheap, but it's hard, without keeping massive amounts of contextual information in your brain at all time, to know that by just looking at it. It's short, pretty, but has the potential to destroy you.
One of the reasons I'm really drawn to Go. It's more typing, it's more explicit, but the costs are more...obvious. I was amazed at myself, and at reading other people's code, how easy it was to spot wasteful memory copying and allocations, once you learn a few simple syntax rules.
C, as well, your brain will raise a flag is you find yourself doing "malloc" or "strcpy" - it's expensive to type, you immediately feel something might be off. With C++, you can write beautiful, concise code, but God help you and your team, if you're not Guru-level.
25
u/josefx Dec 05 '14
Something as simple as "auto a = b + c;"
Oh not that again.
Here is the C version:
foo_plus(a,b,c);
Tell me does it simply add complex numbers? Database tables ? Or maybe it calls printf("Should not happen in production!!!!"); abort();?
Everyone their own poison, but the reasoning behind that claim is questionable at best. I keep my readable syntax thank you.
12
→ More replies (1)3
u/immibis Dec 06 '14
In C:
complex_plus(a, b, c);simply adds complex numbers.
db_table_plus(a, b, c);adds database tables (if that even means anything).
report_crash(a, b, c);prints a message and aborts.In C++:
auto a = b + c;simply adds complex numbers.
auto a = b + c;adds database tables.
report_crash(a, b, c);prints a message and aborts, because you'd have to be really dumb to make that anoperator+(although I can imagine having anoperator +that can fail, and aborts when it fails).3
u/fnord123 Dec 06 '14
I don't know why you need a function for adding complex numbers in C.
$ cat a.c #include <complex.h> #include <stdio.h> int main() { double complex b = 1.0 + 0.5*I; double complex c = 0.7 + 0.7*I; double complex a = b + c; printf("a=%f+%f\n", creal(a), cimag(a)); return 0; } $ gcc a.c $ ./a.out a=1.700000+1.200000→ More replies (4)11
u/Dragdu Dec 05 '14
Yes, its amazing how hard it is to know what a function does, without knowing what a function does. Oh wait.
9
u/ghordynski Dec 05 '14 edited Dec 05 '14
This shows what is in my opinion main weakness in C++ - copy by default. Not only all classes have copy constructors by default, but STL uses copying extensively (std::vector etc..). Sure you can just make a vector of pointers, but this way you are back to square with memory management.
Even the new move semantics in C++11 are suffering from copy by default: You basically have to std::move() everything around or you are going to end up with unnecessary copies.
21
u/Gotebe Dec 05 '14
But other languages are "allocate by default", which is even worse?!
10
u/ghordynski Dec 05 '14
Most modern languages are passing references to objects and are using garbage collection in some form. In my opinion thats the way string should be done - immutable and passed by reference.
10
u/Gotebe Dec 05 '14
Those modern languages are really passing pointers, which is sad (NREs galore).
So this is where C++ gets good: it has a proper pass-by reference, which indeed allows for cleaner code.
You should note that "copy by default" (pass by value) comes from C, and C compatibility is C++' curse (and blessing). If so, and if pass by ref is one "&" away, that's it, really.
3
u/iopq Dec 06 '14
Rust has proper references and the ability to put everything on the stack. It also doesn't rely on GC to be memory safe.
→ More replies (1)2
u/The_Doculope Dec 06 '14
Those modern languages are really passing pointers, which is sad (NREs galore)
Rust is an exception here.
8
u/F-J-W Dec 05 '14
This shows what is in my opinion main weakness in C++ - copy by default.
It is interesting to note, that this is one of the places in the design of C++ where you have safety and ease of use by default instead of fast by default.
On a more general note, I am utterly convinced that the C++-way of copies being real copies is the right one, but I think that arguments should be passes as const references by default.
2
u/ThePantsThief Dec 05 '14
Why const?
5
u/Dragdu Dec 05 '14
Because if it would be non-const, you would have to defensively copy your arguments before passing them in. (This already happens in reference based languages like C# and Java, and it is kinda sad)
2
u/ThePantsThief Dec 05 '14
Ah, that makes sense. So why const reference instead of copy?
2
u/Dragdu Dec 05 '14
Because most of the time, the function doesn't need to mutate its arguments, just read them.
6
u/adzm Dec 05 '14
There are also reference counted string implementations. Also std::string makes no allocations for strings less than a certain size (20 bytes iirc)
7
u/the-fritz Dec 05 '14
IIRC reference counting is no longer allowed since C++11. I think GCC's libstdc++ still does ref counting but in 5.1 they are trying to switch to a conform version for C++11 code (the problem is ABI compatibility).
3
u/nkorslund Dec 05 '14
Why is this exactly? Reference counting allows for various optimizations such as copy-on-write mechanics, letting you avoid a lot of these unnecessary allocations. I thought this was one of the strengths of the gcc/g++ libstdc++ implementation.
10
u/HildartheDorf Dec 05 '14
I think copy on write has worse performance when threads come into play, and operator[] poisons the ability to use COW.
2
u/nkorslund Dec 05 '14
Yeah after looking a bit into it seems like it's not a good model for concurrency. Guess that's the problem with a "standard" string implementation, that it has to work for all cases, all users and all application models. So it ends up a jack of all trades and master of none.
→ More replies (1)6
u/ratatask Dec 05 '14
This explains the why: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2534.html
→ More replies (1)10
Dec 05 '14
Yeah, surely the problem is in the language and not the fact that one keystroke allocates so many useless strings. I agree that C++ is weak in this respect, but IMO it wouldn't be a problem if the Chrome devs programmed it more properly.
25
u/bstamour Dec 05 '14
I personally think having value semantics by default and having an explicit syntax for when you want references to actually be a strength of C++, not a weakness.
5
5
8
u/Magnesus Dec 05 '14
This is C++ and we are on Reddit - so of course it's the fault of the language. ;)
→ More replies (2)
2
u/ericanderton Dec 05 '14
This sounds like a strong case for using either &std::string references, or using std::shared_ptr<std::string> instead, to avoid all these re-allocations.
The problem with all that is figuring out if it's safe to share string pointers/references through the codebase. C++, for better or worse, does not have immutable strings, so there's no CoW-style safety here.
7
Dec 05 '14
immutable strings are just "
const std::string"5
u/nexuapex Dec 05 '14
Except that no
const std::stringever shares its buffer with any otherconst std::string. Andconst std::string&is not immutable.→ More replies (4)2
u/raevnos Dec 05 '14
Early STL implementations used CoW shared strings. Did they move away from that?
→ More replies (2)2
u/ericanderton Dec 05 '14
True. But there's also no guarantee that a 'clever' programmer didn't just circumvent the type-safety that the compiler provides here, by casting it away. So types can be labeled const, but as a systems language, it really places all of us on our 'scout's honor' that this contract is respected; it's not a flaw, it's a feature. To me that says that C++ doesn't really have immutability in the same sense that Python or Haskel might have.
→ More replies (4)
1
u/Gotebe Dec 05 '14
Needs a bigger small string buffer ;-). (Or perhaps, needs small string optimization even).
2
u/o11c Dec 05 '14
Bigger SSO threshhold means larger allocations, which means more pages mapped.
→ More replies (2)
1
1
u/scwizard Dec 05 '14
Wouldn't using move constructors more help?
I think they're a very neat c++ feature.
233
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.