Hacker News Reader

Comment by acqq | Hacker News Reader

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.

View on HN

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 [2] 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.)

Some implementations already do such as

* Clang LibC++ see http://stackoverflow.com/questions/21694302/what-are-the-mec...

* MSVC - see comments http://channel9.msdn.com/Series/C9-Lectures-Stephan-T-Lavave...

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

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.

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 < 6 bytes, the null terminator gets stored in one of the earlier bytes. If it's a pointer, the pointer will be word-aligned, which on a 64-bit machine means that you can zero-out the low-order 3 bits (exactly what you need to store the tag) to extract the actual pointer. If it's a null string (the one case we couldn't represent, since we use 0x07 as the tag for pointers), store it with a null first byte, which also gives compatibility with C.

Whether these gymnastics are worth it is debatable. My intuition is that you lose more in bit-twiddling instructions on common operations than you gain by being able to store an extra byte in short strings, but I'd want to benchmark on real data before implementing.

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.

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

https://stackoverflow.com/questions/21694302/what-are-the-me...

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.

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.

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.

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.

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

I think the right approach is to get a decent high level understanding of how compilers work. Some surprising optimizations and failures to optimize become a lot clearer. For example, SSA makes it obvious why there's absolutely no penalty for using lots of named temporary register-sized variables.

Then learn your particular compilers' abilities by research and reading your assembly output. If you're depending on an optimization, always read the output. You might be pleasantly surprised as often as you're disappointed.

Understanding the rules of the language are important too. In C++, pointer aliasing and the worthlessness of 'const' are huge obstacles to some seemingly easy optimizations.

You probably mean N3664 [1]. The compiler is indeed allowed to get rid of allocations in new expressions it deems unnecessary.

You can verify that recent versions of clang allocate no memory in the function

    int f() { return *new int(123); }

[1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n366...

Devirtualization for example.

Interestingly, with Rust, the borrow checker makes it statically safe to know when you can stack alloc.

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.

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.

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

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.

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

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.

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

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-..., which links to 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-smallst....

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

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.

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.

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

You could just use std::array<char, 255>

Do I have all the string functionality, nicely existing in std::string?

Reply on news.ycombinator.com