8 ms·

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 h

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