15 ms·

Std::string half of all allocations in the Chrome browser process

170 points by mlrtime 12y ago

acqq 12y ago
I'm old enough that I actually programmed in Turbo Pascal 3 (around 1985) which of course produced quite fast code even for the speeds of the processors then (4 MHz processors were enough for everybody, not really, but that's what we had!). That Turbo Pascal had strings that were of the limited size, but they were able to use the stack, not the heap. I still don't understand that the library string in C++ can't use the heap instead of the stack even for the small strings. Most of the allocations detected in the post are actually the short-time ones, and I'm also quite sure that most of the strings aren't too big, which means that using the strings in the Turbo Pascal style (on the stack for the local variable) would remove the need for most of the allocations. I guess that will maybe come in 2020 in C++ standard, if anybody of the people who would need that reads this and works hard. Yay for the march of progress.
- simias 12y ago
  The C++ string library cannot bind the string to the stack frame since it doesn't know how long it's going to live. I suppose the compiler might realize that however and replace dynamic allocation by a static one but I'm not sure it's allowed to do that.
  - acqq 12y ago
    I believe it would be possible to add the functionality I describe to the language if the wish of those involved existed. Even if that would mean not calling it std::string to avoid breaking the existing programs. I don't know of any current compiler that doesn't use heap when the object is made to actually call malloc (which is typically what the "new" eventually calls).
    - tonyedgecombe 12y ago
      You could just use std::array<char, 255>
      - acqq 12y ago
        Do I have all the string functionality, nicely existing in std::string?
  - repsilat 12y ago
    > The C++ string library cannot bind the string to the stack frame since it doesn't know how long it's going to live. Surely some kind of string that lives on the stack can have its storage on the stack because the storage goes out of scope exactly when the object does. I think the only place you might run into trouble is if you try to `move` a stack-allocated string somewhere, because it'll invariably result in a copy.
    - simias 12y ago
      Without any compiler magic involved I don't think it's possible to implement that in C++ in a way compatible with the current std::string interface. The problem is not the allocation of the std::string object itself, it's the allocation of the underlying buffer containing the string. std::string has a static size, the buffer itself is dynamically sized. You could replace the heap alloc with something like calloc (or dynamically sized arrays) in the constructor but then the buffer would be tied to the stack frame of the constructor, not the calling scope (so the memory would become invalid as soon as the constructor returns). Unless I'm missing something completely obvious the only way to implement that would be to ask for the caller to provide the buffer and let the string take ownership of it. It's definitely possible but it's not how std::string works and it's arguably more error-prone since unlike languages like rust there's no full blown lifetime checker in C++, so you'd have to make sure that the string object never outlives the supplied buffer. Alternatively you might be able to supply a custom allocator to std::strings but here be dragons.
      - repsilat 12y ago
        > std::string has a static size, the buffer itself is dynamically sized Yeah, I guess if you're happy with the stack-allocated buffer being sized at compile-time (either switching or overflowing into heap-allocated storage if it gets too big) this all becomes very straightforward. If you want the stack storage to be runtime-sized (or resizeable) then I agree it's going to be a real pain in the neck. It doesn't fit into the C++ programming model cleanly at all. A pity.
    - Someone 12y ago
      If it only used for small strings, that copy would be cheap. It reads a small amount of contiguous memory. Ironically, Google seems to have done something along this way. See http://stackoverflow.com/questions/354442/looking-for-c-stl-like-vector-class-but-using-stack-storage/354481#354481 http://stackoverflow.com/questions/354442/looking-for-c-stl-..., which links to https://code.google.com/p/chrome-browser/source/browse/trunk/src/base/stack_container.h https://code.google.com/p/chrome-browser/source/browse/trunk.... Many projects also have specialized string classes for the 'small string' case. See for example http://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallstring-h http://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallst....
  - pmr_ 12y ago
    That is the kind of magic thinking of C++ programmers sometimes exhibit that drives me insane. Yes, compilers have become excellent at optimizing code, but they aren't magical. The generated code will have some semblance to the code we write. Eliding dynamic allocations is just not possible statically. Heck, we aren't even able to emit warnings for missing deallocations reliably and have to use run-time instrumentation for it. Even in C++ or C, even with good compilers, we still have to go the extra mile if we want fast code.
    - twoodfin 12y ago
      That is the kind of magic thinking of C++ programmers sometimes exhibit that drives me insane. I dunno. I've run into too many programmers on the other end of the spectrum. They're reluctant to take advantage of the genuinely zero-cost abstractions that today's excellent optimizing compilers for C++ enable. I can't find the reference now, but I thought I had seen some discussions at one of the ISO C++ meetings (from Google?) about potential standards changes to allow allocations to be elided when they're limited to some known scope.
      - mappu 12y ago
        Devirtualization for example.
      - vardump 12y ago
        > I dunno. I've run into too many programmers on the other end of the spectrum. They're reluctant to take advantage of the genuinely zero-cost abstractions that today's excellent optimizing compilers for C++ enable. Performance wise it might give a false impression of being zero-cost if you micro-benchmark or are very selective what you consider as a cost. Handy for developer effort wise, sure. Yes, it's often cheap or even 'zero-cost'. But you can't assume that to be always the case. In an actual system it might be not so zero-cost when there are multiple concrete instances of generated code of the template. Each consume require actual generated machine code. Larger code size can have a significant performance cost. TLB and L1C cache misses are far from free. Neither is loading the larger executable for short life time processes. Extra page fault, caused by larger memory requirements, that goes all the way to disk is also rather expensive. The whole picture is simply way too complicated to make blanket statements like that.
  - MichaelGG 12y ago
    Interestingly, with Rust, the borrow checker makes it statically safe to know when you can stack alloc.
    - _delirium 12y ago
      You can also do it in a more limited set of cases in other languages using escape analysis. You can't provide it in all cases, but in a subset of cases you can show that the allocation never escapes a certain stack context, and therefore it's safe to stack-allocate. I believe the JVM does that in many cases.
      - MichaelGG 12y ago
        Yeah, I wish .NET would do that. Just calling, say, String.Split is gonna involve at least two allocations. At high performance levels, a single allocation per piece of work can be noticeable. And fixing it is difficult. You can actually manually allocate managed objects on the stack, but that's pretty hadn't hacky, unsafe, and doesn't help fix functions you call.
      - Dewie 12y ago
        > You can't provide it in all cases, I'm curious how reliable it is. It seems simple, intuitively, but Java (the JVM?) seems to have a reputation of being sub-par in this respect. Maybe it has to do with knowing how the the variables that are sent to other methods are used; if it only has local knowledge (the method that the object is created in), then I guess it has to be pessimistic with regards to all objects that are used as a parameter in method calls in that method.
        jerven 12y ago
        Depends on which one, the Escape Analysis in java7 Hotspot is quite conservative. The one in Graal is very aggressive https://wiki.openjdk.java.net/display/Graal/Graal+Partial+Escape+Analysis https://wiki.openjdk.java.net/display/Graal/Graal+Partial+Es.... Not sure what other VMs do.
  - ninkendo 12y ago
    > The C++ string library cannot bind the string to the stack frame since it doesn't know how long it's going to live. Huh? If course it could, unless I'm not understanding you correctly. A class like: class smallstr { char stack_str[128]; char* heap_ptr; } can easily (with enough logic in the public methods) store small strings in `stack_str` and once it grows larger, allocate some space on the heap, make `heap_ptr` point to it, and copy it over. "since it doesn't know how long it's going to live" doesn't make any sense to me. A caller would just say: { smallstr s("foo"); // do stuff } // stack_str[] is wiped clean with the stack, and a destructor would be implemented to `delete` heap_ptr if it was used. I'm not sure what you're even driving at.
    - simias 12y ago
      Well, you have to take the context of our discussion in consideration, I meant that you couldn't dynamically elect to allocate your buffer on the stack instead of the heap at runtime in the constructor. Your solution just allocates a 128B buffer on the stack for all strings which may or may not end up being used. That makes your string object 128B larger in all situations. Since we were talking about std::string, I'm pretty sure many people wouldn't be happy if sizeof(std::string) suddenly took 128B (g++'s sizeof(std::string) is 8B on my system). What I had in mind was stuff like alloca and other local scope allocation techniques that would get tied to the constructor stack frame not the caller's.
      - SamReidHughes 12y ago
        g++'s sizeof(std::string) is only 8 bytes because it's a single pointer such that the struct can be reinterpret_casted to a const char * and you get the same thing that c_str() gives you. It's reference-counted (across threads!), copy-on-write. I don't think people would mind a 24-byte std::string (on 64-bit systems), which would consist of a pointer, size, and capacity, and which would allow 22-byte strings to be stored inline. On Windows, sizeof(std::string) is 24 or 32 depending on 32- or 64-bit. sizeof(vector<char>) is 12 and 24, respectively, of course. I believe the extra size of the std::string is for storing strings inline. I'd guess their implementation looks like struct { char *ptr; size_t size; union { size_t capacity; char buf[16]; } u; };, which sacrifices some size in favor of keeping the code paths simple.
