Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

groups.google.com

Post reply on HN
Print view View original

121–130 of 170 posts

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

#121

Post by thrownaway2424 »

riffraff wrote: post #49
ctur wrote: post #15

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…

FWIW, the email thread does say that some "base::StringPiece" should be used more often.

StringPiece is here https://chromium.googlesource.com/chromium/src/base/+/master...

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

#122

Post by humanrebar »

userbinator wrote: post #107

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 difficul…

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

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

#123

Post by thrownaway2424 »

ctur wrote: post #15

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…

It hardly seems like introducing yet another type can solve this problem which is caused by temporary conversion back and forth between string and char*.

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

#124

Post by tedunangst »

vardump wrote: post #115
rwmj wrote: post #70

Earlier quoted context omitted.

Almost all of Windows (including apps that predominantly do string and tree manipulation) is written in C++. Almost all of Linux userspace is written in C. These are still terrible, insecure, fragile languages which cause frustration and loss to programmers and users every day.

Shame you're downvoted, because you're pretty much right. Don't get me wrong, correct code can very well be written in C/C++. It's just 95% of the programmers using those languages are not very skilled. The programs tend to be wrong and fragile. In C++, most of this fragility derives from its C-roots. C/C++ is also a poor match to today's CPUs. It's very slow compared to what the hardware is capable of. Compare for e…

Neither of you are really answering the question. You still haven't proposed a language is better.

When the half dozen browsers that represent about 99.9% of the browswer market all use C++, perhaps the explanation is not "They're all wrong."

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

#125

Post by DannyBee »

rwmj wrote: post #82
ibebrett wrote: post #74

Earlier quoted context omitted.

what experience do you have with writing c++? what is the last large project you completed with it? i'm not a huge fan of c++, but it has been the foundation of an extremely large number of wildly successful and pervasive projects.

I have in the past written many large C++ projects. I now try to avoid it as much as possible, but the last time I programmed in C++ was just two weeks ago[1], and it reminded me how bad it was -- terrible error messages, and abysmal performance of the final program. At some point I will have to replace it because the program doesn't meet our performance requirements, and no one can tell me why[2]. (Edit: Apparently…

Of all the things you shudl expect from a non-C++ language, performance is highly unlikely to be on that list.

If you can't get something to be performant with C++, it's pretty unlikely you'll get it to be performant with most other languages.

(Unless you want to try it in fortran)

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

#126

Post by jerven »

nostrademons wrote: post #114
MrBuddyCasino wrote: post #112

Earlier quoted context omitted.

I was aware of the substring issue and the fact that CJK languages require 2 chars, but I might have used codePointAt() instead of offsetByCodePoint(), to be honest. So I agree unicode string indexing is not as easy as it should be, due to a stupid API - but if thats all, I'm not sure that passes for 'hard'. It is also not something inherent to strings in general, the language designers simply messed this up. Btw., I…

The point is that these are trade-offs. The reason for the stupid API is because by getting precise multilingual handling, you give up either O(1) string indexing or representing characters in less than 3 bytes/char. If you naively use offsetByCodePoint on megabyte-long strings, you may find your performance slows to a crawl. The reason for the memory leak is that you can either have fast substring() or accidental me…

