21

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

Improve this question
6
  • 2
    On what platform do you get this result? I ask because I've seen platforms (Texas Instruments DSPs) where a byte is considered to be 16-bits. Commented Feb 20, 2011 at 17:34
  • What is the result of sizeof(char*) on your platform? Commented Feb 20, 2011 at 17:39
  • 2
    I'm guessing that std::string contains a pointer to a dynamically-allocated string implementation object. Keep in mind that GCC's string are COW (copy on write). I've tried looking at gcc's basic_string.h for some insights, but got a headache trying to read the cryptic code. Commented Feb 20, 2011 at 17:52
  • 1
    @Emile Cormier: Number of bits in a byte is defined by CHAR_BITS Commented Feb 20, 2011 at 18:21
  • Are the string Imutable? If so then you may save space. But if they need to be manipulated then it is unlikely that you will save anything because of the extra complexity you introduce. Commented Feb 20, 2011 at 18:31

3 Answers 3

Reset to default
16

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.

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

3 Comments

Many implementations use the Small Buffer Optimization to not do allocations for strings less than 3-7ish characters, does GCC not do this?
I just checked microsoft's implementation, which allows strings of up to 15 chars (plus NULL) with no allocation.
gcc uses cow string that is nonconforming.. they will switch to sso when they can do a breaking abi change... Herb mentions it often...
9

I'm going to guess you are on a 32 bit, 8 bit per byte platform. I'm also going to guess that at least on the gcc version you are using, that they are using a reference counted implementation for std::string. The 4 byte sizeof you see is a pointer to a structure containing the reference count and the string data (and any allocator state if applicable).

In this design of gcc's the only "short" string has size == 0, in which case it can share a representation with every other empty string. Otherwise you get a refcounted COW string.

To investigate this yourself, code up an allocator that keeps track of how much memory it allocates and deallocates, and how many times. Use this allocator to investigate the implementation of the container you're interested in.

Improve this answer

Comments

3

If it's guaranteed that ">100,000 strings of 4-16 characters each", then don't use std::string. Instead, write your own ShortString class. It's interesting that "sizeof(std::string) == 4", how is that possible? What are sizeof(char) and sizeof(void *)?

Improve this answer

4 Comments

It's always possible. It could just hold a pointer to some kind of internal string structure, which holds all the usual data, like length and pointer to the string data.
sizeof(char) is always 1.
@jalf If it just holds a pointer to an internal structure, then the actual memory cost is added by sizeof(void *) when the string is longer than sizeof(void *)-1. I could imagine some size optimization based on the pointer encoding is done for std::string when the size is small.
@albert: I don't understand what you mean. But to get sizeof(std::string) == 4, you just need to be on a 32-bit system (where pointers are 4 bytes wide), and then store a single pointer, and no other members inside the string class. That pointer can just refer to a secondary data structure containing length/capacity and a pointer to the actual string buffer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.