- barrkel 12y ago
  C++'s std::string could store the first few characters inline, and only fall back to heap storage if the string is too big. I'd be surprised if some implementations don't do this already. TurboPascal's strings had a number of quirks. Maximum length was limited to 255 characters, but different string variables could declare different lengths in their types. Writing string functions that could work with any string required using the OpenString type[1], which passed the string by reference instead of by value, with pseudo-const semantics (the parameter couldn't be passed as a var parameter elsewhere). Using the default String type meant allocating 256 bytes for every string variable. You'd want to pass it by reference (with 'var', and later using 'const') to avoid the extra copying. {$P+} in later versions made string-typed parameters openstring by default[2]. [1] http://putka.upm.si/langref/turboPascal/0109.html http://putka.upm.si/langref/turboPascal/0109.html [2] http://putka.upm.si/langref/turboPascal/047E.html http://putka.upm.si/langref/turboPascal/047E.html (I implemented the migration from AnsiString to WideString in the Delphi compiler when I worked for Borland. I know far too much about Pascal and Delphi strings.)
  - jbandela1 12y ago
    Some implementations already do such as * Clang LibC++ see http://stackoverflow.com/questions/21694302/what-are-the-mechanics-of-short-string-optimization-in-libc http://stackoverflow.com/questions/21694302/what-are-the-mec... * MSVC - see comments http://channel9.msdn.com/Series/C9-Lectures-Stephan-T-Lavavej-Core-C-/Stephan-T-Lavavej-Core-C-9-of-n http://channel9.msdn.com/Series/C9-Lectures-Stephan-T-Lavave...
  - maxs 12y ago
    It's called the short string optimization. It was used once but I am not sure if it is any more. C++11 move semantics may help a lot with string churning...
    - bodyfour 12y ago
      As others have mentioned some libraries do use it. It has tradeoffs though. In a "traditional" implementation sizeof(std::string)==sizeof(char * ) -- it keeps a pointer to the first byte of the text with the metadata (minimally: size and capacity) stored before it in memory. c_str() is just a "return p_;" and size() is something like "return reinterpret_cast<const size_t * >(p_)[-1];" Now to add the short-string optimization you need to do one of two things: 1. Add a small buffer we can point "p_" to inside the std::string itself. However, strings are very common inside of structures so this will bloat objects throughout your program 2. If you're clever you can use the lowest bit of the pointer to indicate that it's an interned string which would let you store 6 byte strings inside the pointer itself on a 64-bit machine (remember you still need the '\0' for c_str()'s benefit) However now c_str(), size(), etc all need an extra branch instruction. These are normally inlined methods, so now you've bloated/slowed the code instead. Personally I prefer a keep-it-simple string implementation for most things.
- hannibalhorn 12y ago
  You can specify the allocator to use with basic_string, and stack based allocators are possible. I've certainly used them with STL containers. It's just not the default.
- CrimsonVoid 12y ago
  C++ libraries can optimize smaller strings and store them on the stack. It's commonly known as short string optimization. I'm not sure how many libraries actually use SSO, but I think the three major vendors use something similar. https://stackoverflow.com/questions/10315041/meaning-of-acronym-sso-in-the-context-of-stdstring/10319672 https://stackoverflow.com/questions/10315041/meaning-of-acro... https://stackoverflow.com/questions/21694302/what-are-the-mechanics-of-short-string-optimization-in-libc https://stackoverflow.com/questions/21694302/what-are-the-me...
ajuc 12y ago
I've worked on a project that used all of these: std::string, QString, OString, char*. All were required by a different library that we needed. This is why a good string type should be in core language.
- raverbashing 12y ago
  This is the problem with C++ (and in a certain part, with C) "Everybody" has their own C++ string (MFC, QT, several libraries, heck, even GObject library has their strings) Same with C Now, you won't see anybody reimplementing strings in Java. C#, Python, JS, etc Lessons learned, their strings work std:string is certainly a step forward and should be used for most projects today
  - csl 12y ago
    I guess the underlying problem is that C++ doesn't have a standardized ABI. So you get things like QStrings, etc.
    - pjmlp 12y ago
      It is a standardization problem. When C++ got introduced, it used only C standard library, so everyone wrote their own library. C++ was already 10 years old when C++98 was a thing and compilers still needed to catch up. You don't re-write old code just because, so this cruft shows everywhere.
    - ajuc 12y ago
      It's not a matter of ABI. Even source code level compatibility would solve most of the problems. I am happy to recompile as long as I don't need to convert on every api boundary.
  - pjmlp 12y ago
    > Lessons learned, their strings work It is worse than that, because the other alternative systems programming languages that eventually lost to C and C++ also had their string type. Just C did not, and C++ followed along due to its compatibility story.
ExpiredLink 12y ago
During the 10 years I used C++ I never saw a project that used std::string as their standard string. The implementation of std::string not standardized. It may or may not have a 'small string optimization' which may not be an optimization at all. Instead of specifying a mundane immutable built-in string like in Java the C++ Standards committee decided to add even more 'advanced' features to an already overloaded language.
- richardwhiuk 12y ago
  Heh, as if Java's string was mundane, or even particularly well standardised. The implementation for String have varied in each of the JVM versions, and Android has a different version to the JDK. Java's string, depending on the string, length, JVM version and a bunch of other factors may or may not: - Be interned - so the result of "str1" == "str1" is compiler dependant (you must do "str1".equals("str1")). - Maintain references to the string when doing a substring - e.g. "Java is a language full of quirks......".substring(0,4) may or may not hold a reference to the entire string. This has huge performance tradeoffs - e.g. if you parse JSON by doing .substring(), and aren't careful, then you can end up holding onto the entire unparsed JSON, even if you only keep track of a single obejct.
  - kjetil 12y ago
    Are you seriously suggesting that String incompatibilites are a big issues in Java? String interning is specified in the JLS: http://docs.oracle.com/javase/specs/jls/se8/html/jls-3.html#jls-3.10.5 http://docs.oracle.com/javase/specs/jls/se8/html/jls-3.html#... As far as I can tell, the substring "feature" has been there since Java 1.0 and was fixed in Java 7. Hardly groundbreaking stuff.
- csl 12y ago
  The interface and behavior of std::string is standardized. Library writers are free to implement it in any way that honors the standard. However, sometimes the requirements may lead to less than optimal implementations, I believe. So as long as Chrome uses std::string for internal use only, there shouldn't be any problems. Using them across ABI boundaries, however, is another story.
vegancap 12y ago
I literally started programming in C++ this week and I figured the over-use of std::string couldn't be a good thing hehe
- csl 12y ago
  It always depends on your needs. Before you start avoiding std::string, note that the article said that one of the problems was that they went from std::string to C-strings and then allocated a new std::string. This often happens when you use both kind of strings in your code. The takeaway is to stick either to C strings or use std::strings with reference passing, dropping down to c_str() when needed.
  - vegancap 12y ago
    Thanks, that was a lot more helpful response :) I think the most confused I've been so far (coming from a PHP background) was all the different types of strings!
- w8rbt 12y ago
  std::string solves more problems than it creates. Use it.
  - zl4000 12y ago
    Definitely, and where `std::string`'s interface is not enough, use thrid party libs which work on std::strings, like boost string algoriths, std regex, or uftcpp.
- pjmlp 12y ago
  Well, you could just use char* and produce security exploits everywhere.
- zl4000 12y ago
  No that's BS. `std::string` should be used where ever it is applicable. The whole issue that this post about chrome was talking about was dealing with a poor usage of `std::string`, such as passing c_str() to then go and construct another string instead of passing by const ref. Or building a set of `std::string` to simply check if a value exists. That's just shit code, not an issue with `std::string`.
ctur 12y ago
folly::fbstring, a drop-in replacement for std::string, is part of the folly library that we (Facebook) open sourced a while back. It allocates small strings in-line and larger strings on the heap and has optimizations for medium and large strings, too. It's proven quite effective for us, particularly when used with jemalloc, which it conspires with for more optimal memory management. We use it as std::string for our C++ applications and libraries, completely replacing std::string both for our own code and third-party code. https://github.com/facebook/folly/blob/master/folly/docs/FBString.md https://github.com/facebook/folly/blob/master/folly/docs/FBS... In addition, it is worth noting folly::StringPiece (from folly/Range.h), which is generally a better interface for working with in-memory ranges of bytes. Hardly a new idea (it's inspired by similar libraries, such as in re2), but it permeates the APIs of many of our larger C++ systems, and folly itself, and often avoids passing std::string objects around at all. Finally, there is also folly::fbvector, which offers similar improvements over std::vector.
- raverbashing 12y ago
  Yeah, and if I want to use it I need to replace std::string all around my code. I can't use it for other libraries, unless I replace and recompile them. And tomorrow a new library comes I need to replace everything again. Your effort is commendable, and I know squeezing gains are important in the case of fb, but in the end it's just locking yourself in a library that should've been a second though/built in.
  - Cthulhu_ 12y ago
    1. Find / replace, I'm sure the API is simple enough and performance gains are worth the effort. 3. You don't need to replace anything, ever - only if you feel like your string performance is lacking, and that particular new library satisfies your needs (in terms of effort vs performance gains). I don't get why people believe that whenever something new comes out they have to switch over, and as a result are terrified of innovation. 4. I disagree with the "should've been built in" statement; the default std::string implementation is good enough for most (like any std:: thing). Besides, std:string was designed 25+ years ago, over a dozen CPU generations ago; the demands of today are must different.
