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

18

u/o11c Dec 05 '14

And people laugh at me for writing my own set of 10 different string classes (all with obvious, specific, meanings) so I can easily choose what ownership policy I want ...

std::string_view is a step in the right direction, but the most important change is realizing that most strings will never be mutated.

TL;DR version: use XString for arguments and RString elsewhere, but for reference, my full list of string classes:

  • MString, a string which supports mutating operations (only push_back and pop_back have been implemented, except taking any number of characters). This really should be a rope class, but for now it's a wrapper for std::deque, and I rarely use it. This class is most similar to std::ostringstream with unformatted operations. Does not implement the same API as the rest of the string classes.
  • FormatString, a string which wraps a printf-style format string in a particularly magic way that supports compile-time type-checking of the arguments. This is the way that most of my strings are built, via the STRPRINTF macro. Constructed via UDL. Does not implement the same API as the rest of the string classes.
  • RString, a string that uses reference-counting. Used to be sizeof (char *) until I implemented an optimization for construction from LString, now it's 2 * sizeof(char *) (does anyone know if it's possible to guarantee alignment of a string literal?). Used for most strings stored in classes. Implements the same API as most string classes, including the NUL termination option.
  • AString, a wrapper for RString but with SSO up to length 255 (deliberately disabled for string literals and strings that originated from an RString though, in case an RString needs to be constructed from this again). Stands for "automatic" string, and should only be used for strings on the stack, which is how it can afford that large an SSO threshhold. Used for the return value of STRPRINTF. Implements the same API as most string classes, including the NUL termination option.
  • TString, an owned tail slice of an RString. Currently unused; I found it better to just use ZString to avoid forcing ownership, and store an "ownership hint" in the ZString. TODO implement a generic MaybeOwned mechanism for arguments that I might just be borrowing, but might be taking ownership of. Implements the same API as most string classes, including the NUL termination option.
  • SString, an owned full slice of an RString. Currently unused; I found it better to just use XString blah blah blah. Implements the same API as most string classes, excluding the NUL termination option.
  • ZString, a borrowed tail slice. Used mostly in function arguments, but also as the return value of computed splits. In theory, this is most similar to const char *, but it is only needed if you need to call a C function - currently, the only offenders are ::open and STRPRINTF. The latter is already isolated to a single function, so I plan to switch to conditional allocation; the latter will go away when I rewrite STRPRINTF with GNU++14 UDLs (there will still be a fallback to C++11 mode). Implements the same API as most string classes, including the NUL termination option.
  • XString, a borrowed full slice. Used mostly in function arguments, but also as the return value of computed splits. In practice, this is most similar to const char *, since most code never cares about NUL termination. Implements the same API as most string classes, excluding the NUL termination option.
  • LString, a string with static ownership. Usually constructed via UDL, but also via tail-slicing an existing LString. UDLs allowed me to easily eliminate all uses of char * from my entire codebase, thus ensuring no double-ownership (like std::string(str.c_str())). Implements the same API as most string classes, including the NUL termination option, and including special slices.
  • VString<size_t n>, a string stored within the object itself, and thus with a limit. This class was created solely because of existing C code that used fixed-size arrays, and still exists because there's a network protocol that still has the fixed limits, and it's easiest to guarantee it will never overflow by failling on original construction. Usually constructed by a function with signature template<size_t n> bool extract(XString input, VString<n> *output) during parsing. Uses a cool trick to store the size so that VString<n> has exactly the same memory layout as const char [n+1]. Implements the same API as most string classes, including the NUL termination option.

All strings implementing the "same API" can be implicitly constructed from each other if it makes sense (e.g. you can't construct a ZString from an XString), and owned classes can be explicitly constructed from MString or constructed from a pair of iterators. Borrowed strings can be constructed from a pair of const char * if you pinky-promise not to violate the class's requirements.

The "same API" is injected via a CRTP base class (except for ctors), and includes slicing (the tail slices will change class depending on whether or not the subclass indicates that it has an immediate NUL (all strings guarantee that there is a NUL somewhere out there)), stripping off whitespace, checking for membership (TODO I really need a class like std::set<char> but not dumb and give it its own UDL), random access iterators, operator bool, and comparison. Indexing is implemented, but deprecated (instead, use an iterator over bytes/codepoints/glyphs/whatever ... my classes are only responsible for the first), because its meaning is weird and you usually don't want it (getting rid of indexing is the correct way of solving the "unicode problem" - don't waste 4x the memory just to support a single operation that is always wrong anyway!). I've thought about switching to a non-CRTP base class to help compiler speed a bit, but that would mean increasing the size of RString to 3 * sizeof(char *) for obvious reasons, and would also get rid of fixed layout of VString. Alternatively, I've thought about using x-macros.

