C++ – std::string implementation in GCC and its memory overhead for short strings

ccompiler-constructionmemory-managementstring

I am currently working on an application for a low-memory platform that requires an std::set of many short strings (>100,000 strings of 4-16 characters each). I recently transitioned this set from std::string to const char * to save memory and I was wondering whether I was really avoiding all that much overhead per string.

I tried using the following:

std::string sizeTest = "testString";
std::cout << sizeof(sizeTest) << " bytes";

But it just gave me an output of 4 bytes, indicating that the string contains a pointer. I'm well aware that strings store their data in a char * internally, but I thought the string class would have additional overhead.

Does the GCC implementation of std::string incur more overhead than sizeof(std::string) would indicate? More importantly, is it significant over this size of data set?

Here are the sizes of relevant types on my platform (it is 32-bit and has 8 bits per byte):

char: 1 bytes
void *: 4 bytes
char *: 4 bytes
std::string: 4 bytes

Best Answer

Well, at least with GCC 4.4.5, which is what I have handy on this machine, std::string is a typdef for std::basic_string<char>, and basic_string is defined in /usr/include/c++/4.4.5/bits/basic_string.h. There's a lot of indirection in that file, but what it comes down to is that nonempty std::strings store a pointer to one of these:

  struct _Rep_base
  {
size_type       _M_length;
size_type       _M_capacity;
_Atomic_word        _M_refcount;
  };

Followed in-memory by the actual string data. So std::string is going to have at least three words of overhead for each string, plus any overhead for having a higher capacity than `length (probably not, depending on how you construct your strings -- you can check by asking the capacity() method).

There's also going to be overhead from your memory allocator for doing lots of small allocations; I don't know what GCC uses for C++, but assuming it's similar to the dlmalloc allocator it uses for C, that could be at least two words per allocation, plus some space to align the size to a multiple of at least 8 bytes.

Related Solutions

C++ – How to concatenate a std::string and an int

In alphabetical order:

std::string name = "John";
int age = 21;
std::string result;

// 1. with Boost
result = name + boost::lexical_cast<std::string>(age);

// 2. with C++11
result = name + std::to_string(age);

// 3. with FastFormat.Format
fastformat::fmt(result, "{0}{1}", name, age);

// 4. with FastFormat.Write
fastformat::write(result, name, age);

// 5. with the {fmt} library
result = fmt::format("{}{}", name, age);

// 6. with IOStreams
std::stringstream sstm;
sstm << name << age;
result = sstm.str();

// 7. with itoa
char numstr[21]; // enough to hold all numbers up to 64-bits
result = name + itoa(age, numstr, 10);

// 8. with sprintf
char numstr[21]; // enough to hold all numbers up to 64-bits
sprintf(numstr, "%d", age);
result = name + numstr;

// 9. with STLSoft's integer_to_string
char numstr[21]; // enough to hold all numbers up to 64-bits
result = name + stlsoft::integer_to_string(numstr, 21, age);

// 10. with STLSoft's winstl::int_to_string()
result = name + winstl::int_to_string(age);

// 11. With Poco NumberFormatter
result = name + Poco::NumberFormatter().format(age);

is safe, but slow; requires Boost (header-only); most/all platforms
is safe, requires C++11 (to_string() is already included in #include <string>)
is safe, and fast; requires FastFormat, which must be compiled; most/all platforms
(ditto)
is safe, and fast; requires the {fmt} library, which can either be compiled or used in a header-only mode; most/all platforms
safe, slow, and verbose; requires #include <sstream> (from standard C++)
is brittle (you must supply a large enough buffer), fast, and verbose; itoa() is a non-standard extension, and not guaranteed to be available for all platforms
is brittle (you must supply a large enough buffer), fast, and verbose; requires nothing (is standard C++); all platforms
is brittle (you must supply a large enough buffer), probably the fastest-possible conversion, verbose; requires STLSoft (header-only); most/all platforms
safe-ish (you don't use more than one int_to_string() call in a single statement), fast; requires STLSoft (header-only); Windows-only
is safe, but slow; requires Poco C++ ; most/all platforms

C++ – initializing std::string from char* without copy

You can't actually form a std::string without copying the data. A stringstream would probably reuse the memory from pass to pass (though I think the standard is silent on whether it actually has to), but it still wouldn't avoid the copying.

A common approach to this sort of problem is to write the code which processes the data in step 3 to use a begin/end iterator pair; then it can easily process either a std::string, a vector of chars, a pair of raw pointers, etc. Unlike passing it a container type like std::string, it would no longer know or care how the memory was allocated, since it would still belong to the caller. Carrying this idea to its logical conclusion is boost::range, which adds all the overloaded constructors to still let the caller just pass a string/vector/list/any sort of container with .begin() and .end(), or separate iterators.

Having written your processing code to work on an arbitrary iterator range, you could then even write a custom iterator (not as hard as it sounds, basically just an object with some standard typedefs, and operator ++/*/=/==/!= overloaded to get a forward-only iterator) that takes care of advancing to the next fragment each time it hit the end of the one it's working on, skipping over whitespace (I assume that's what you meant by trim). That you never had to assemble the whole string contiguously at all. Whether or not this would be a win depends on how many fragments/how large of fragments you have. This is essentially what the SGI rope mentioned by Martin York is: a string where append forms a linked list of fragments instead of a contiguous buffer, which is thus suitable for much longer values.

UPDATE (since I still see occasional upvotes on this answer):

C++17 introduces another choice: std::string_view, which replaced std::string in many function signatures, is a non-owning reference to a character data. It is implicitly convertible from std::string, but can also be explicitly constructed from contiguous data owned somewhere else, avoiding the unnecessary copying std::string imposes.

Best Answer

Related Solutions

C++ – How to concatenate a std::string and an int

C++ – initializing std::string from char* without copy

Related Topic