ryandrake 12y ago
If you dig deeper and actually look at the source diffs, you will see that this is not about std::string being "bad" (it's not), but it's about problems with how they're using std::string. Most of the trouble was constantly converting back and forth between std::string and const char*, which needlessly produces temporary allocations. Simply moving to passing everything around as const references should help enormously with memory churn. EDIT: Spelling :)
- MichaelCrawford 12y ago
  I beat the subject of data representation completely to death in my article "Pointers, References and Values" at: http://www.warplife.com/tips/code/c++/memory-management/parameters/ http://www.warplife.com/tips/code/c++/memory-management/para... One of the worst performance problems in C++ is quite commonly the creation of invisible temporaries. Sometimes they are necessary but commonly they are not. There are specific cases where it's better to pass a value rather than a reference, for example if you have an integer in a register, and your parameter passing conventions calls for passing parameters in registers, then passing that integer as a value, rather than a reference (const or otherwise) avoids the use of memory; it also avoids the use of the memory cache, which is likely to be a more serious problem. In general, for a C++ program to make lots of allocations of just one class isn't such a bad thing. If your default implementation is slower than you like, you might be able to speed things up considerably, as well as save memory, reduce disk paging and so on by using a custom memory allocator just for that class.
TazeTSchnitzel 12y ago
One thing I've learned from PHP's internals is that using reference-counted strings and copying on write is a fantastic idea. You can save an awful lot of memory and allocations, and simplify your code.
- zl4000 12y ago
  Copy on write is not at all helpful in a language like C++ where concurrency can be concerned.
  - TazeTSchnitzel 12y ago
    ...how so?
    - bodyfour 12y ago
      If you have a single-threaded runtime then reference counts are cheap and easy. Once you need to support multithreading you need to use CPU atomic instructions to maintain the reference count safely. As the number of CPU cores increases the relative cost of this operation goes up. COW strings were a very common optimization when 1-2 CPUs were standard. That's why it's there in GNU's libstdc++ for example. On a modern server with 24 cores it's pretty dubious. It'd only make sense if you were copying (and then not mutating) a lot of your strings.
- adamtj 12y ago
  Reference counted copy-on-write strings are little landmines just waiting to blow your leg off should you venture into multi-threaded territory. If you use copies of such a string in multiple different threads, you may find that simply creating a new copy of the original string or any of its subsequent copies can cause an incorrect reference count which will trigger a double-free and a segfault at some later time, possibly long after all non-main threads have ended. You can't even lock all accesses to a string with a simple mutex. You have to also lock all descendant and ancestor copies, including all temporary copies, as when passing by value to a function. A COW string is basically a pointer to an internal shared data structure. You need to lock accesses to the shared structure, not the pointers to it, and you can only do that internally. The only way to reliably use such a string with multiple threads is to make the internal reference count and buffer manipulations thread-safe. It may save you some allocations and copies, but the thread safety will slow things down. How much, I don't know. I wouldn't be surprised if thread-safe copy-on-write is slower than copy-always.
DanielBMarkham 12y ago
One of the recurring things I see in programming literature for the last 20 years or more is performance hits when using string. I've seen essays on this in at least four different programming languages. You'd think it'd be simple, but it's not. String is an allocated buffer of unknown final size, and since it represents some kind of meaning in a human language, and since human languages have indeterminate length for conveying any one concept, concatentation is extremely common. This is actually one of those cases where I like c better, warts and all. Whenever you use a string, you should carefully think about what you're going to do with it, and if at all possible allocate all you need up front. Beats the heck out of taking an unexpected GC call somewhere later when you weren't expeccting it.
- zl4000 12y ago
  > Beats the heck out of taking an unexpected GC call somewhere later when you weren't expeccting it. How is that an issue with c++ `std::string`
humanrebar 12y ago
The problem with std::string is that it's named wrong. It should be called std::string_buffer, because that is what it is. Its performance characteristics are closer to a std::vector than a std::array (now available since C++11). Many projects cannot copy around std::vector<char> in good conscience. They really want a copy-on-write string, an immutable string, a rope, a reference-counted string, or an always-in-place string. Or some combination of the above depending on the circumstance. The problem is that std::string is not a good type to use as a parameter for various reasons. In addition to its aggressive allocation behavior, it's also fairly inflexible. What are the alternatives? 1. boost::string_ref - available now, so use it 2. std::string_view - available starting in C++14 and works roughly like boost::string_ref 3. pass around pairs of iterators instead of single objects 3) is actually the most flexible, though it requires different kinds of overhead. The most obvious way would be to template all your string-accepting functions on two parameters: the type of your begin iterator and the type of your end iterator. But the benefit is that you can pass around any of the above to your heart's content, plus more, like elements in tries. std::string still has an important place, but it should generally be used as a private member variable, not as something you require in your interface. Pretty much the same thing goes for char* unless you are implementing a C ABI (plus a size, please). Even then, you can immediately convert to/from a boost::string_ref and still have yourself a self-contained reference to a bounded character sequence.
- rwmj 12y ago
  Or proper garbage collection so you don't need to worry about who owns the string and you don't have the big overhead of ref-counting. Why on earth are they using C++ for a web browser anyway? That's about the worst possible choice of programming language for that problem domain.
  - IvyMike 12y ago
    So which web browsers are not written in C++?
    - rwmj 12y ago
