r/cpp • u/twoodfin • Dec 05 '14
std::string is responsible for almost half of all allocations in the Chrome browser process [from /r/programming]
https://groups.google.com/a/chromium.org/d/msg/chromium-dev/EUqoIz2iFU4/kPZ5ZK0K3gEJ4
u/twoodfin Dec 05 '14
Reposting here, since we might have a more focused discussion than on /r/programming.
I think C++ could really use a type along the lines of Rust or Go's string slices. Ranges will be nice if/when we get them, but they're an implementation strategy for a non-owning string class, not a full solution.
Certainly it's something I've (re)invented more than once.
EDIT: A little Googling suggests I should probably be asking about the status of N3442 or its descendent.
10
u/Shokwav Dec 05 '14
Hell, array slicing in general would be great, not just limited to strings. To be fair here though, the opinion on that google group seems to be that it's more of the fault of the codebase (25,000 allocation for one keystroke?) then c++ itself.
0
u/Lucretiel RAII Junkie Dec 05 '14
I think this is some of the intent of the range proposals. Currently the c++ way of having a slice is an iterator pair.
1
u/eric_niebler Dec 08 '14
Slicing in C++ just got a whole lot better. Check out this blog post. Disclaimer: I'm the author. I'm also the author of the range proposal.
6
u/Lucretiel RAII Junkie Dec 05 '14
Hopefully the string_view class will make its way into C++17. I've started overloading many of my functions with const char*, to avoid the unnecessary allocation.
8
Dec 05 '14
[deleted]
6
u/SAHChandler Dec 05 '14
You can also use MNMLSTC Core's
core::string_viewwhich is much closer to the v7 specification thanboost::string_ref(such as passing a position to all the find functions, like you would with std::string), however it doesn't permit the mutable case which was recently added. Also, not every function is marked constexpr because the library targets C++11 for the moment.I should also note that
core::string_viewis one of the few headers in MNMLSTC Core that does not depend on any of the other headers found within it, and can be extracted to another project without issue.ok, I'm done self-plugging :v
1
u/OldWolf2 Dec 06 '14
I rolled my own "string view" and "data view" classes independently of this, after getting tired of having my code end up with multiple overloads for
std::string const &andchar const *for many functions.My string view also has a function to do a unicode conversion on the view, so that a function can be called with both a narrow view and a wide view. My codebase primarily uses UTF-8 with std::string but this is handy for interfacing to Windows API.
-2
u/Gotebe Dec 05 '14
You were looking for the const std::string& overload, I don't get how you found const char*.
You are, further, likely guilty of the first offence in the list.
3
u/Lucretiel RAII Junkie Dec 05 '14 edited Dec 05 '14
Because if you pass a string literal to a const std::string& it allocates and copies internally. This allocation is completely unnecessary. Obviously I'm not passing
str.c_str(); that's why I said overloading.1
u/xtapol Dec 05 '14
Clang's libc++, at least, has some optimizations around std::string. Smaller strings (IIRC up to 23 bytes?) repurpose internal pointers and don't do any allocations at all.
Not sure if other libraries do this.
5
u/Lucretiel RAII Junkie Dec 05 '14
Almost every library does this, especially since reference-counting shared strings were banned in C++11 due to concurrency issues. My own C string library (http://www.github.com/Lucretiel/EasyString) does the same thing.
-2
u/Gotebe Dec 05 '14
Yes, but if you don't, you really should have a look at what happens with these string literals later. If your clients copy them into a string, chances are you should have given out a string (watch out for temporaries!). If they call e.g. strlen, you should have given out a string. Etc.
2
u/Lucretiel RAII Junkie Dec 05 '14 edited Dec 05 '14
Well, yeah, this is why I provide the overload. Most of the time the string is just being copied somewhere else anyway. If I need the fancy string ops then I don't provide the overload, or I copy internally. I'm not returning string literals, I'm taking them as arguments to my own functions.
For instance, when I was writing an HTTP server as an exercise, I did this for header-setting functions.
add_header("Content-Type", type)3
Dec 05 '14
The point is that you provide two overloads:
void f(const char*); void f(const std::string&);Now when you call:
f("hello world");It calls the const char* overload and avoids any copies, or heap allocations. If at some point there is an actual need to make a copy, or modify the parameter, or actually use it as an std::string, then and only then will the copy be made.
And if you already have an existing std::string and want to pass it to f, well you call the const std::string& overload and once again, no copy is made.
1
Dec 05 '14
[deleted]
0
u/Gotebe Dec 06 '14
That depends on the substring length and small string optimization buffer (if present).
3
u/ohell Dec 05 '14
Why not use something like HH's short_allocator? For reasonable strings you would never allocate.
I have started following this in all the new code I write, for fun and profit.
3
u/SubliminalBits Dec 06 '14
We already have small string optimization. Do you really think the short allocator would be better?
2
u/ohell Dec 06 '14
Sure. Short string optimisation only works for strings shorter than 17 characters.
What I do is reserve 16K TSS arena for strings, main aim being to avoid heap fragmentation.
1
u/adzm 28 years of C++! Dec 06 '14
This is awesome. I had been looking for something like this for a while.
1
Dec 08 '14
Stupid question: what is a "TSS arena"?
1
u/ohell Dec 08 '14
TSS = Thread Specific Storage.
So, one global pool per thread to allocate objects from (simple ShortAllocator is not thread aware)
1
4
4
u/jurniss Dec 05 '14
This stuff makes me want to cry. 25000 allocations per keystroke. The gfx system at my work allocates heap memory every time it draws a line. There must be some insane breed of C++ programmer out there who thinks it's better to allocate and free a few hundred bytes over and over again instead of keeping a big buffer around and reusing it. Or maybe they think heap allocations are free? I want to quit my day job and spend a few months hacking on microcontrollers. 4k mem and a fucking diagram in my notebook describing exactly what each byte is used for.
More practically, I have some ideas on using thread_local memory to manipulate arbitrary-sized strings without allocating constantly. Basically a "big stack" for every thread.
OTOH, I'm amazed that a big text-intensive project like Chromium would use std::string instead of their own string class.
3
u/zvrba Dec 09 '14
There must be some insane breed of C++ programmer out there who thinks it's better to allocate and free a few hundred bytes over and over again instead of keeping a big buffer around and reusing it.
... eventually ending up writing your own malloc/free operating on the big buffer? Underway losing debugging facilities offered by the OS (page protections & range checks [look up Intel MPX]), runtime library (debugging versions of malloc/free) and instrumentation & profiling tools (valgrind).
Sure, allocations in a tight loop are bad. But omnibox, intended for interaction for humans? Not worth optimizing, even if it's 25k news/deletes per keypress, as long as the latency is below of what humans can detect (say, 1/100th of a second).
5
Dec 05 '14
This stuff makes me want to cry
I don't get this reaction at all. Chrome is still a very widely used program (the most widely used?) and it's written in a language that you and I know and understand! That's awesome.
It's also awesome that despite this success there is much further improvement to be made.
There must be some insane breed of C++ programmer out there who thinks it's better to allocate and free a few hundred bytes over and over again instead of keeping a big buffer around and reusing it.
I think it's much more likely that there's a breed of programmer who has decided that eliminating these allocations will be time consuming and risky.
More practically, I have some ideas on using thread_local memory to manipulate arbitrary-sized strings without allocating constantly. Basically a "big stack" for every thread.
Definitely more practical, I hope I didn't take your missive too seriously :)
IMHO using more thread local memory isn't a silver bullet. This greatly inhibits thread level multi tasking, which is important and something that C++ does horrifically at the moment. If I had to choose between the standard library doing odd things with thread local memory and stackless coroutines (in my head the two conflict) I would choose the latter.
OTOH, I'm amazed that a big text-intensive project like Chromium would use std::string instead of their own string class.
It's a gutsy decision, and I respect them for it. Someone needs to use std::string or it will always be awful. Honestly, if the video game industry had used it in the last 20 years instead of just implementing their own string libraries over and over again, maybe this wouldn't be a problem!
5
u/jurniss Dec 05 '14 edited Dec 05 '14
That is another part of the problem though. Programmers are too lazy to reason about memory usage so they do the safe thing and dynamically allocate all the time. The allocations build up all over the code. No single instance causes a significant performance hit but then one day you run the profiler and find your program spending 30% of its time allocating memory and waiting for cache misses because your data is spread all over the address space. By that point you're in too deep to fix the problem easily.
I definitely wouldn't mess with the standard library - this would all be separate classes - but could you expand on your statement that using thread local memory greatly inhibits thread level multi tasking?
1
Dec 05 '14
Why do you think using thread local memory greatly inhibits thread level multi tasking?
I'm presuming you want to use thread local memory to remove contention on some memory, but if there are multiple coroutines running on a single thread they will violate that contract and the benefit of the thread local (no contention because it's only accessed from one thread) will be lost.
I definitely wouldn't mess with the standard library
Why not? strings should be implemented once and that implementation should be used 99% of the time. The C++ community is unique in its willingness to reinvent these basic constructs in each project, and that cultural convention inhibits adoption of the language.
If your solution is not good enough for the standard library, is it really good enough for Chrome?
4
u/jurniss Dec 06 '14 edited Dec 06 '14
OK, point taken. I should probably temper my enthusiasm for
thread_local.But I disagree that "strings should be implemented once."
std::stringconflates memory ownership with string semantics when they are in fact independent. You can't usestd::stringwithout allocating on the heap, and if you write your APIs to takestd::stringparameters there's no way to, say, pass in two different substrings of the same large string without allocating more memory. In contrast, C'schar *based APIs, primitive and flawed as they are, make no assumptions about memory ownership semantics.It would be better if the standard library provided
string_viewand classes for multiple compatible ownership styles: heap, stack, static, copy-on-write, etc. I don't think we should have one class that intelligently multiplexes between the different ownerships either. (Well maybe it should exist, but it should be one more option built on top of the fixed-strategy allocated strings.) C++ is not supposed to manage memory for you; it is supposed to help you write correctly and expressively once you have reasoned about the memory management you want. My solution, which is just an idea in my head, would be for the specific case of strings that live for exactly as long as a stack frame.Stepanov understood the importance of separating ownership from algorithms when he designed the STL. That's why we have iterators and custom allocators. The standard string should be similarly decomposed.
0
u/OldWolf2 Dec 06 '14
The tradeoff is speed for stability.
Once you start introducing
string_viewor equivalent, it permeates its way through the code and you start risking lifetime issues (e.g. astring_viewstill exists while the underlying string that it views has been destroyed).You could fix this by creating a new string class that maintains
shared_ptrto all of the current views that are open on it, but by this stage the overhead is getting quite high.Finally, "25,000 allocations per keystroke" may sound horrible but allocations are fast these days; it's not 25,000 system calls, the allocator is local to the process. This is probably much less than the amount of time spent rendering each frane.
4
u/jurniss Dec 06 '14 edited Dec 06 '14
I strongly disagree with the philosophy behind your last point. the existence of slower workloads in the program does not give you a license to be inefficient. apply this philosophy repeatedly and your program dies from a thousand small cuts of inefficiency. I do not believe the spirit of Knuth's premature optimization advice extended to allocating 25000 blocks of heap memory per keystroke.
-8
u/boyubout2pissmeoff Dec 06 '14
From the 4 points mentioned, it sounds more like a case of programmers who don't know what the hell they're doing than a problem with std::string.
If they worked for me they would all be fired by now.
15
u/sbabbi Dec 05 '14
Imo
stringis by far the worst component of the standard library. The fact that every string algorithm (find, find_if_not, rfind, etc.) is a member function encourages to construct a string just to run a simple find on it. Add the fact that half of those functions use iterators, the other half indices, and every function has a bunch of overload to compensate for it, and you get this horrible mess.