Even if you use 3 bytes per char you are not guaranteed O(1) string indexing as you will still have surrogate pairs :( So you need to normalize these first... or deal with them in searching :(

String in more modern languages are standardised in one form and widely used in all libraries. C and C++ are the exceptions to this.

For example I hardly ever see CharSequence implementations in Java code. It is the most underused interface I know of, because for most people String is good enough. In idiomatic Java code the performance issue discussed here does not occur. Strings being final and passed by reference (or more correctly the reference is copied by value) the same string does not get reallocated all over the place.

The C++ problem is that std:string does not suffice for the common case and we end up with QStrings that are difficult to convert to boost:string.

In Java land when String does not meet the perf needs we implement a custom CharSequence but these are easy to convert to Strings if needed (easier than QString to Boost string).

So we end up with most Java programers knowing just StringBuilder, String and char[]. ByteBuffer is really about bytes and easy to convert to a CharBuffer.

The Java Language has some downsides in standardising on UTF-16 for its common String type (Moving on from UCS-2). But even if had chosen extended ASCII like Oberon it would at least be consistent everywhere.

I believe that javac replaces + with StringBuilder calls. And in loops the multiple StringBuilder allocs are removed and replaced by appending to one StringBuilder.

The Java Strings are far from perfect in UniCode terms but a whole lot better than std::String and its 16+32 friend.

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

#127

Post by pubby »

bodyfour wrote: post #90
ajuc wrote: post #4

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.

The real language problem is that classes are closed -- you can't add your own methods to std::string (other than operators) As a C++ program grows it's more and more tempting to make your own private string class (either by inheriting from std::string, encapsulating it, or reimplementing it) that interacts more naturally with your program's other types. I've done this myself. Of course this works great until you nee…

What's wrong with free functions?

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

#128

Post by jerven »

Dewie wrote: post #101
_delirium wrote: post #31

Earlier quoted context omitted.

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.

> 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…

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+Es.... Not sure what other VMs do.

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

#129

Post by bodyfour »

nostrademons wrote: post #104
bodyfour wrote: post #84

Earlier quoted context omitted.

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 (p_)[-1];" Now to add the short-string optimization you nee…

2. You can actually go up to 7 bytes as long as you're sure you get word-aligned pointers back from malloc (usually a good bet). Make the tag the last byte, indicate a short string by "tag_byte & 0x07 != 7", and then store the length as "7 - tag", reserving tag 7 for pointers. If it's a 7-byte string, then the tag byte itself will be 0, serving as the null terminator. If it's Whether these gymnastics are worth it is…

Remember that on a little-endian machine (i.e. nearly everything now) the "last byte" of the pointer is actually the first byte of the string. The only way you can use the 8th byte of the string as your sentinel is if you can be sure that the allocator won't ever give you a pointer with MSB=0x00.

You are right that on big-endian machines you can smuggle a 7th byte into the pointer though by sharing the "tag" and the '\0' terminator. You don't really have to worry about the 0-byte case since in a traditional implementation there is a shared empty-string sentinel that the default constructor uses. So if you are mutating a short-string and the result is 0 bytes you can always just replace it with a pointer to the shared sentinel.

I agree with your intuition about the costs. I think your program would have to be pretty dominated with tiny strings for all of this optimization to help much. My guess is that it would microbenchmark well. However, all of those extra branches would add pressure to I-Cache and branch predictor history which would offset it in the real world.

folly's fbstring actually has 3 separate regimes (interned tiny strings, classic normal strings, threadsafe-COW large strings) so I guess they decided that the extra branches were worth it for them. I still prefer a simpler design where c_str()/size() don't require any branches though.

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

#130

Post by ahomescu1 »

MrBuddyCasino wrote: post #83
roel_v wrote: post #37

Earlier quoted context omitted.

"Lessons learned, their strings work" Except that they don't. Either they are 'complete' but massive and thus slow, or they start as 'array of byte' and then their designers spend 10 years implementing a more 'complete' string type that is still fast enough and end up as #1 anyway. Of course the C++ way where there is no string type that everyone uses sucks too, it's just that strings are almost impossible to get 'ri…

It boggles the mind how many different ways to represent Strings there are in C++, and String handling in general is the major reason I'll never touch it (or C) with a 10 feet pole. I'm interested to hear though how the String handling in Java is broken. This is everything I have to know: - String - CharSequence - char[] / Character[] - StringBuilder Done. Finito. Strings are immutable, the GC will clean up after me.…

> Only downside: more memory needed, but nobody except the embedded guys care anymore.

As an Android user, I care. Android needs 2GB of memory to run the apps that iOS only needs 1GB for (running Android on a tablet with 1GB has been painful for me).

Post reply on HN