hesdeadjim 12y ago
It's always driven me nuts that the base string in the STL is a fully mutable container that must manage it's own memory. I much prefer a string being either immutable, or an interface that you can implement however you see fit: a view over a raw buffer, a ref to a globally shared string instance that may or may not be ref counted, or like the STL, a version that self-manages its own memory. Besides boost::string_ref, there is also a more generic flyweight implementation requiring only an equality concept for it's template parameter: http://www.boost.org/doc/libs/1_56_0/libs/flyweight/doc/tutorial/ http://www.boost.org/doc/libs/1_56_0/libs/flyweight/doc/tuto...
ceejayoz 12y ago
I sure as hell believe it. I'm on an older, slightly creaky Macbook Pro, and typing in Chrome's box is frequently a nightmare if I'm running something like a VM. Keystrokes lag tremendously.
- themoonbus 12y ago
  Same situation here... I have to clear my browser history every couple of months in order for it to perform adequately.
  - gongar 12y ago
    Yeah, same here. I've to clear history like every few weeks. Else it lags so badly.
    - deleted 12y ago
      [deleted]
CyberDildonics 12y ago
I'm not even sure if I do stuff like this in prototypes. My experience has been that using a matrix/arena/pool can speed a program up that has inner loop allocations by x7. I think the average pc can do about 10,000,000 heap allocations per second, but as far as I know it causes thread locking to some degree. Don't many std::string implementations have small string optimizations? This is actually the first time I have every heard of C++ strings being the bottleneck of an application (and it seems that is even still up for debate here).
- paulhodge 12y ago
  If you're interested in this topic then you should read the whole discussion in the link. There is a lot of talk about what optimizations are in play.
DigitalSea 12y ago
It all makes sense now. For some reason on my gaming PC which is pretty spec'd out in almost every way, Chrome will lag when typing into the Omnibox and requires me to close it completely and reopen it frequently. For a while I thought perhaps I had an issue with my CPU getting too hot, a bad plugin or faulty RAM, but this exact issue appears to be the cause of all of my problems. The only thing that seems to fix the issue temporarily is clearing out my browsing history every few weeks, otherwise the issue gets to the point where you can wait a couple of seconds for a word you have typed to appear. Don't get me started on the performance of using Chrome inside of a VM, that is a whole other world of hurt right there.
- dwild 12y ago
  On my Asus Transformer Book t100, that I use for all my personal stuff, I never have any issue with lag. In some rare case it can lag but it's temporary and then it's fast again. If your history is pretty big and it's all stored on a slow HDD, I can see how your IO could be the bottleneck.
  - DigitalSea 12y ago
    I am a front-end developer, so my history grows a lot every single day. After a few weeks, my history is a culmination of documentation links, testing links, StackOverflow posts and more. I actually did some testing a little while ago and could see the bottleneck taking place. My CPU usage would spike up to 100% whenever I would type something into the Omnibox when I had a few weeks worth of history. I spotted this on a clean install of Chrome, I signed into my Google account, but disabled all plugins and it still occurred. Weirdly enough, not everyone seems to experience this issue.
    - groby_b 12y ago
      If you feel comfortable sharing your history, filing a bug on crbug.com with this info might help out the Chromium devs. (Don't share it right away - ask to have the bug closed to public view before you share)
- 12y ago
jamesu 12y ago
In a certain 3d game engine we use, the devs decided to refactor a lot of old code in the animation code which used a hashed string type to use their new all-in-one reference counted String type instead. Safe to say this turned out to be a disaster for performance since every time an animation or not had to be evaluated from a name (which we ended up doing a lot), a string had to be allocated on the heap. Some people sadly underestimate how bad objects which rely on heap allocation can be in performance-critical code.
GregBuchholz 12y ago
Well, it is a good thing they wrote it in such a high-performance language then...
amaks 12y ago
There are many things in the standard C++ library which are named incorrectly (std::string), awkwardly (std::unordered_map) and and implemented inefficiently from the perspective of modern CPUs (same std::unordered_map, which uses linked list for the underlying hash table buckets). See the great talk on CppCon 2014 about those issues - https://www.youtube.com/watch?v=fHNmRkzxHWs https://www.youtube.com/watch?v=fHNmRkzxHWs.
userbinator 12y ago
25000 (!!) allocations are made for every keystroke in the Omnibox. The Omnibox is no doubt far more complex than simple text box since entering characters into it can invoke things like network connections (for search suggestions), but 25k allocs is still a bit on the excessive side. Strings are an interesting case in that in general they are of indeterminate (and variable) length, which makes them somewhat difficult to accommodate in computer memory which is finite and allocated in fixed-length pieces. Abstractions like std::string have been created to make it simpler and easier to perform operations like appending, resizing, copying, and concenating, but I think this is part of the problem: by making these operations so easy and simple for the programmer, they're more inclined to overuse them instead of asking questions like "do I really need to create a copy just to modify one character? do I really need to append to this string? how long can it be?" Essentially, the abstraction encourages ignorance of the real nature of the actual operations, leading to more inefficient code. It only helps the programmer to perform these tedious operations more easily, and doesn't help at all with the decision of whether such tedious operations should be needed at all, which I think is more important; the first question when designing shouldn't be "what abstractions should I use to do X?", but "do I really need to do X, or is there are simpler way that doesn't need to?" The most efficient way to do something is to not do it at all. Contrast this with a language like C, in which string operations are (unless the programmer writes or uses a library) far more explicit, and the programmer can be more aware of what his/her code is actually doing. That's why I believe every programmer who has to deal with strings should have at one point been exposed to implementing a resizable string buffer and/or length-delimited string library, to see the real nature of the problem (including how to do length management correctly.) Without this basic, low-level understanding of how to use memory, the advantages of all the other fancy string abstractions won't make much sense either.
- humanrebar 12y ago
  > Contrast this with a language like C, in which string operations are (unless the programmer writes or uses a library) far more explicit String operations are more explicit. Mostly. But some things (like sharing between threads, type conversion, and memory ownership) are very implicit and unsafe. Some of the implicitness to C programmers is so familiar that they don't notice it: /* 1. This function returns an error code * and not a size * 2. zero is success, nonzero is an error */ int /* 3. this method belongs in mylib * 4. this function supports ASCII??? * 5. this function allows memory to overlap? */ mylib_copy_first_n( /* 6. *out_s is allocated * 7. *out_s is greater than n bytes in size * 8. out_s will hold a null terminated string */ char const * out_s, /* 9. in_s is allocated * 10. *in_s holds at least n characters * 11. it's not a big deal if in_s has null characters */ char const * in_s, /* 10. n is not negative * 11. if n is zero, something sane will happen */ int n); I wouldn't hold up C as an example of explicitness. Now, this isn't a great example of C code, but even in the best examples of C code, there is a lot of correctness by convention and documentation. To be fair, I'm not aware of any languages and libraries that are fully explicit in type, behavior, and memory usage. Maybe Ada or one of the functional languages get it right. But there are a set of C++ tools that can make this sort of thing fast and correct. That's why it's disappointing that std::string isn't fast and is only mostly correct.
