10

In a project about a decade ago, we found that std::vector's dynamic allocations caused a serious performance drain. In this case it was many small vectors allocated, so the quick solution was to write a vector-like class wrapping around a stack-based pre-allocated char array used as the raw storage for its capacity. The result was a static_vector<typename T, std::size_t Max>. Such a thing is easy enough to write if you know a few basics, and you can find quite a few such beasts on the web. In fact, boost has one, too, now.

Working on an embedded platform now, we happen to need a static_basic_string. That would be a string that pre-allocates a fixed maximum amount of memory on the stack and uses that as its capacity.

At first I thought this should be fairly easy (it could be based it on the existing static_vector, after all), but looking again at std::basic_string's interface I am not so sure anymore. It is way more complex than std::vector's interface. Especially implementing the family of find() functions std::basic_string comes with is more than just a tedious task.

That got me thinking again. After all, this is what allocators were created for: replace allocation based on new and delete with some other means. However, to say that the allocator interface is unwieldy would be an understatement. There are a few articles out there explaining it, but there is a reason I have seen so very few home-grown allocators in the last 15 years.

So here is my question:

If you had to implement a basic_string lookalike, how would you do it?

  • Write your own static_basic_string?
  • Write an allocator to pass to std::basic_string?
  • Do something I did not think of?
  • Use something from boost I am not aware of?

As always, there is a rather essential restriction for us: Being on an embedded platform, we are tied to GCC 4.1.2, so we can only employ C++03, TR1, and boost 1.52.

Improve this question
20
  • This might be better suited for programmers.se since it's entirely in the designing phase Commented Oct 14, 2014 at 8:48
  • @Marco: Mhmm. Looking at programmers.stackexchange.com/help/on-topic, "software architecture and design" is indeed listed there. However. 1) It's buried within a lot of other topics that have nothing to do with my question and seems to indicate they are talking about architecture on a very different level, and 2) I don't consider this a pure design question, because the interface is fixed (it's std::basic_string's interface) and I am more asking about how to implement it. Yes, this is fuzzy, but I do believe the question belongs here more than there. ICBWT. Commented Oct 14, 2014 at 9:05
  • 2
    Why do you think allocators are so scary?.. I've used them on a couple of occasions; after all, this is what they are for. Derive "stack_string" from "basic_string", include allocator with built-in buffer as a member, pass that allocator to basic_string ctor. Commented Oct 14, 2014 at 9:17
  • Is dynamic allocation totally out of the question, or would it be acceptable to do one dynamic allocation per std::basic_string instance, regardless of how its content changes later? Commented Oct 14, 2014 at 9:17
  • 1
    @CouchDeveloper / @LightnessRacesinOrbit: consider a struct with lots of small string members - having them near-contiguous in memory - typically on the same page(s) of cache - sounds very advantageous compared to having each stored by pointers that - even if from the same custom pool - might be impractical to avoid allocating "discontiguously" without other undesirable coordination overheads. Commented Oct 14, 2014 at 10:57

7 Answers 7

Reset to default
4

The first question is: how much of the extra interface do you use? Most of std::string's additional interfaces can be trivially implemented using functions in <algorithm> (e.g. std::find, std::find_if and std::search), and in a lot of cases, there are large chunks of it that won't be used anyway. Just implement it on an as needed basis.

I don't think you can make this work with a custom allocator. The only way to get the memory "on stack" would be to declare it as a member of the custom allocator, which would create all sorts of problems when copying them. And allocators must be copiable, and the copies must be idempotent.

Perhaps you can find a free implementation on the net of std::string which uses the small string implementation; then modify it so that the cutoff size (beyond which it uses dynamic allocation) is larger than any strings you actually use. (There are several open-source implementations of the standard library available; the one delivered with g++ still uses COW, but I suspect that most of the others use SSO.)

Improve this answer
Sign up to request clarification or add additional context in comments.

16 Comments