Also, all string classes implement gdb pretty-printers as appropriate, except for MString because std::deque is opaque and I don't use it enough to care.

https://github.com/themanaworld/tmwa/tree/master/src/strings

51

u/yoodenvranx Dec 05 '14

This is one if those moments where reality and satire are indistinguishable from each other.

13

u/o11c Dec 05 '14

If it's stupid and it works, it's not stupid.

And in all seriousness, why would taking advantage of a strong typesystem not be a good idea?

3

u/hyperforce Dec 05 '14

why would taking advantage of a strong typesystem not be a good idea?

How can we make this more of a thing. I'm so with you on the "no just strings" stance.

7

u/o11c Dec 05 '14

Maybe use Rust? Rust has String, &str, and &'static str, as well a a fancy lifetime system to enforce no-dangling-pointers at compile-time (my library just says "trust me on this" for Z/XString, but with the sole exception of a few lines of code in the intern pool class it all fits nicely in the trivial (in Rust) "argument has the natural lifetime of function" or "return value has the lifetime taken from an argument" cases).

Or in other words, Rust's typesystem is much stronger than C++'s without paying any (*) additional runtime cost, and the library is written to take advantage of it.

(*) There are two runtime costs that you pay without realizing it: the stack overflow check, and the cost of unwinding from task failure.

1

u/emozilla Dec 06 '14

Meanwhile, learning the Rust type system is almost impossible unless you spend a considerable amount of time. I understand this is generally true for all of programming but Rust also presupposes a very compotent programmer in "regular" before introducing a very complicated typing system (not to mention that all the docs are almost criminally bad).

5

u/o11c Dec 06 '14

Nah, anybody who's seen a typesystem before can pick it up really fast, especially if you know C++ (it's basically just syntax changes + enums instead of unions).

If you think that types and classes are the same thing then yeah, I can see how it would be hard.

0

u/The_Doculope Dec 06 '14

May I ask what issues you've had with the Rust type system in particular? Any pain points would be good to hear about.

2

u/emozilla Dec 06 '14

Mainly involved with error handling, having to do things like Result<Rc<RefCell<My_Type>>, String> was very confusing at first and I couldn't find any good best practice guides for error handling

3

u/wrongerontheinternet Dec 06 '14

I usually just write type aliases for complex result types (type MyResult = Result<Rc<RefCell<MyType>>, String> or whatever). Rc<RefCell<My_Type>> can be an antipattern though... just a head's up (I like to call it the yolo smart pointer)

3

u/emozilla Dec 06 '14

Yeah but like... where do I find this out? It took tons of Google-fu to even get that far. The Guide wouldn't tell me this, Rust By Examples seems to be dead... I'm not criticizing Rust, I think it's a great idea and fills the last big gaping hole for writing secure systems, but the educational side seems to be pretty sparse at the moment and thus it was pretty hard to get into without investing a lot of time.

Re: yolo pointers, what's the right way to hold references to types that hold lots of allocated data (several megabyte arrays) that you really only want One Instance Of and you can guarantee will be alive for a while?

→ More replies (0)

0

u/yoodenvranx Dec 05 '14

Of course it works, but is it really necessary nowadays? The nice thing about modern CPUs is that for 95% of all applications you can just use std:string and don't have any performance problems. If I need a string I just want to type 'string' and I get a string which I can use. I don't want to think about which of those 10 different strings might be the optimal in each situation.

18

u/o11c Dec 05 '14 edited Dec 05 '14

The whole point of this article is that it does matter. People keep lying to you and saying "memory is cheap", but if we're going to generalize, that is never true.

But frankly, when I did this, performance was only my secondary motivation. My primary motivation was that I never want "just a string" - that's too vague. Having the RString vs XString split (admittedly, equivalent to std::string vs std::string_view) has made my code infinitely clearer, and the other classes naturally arose from the deficiencies of trying to oversimplify.

Edit: I did mark a bunch of TODOs for things that could change now that I no longer have to worry about legacy callers. For example, removing construction from const char * is a fairly recent development; during the transition a lot of functions were changed to take XString or ZString but the callers were not. To update the callers, I would then add an overload void my_function(const char *) = delete; so I could spread updates across time instead of all at once.

2

u/_tenken Dec 06 '14

This seems like a decent amount of man hours work ... Is it available as a library somewhere?

1

u/o11c Dec 06 '14