wfunction 12y ago
Why in the world are they even using c_str so often in the first place? That makes me worry more about security holes than performance...

170 points by mlrtime 12y ago

acqq 12y ago

I'm old enough that I actually programmed in Turbo Pascal 3 (around 1985) which of course produced quite fast code even for the speeds of the processors then (4 MHz processors were enough for everybody, not really, but that's what we had!). That Turbo Pascal had strings that were of the limited size, but they were able to use the stack, not the heap. I still don't understand that the library string in C++ can't use the heap instead of the stack even for the small strings. Most of the allocations detected in the post are actually the short-time ones, and I'm also quite sure that most of the strings aren't too big, which means that using the strings in the Turbo Pascal style (on the stack for the local variable) would remove the need for most of the allocations. I guess that will maybe come in 2020 in C++ standard, if anybody of the people who would need that reads this and works hard. Yay for the march of progress.

simias 12y ago
The C++ string library cannot bind the string to the stack frame since it doesn't know how long it's going to live. I suppose the compiler might realize that however and replace dynamic allocation by a static one but I'm not sure it's allowed to do that.
- acqq 12y ago
  I believe it would be possible to add the functionality I describe to the language if the wish of those involved existed. Even if that would mean not calling it std::string to avoid breaking the existing programs. I don't know of any current compiler that doesn't use heap when the object is made to actually call malloc (which is typically what the "new" eventually calls).
  - tonyedgecombe 12y ago
    You could just use std::array<char, 255>
    - acqq 12y ago
      Do I have all the string functionality, nicely existing in std::string?
- repsilat 12y ago
  > The C++ string library cannot bind the string to the stack frame since it doesn't know how long it's going to live. Surely some kind of string that lives on the stack can have its storage on the stack because the storage goes out of scope exactly when the object does. I think the only place you might run into trouble is if you try to `move` a stack-allocated string somewhere, because it'll invariably result in a copy.
  - simias 12y ago
    Without any compiler magic involved I don't think it's possible to implement that in C++ in a way compatible with the current std::string interface. The problem is not the allocation of the std::string object itself, it's the allocation of the underlying buffer containing the string. std::string has a static size, the buffer itself is dynamically sized. You could replace the heap alloc with something like calloc (or dynamically sized arrays) in the constructor but then the buffer would be tied to the stack frame of the constructor, not the calling scope (so the memory would become invalid as soon as the constructor returns). Unless I'm missing something completely obvious the only way to implement that would be to ask for the caller to provide the buffer and let the string take ownership of it. It's definitely possible but it's not how std::string works and it's arguably more error-prone since unlike languages like rust there's no full blown lifetime checker in C++, so you'd have to make sure that the string object never outlives the supplied buffer. Alternatively you might be able to supply a custom allocator to std::strings but here be dragons.
    - repsilat 12y ago
      > std::string has a static size, the buffer itself is dynamically sized Yeah, I guess if you're happy with the stack-allocated buffer being sized at compile-time (either switching or overflowing into heap-allocated storage if it gets too big) this all becomes very straightforward. If you want the stack storage to be runtime-sized (or resizeable) then I agree it's going to be a real pain in the neck. It doesn't fit into the C++ programming model cleanly at all. A pity.
  - Someone 12y ago
    If it only used for small strings, that copy would be cheap. It reads a small amount of contiguous memory. Ironically, Google seems to have done something along this way. See http://stackoverflow.com/questions/354442/looking-for-c-stl-like-vector-class-but-using-stack-storage/354481#354481 http://stackoverflow.com/questions/354442/looking-for-c-stl-..., which links to https://code.google.com/p/chrome-browser/source/browse/trunk/src/base/stack_container.h https://code.google.com/p/chrome-browser/source/browse/trunk.... Many projects also have specialized string classes for the 'small string' case. See for example http://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallstring-h http://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallst....
- pmr_ 12y ago
  That is the kind of magic thinking of C++ programmers sometimes exhibit that drives me insane. Yes, compilers have become excellent at optimizing code, but they aren't magical. The generated code will have some semblance to the code we write. Eliding dynamic allocations is just not possible statically. Heck, we aren't even able to emit warnings for missing deallocations reliably and have to use run-time instrumentation for it. Even in C++ or C, even with good compilers, we still have to go the extra mile if we want fast code.
  - twoodfin 12y ago
    That is the kind of magic thinking of C++ programmers sometimes exhibit that drives me insane. I dunno. I've run into too many programmers on the other end of the spectrum. They're reluctant to take advantage of the genuinely zero-cost abstractions that today's excellent optimizing compilers for C++ enable. I can't find the reference now, but I thought I had seen some discussions at one of the ISO C++ meetings (from Google?) about potential standards changes to allow allocations to be elided when they're limited to some known scope.
    - mappu 12y ago
      Devirtualization for example.
    - vardump 12y ago
      > I dunno. I've run into too many programmers on the other end of the spectrum. They're reluctant to take advantage of the genuinely zero-cost abstractions that today's excellent optimizing compilers for C++ enable. Performance wise it might give a false impression of being zero-cost if you micro-benchmark or are very selective what you consider as a cost. Handy for developer effort wise, sure. Yes, it's often cheap or even 'zero-cost'. But you can't assume that to be always the case. In an actual system it might be not so zero-cost when there are multiple concrete instances of generated code of the template. Each consume require actual generated machine code. Larger code size can have a significant performance cost. TLB and L1C cache misses are far from free. Neither is loading the larger executable for short life time processes. Extra page fault, caused by larger memory requirements, that goes all the way to disk is also rather expensive. The whole picture is simply way too complicated to make blanket statements like that.
- MichaelGG 12y ago
  Interestingly, with Rust, the borrow checker makes it statically safe to know when you can stack alloc.
  - _delirium 12y ago
    You can also do it in a more limited set of cases in other languages using escape analysis. You can't provide it in all cases, but in a subset of cases you can show that the allocation never escapes a certain stack context, and therefore it's safe to stack-allocate. I believe the JVM does that in many cases.
    - MichaelGG 12y ago
      Yeah, I wish .NET would do that. Just calling, say, String.Split is gonna involve at least two allocations. At high performance levels, a single allocation per piece of work can be noticeable. And fixing it is difficult. You can actually manually allocate managed objects on the stack, but that's pretty hadn't hacky, unsafe, and doesn't help fix functions you call.
    - Dewie 12y ago
      > You can't provide it in all cases, I'm curious how reliable it is. It seems simple, intuitively, but Java (the JVM?) seems to have a reputation of being sub-par in this respect. Maybe it has to do with knowing how the the variables that are sent to other methods are used; if it only has local knowledge (the method that the object is created in), then I guess it has to be pessimistic with regards to all objects that are used as a parameter in method calls in that method.
      - jerven 12y ago
        Depends on which one, the Escape Analysis in java7 Hotspot is quite conservative. The one in Graal is very aggressive https://wiki.openjdk.java.net/display/Graal/Graal+Partial+Escape+Analysis https://wiki.openjdk.java.net/display/Graal/Graal+Partial+Es.... Not sure what other VMs do.