Regarding the custom allocator: he wrote that he wants to wrap around an existing stack-allocated buffer, which should be possible, right?
@leemes Maybe. There's still the problem of scope: when he returns a string, the copy will use the same allocator as what is being copied. If that in turn uses a stack-allocated buffer, he's going to be in deep trouble.
In fact, I have no idea how to make allocators use local stack space, but I wondered whether someone could point out an easy way. Regarding finding an implementation that employs SSO: As I said, I am not worried about the memory management. I have implemented this already (for that static_vector) and I could even base static_basic_string on that, rather than implementing it again.
Your advice to drop the parts of the interface that are harder to do, namely the find() family, seems good enough to me. I just asked all the developers here today when they had last used one of string's find functions, and it turned out that some had never used them, others once in a decade. So I guess I will just skip them for now.
@sbi I'm about the same, and I do a lot of parsing. 99% of the time, I'll just use the functions in <algorithm>. Similarly, things like insert or replace seem to be pretty rare as well; I'll typically be building up a copy, and just be appending.
|
1

It is easy, write a stack allocator, here's an example:

https://codereview.stackexchange.com/questions/31528/a-working-stack-allocator

With allocators, you can just as easily allocate, for example, from a memory-mapped file, i.e. from the disk drive, or from a static array of chars.

Improve this answer

4 Comments

This solution allocates strings inside a custom stack data structure, not on a true stack that compiler uses to remember return address. It still may work as a solution. I upvote.
This code is in C++14. The requirement was C++03...still, the principle holds, it can be re-written. Note that std::basic_string uses the allocator in weird and wonderful ways, so you will have to add things like comparison operators. Also note that std::basic_string (and other containers) use copy constructor of the allocator liberally, and the stack_store does not handle that gracefully.
@arunasr It is c++11 code. At least this is what I compile it with.
@user1095108 The point is, it is not C++03/C++98. And it will not compile if used with basic_string because it does not implement operator== and struct rebind. I am not sure how it will handle copy operation, but by the look of it, it is not going to be pretty.
1

LLVM ADT has the SmallString class. It also has SmallVector and many other useful classes.

While the current LLVM code base moves towards using C++11, (not-so-)old versions of LLVM support C++03.

Improve this answer

3 Comments

Interesting. Can this be used as a drop-in replacement for std::basic_string?
@sbi its interface looks similar to the basic_string's, but it doesn't have some constructors
Mhmm. I'd rather have a something I can drop in, recompile, and be done. (As I wrote, the interface is to be std::basic_string.) Thanks anyway!
1

An excellent starting point is Alexandrescu's policy-based string class, described in this Dr Dobbs article. It includes a SSO policy that basically does what you want (search the page for SmallStringOpt), and is easy to modify if/as you deem necessary. It's predates C++11 so you're fine there too.

Improve this answer

8 Comments

The intrinsics of memory management for this I have covered. It's the rewriting of some of the other operations that made me question my approach.
@sbi "rewriting of some of the other operations" - when you instantiate Alexandrescu's template with the SSO policy, you get all the other std::string-style operations. How does that not address your concern?
Ah, OK then, if that is a drop-in replacement for std::basic_string, this should work. Thanks, I'll look at it.
@sbi Yup - first paragraph - "...article provides and explains a policy-based basic_string implementation that gives you twelve Standard-compliant canned implementations featuring various optimizations and tradeoffs...". Cheers.
Thanks, I could indeed "borrow" those implementations from there (+1). However, as James has pointed out, I could just as well leave them unimplement for the time being, because they are rarely ever needed.
|
1

There are lots of basic_string implementations, some entirely based on dynamic allocation, some other on dynamic allocation only for string wider than a given length (in fact, they use their own internal buffer when it fits).

Using an allocator is probably not the way to go, since the interface between the string and the allocator assumes that the allocator object is part of the container, but the allocated memory comes from outside the container itself. You can arrange it by implementing an allocator using the POSIX alloca, with all the drawbacks.

The problem when implementing strings on stack is that you cannot let it dynamically grow (may be the stack at that time has something more over) but you also have to take care of operations like += that can make a string longer and longer.

So you end up by preallocating (as an array or as a alloca supplied buffer, within your class or within an allocator does not change the problem) an amount of bytes you'll mostly waste either but not filling them all, or by not using them if the string has grown too much and requires to be dynamic.

There is probably a trade-off tightened to the memory-to-cache communication process (usually runs with 128 bytes or 4KBytes), but it is strongly hardware dependent, so the complexity to afford will not most likely pay for.

A more affordable solution can be an allocator that still allocates on the heap, but has the capability to retain and reuse the returned blocks (up to certain limit) reducing the need to ask the system to allocated / deallocate.

But performance, in this case, may not necessarily benefit if the underlying system already implement new/delete in that way.

Improve this answer

4 Comments