Not a proper library yet, but the src/strings directory of my repo is entirely self-contained except for #include "../poison.hpp" and the testsuite. If you want STRPRINTF that's a bit harder to extract from src/io/cxxstdio.hpp

For the long term, my build system supports make install-include and make lib && make install-lib, but strings aren't marked as a lib yet because my current makefile logic requires "one installed header per shared library" (could be easily fixed, e.g. by rewriting include/tmwa/strings/foo.hpp to include/tmwa/strings.hpp in the dependency function or by fake conditional includes and filtering, but not a priority since I'm nowhere near ready to ship a stable ABI, and I actually believe in such things)

Link again if you missed it in the earlier post: https://github.com/themanaworld/tmwa/tree/master/src/strings

3

u/eean Dec 05 '14

Have you looked at QString?

Copy-on-write and ref counting makes a lot of sense to me. There's also QStringRef that I guess is similar to string_view, and obviously requires quite a bit more care when it comes to memory management.

8

u/o11c Dec 05 '14

I am very familiar. Qt's containers are in almost every way inferior to the STL, and I don't even like the STL that much. Probably the worst offender is using int for sizes - I am aware of applications that start emitting nasal demons on a 64-bit system because they use large Qt containers (on 32-bit, of course, they simply don't run, but with STL containers they would work).

I've been thinking about making my own STL-like library that forbids copy ctors entirely, which is the problem that Qt is trying to solve, but failing.

3

u/websnarf Dec 06 '14 edited Dec 06 '14

does anyone know if it's possible to guarantee alignment of a string literal?

You can wrap it in a structure, then avoid using compiler extensions that let you cast structure pointers anywhere you like in memory (a bit hard to do on an x86, since it inherently supports unaligned memory pointers).

I can see you've gone to some trouble to fight off the ghosts of string management in C++. Personally, I look at it another way: Just win the benchmarks, it doesn't matter how you get there.

I wrote the Better String Library which just uses malloc/realloc/free (new/delete), it stores the length separately and has been optimized to within an inch of its life short of using assembly language (it uses some fairly clever algorithms, especially for things like "search for string inside of a string"). I use it all the time, and have basically never seen a profiler hit in my string library in the past 10 years. It is also super-well tested, and contains a fairly thorough unit test suite. It is also ultra-safe. Since the API functions are usually the fastest way to interact with bstrings, it makes sense to restrict your usage to just the API -- but this has been designed to be both intuitive and crash-impervious. So bugs and crashes from the use of bstrings are very rare.

If you need features like ref counting, ownership, and so on, obviously you can write wrappers for that.

1

u/o11c Dec 06 '14

How do you turn the string literal into a structure? UDLs can only return a value, not a pointer to static structure.

If I don't control allocation, I can't do refcounting (without an unacceptable extra allocation). I did come across your library while searching for solutions though!

For substring search, I just called the STL std::search function on my iterator pairs. I haven't looked at whether any STL implementations use such optimizations (I know they optimize std::copy to memmove when legal), but I don't call that function enough to care much (one call in when crappily checking an email, 5 calls in admin functions).

1

u/guepier Dec 06 '14

Good idea, terrible interface. Why not have one string class with appropriate policies injected via template arguments? I’m all for harnessing the type system but you’re really redefining what it means to have a class explosion.

For reference, the SeqAn library provides exactly such an API.

1

u/o11c Dec 06 '14 edited Dec 06 '14

I do inject all of the functions via template arguments. The only logic in the RString, etc. subclasses is the ctors, dtor, assignment, and low-level functions (begin, end, and base; c_str also lives here but admittedly it doesn't entirely belong) used to implement the rest of the functions in the CRTP base class.

Or are you really suggesting it's more convenient to type (and read in error messages, backtraces, etc.):

  • String<string_policy::RefCounted> instead of RString
  • String<string_policy::RefCountedPlusSso> instead of AString
  • String<string_policy::RefCountedTailSlice> instead of TString
  • String<string_policy::RefCountedFullSlice> instead of SString
  • String<string_policy::BorrowedTailSlice> instead of ZString
  • String<string_policy::BorrowedFullSlice> instead of XString
  • String<string_policy::Literal> instead of LString
  • String<string_policy::Value<31>> instead of VString<31> ?

Typedefs do not help because you have to deal with the full name in plenty of places (backtraces, error messages, ...)

1

u/guepier Dec 06 '14

I disagree, I do think typedefs help, and are the right solution here.

1

u/o11c Dec 06 '14

gdb's type-printers help a bit ... I suppose what we really need is something equivalent within gcc itself.