- ninkendo 12y ago
  > The C++ string library cannot bind the string to the stack frame since it doesn't know how long it's going to live. Huh? If course it could, unless I'm not understanding you correctly. A class like: class smallstr { char stack_str[128]; char* heap_ptr; } can easily (with enough logic in the public methods) store small strings in `stack_str` and once it grows larger, allocate some space on the heap, make `heap_ptr` point to it, and copy it over. "since it doesn't know how long it's going to live" doesn't make any sense to me. A caller would just say: { smallstr s("foo"); // do stuff } // stack_str[] is wiped clean with the stack, and a destructor would be implemented to `delete` heap_ptr if it was used. I'm not sure what you're even driving at.
  - simias 12y ago
    Well, you have to take the context of our discussion in consideration, I meant that you couldn't dynamically elect to allocate your buffer on the stack instead of the heap at runtime in the constructor. Your solution just allocates a 128B buffer on the stack for all strings which may or may not end up being used. That makes your string object 128B larger in all situations. Since we were talking about std::string, I'm pretty sure many people wouldn't be happy if sizeof(std::string) suddenly took 128B (g++'s sizeof(std::string) is 8B on my system). What I had in mind was stuff like alloca and other local scope allocation techniques that would get tied to the constructor stack frame not the caller's.
    - SamReidHughes 12y ago
      g++'s sizeof(std::string) is only 8 bytes because it's a single pointer such that the struct can be reinterpret_casted to a const char * and you get the same thing that c_str() gives you. It's reference-counted (across threads!), copy-on-write. I don't think people would mind a 24-byte std::string (on 64-bit systems), which would consist of a pointer, size, and capacity, and which would allow 22-byte strings to be stored inline. On Windows, sizeof(std::string) is 24 or 32 depending on 32- or 64-bit. sizeof(vector<char>) is 12 and 24, respectively, of course. I believe the extra size of the std::string is for storing strings inline. I'd guess their implementation looks like struct { char *ptr; size_t size; union { size_t capacity; char buf[16]; } u; };, which sacrifices some size in favor of keeping the code paths simple.
barrkel 12y ago
C++'s std::string could store the first few characters inline, and only fall back to heap storage if the string is too big. I'd be surprised if some implementations don't do this already. TurboPascal's strings had a number of quirks. Maximum length was limited to 255 characters, but different string variables could declare different lengths in their types. Writing string functions that could work with any string required using the OpenString type[1], which passed the string by reference instead of by value, with pseudo-const semantics (the parameter couldn't be passed as a var parameter elsewhere). Using the default String type meant allocating 256 bytes for every string variable. You'd want to pass it by reference (with 'var', and later using 'const') to avoid the extra copying. {$P+} in later versions made string-typed parameters openstring by default[2]. [1] http://putka.upm.si/langref/turboPascal/0109.html http://putka.upm.si/langref/turboPascal/0109.html [2] http://putka.upm.si/langref/turboPascal/047E.html http://putka.upm.si/langref/turboPascal/047E.html (I implemented the migration from AnsiString to WideString in the Delphi compiler when I worked for Borland. I know far too much about Pascal and Delphi strings.)
- jbandela1 12y ago
  Some implementations already do such as * Clang LibC++ see http://stackoverflow.com/questions/21694302/what-are-the-mechanics-of-short-string-optimization-in-libc http://stackoverflow.com/questions/21694302/what-are-the-mec... * MSVC - see comments http://channel9.msdn.com/Series/C9-Lectures-Stephan-T-Lavavej-Core-C-/Stephan-T-Lavavej-Core-C-9-of-n http://channel9.msdn.com/Series/C9-Lectures-Stephan-T-Lavave...
- maxs 12y ago
  It's called the short string optimization. It was used once but I am not sure if it is any more. C++11 move semantics may help a lot with string churning...
  - bodyfour 12y ago
    As others have mentioned some libraries do use it. It has tradeoffs though. In a "traditional" implementation sizeof(std::string)==sizeof(char * ) -- it keeps a pointer to the first byte of the text with the metadata (minimally: size and capacity) stored before it in memory. c_str() is just a "return p_;" and size() is something like "return reinterpret_cast<const size_t * >(p_)[-1];" Now to add the short-string optimization you need to do one of two things: 1. Add a small buffer we can point "p_" to inside the std::string itself. However, strings are very common inside of structures so this will bloat objects throughout your program 2. If you're clever you can use the lowest bit of the pointer to indicate that it's an interned string which would let you store 6 byte strings inside the pointer itself on a 64-bit machine (remember you still need the '\0' for c_str()'s benefit) However now c_str(), size(), etc all need an extra branch instruction. These are normally inlined methods, so now you've bloated/slowed the code instead. Personally I prefer a keep-it-simple string implementation for most things.
hannibalhorn 12y ago
You can specify the allocator to use with basic_string, and stack based allocators are possible. I've certainly used them with STL containers. It's just not the default.
CrimsonVoid 12y ago
C++ libraries can optimize smaller strings and store them on the stack. It's commonly known as short string optimization. I'm not sure how many libraries actually use SSO, but I think the three major vendors use something similar. https://stackoverflow.com/questions/10315041/meaning-of-acronym-sso-in-the-context-of-stdstring/10319672 https://stackoverflow.com/questions/10315041/meaning-of-acro... https://stackoverflow.com/questions/21694302/what-are-the-mechanics-of-short-string-optimization-in-libc https://stackoverflow.com/questions/21694302/what-are-the-me...

ajuc 12y ago

I've worked on a project that used all of these: std::string, QString, OString, char*. All were required by a different library that we needed. This is why a good string type should be in core language.

raverbashing 12y ago
This is the problem with C++ (and in a certain part, with C) "Everybody" has their own C++ string (MFC, QT, several libraries, heck, even GObject library has their strings) Same with C Now, you won't see anybody reimplementing strings in Java. C#, Python, JS, etc Lessons learned, their strings work std:string is certainly a step forward and should be used for most projects today
- csl 12y ago
  I guess the underlying problem is that C++ doesn't have a standardized ABI. So you get things like QStrings, etc.
  - pjmlp 12y ago
    It is a standardization problem. When C++ got introduced, it used only C standard library, so everyone wrote their own library. C++ was already 10 years old when C++98 was a thing and compilers still needed to catch up. You don't re-write old code just because, so this cruft shows everywhere.
  - ajuc 12y ago
    It's not a matter of ABI. Even source code level compatibility would solve most of the problems. I am happy to recompile as long as I don't need to convert on every api boundary.
- pjmlp 12y ago
  > Lessons learned, their strings work It is worse than that, because the other alternative systems programming languages that eventually lost to C and C++ also had their string type. Just C did not, and C++ followed along due to its compatibility story.

ExpiredLink 12y ago

During the 10 years I used C++ I never saw a project that used std::string as their standard string. The implementation of std::string not standardized. It may or may not have a 'small string optimization' which may not be an optimization at all. Instead of specifying a mundane immutable built-in string like in Java the C++ Standards committee decided to add even more 'advanced' features to an already overloaded language.

richardwhiuk 12y ago
Heh, as if Java's string was mundane, or even particularly well standardised. The implementation for String have varied in each of the JVM versions, and Android has a different version to the JDK. Java's string, depending on the string, length, JVM version and a bunch of other factors may or may not: - Be interned - so the result of "str1" == "str1" is compiler dependant (you must do "str1".equals("str1")). - Maintain references to the string when doing a substring - e.g. "Java is a language full of quirks......".substring(0,4) may or may not hold a reference to the entire string. This has huge performance tradeoffs - e.g. if you parse JSON by doing .substring(), and aren't careful, then you can end up holding onto the entire unparsed JSON, even if you only keep track of a single obejct.
- kjetil 12y ago
  Are you seriously suggesting that String incompatibilites are a big issues in Java? String interning is specified in the JLS: http://docs.oracle.com/javase/specs/jls/se8/html/jls-3.html#jls-3.10.5 http://docs.oracle.com/javase/specs/jls/se8/html/jls-3.html#... As far as I can tell, the substring "feature" has been there since Java 1.0 and was fixed in Java 7. Hardly groundbreaking stuff.
csl 12y ago
The interface and behavior of std::string is standardized. Library writers are free to implement it in any way that honors the standard. However, sometimes the requirements may lead to less than optimal implementations, I believe. So as long as Chrome uses std::string for internal use only, there shouldn't be any problems. Using them across ABI boundaries, however, is another story.

vegancap 12y ago

I literally started programming in C++ this week and I figured the over-use of std::string couldn't be a good thing hehe

csl 12y ago
It always depends on your needs. Before you start avoiding std::string, note that the article said that one of the problems was that they went from std::string to C-strings and then allocated a new std::string. This often happens when you use both kind of strings in your code. The takeaway is to stick either to C strings or use std::strings with reference passing, dropping down to c_str() when needed.
- vegancap 12y ago
  Thanks, that was a lot more helpful response :) I think the most confused I've been so far (coming from a PHP background) was all the different types of strings!
w8rbt 12y ago
std::string solves more problems than it creates. Use it.
- zl4000 12y ago
  Definitely, and where `std::string`'s interface is not enough, use thrid party libs which work on std::strings, like boost string algoriths, std regex, or uftcpp.
pjmlp 12y ago
Well, you could just use char* and produce security exploits everywhere.
zl4000 12y ago
No that's BS. `std::string` should be used where ever it is applicable. The whole issue that this post about chrome was talking about was dealing with a poor usage of `std::string`, such as passing c_str() to then go and construct another string instead of passing by const ref. Or building a set of `std::string` to simply check if a value exists. That's just shit code, not an issue with `std::string`.

ctur 12y ago

folly::fbstring, a drop-in replacement for std::string, is part of the folly library that we (Facebook) open sourced a while back. It allocates small strings in-line and larger strings on the heap and has optimizations for medium and large strings, too. It's proven quite effective for us, particularly when used with jemalloc, which it conspires with for more optimal memory management. We use it as std::string for our C++ applications and libraries, completely replacing std::string both for our own code and third-party code. https://github.com/facebook/folly/blob/master/folly/docs/FBString.md https://github.com/facebook/folly/blob/master/folly/docs/FBS... In addition, it is worth noting folly::StringPiece (from folly/Range.h), which is generally a better interface for working with in-memory ranges of bytes. Hardly a new idea (it's inspired by similar libraries, such as in re2), but it permeates the APIs of many of our larger C++ systems, and folly itself, and often avoids passing std::string objects around at all. Finally, there is also folly::fbvector, which offers similar improvements over std::vector.

