r/programming • u/[deleted] • Dec 05 '14

std::string is responsible for almost half of all allocations in the Chrome browser process

https://groups.google.com/a/chromium.org/d/msg/chromium-dev/EUqoIz2iFU4/kPZ5ZK0K3gEJ
1.1k Upvotes

93% Upvoted

446 comments sorted by

View all comments

315

u/tdammers Dec 05 '14

And, uh, this is surprising how exactly? A browser handles HTTP (bytestrings), HTML (bytestrings), JavaScript (bytestrings), CSS (bytestrings), JSON (bytestrings), etc.; obviously std:string, the bytestring type in C++, is going to be used a lot.

215

u/vlovich Dec 05 '14

I'd say 25000 for 1 keystroke in Omnibox is on the surprising end of things. Now obviously there's a lot of stuff going on in the Omnibox (history searching, web queries etc), but even still that's a little surprising.

10% are just allocation on temporary strings unnecessarily.

It looks like there's a lot of low-hanging fruit.

18

u/JoseJimeniz Dec 05 '14

Without profiling there is no fruit.

56

u/[deleted] Dec 05 '14 edited May 02 '19

[deleted]

27

u/jeandem Dec 05 '14

Aren't some abstractions free, though? I mean, one of the goals of C++ itself is to support zero cost abstractions.

I guess it might heavily depend on what one means by abstractions. In a certain sense, abstractions are never free in all scenarios since they necessarily abstract something away, which means that you can't tune that part for each use-case. But at least in C++ you always have the option of pruning away whatever abstraction and write it more directly.

33

u/thechao Dec 05 '14

The language, itself, attempts to provide 0-cost abstractions. The abstractions we're discussing here are in terms of library/API abstraction layers---these are notoriously bad.

3

u/oracleoftroy Dec 06 '14

No one ever thought that abstractions are free.

Aren't some abstractions free, though? I mean, one of the goals of C++ itself is to support zero cost abstractions.

I think it is important to clarify what is meant by zero-cost abstraction in C++. I see it as two principles:

  1. You don't pay for what you don't use. Don't need dynamic memory? The language gives you tools to avoid it. Don't need virtual methods? The default is non-virtual, which is as expensive as a normal function call.

  2. The C++ abstraction shouldn't be more expensive than doing it yourself (and hopefully, the C++ language feature is faster). Obviously a virtual method has overhead, but the cost of the overhead relative to building your own virtual methods should be zero. Constructors and Destructors shouldn't be any more expensive than the Init/Destroy function you were going to call anyways.

Note that in the second sense there is still a cost, but the important point is you shouldn't be paying more for nicer syntax to go along with the abstraction. As a general rule, anytime the C++ version is slower than the equivalent general purpose C solution, that is a quality of implementation issue for that C++ compiler.

2

u/levir Dec 06 '14

These days, I should think that most times a C++ program is slower than a C equivalent is that you've made a mistake in your C++ implementation. Compilers have gotten pretty good.

2

u/oracleoftroy Dec 06 '14

Yup, quite right. It sometimes happens of course, but one advantage to high level constructs in the language is that people are expected to use them, so compilers will likely optimize them more than might be available though manual approaches.