Yes, this certainly requires overallocation. However, the strings in question are usually limited to 16 or 32 characters, so this shouldn't be a problem. Also, this all is to interface with a C API which presumes pre-allocated buffers, which must not be re-allocated, and thus also overallocate.
If that's the case, you need a size_t plus a space that can either contain 32 chars or a pointer (the discriminator is size()<32). Due to the peculiarity of the data, you probably will make it an independent self-contained class, eventually implicitly convertible to ad from std::string. The use of a custom allocators together with basic_string can be dagerous: what happens if a basic_string (that assumes data are outside of it and can be moved around) tries to "move"?
What you describe is SSO. But we can't use that, because it falls back on dynamic memory – which we cannot use here.
Yep, so it seems. Well, that's what I am doing now.
0

I'd use a combination of implementation-defined VLAs and standard algorithms, I should think.

Improve this answer

Comments

-1

This is a working code, but NOT THE RECOMMENDED WAY.

This code has a lot of traces to show what it is doing. It does not check that the size of the allocation request does not exceed the buffer. You can this check if necessary. Note that std::basic_string tries to allocate more than necessary. 

#include <string> #include <iostream> template<typename T, size_t S> class fixed_allocator { typedef std::allocator<T> _base; std::ostream& trace() const { return std::cerr << "TRACE fixed_allocator " << (void*)this ; } public: typedef typename _base::value_type value_type; typedef typename _base::pointer pointer; typedef typename _base::const_pointer const_pointer; typedef typename _base::reference reference; typedef typename _base::const_reference const_reference; typedef typename _base::size_type size_type; typedef typename _base::difference_type difference_type; template<class C> struct rebind { typedef fixed_allocator<C, S*sizeof(C)/sizeof(T)> other; }; T* buffer_; fixed_allocator(T* b) : buffer_(b) { trace() << "ctor: p=" << (void*)b << std::endl; } fixed_allocator() : buffer_(0) { trace() << "ctor: NULL" << std::endl; }; fixed_allocator(const fixed_allocator &that) : buffer_(that.buffer_) { trace() << "ctor: copy " << (void*)buffer_ << " from " << (void*) &that << std::endl; }; pointer allocate(size_type n, std::allocator<void>::const_pointer hint=0) { trace() << "allocating on stack " << n << " bytes" << std::endl; return buffer_; } bool operator==(const fixed_allocator& that) const { return that.buffer_ == buffer_; } void deallocate(pointer p, size_type n) {/*do nothing*/} size_type max_size() const throw() { return S; } }; int main() { char buffer_[256]; fixed_allocator<char, 256> ator(buffer_); std::basic_string<char, std::char_traits<char>, fixed_allocator<char, 256> > str(ator); str.assign("ipsum lorem"); std::cout << "String: '" << str << "' length " << str.size() << std::endl; std::cout << " has 'l' at " << str.find("l") << std::endl; str.append(" dolor sit amet"); std::cout << "String: '" << str << "' length " << str.size() << std::endl; str.insert(0, "I say, "); std::cout << "String: '" << str << "' length " << str.size() << std::endl; str.insert(7, "again and again and again, "); std::cout << "String: '" << str << "' length " << str.size() << std::endl; str.append(": again and again and again, "); std::cout << "String: '" << str << "' length " << str.size() << std::endl; return 0; }

This code has been tested on GCC and LLVM and performs as expected (or unexpected).

The syntax in unwieldy. It is not possible to derive from basic_string and embed the buffer. Far better way is to create a small specialised buffer_string class with the required subset of basic_string interface.

Improve this answer

10 Comments

Have you tried manipulating the string after assigning to it for the first time so that it would need to grow?
The string is created empty and then manipulated (assigned). Does that count as "manipulation so that it needs to grow"? I did not try anything more than you see in the code, but I expect basic_string to simply call "allocate", possibly with the hint, and all it will get is the same buffer.
str.append(" dolor sit amet"); worked perfectly well, if you allocate big enough buffer. basic_string tried to allocate 51 bytes at this, which cause "stack smash" exception with the original program. Having increased the buffer to 60, no problem.
My point is that, when the string needs to reallocate, you simply return the pointer to the current data. However, the string will copy the old data to the newly allocated memory. Yes, I forgot that this would appear to work fine if the start of the string isn't changed. But it's still wrong. (Unless I am – again – missing something, inserting would unveil this flaw.)
Don't be lazy! Cut, paste, compile and play. str.insert(0, "I say, "); works perfectly well.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.