raverbashing 12y ago
Yeah, and if I want to use it I need to replace std::string all around my code. I can't use it for other libraries, unless I replace and recompile them. And tomorrow a new library comes I need to replace everything again. Your effort is commendable, and I know squeezing gains are important in the case of fb, but in the end it's just locking yourself in a library that should've been a second though/built in.
- Cthulhu_ 12y ago
  1. Find / replace, I'm sure the API is simple enough and performance gains are worth the effort. 3. You don't need to replace anything, ever - only if you feel like your string performance is lacking, and that particular new library satisfies your needs (in terms of effort vs performance gains). I don't get why people believe that whenever something new comes out they have to switch over, and as a result are terrified of innovation. 4. I disagree with the "should've been built in" statement; the default std::string implementation is good enough for most (like any std:: thing). Besides, std:string was designed 25+ years ago, over a dozen CPU generations ago; the demands of today are must different.

ryandrake 12y ago

If you dig deeper and actually look at the source diffs, you will see that this is not about std::string being "bad" (it's not), but it's about problems with how they're using std::string. Most of the trouble was constantly converting back and forth between std::string and const char*, which needlessly produces temporary allocations. Simply moving to passing everything around as const references should help enormously with memory churn. EDIT: Spelling :)

MichaelCrawford 12y ago
I beat the subject of data representation completely to death in my article "Pointers, References and Values" at: http://www.warplife.com/tips/code/c++/memory-management/parameters/ http://www.warplife.com/tips/code/c++/memory-management/para... One of the worst performance problems in C++ is quite commonly the creation of invisible temporaries. Sometimes they are necessary but commonly they are not. There are specific cases where it's better to pass a value rather than a reference, for example if you have an integer in a register, and your parameter passing conventions calls for passing parameters in registers, then passing that integer as a value, rather than a reference (const or otherwise) avoids the use of memory; it also avoids the use of the memory cache, which is likely to be a more serious problem. In general, for a C++ program to make lots of allocations of just one class isn't such a bad thing. If your default implementation is slower than you like, you might be able to speed things up considerably, as well as save memory, reduce disk paging and so on by using a custom memory allocator just for that class.

TazeTSchnitzel 12y ago

One thing I've learned from PHP's internals is that using reference-counted strings and copying on write is a fantastic idea. You can save an awful lot of memory and allocations, and simplify your code.

zl4000 12y ago
Copy on write is not at all helpful in a language like C++ where concurrency can be concerned.
- TazeTSchnitzel 12y ago
  ...how so?
  - bodyfour 12y ago
    If you have a single-threaded runtime then reference counts are cheap and easy. Once you need to support multithreading you need to use CPU atomic instructions to maintain the reference count safely. As the number of CPU cores increases the relative cost of this operation goes up. COW strings were a very common optimization when 1-2 CPUs were standard. That's why it's there in GNU's libstdc++ for example. On a modern server with 24 cores it's pretty dubious. It'd only make sense if you were copying (and then not mutating) a lot of your strings.
adamtj 12y ago
Reference counted copy-on-write strings are little landmines just waiting to blow your leg off should you venture into multi-threaded territory. If you use copies of such a string in multiple different threads, you may find that simply creating a new copy of the original string or any of its subsequent copies can cause an incorrect reference count which will trigger a double-free and a segfault at some later time, possibly long after all non-main threads have ended. You can't even lock all accesses to a string with a simple mutex. You have to also lock all descendant and ancestor copies, including all temporary copies, as when passing by value to a function. A COW string is basically a pointer to an internal shared data structure. You need to lock accesses to the shared structure, not the pointers to it, and you can only do that internally. The only way to reliably use such a string with multiple threads is to make the internal reference count and buffer manipulations thread-safe. It may save you some allocations and copies, but the thread safety will slow things down. How much, I don't know. I wouldn't be surprised if thread-safe copy-on-write is slower than copy-always.

DanielBMarkham 12y ago

One of the recurring things I see in programming literature for the last 20 years or more is performance hits when using string. I've seen essays on this in at least four different programming languages. You'd think it'd be simple, but it's not. String is an allocated buffer of unknown final size, and since it represents some kind of meaning in a human language, and since human languages have indeterminate length for conveying any one concept, concatentation is extremely common. This is actually one of those cases where I like c better, warts and all. Whenever you use a string, you should carefully think about what you're going to do with it, and if at all possible allocate all you need up front. Beats the heck out of taking an unexpected GC call somewhere later when you weren't expeccting it.

zl4000 12y ago
> Beats the heck out of taking an unexpected GC call somewhere later when you weren't expeccting it. How is that an issue with c++ `std::string`

humanrebar 12y ago

The problem with std::string is that it's named wrong. It should be called std::string_buffer, because that is what it is. Its performance characteristics are closer to a std::vector than a std::array (now available since C++11). Many projects cannot copy around std::vector<char> in good conscience. They really want a copy-on-write string, an immutable string, a rope, a reference-counted string, or an always-in-place string. Or some combination of the above depending on the circumstance. The problem is that std::string is not a good type to use as a parameter for various reasons. In addition to its aggressive allocation behavior, it's also fairly inflexible. What are the alternatives? 1. boost::string_ref - available now, so use it 2. std::string_view - available starting in C++14 and works roughly like boost::string_ref 3. pass around pairs of iterators instead of single objects 3) is actually the most flexible, though it requires different kinds of overhead. The most obvious way would be to template all your string-accepting functions on two parameters: the type of your begin iterator and the type of your end iterator. But the benefit is that you can pass around any of the above to your heart's content, plus more, like elements in tries. std::string still has an important place, but it should generally be used as a private member variable, not as something you require in your interface. Pretty much the same thing goes for char* unless you are implementing a C ABI (plus a size, please). Even then, you can immediately convert to/from a boost::string_ref and still have yourself a self-contained reference to a bounded character sequence.