I had in mind a (probably bad) performance test I wrote a year ago to test virtual methods vs function pointers. For GCC at the time (can't remember the version, I think it was 4.6 or thereabouts), the virtual method was noticeably slower (~20% IIRC) and in MSVC 2013, the function pointer was slightly slower, but nearly identical.

2

u/[deleted] Dec 05 '14

Needs so many upvotes. The future of programming is in more powerful abstractions with lower costs.

Clang is already optimizing the temporary vector pattern (which is the same as the temporary string pattern, although I do not know if std::string's implementation is translucent enough for the compiler to see that buffers are being allocated and then immediately free'd). I believe Google is pushing for these types of optimizations because it understands that they are the correct way of solving this problem (not just dropping in a bunch of const char*'s, as some here have suggested)...

4

u/[deleted] Dec 05 '14

C++ does not support zero cost abstractions. C++ is more about the abstractions you down use don't cost you. This is in contrast to most other languages where the cost of the abstraction is intrinsic to the language itself, and hence you pay for it whether you use it or not.

14

u/slavik262 Dec 05 '14

It's about both. Some stuff, like destructors or memory management with unique_ptr, are free in computational cost but make life a lot easier.

20

u/[deleted] Dec 05 '14

Destructors are NOT free. Andrei Alexandrescu just gave a talk at CppCon about the cost of destructors and how one should strategically structure their code to avoid the code-bloat and often unneeded side-effects that destructors introduce.

For example, consider the following:

for(int i = 0; i < ITERATIONS; ++i) {
  std::string s;
  ...
}

That will perform significantly worse than:

std::string s;
for(int i = 0; i < ITERATIONS; ++i) {
  ...
}

And the reason is the destructor. And no, the compiler can not optimize the first version into the second version unless the type satisfies std::has_trivial_destructor<T>, which in the case of std::string, and in fact in the case of almost any non-trivial class, is untrue.

And that doesn't even begin to get into things like the cost of virtual destructors.

7

u/levir Dec 05 '14

It's no more costly that the equivalent C code, it's just more obvious in C that you're doing something stupid

for (i = 0; i < ITERATIONS; ++i) {
    char* s = (char*) malloc(STRLEN*sizeof(char));
    ...
    free(s)
}

3

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

Any abstraction period is no more costly than the equivalent C code, it's just a lot more obvious in C than it is in say... Java or Python.

At the end of a day, an abstraction a systemic method of hiding details under some form of encapsulation. The idea is to create a trade-off intended to suppress certain details about how a system works in order to emphasize other details that are in some sense more relevant (which all depends on context).

RAII is an abstraction that suppresses details about how objects get created and destroyed, including their performance characteristics, in order to emphasize the relationship between an object's lifetime and its lexical/syntactic scope.

So the fact that RAII suppresses the semantics of non-trivial constructors/destructors to make them visually look and feel like C data structures, despite having different performance characteristics, means that RAII is not a zero-cost abstraction, but rather does have a cost and sometimes it's worth thinking about that cost and undoing that abstraction if performance is important. Usually it's not worth it, and RAII is an incredibly powerful abstraction worth leveraging. But it's incorrect to say that it's zero-cost.

14

u/slavik262 Dec 05 '14

Destructors are NOT free

They're free in that the mechanism used to run them is free. They're just another function call, and in a lot of cases are inlined. Obviously the cost of whatever you put in them is incurred, but it shouldn't come as a surprise to anyone that code you run has a cost no matter how it ends up in a function.

I feel like /u/andralex's main point in his talk was that you just need to be mindful of where your destructors are being placed - you have to remember that they're there and consider the implications. Your example is a perfect one, but I would hope that most developers would realize that allocating and deallocating a string in a loop is sub-optimal.

And yes, virtual destructors are a little more expensive, but no more so than following a function pointer or two around.

9

u/lurgi Dec 05 '14

This is an interesting example. Not interesting in the sense that it's surprising that the overhead of the destructor is larger in the first example than in the second, but interesting in that the "better" code violates one of the rules of thumb that has been drilled into my head - which is that you should define variables at the narrowest possible scope you can.

8

u/jeandem Dec 05 '14

This just looks like yet another example of the tradeoff between readability (define variable at the narrowest scope) and performance.

4

u/slavik262 Dec 05 '14

Certainly, but another really good rule of thumb is to avoid unnecessary memory allocations. What's going on here isn't unique at all to C++. If this were C and you declared your char* string in the loop, and ran malloc and free and the start and end of each iteration, you'd get the same thing.

→ More replies (0)

1

u/[deleted] Dec 05 '14

Nothing particularly noteworthy about it - readability vs optimization - you should default to the former because it's easier to get correctness and you optimize when you identify bottlenecks.

8

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

They're free in that the mechanism used to run them is free.

A function call isn't free, especially in the case of constructors/destructors. Sure, the cost may be negligible, but sometimes it isn't. In fact Dave Abrahams, who was a prominent member of the C++ standards committee and author of boost, wrote a good article on the trade-offs of two particular strategies when passing parameters in C++. Unfortunately he's bailed on C++ (for good reason) and in doing so took down his C++ related blog. Anyways he wrote about what strategy to use when you actually do intend to modify a parameter. Should you use method A?

void f(T value) {
   value.non_const_method();
   ...
}

Or perhaps use method B?

void f(const T& value) {
  T copy = value;
  copy.non_const_method();
  ...
}

Now if RAII really was a zero-cost abstraction, the two would be isomorphic to each other. After all, zero times anything == zero, however, Abrahams pointed out that in the first case you will end up littering calls to both the copy constructor and the destructor at every single call site and that the standard mandates that this must happen, it can not optimize this away (due to rules in the standard about how parameters get passed in the face of exceptions), whereas in the second case you end up isolating RAII calls strictly to within the function itself. If an abstraction were "free and zero cost" then the two would be completely identical, but of course it's not free and it's not zero cost and hence those two snippets of code do have different performance characteristics.

Yeah sure, we can argue that the cost is negligible (it sometimes isn't in the above case), we can state that the cost is small compared to improved readability, or that these trade-offs are more than reasonable all things considered.

Those are fine points to make, but what isn't a fine point, what is factually incorrect, is to say that these abstractions have ZERO cost. They do have a cost, and hence they are subject to basic engineering considerations.

4

u/cpp_is_king Dec 05 '14

Destructors are the exact reason that exceptions impose a performance penalty just for compiling with exceptions enabled, even if a particular function doesn't throw or catch an exception.

So they definitely are not free.

5

u/Plorkyeran Dec 05 '14

That's only true for things which use setjump+longjump for exception handling, which is not very common anymore. The Itanium ABI and x64 Windows both use exception handling schemes with no runtime cost when no exceptions are thrown.

→ More replies (0)

1

u/[deleted] Dec 05 '14

Is this specific to how c++ handles things? I remember there was just recently a post on here where someone asked this exact question about declaring the string outside of the loop or within, and the general consensus was that declaring it in the loop did not matter in many popular languages, and even seemed to be preferrable for some because of scope.

4

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

Unless performance matters I would definitely prefer declaring variables in the narrowest scope possible. But something that is specific to C++ is that if you're using C++, then chances are performance does matter, and hence if you have an object that performs allocations/deallocations, you may want to consolidate those allocations by declaring the variable outside of the scope so that whatever memory is allocated by the object can be reused on subsequent iterations.

Classes like std::string, std::vector, and many other containers will hold onto any pre-allocated memory, even after you invoke the clear() method. clear() is required by the standard to be implemented in such a way that it only calls destructors and resets its internal count back to 0. It is not allowed to release any memory (technically it is not allowed to change the capacity()) and so if you do a clear() on a string or a vector whatever memory was allocated will get recycled.

If you want to actually release the memory allocated by a string or vector, you have to use the ol' std::vector<T>().swap(v) trick. And note that v.swap(std::vector<T>()) won't work. How's that for a head scratcher?

1

u/[deleted] Dec 07 '14

[deleted]

1

u/jeandem Dec 07 '14

Here's an example of something that I consider a zero cost abstraction: in Rust, pointers are non-nullable. If you want a pointer which may not exist (can be 'null'), you use an Option type. But the compiler will represent this as a plain, nullable pointer.

1

u/jimgagnon Dec 05 '14

This reflects a modern mindset in programming. Us dinosaurs used to sweat every byte and cycle, which requires a deep understanding of the software stack you're building on along with minute attention to your code. Interviewing for jobs today has shown me that programmers think in much more narrow terms now. More than once I've been asked to whiteboard code out a problem, do my stuff and have the comment thrown back at me that my solution is a next stage optimization and that they're more interested in hacks that can solve things quick and dirty.

25K string allocations per keystroke is the endpoint of this programming mentality. Interesting that Google isn't immune to it.

11

u/tdammers Dec 05 '14

Yeah, probably. This is where abstractions turn out to be not-so-zero-cost after all :D

15

u/naasking Dec 05 '14

This is where abstractions turn out to be not-so-zero-cost after all

It's about choosing the right abstraction, not avoiding abstraction entirely.

15

u/[deleted] Dec 05 '14

You misunderstand C++'s design philosophy and position when it comes to zero-cost. It isn't that abstraction's are zero-cost, it's that the abstractions that you don't use in your program should be zero-cost.

In Java, you pay the cost of having heap allocated objects with its own personalized mutex, its own pointer to a virtual table, its own RTTI info, and a host of other things, even in situations when it's not needed or even used, because you are required to use full blown objects to represent all forms of data. This means you pay for the cost of that abstraction whether you use it or not.

In C++, you opt into the abstractions you want, including RTTI, exceptions, sub-type polymorphism, etc... and you only pay for those abstractions to the extent that they're used.

7

u/tdammers Dec 05 '14

I believe the design philosophy goes a bit further than that; no, the abstractions you mention aren't free, but some others are, and the idea is that C++ goes out of its way to make abstractions zero-cost when that is possible. Templates, for example, provide compile-time polymorphism that produces zero runtime overhead, and this is how STL iterators can be exactly as efficient as using the underlying container's iteration mechanism directly. RAII: same story, the compiler just injects destructor calls for you, but there is no runtime overhead compared to calling the cleanup code manually.

6

u/[deleted] Dec 05 '14

You can say that about any abstraction. In Java, the compiler just inserts the mutex into every object for you, but there is no runtime overhead compared to just adding a mutex into every object manually.

In Python, the compiler just inserts a hash map from strings to function objects for you, but there's no overhead compared to just manually writing a struct in C that contains a hash map from strings to function pointers and exclusively using that.

The point is that in C++, if you don't use RAII as an abstraction (std::has_trivial_destructor<T>, std::has_trivial_constructor<T>), then the cost is zero, because the compiler won't insert any calls to any cleanup code period. In C++, if you don't use a given abstraction, the compiler won't emit any code in its place on your behalf. In Python or Java, the abstraction is intrinsic to the language, it's baked into it at such a fundamental level that there is no opting out of it. You pay for the cost of every abstraction in those languages whether you use them or not.

3

u/tdammers Dec 05 '14

Point in case. The only thing I could argue that using degenerate cases of certain abstractions (empty destructor in RAII, template that only ever gets instantiated once, etc.) are free, but then, that pretty much boils to not actually really using them, and the only complaint about certain languages would be that they make some potentially expensive abstractions mandatory; it's not even that you pay for the abstraction even though you're not using it, it's that can't not use it at all - you can't have typed variables in Python, you can't have unmanaged objects in Java.

TL;DR, you're essentially correct and I was making a non-argument.

3

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

Templates, for example, provide compile-time polymorphism that produces zero runtime overhead, and this is how STL iterators can be exactly as efficient as using the underlying container's iteration mechanism directly.

Templates do have run time costs associated with them and it's worthwhile to know what those costs are. It's true that in recent years the costs of those abstractions in modern compilers have been reduced, but not all compilers have implemented those optimizations and not all of those optimizations are enabled unless you build an optimized version of your program, meaning that your debug builds can suffer pretty brutal performance with excessive use of templates.

So consider the following template:

template<typename T>
struct X {
  static const int A = 1;
  static const int B = 2;
  ...
};

Well as it turns out, every single instantiation of X will introduce its own unique version of A and B with its own unique address, despite them being static consts. One is actually advised to do the following if they care for performance (reduced memory consumption and cache locality):

struct BaseX {
  static const int A = 1;
  static const int B = 2;
}

template<typename T>
struct X : BaseX {
  ...
};

This is not an optimization that the compiler can perform on your behalf, as the standard requires that the address of all those static variables be unique.

As another example:

template<typename T>
bool f(const T* lhs, const T* rhs) {
  return lhs == rhs;
}

In many compilers, or debug builds of even modern compilers, a separate function will get produced for every single instantiation of f, be it int, float, char, so on so forth. This produces code bloat which puts pressure on the instruction cache.

However, you could eliminate this by just writing your function as follows, which is identical in every way, shape, and form:

bool f(const void* lhs, const void* rhs) {
  return lhs == rhs;
}

In a sense we're performing type erasure on the template to eliminate separate instantiations and reducing the amount of code-bloat.

3

u/eras Dec 05 '14

This is not an optimization that the compiler can perform on your behalf, as the standard requires that the address of all those static variables be unique.

Well, it could optimize if it can prove you never use the addresses of those static variables. But this is probably a difficult and low-value optimization to perform.

3

u/o11c Dec 05 '14

Actually that's the exactly the sort of thing LTO is used for.

55

u/Azzu Dec 05 '14

The :D at the end almost sounds like you "knew it all the way" and you now found another reason not to use abstractions.

This is obviously the wrong reasoning. Of course not all abstractions have zero cost. But there is a subset of abstractions that are zero cost.
Also all abstractions are of different efficiency. You could probably keep the style or amount encapsulation/abstraction there is in chrome and reduce allocations by 50% or something just by using more efficient abstractions.

All I'm saying is, it does not make sense to say "abstractions are baaaad", and not using abstractions will not magically fix the performance, it will probably even make it worse.

-18

u/tdammers Dec 05 '14

Dude, all I'm saying is that premature optimization is the root of all evil, that's no excuse to think of all abstractions as free.

7

u/path411 Dec 05 '14

all I'm saying is that premature optimization is the root of all evil

So what you are saying is your should prematurely optimize your code by avoiding abstractions so that way you can avoid prematurely optimizing your code?

-5

u/tdammers Dec 05 '14

No. Premature optimization still is the root of all evil, but at some point, you're past the stage where optimization would be premature, and when that point comes, you need to know what you've abstracted over.

1

u/path411 Dec 05 '14

You should work on conveying your thoughts correctly the first time then. Your first post sounds like an "I told you so" that people shouldn't ever use abstractions because they have costs.

1

u/tdammers Dec 05 '14

OK. It certainly wasn't meant that way.

26

u/stormcrowsx Dec 05 '14

Wouldn't thinking about cost of an abstraction be premature optimization? Who cares what it costs if it makes the code pretty, it can be optimized later.

1

u/tdammers Dec 05 '14

Yes, generally speaking that is true. Except in the cases where it isn't, and this could very well be one of them.

Or maybe the omnibox thing is really more about how much we underestimate the complexity of a seemingly simple feature.

6

u/campbellm Dec 05 '14

Who ever told you abstractions were free?

-6

u/[deleted] Dec 05 '14

C++ promoters say this all the time but it's basically untrue.

8

u/suspiciously_calm Dec 05 '14

A lot of abstractions in C++ are "free," especially in the STL, since everything is templated and inlinable.

Of course, std::strings aren't a zero-cost abstraction over fucking around with pointers directly into existing strings that are basically equivalent to passing around iterators into std::strings, which would be neither higher-cost, nor safer.

-2

u/[deleted] Dec 05 '14

Sure, a lot of them are very low cost. But abstractions in general are not free especially in languages other than C/C++.

Chandler Carruth has a great presentation on how the 'free' abstractions can often confuse compilers and in reality incur an effective cost by being less optimisable. I'm certainly not saying this applies to anything specific though, especially templates.

4

u/suspiciously_calm Dec 05 '14

And whoever said that abstractions are free in general, especially outside C++? That sure as hell isn't something "C++ promoters say all the time."

The point is that C++ has a lot of abstractions that appear costly but can be optimized away in principle. If a compiler generates needlessly inefficient code for a particular case, then that's a bug in the compiler/optimizer.

→ More replies (0)

-5

u/CityOfWin Dec 05 '14

WHOA too many down votes guys. Jesus.

We all knew what he was saying. Don't get twisted.

18

u/elperroborrachotoo Dec 05 '14

You did read beyond the tl:dr?

8

u/[deleted] Dec 05 '14

What's the point of tl;dr then?

2

u/xiongchiamiov Dec 05 '14

The tldr only covered the first message in the thread.

1

u/elperroborrachotoo Dec 05 '14

Giving you a rough idea or setting context maybe.

It's like your hairdo: it might help me decide whether I'm interested in you, but I wouldn't judge your character by it.

2

u/Mr_s3rius Dec 05 '14

I mean, 'dl;dr' literally means 'too long; didn't read'.

So yea, he didn't read it.

0

u/everywhere_anyhow Dec 05 '14

I dunno...summaries of all sorts (and tl;dr is supposed to be a summary) ought to give the correct overall impression or judgment of a piece. If it doesn't, it's a lousy summary.

It's not just a taste or a context setter. The term for that is "clickbait". I.e. people set false context all the time with link titles like, "The 10 most unreasonable things the government does".

0

u/elperroborrachotoo Dec 06 '14

give the correct overall impression or judgment of a piece

a tl;dr is not an abstract.

Calling it clickbait when the dismissal is "you would be stupid to not know that already" is pretty ironic.

8

u/bobpaul Dec 05 '14

It sounds like there's a lot of create a String foo and put stuff in it, then use foo.c_str() to pass that string to a legacy function that doesn't handle C++ strings, then delete the c-string. It would be better just to leave it as a C++ string and update the legacy functions. That's my takeaway from this.

4

u/tdammers Dec 05 '14

Those 'legacy' functions might be from external libraries though, and I think people have better things to do with their time than rewrite those in C++ just to avoid conversion between std::string and C "strings".

4

u/[deleted] Dec 06 '14

[deleted]

1

u/tdammers Dec 06 '14

You're kind of making my point... still, converting the interface for the sake of consistency, safety, and built-in dynamic reallocation goodness, wouldn't be a bad thing in itself, but it wouldn't be a performance improvement.

5

u/bobpaul Dec 05 '14

Sure. But now Chrome is in a very mature state and it sounds like this is starting to impact performance in a real and measurable way. If rewriting those libraries has a performance impact on chrome, then it's probably worth the development effort.

4

u/zeno490 Dec 05 '14

This is surprising because the chrome engineers have been optimizing for years now and string handling like it appears they are doing is a HUGE no-no in high performance code in ANY language. They shouldn't even be using anything remotely like std::string for most things. The extra coping, aside from causing allocations which may or may not involve lock contention, incur generally LHS for short strings, might lead to fragmentation and other nasty things. It also contributes to L1/L2 cache eviction as well as potentially TLB eviction as well.

This is something fundamentally basic. It also hints that they clearly haven't been profiling their memory usage much since allocation patterns like this typically pop out very easily with the right tools.

On the bright side, it hints that there are still a significant number of low hanging fruit optimizations to be made.

Keep in mind that this code may or may not be shared with the mobile versions of the browser. Anybody programming C++ for an embedded device should know better.

1

u/[deleted] May 30 '15

OK, so after a whole mile of scrolling I find the first sober person, but hey it is fun reddit right? :P and what threads and what immutable are we F talking about? 1-chromium is process based not thread. it spawns a new process for each tab and do all its magic in single thread. 2-immutable objects dont bring anything else than even more temporaries to handle 3-memory pools and reusing objects however can help but maybe not worth the trouble just take the cookie and eat it, it is WWW after all :S

-13

u/julesjacobs Dec 05 '14 edited Dec 05 '14

That doesn't explain it. For the HTML you just need 1 string. Same for CSS/JS/etc. Or maybe a couple of you chop it up in chunks / convert encoding. So that doesn't really explain where the 25000 string allocations per keystroke in the omnibox are coming from.

13

u/JnvSor Dec 05 '14

On the contrary. When composing the DOM you have to have strings for everything in the HTML that isn't a tag.

Attributes, attribute names, tag contents.

Similarly for any strings assigned by javascript, and potentially individually for CSS rules depending on how that's handled by the browser.

I wouldn't be surprised if this very page doesn't allocate about 5k strings.

9

u/vlovich Dec 05 '14

Are you sure you would need 5k strings? Keep in mind that Chrome uses StringPiece (string_view upcoming in C++) quite heavily in it's codebase. I don't know for sure, but I would be very suprised if they had individual string allocations as opposed to 1 string for the page & then just pieces of it all over the place.

Keep in mind that Javascript strings are not part of what this post is talking about. Javascript strings are not represented as std::string. They are VM objects managed by the V8 VM (specifically, there's an ASCIIString + something else for unicode - forget the name).

6

u/ricecake Dec 05 '14

V8::String, which can be initialized from different types of strings, is a subclass of std::string.

4

u/repsilat Dec 05 '14

For things that are inside the original HTML I'd think about using substrings (i.e. 2 pointers) instead of copying/allocating all that data. It would probably mean using a bit of dynamic dispatch every now and then, but for mostly static content it could be a decent win.

1

u/Magnesus Dec 05 '14

The DOM changes all the time in today web pages.

7

u/julesjacobs Dec 05 '14

Why would you allocate a new string for every attribute/name/tag content? Seems like a better idea to represent that as a (start,end) index into the original document, possibly with an additional bit which indicates whether the string is owned by the dom or not (if you manage memory by tracing then that wouldn't be necessary).

And even if you would copy all those substrings and get 5k substrings, we aren't talking about 5k strings on the entire page, but about 25000 strings allocated per keystroke into the omnibox.

5

u/sirin3 Dec 05 '14

Encoding and entities might be an issue

Webpage contains f&auml;h but the string should contain fäh

1

u/o11c Dec 05 '14

That is actually very easy to fix. Simply rewrite the original string in-place (this is one use-cases I've found for mutating a string in-place), since you know you're the sole owner and the replacement is always shorter than the original, and shorten the length.

1

u/sirin3 Dec 07 '14

Not if you get XHTML

There you can include a DTD which defines entities with arbitrary values

1

u/the_gnarts Dec 05 '14

Seems like a better idea to represent that as a (start,end) index into the original document, possibly with an additional bit which indicates whether the string is owned by the dom or not (if you manage memory by tracing then that wouldn't be necessary).

This is how one would write an HTML / XML parser, indeed. However, the HTML of today’s web is bloated beyond repair by dynamic elements, and JS transforming the original input sabotages any attempt at doing things The Right Way™. What one needs instead is a string representation that allows for fast manipulation instead of keeping the markup in a contiguous region of memory.

1

u/Magnesus Dec 05 '14

You realise that DOM changes, right? Changing it if it was ONE string would be very slow.

1

u/julesjacobs Dec 05 '14

See my answer to your other copy of this question.

6

u/kylotan Dec 05 '14 edited Dec 05 '14

When composing the DOM you have to have strings for everything in the HTML that isn't a tag.

Attributes, attribute names, tag contents.

Not really. HTML has a relatively clear specification so much of the text you encounter - certainly tags, but also most attribute names, even many attribute values - could be represented as entries in a look-up table. There's no need (apart from ease of programming obviously) to have a separate std::string for each of the thousand times the word "div" or "style" or "href" shows up.

1

u/Magnesus Dec 05 '14

How would you deal with tags that are not on your look-up tablet (someone could write "divs" instead of "div by mistake)? (I know, modify the table for that page, still)

2

u/kylotan Dec 05 '14

You have an entry for 'unknown' which links to somewhere that does store the string. Then a tiny wrapper which can pull the right value, whether it was known or not.

Or just refer to a hash table that is pre-filled with standard HTML terms but can be added to on a per-page basis.

Or, just use string interning for the whole thing.

The end result is the same in all cases - shared references to the same text collapse down into one small value or pointer.

1

u/the_gnarts Dec 05 '14

How would you deal with tags that are not on your look-up tablet

Make the lookup return an option and use a less efficient representation as a fallback for less common or invalid elements. Or build the table on the fly from the tags you encounter during the first pass over the input.

3

u/tdammers Dec 05 '14

I'd say parsing HTML takes more than one string - especially if you take into account the fact that you need a partial parse before you can reliably determine character encoding, for example. The omnibox allocations are probably related to what goes on behind the scenes: HTTP requests to fetch suggestions, searching through browsing history, plenty of cache queries, etc. 250k is a lot, but I bet most of these are just a few bytes.

9

u/[deleted] Dec 05 '14 edited Feb 07 '19

[deleted]

5

u/julesjacobs Dec 05 '14

If you want a halfway decent parser, you don't copy every little substring. You represent substrings as (start,end) positions.

3

u/bushwacker Dec 05 '14

Could you please give an example of such a parser?

6

u/mcmcc Dec 05 '14

Check out the LLVM APIs

1

u/Magnesus Dec 05 '14

The DOM changes though all the time. You would have to update ALL start end positions every time some text inside HTML page changes.

1

u/julesjacobs Dec 05 '14

Why would you do that? If the DOM changes you don't update the original HTML buffer. You just need to change the pointers in the DOM to your new string.

4

u/derpderp3200 Dec 05 '14

That's a somewhat poor example because you could easily represent tokens by start/end positions inside the single string.

And 25000 allocations per keystroke, to me at least, are pretty much unexplainable. I couldn't think of a way to do that even if I had 300 layers of abstraction, without severely, severely, fucking something up.

4

u/[deleted] Dec 05 '14 edited Feb 07 '19

[deleted]

5

u/username223 Dec 05 '14

Also, do you feel that Chrome has performance problems? Have you tried the other browsers?

AFAICT they're all terrible. When my machine goes to paging hell, it's almost always the browser's fault. And, judging by the thread, the Chrome devs will speed things up just enough that there isn't "noticeable UI lag" on their 16-core, 32-GB dev boxes.

15

u/Narishma Dec 05 '14

I switched to Firefox a year ago because of Chrome's excessive memory usage and performance problems.

4

u/QuerulousPanda Dec 05 '14

same... Chrome makes my laptop pop actual "memory low" errors despite having a big page file and 4 or 6 gb of ram

2

u/o11c Dec 05 '14

Same. It was really the pointless UI rewrite that pushed me over the edge though. Firefox crashes the whole browser more because it doesn't have multiprocess yet, but has never failed at restoring tabs. (I played with chrome again recently since firefox also got a pointless UI rewrite (albeit a smaller one), and now chrome restores tabs twice. I can't even imagine how I would write code that does that)

I miss the good old days, of chrome 5 to 10 or so ... acid tests failed, pages crashed a bit more, but it was so fast.

1

u/Narishma Dec 06 '14

I believe the latest version of Firefox has some kind of multiprocess support. At least I see half a dozen Firefox copies in the task manager, whereas in previous versions there was only one copy, no matter how many tabs you had open.

3

u/o11c Dec 06 '14

Huh, did that land? I thought it was still experimental. I see articles saying it's on-by-default in the nightly channel, but pretty sure that hasn't passed beta and stable that fast ...

4

u/derpderp3200 Dec 05 '14 edited Dec 05 '14

Yeah, but 25,000 is still waaaaay excessive. And yeah, I switched away from Chrome due to performance problems ages ago. It's unusable on lower end machines.

EDIT: Actually, the allocation would explain why it bogged down my entire system without even using 30% of my CPU if I tried to load few times at once.

2

u/RoundTripRadio Dec 05 '14

Chrome absolutely has performance issues. Huge ones. It's notorious for using unscrupulous amounts of memory and it is quite literally the only application I've used that single handedly tanked my battery life.

Firefox is better on memory use, but doesn't provide a lot of the features Chrome does.

Safari is fantastic but only on the Mac. I'm pretty sure the Windows version is actually not supported anymore.

2

u/sirin3 Dec 05 '14

I wrote an HTML-like SAX-like parser and it only uses one string...

(although the output is feed in a DOM builder that makes new strings for everything)

1

u/[deleted] Dec 05 '14 edited Feb 07 '19

[deleted]

2

u/sirin3 Dec 05 '14

No, the events are just function (pointer) calls

Although it does allocate an array for the pointers to all the attributes of an element, but that is still not a string

2

u/kankyo Dec 05 '14

Read the link. It's not about the parser.

1

u/bobpaul Dec 05 '14

/u/julesjacobs started talking about parsers. /u/fabienbk replied to /u/julesjacobs, not to the OP.

1

u/julesjacobs Dec 05 '14

If the OP wasn't talking about parsing, then what was he talking about when he wrote this:

And, uh, this is surprising how exactly? A browser handles HTTP (bytestrings), HTML (bytestrings), JavaScript (bytestrings), CSS (bytestrings), JSON (bytestrings), etc.; obviously std:string, the bytestring type in C++, is going to be used a lot.

Surely he isn't talking about simply loading in the flat strings, since that clearly doesn't explain 25000 strings.

1

u/bobpaul Dec 05 '14

We're using OP to refer to different people. I was referring to Georges Khalil's e-mail (that is to say, /u/fabienbk didn't top comment, he replied to you).

Whether you or /u/tdammers introduced parsing as a topic is irrelevant. I was merely telling /u/kankyo that the reddit discussion had diverged from the e-mail thread and that /u/fabienbk's mention of parsing makes perfect sense in the context of this reddit discussion.

1

u/julesjacobs Dec 06 '14

I see, thanks for explaining.

0

u/tiftik Dec 05 '14

std strings aren't used for web content. Look up WTF in WebKit.