none
STL string is a memory hog

    Question

  • The size of the STL string is 32 bytes, including 4 bytes of wasted padding in the middle and the 16 bytes buffer for short strings. In a large application STL strings consume extra megabytes of space. In comparison, the size of the STLport's STL string is 24 bytes with the small buffer and it can also be compiled without the buffer, if memory is a concern, in which case its size is only 12 bytes.

    Can you optimize the STL string to at least get rid of the padding? Also, can you provide an implementation that would allow people choose whether to use the internal buffer or not?
    Friday, December 14, 2007 12:45 PM

Answers

  • > Small internal buffer is a good optimization when memory is not an issue.

     

    Actually, it can reduce memory consumption too - remember that dynamic memory allocation involves overheads.

     

    > My comment was that other STL implementations allow developers to build their

    > STL to choose whether to use this optimization or not (again, STLport is a good

    > example of that).

     

    Being able to enable or disable this feature could certainly be useful - however, it can also be a source of problems.  The _SECURE_SCL and _HAS_ITERATOR_DEBUGGING options change the representations of STL containers (what it does to std:: string is more subtle and confusing), so all translation units that are linked into a single binary must be compiled with the same settings, and binaries that pass STL containers and iterators around must be compiled with the same settings.  This already causes problems for customers, which a _SMALL_STRING_OPTIMIZATION switch would exacerbate.

     

    That's not to say that we won't ever implement such a switch - only that doing so wouldn't be free of negative impacts.

     

    > I'm happy to hear that you are looking into this. I'm also sure a lot of people

    > would appreciate it if you could release a service pack with an optimized STL

    > some time before VC10.

     

    Changing the representation of std:: string would break binary compatibility, which we cannot do in a service pack.

     

    VC9 TR1 (which will also be in VC9 SP1) is adding lots of TR1 stuff and even making a few unrelated STL fixes, but nothing that can break binary compatibility.

     

    Stephan T. Lavavej

    Visual C++ Libraries Developer

    Saturday, December 15, 2007 12:23 AM