rwmj 12y ago
Or proper garbage collection so you don't need to worry about who owns the string and you don't have the big overhead of ref-counting. Why on earth are they using C++ for a web browser anyway? That's about the worst possible choice of programming language for that problem domain.
- IvyMike 12y ago
  So which web browsers are not written in C++?
  - rwmj 12y ago

hesdeadjim 12y ago

It's always driven me nuts that the base string in the STL is a fully mutable container that must manage it's own memory. I much prefer a string being either immutable, or an interface that you can implement however you see fit: a view over a raw buffer, a ref to a globally shared string instance that may or may not be ref counted, or like the STL, a version that self-manages its own memory. Besides boost::string_ref, there is also a more generic flyweight implementation requiring only an equality concept for it's template parameter: http://www.boost.org/doc/libs/1_56_0/libs/flyweight/doc/tutorial/ http://www.boost.org/doc/libs/1_56_0/libs/flyweight/doc/tuto...

ceejayoz 12y ago

I sure as hell believe it. I'm on an older, slightly creaky Macbook Pro, and typing in Chrome's box is frequently a nightmare if I'm running something like a VM. Keystrokes lag tremendously.

themoonbus 12y ago
Same situation here... I have to clear my browser history every couple of months in order for it to perform adequately.
- gongar 12y ago
  Yeah, same here. I've to clear history like every few weeks. Else it lags so badly.
  - deleted 12y ago
    [deleted]

CyberDildonics 12y ago

I'm not even sure if I do stuff like this in prototypes. My experience has been that using a matrix/arena/pool can speed a program up that has inner loop allocations by x7. I think the average pc can do about 10,000,000 heap allocations per second, but as far as I know it causes thread locking to some degree. Don't many std::string implementations have small string optimizations? This is actually the first time I have every heard of C++ strings being the bottleneck of an application (and it seems that is even still up for debate here).

paulhodge 12y ago
If you're interested in this topic then you should read the whole discussion in the link. There is a lot of talk about what optimizations are in play.

DigitalSea 12y ago

It all makes sense now. For some reason on my gaming PC which is pretty spec'd out in almost every way, Chrome will lag when typing into the Omnibox and requires me to close it completely and reopen it frequently. For a while I thought perhaps I had an issue with my CPU getting too hot, a bad plugin or faulty RAM, but this exact issue appears to be the cause of all of my problems. The only thing that seems to fix the issue temporarily is clearing out my browsing history every few weeks, otherwise the issue gets to the point where you can wait a couple of seconds for a word you have typed to appear. Don't get me started on the performance of using Chrome inside of a VM, that is a whole other world of hurt right there.

dwild 12y ago
On my Asus Transformer Book t100, that I use for all my personal stuff, I never have any issue with lag. In some rare case it can lag but it's temporary and then it's fast again. If your history is pretty big and it's all stored on a slow HDD, I can see how your IO could be the bottleneck.
- DigitalSea 12y ago
  I am a front-end developer, so my history grows a lot every single day. After a few weeks, my history is a culmination of documentation links, testing links, StackOverflow posts and more. I actually did some testing a little while ago and could see the bottleneck taking place. My CPU usage would spike up to 100% whenever I would type something into the Omnibox when I had a few weeks worth of history. I spotted this on a clean install of Chrome, I signed into my Google account, but disabled all plugins and it still occurred. Weirdly enough, not everyone seems to experience this issue.
  - groby_b 12y ago
    If you feel comfortable sharing your history, filing a bug on crbug.com with this info might help out the Chromium devs. (Don't share it right away - ask to have the bug closed to public view before you share)
12y ago

jamesu 12y ago

In a certain 3d game engine we use, the devs decided to refactor a lot of old code in the animation code which used a hashed string type to use their new all-in-one reference counted String type instead. Safe to say this turned out to be a disaster for performance since every time an animation or not had to be evaluated from a name (which we ended up doing a lot), a string had to be allocated on the heap. Some people sadly underestimate how bad objects which rely on heap allocation can be in performance-critical code.

GregBuchholz 12y ago

Well, it is a good thing they wrote it in such a high-performance language then...

amaks 12y ago

There are many things in the standard C++ library which are named incorrectly (std::string), awkwardly (std::unordered_map) and and implemented inefficiently from the perspective of modern CPUs (same std::unordered_map, which uses linked list for the underlying hash table buckets). See the great talk on CppCon 2014 about those issues - https://www.youtube.com/watch?v=fHNmRkzxHWs https://www.youtube.com/watch?v=fHNmRkzxHWs.

userbinator 12y ago

25000 (!!) allocations are made for every keystroke in the Omnibox. The Omnibox is no doubt far more complex than simple text box since entering characters into it can invoke things like network connections (for search suggestions), but 25k allocs is still a bit on the excessive side. Strings are an interesting case in that in general they are of indeterminate (and variable) length, which makes them somewhat difficult to accommodate in computer memory which is finite and allocated in fixed-length pieces. Abstractions like std::string have been created to make it simpler and easier to perform operations like appending, resizing, copying, and concenating, but I think this is part of the problem: by making these operations so easy and simple for the programmer, they're more inclined to overuse them instead of asking questions like "do I really need to create a copy just to modify one character? do I really need to append to this string? how long can it be?" Essentially, the abstraction encourages ignorance of the real nature of the actual operations, leading to more inefficient code. It only helps the programmer to perform these tedious operations more easily, and doesn't help at all with the decision of whether such tedious operations should be needed at all, which I think is more important; the first question when designing shouldn't be "what abstractions should I use to do X?", but "do I really need to do X, or is there are simpler way that doesn't need to?" The most efficient way to do something is to not do it at all. Contrast this with a language like C, in which string operations are (unless the programmer writes or uses a library) far more explicit, and the programmer can be more aware of what his/her code is actually doing. That's why I believe every programmer who has to deal with strings should have at one point been exposed to implementing a resizable string buffer and/or length-delimited string library, to see the real nature of the problem (including how to do length management correctly.) Without this basic, low-level understanding of how to use memory, the advantages of all the other fancy string abstractions won't make much sense either.

humanrebar 12y ago
> Contrast this with a language like C, in which string operations are (unless the programmer writes or uses a library) far more explicit String operations are more explicit. Mostly. But some things (like sharing between threads, type conversion, and memory ownership) are very implicit and unsafe. Some of the implicitness to C programmers is so familiar that they don't notice it: /* 1. This function returns an error code * and not a size * 2. zero is success, nonzero is an error */ int /* 3. this method belongs in mylib * 4. this function supports ASCII??? * 5. this function allows memory to overlap? */ mylib_copy_first_n( /* 6. *out_s is allocated * 7. *out_s is greater than n bytes in size * 8. out_s will hold a null terminated string */ char const * out_s, /* 9. in_s is allocated * 10. *in_s holds at least n characters * 11. it's not a big deal if in_s has null characters */ char const * in_s, /* 10. n is not negative * 11. if n is zero, something sane will happen */ int n); I wouldn't hold up C as an example of explicitness. Now, this isn't a great example of C code, but even in the best examples of C code, there is a lot of correctness by convention and documentation. To be fair, I'm not aware of any languages and libraries that are fully explicit in type, behavior, and memory usage. Maybe Ada or one of the functional languages get it right. But there are a set of C++ tools that can make this sort of thing fast and correct. That's why it's disappointing that std::string isn't fast and is only mostly correct.

wfunction 12y ago

Why in the world are they even using c_str so often in the first place? That makes me worry more about security holes than performance...