How to implement a string that solely allocates on the stack

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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