All replies

  • What compiler are you using? I tried with Visual C++ 2003, Visual C++ 2005 and Visual C++ 2008 and they all showed that the size of std:: string is 28 bytes.

     

    Also the compilers layout dumps don't show 4 bytes of internal padding. Here are what the compiler shows.

     

    Code Block

    class _Bxty size(16):
     +---
     0 | _Buf
     0 | _Ptr
     +---

     

    class ?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@ size(28):
     +---
     | +--- (base class ?$_String_val@DV?$allocator@D@std@@)
     | | +--- (base class _String_base)
     | | | +--- (base class _Container_base)
     | | | +---
     | | +---
     0 | | ?$allocator@D _Alval
     | +---
       | <alignment member> (size=3)
     4 | _Bxty _Bx
    20 | _Mysize
    24 | _Myres
     +---

     

     

    The 3 bytes of padding is there to alignment the pointer in the buffer.
    Friday, December 14, 2007 3:40 PM
    Moderator
  • It's 28 bytes in the release mode and 32 in debug - I stand corrected on that.

    However, the size is still more than other STL implementations provide. As far as padding goes, If I look at a string allocated this way,
        new std:Tongue Tiedtring("123456789012345");
    I should see all data members assigned to some values and the internal buffer filled up. However, I see the the 4 heap filler bytes at the beginning (highlighted).
    0x01F63C78  0d f0 ad ba 31 32 33 34 35 36 37 38 39 30  .ð­º1234567890
    0x01F63C86  31 32 33 34 35 00 0f 00 00 00 0f 00 00 00  12345.........
    This memory is from a release build run, so no debug heap is used.

    Andre
    Friday, December 14, 2007 4:49 PM
  • The three bytes of padding is because the allocator<char> object in the base-class - even though this object has no non-static data-members itself our object model still requires us to allocate one byte for the enclosing class - as do, I believe many other C++ object models. The existence of this one byte-base class requires us to add 3 bytes of padding before the next data-member.

     

    I compiled the same code with the EDG compiler and they gave the same size for the class and the same layout for the non-static data members.

     

    The current implementation was decided upon after careful consideration and analysis - we feel that it strikes the right balance between space and performance. It might not be perfect for all situations but we do feel that it is a good compromise.

    Friday, December 14, 2007 5:27 PM
    Moderator
  •  Jonathan Caves - MSFT wrote:

    The three bytes of padding is because the allocator<char> object in the base-class - even though this object has no non-static data-members itself our object model still requires us to allocate one byte for the enclosing class - as do, I believe many other C++ object models. The existence of this one byte-base class requires us to add 3 bytes of padding before the next data-member.


    If you are referring to the C++ object model described in the C++ standard, then it's not quite true. Take a look at the section 1.8.5 of the standard (14882:2003, p5), which says:

    Unless it is a bit-field (9.6), a most derived object shall have a non-zero size and shall occupy one or more
    bytes of storage. Base class sub-objects may have zero size.


     Jonathan Caves - MSFT wrote:
    I compiled the same code with the EDG compiler and they gave the same size for the class and the same layout for the non-static data members.

     

    I never used EDG, so have to ask - do you mean that you tried an STL library that comes with it? If you need a library to compare, check out the one I mentioned in my initial post. Their STL string is 24 bytes in size with the buffer and 12 without.

    Andre
    Friday, December 14, 2007 7:14 PM
  • 1) You are correct - and in this case when we can make the size of the base-class zero we do.

    2) No: I tried the EDG compiler with our implementation of std:: string - this showed that in this case our object layout was correct and we did not have any unnecessary padding.

    Friday, December 14, 2007 7:49 PM
    Moderator
  •  Jonathan Caves - MSFT wrote:

    1) You are correct - and in this case when we can make the size of the base-class zero we do.

    Pardon me if I'm getting this wrong - I haven't had a chance to look closely at the basic string implementation, but wouldn't you get rid of this padding if you declared the allocator static:
       static _Alty _Alval;   // allocator object for strings

    Andre
    Friday, December 14, 2007 10:05 PM
  • The Empty Base Class Optimization permits a truly empty base class to require no storage. It's not perfect, though - the addresses of distinct objects of the same type still have to be distinct, so when you repeatedly inherit from an empty base class, they can end up requiring storage.

     

    The question here is whether a class containing an empty class is itself empty. My reading of the Standard was ambiguous on whether the EBCO applies in this case, but as far as I can tell, no existing compiler applies the EBCO here.

     

    This is why allocators occupy space in VC's implementations of the Standard containers.  Some STL implementations inherit from their allocators in order to avoid this, but I've heard that there are downsides to this (I didn't hear more specific details).

     

    We did some work in VC9 to reduce the space of containers and iterators in certain configurations, but std:: string was not affected.

     

    In VC10, I'd like to eliminate this allocator bloat, at least in the case of std::allocator (which is stateless if not specialized by the user).

     

    As for the short string buffer, that is a feature, not a bug - it avoids dynamic allocations for short strings, which can be a major win.  This benefits some users.

     

    As usual, the Standard Library is highly flexible and performant - but it is not infinitely so, and there will always be situations in which a particular implementation of the Standard Library is unsuitable.

     

    If you have further questions, feel free to E-mail me at stl@microsoft.com .

     

    Thanks,
    Stephan T. Lavavej
    Visual C++ Libraries Developer

    Friday, December 14, 2007 10:20 PM
  • > wouldn't you get rid of this padding if you declared the allocator static

     

    Yes, but VC's Standard Library implementation supports stateful allocators (such support is permitted, but not required, by the Standard).

     

    Stephan T. Lavavej

    Visual C++ Libraries Developer

    Friday, December 14, 2007 10:22 PM
  • Stephan,

    Thank you very much for a detailed and to the point answer. It is much appreciated.

     Stephan T. Lavavej - MSFT wrote:
    As for the short string buffer, that is a feature, not a bug - it avoids dynamic allocations for short strings, which can be a major win.  This benefits some users.

    I never said it was a bug. Small internal buffer is a good optimization when memory is not an issue. My comment was that other STL implementations allow developers to build their STL to choose whether to use this optimization or not (again, STLport is a good example of that).

     Stephan T. Lavavej - MSFT wrote:
    In VC10, I'd like to eliminate this allocator bloat, at least in the case of std::allocator (which is stateless if not specialized by the user).

    I'm happy to hear that you are looking into this. I'm also sure a lot of people would appreciate it if you could release a service pack with an optimized STL some time before VC10.

    Andre

    Friday, December 14, 2007 10:50 PM
  • > Small internal buffer is a good optimization when memory is not an issue.

     

    Actually, it can reduce memory consumption too - remember that dynamic memory allocation involves overheads.

     

    > My comment was that other STL implementations allow developers to build their

    > STL to choose whether to use this optimization or not (again, STLport is a good

    > example of that).

     

    Being able to enable or disable this feature could certainly be useful - however, it can also be a source of problems.  The _SECURE_SCL and _HAS_ITERATOR_DEBUGGING options change the representations of STL containers (what it does to std:: string is more subtle and confusing), so all translation units that are linked into a single binary must be compiled with the same settings, and binaries that pass STL containers and iterators around must be compiled with the same settings.  This already causes problems for customers, which a _SMALL_STRING_OPTIMIZATION switch would exacerbate.

     

    That's not to say that we won't ever implement such a switch - only that doing so wouldn't be free of negative impacts.

     

    > I'm happy to hear that you are looking into this. I'm also sure a lot of people

    > would appreciate it if you could release a service pack with an optimized STL

    > some time before VC10.

     

    Changing the representation of std:: string would break binary compatibility, which we cannot do in a service pack.

     

    VC9 TR1 (which will also be in VC9 SP1) is adding lots of TR1 stuff and even making a few unrelated STL fixes, but nothing that can break binary compatibility.

     

    Stephan T. Lavavej

    Visual C++ Libraries Developer

    Saturday, December 15, 2007 12:23 AM
  •  Stephan T. Lavavej - MSFT wrote:

    > Small internal buffer is a good optimization when memory is not an issue.

     

    Actually, it can reduce memory consumption too - remember that dynamic memory allocation involves overheads.

    Only in a special case where mostly short strings are used (15 narrow or 7 wide characters). One allocated memory block is 8 bytes of control information and 8 bytes of the 0xAB filler at the end, if small-block heap is not used. SBH seems to reduce this to 8 bytes, although I'm not too sure. However, for strings longer than these limits, the internal buffer is a waste of 12 bytes (since the string pointer shares the same buffer) on top of the heap's 16-byte overhead.


    Just to give you an idea of how bad can it be, the heap of an application compiled against STLport's STL string with the internal buffer disabled (its sizeof is then 12 bytes) is reduced from 230MB to 198MB in the same small test with a few users.


     Stephan T. Lavavej - MSFT wrote:

    Changing the representation of std:: string would break binary compatibility, which we cannot do in a service pack.

     

    VC9 TR1 (which will also be in VC9 SP1) is adding lots of TR1 stuff and even making a few unrelated STL fixes, but nothing that can break binary compatibility.


    I see. Thanks for the clarification.


    Andre

    Saturday, December 15, 2007 7:55 PM