std::vector padding behavior and alignment

Discussion in 'C++' started by Andrew Tomazos, Apr 28, 2009.

  1. Please consider the following:

    We construct a std::vector, push_back 1000 items and then destroy it.
    Each normal constructor. copy constructor and destructor is counted...

    #include <vector>
    #include <cstdio>

    class A
    {
    public:
    A(int x) : m_x(x) { s_iConstructs++; }
    A(const A& a) { s_iCopies++; }
    ~A() { s_iDestructs++; }

    static void dump()
    {
    std::printf("s_iConstructs == %d\n", s_iConstructs);
    std::printf("s_iCopies == %d\n", s_iCopies);
    std::printf("s_iDestructs == %d\n", s_iDestructs);
    }

    private:
    int m_x;

    static int s_iConstructs;
    static int s_iCopies;
    static int s_iDestructs;
    };

    int A::s_iConstructs(0);
    int A::s_iCopies(0);
    int A::s_iDestructs(0);

    int main(int argc, char** argv)
    {
    {
    std::vector<A> v;
    for (int i = 0; i < 1000; i++)
    v.push_back(A(i));
    }

    A::dump();
    }

    The output from gcc version 4.3.2:

    s_iConstructs == 1000
    s_iCopies == 2023
    s_iDestructs == 3023

    The output from Microsoft C/C++ Compiler v15.x:

    s_iConstructs == 1000
    s_iCopies == 3137
    s_iDestructs == 4137

    Clearly when a new item is pushed onto the vector, the underlying
    memory is not reallocated each time. If it were, the number of copy
    constructor calls would be closer to 500,000. Instead they are closer
    to 3,000.

    Furthermore as type A has no default constructor, we must conclude
    that std::vector is heap allocating an uninitialized buffer beyond the
    size that it requires, and leaving that extra area uninitialized.

    It must allocate its buffer with malloc and not with new[], as new[]
    requires that the type be default constructable. (Is this correct?)

    When a new item is pushed, it must be using placement new to copy
    construct the items in-place over this uninitialized memory.

    Now some types have certain alignment restrictions (such as being 4-
    byte aligned or 16-byte aligned to the memory address space).

    When new SomeAlignedType[1000] is called, the new[] memory allocator
    must be aware of these alignment requirements, and select an
    appropriately aligned section of memory for the type.

    My question is this: How can std::vector use malloc and still respect
    these alignment restrictions? By what method does std::vector detect
    the alignment requirements of a certain type, and then by what method
    does it allocate its array?

    If the answer is implementation dependent than specifically how does
    gcc and msvc do it?

    Is this facility documented and available to user-defined container
    types?

    Thanks,
    Andrew.
     
    Andrew Tomazos, Apr 28, 2009
    #1
    1. Advertising

  2. * Andrew Tomazos:
    > Please consider the following:
    >
    > We construct a std::vector, push_back 1000 items and then destroy it.
    > Each normal constructor. copy constructor and destructor is counted...
    >
    > #include <vector>
    > #include <cstdio>
    >
    > class A
    > {
    > public:
    > A(int x) : m_x(x) { s_iConstructs++; }
    > A(const A& a) { s_iCopies++; }
    > ~A() { s_iDestructs++; }
    >
    > static void dump()
    > {
    > std::printf("s_iConstructs == %d\n", s_iConstructs);
    > std::printf("s_iCopies == %d\n", s_iCopies);
    > std::printf("s_iDestructs == %d\n", s_iDestructs);
    > }
    >
    > private:
    > int m_x;
    >
    > static int s_iConstructs;
    > static int s_iCopies;
    > static int s_iDestructs;
    > };
    >
    > int A::s_iConstructs(0);
    > int A::s_iCopies(0);
    > int A::s_iDestructs(0);
    >
    > int main(int argc, char** argv)
    > {
    > {
    > std::vector<A> v;
    > for (int i = 0; i < 1000; i++)
    > v.push_back(A(i));
    > }
    >
    > A::dump();
    > }
    >
    > The output from gcc version 4.3.2:
    >
    > s_iConstructs == 1000
    > s_iCopies == 2023
    > s_iDestructs == 3023
    >
    > The output from Microsoft C/C++ Compiler v15.x:
    >
    > s_iConstructs == 1000
    > s_iCopies == 3137
    > s_iDestructs == 4137
    >
    > Clearly when a new item is pushed onto the vector, the underlying
    > memory is not reallocated each time. If it were, the number of copy
    > constructor calls would be closer to 500,000. Instead they are closer
    > to 3,000.
    >
    > Furthermore as type A has no default constructor, we must conclude
    > that std::vector is heap allocating an uninitialized buffer beyond the
    > size that it requires, and leaving that extra area uninitialized.
    >
    > It must allocate its buffer with malloc and not with new[], as new[]
    > requires that the type be default constructable. (Is this correct?)


    No. The internal buffer will in practice be allocated as a buffer of 'char' or
    'unsigned char', via 'std::allocator::allocate'. It's a buffer of bytes
    (although at the 'std::vector' code level accessed as a buffer of uninitialized
    T), and it can be allocated using just about any allocation mechanism.


    > When a new item is pushed, it must be using placement new to copy
    > construct the items in-place over this uninitialized memory.


    Yes, effectively. It does that using 'std::allocator::construct', which in turn
    does the placement new.


    > Now some types have certain alignment restrictions (such as being 4-
    > byte aligned or 16-byte aligned to the memory address space).
    >
    > When new SomeAlignedType[1000] is called, the new[] memory allocator
    > must be aware of these alignment requirements, and select an
    > appropriately aligned section of memory for the type.


    Yes, but only implicitly. In practice it doesn't use different alignments for
    different types. It just uses some suitably large alignment, say 8.


    > My question is this: How can std::vector use malloc and still respect
    > these alignment restrictions?


    Both 'malloc' and 'new' return a pointer suitably aligned for any type.


    > By what method does std::vector detect
    > the alignment requirements of a certain type,


    In practice it doesn't. In principle it could. C++0x introduces some support for
    alignment issues.


    > and then by what method
    > does it allocate its array?


    A std::vector uses the allocator that it's been instantiated with. By default
    that's 'std::allocator<T>'. Whose 'allocate' routine in turn uses '::eek:perator
    new', the global byte level allocation function (which in practice probably just
    forwards to 'malloc', but this is implementation-dependent).


    > If the answer is implementation dependent than specifically how does
    > gcc and msvc do it?


    Oh, check the standard library implementation source code.

    For MSVC that should be particularly easy, at least if you have Visual Studio
    which has an excellent debugger: just step into the push_back call.


    > Is this facility documented and available to user-defined container
    > types?


    Yes, look up 'std::allocator'.

    However, it's not the best design ever made.


    Cheers & hth.,

    - Alf

    --
    Due to hosting requirements I need visits to <url: http://alfps.izfree.com/>.
    No ads, and there is some C++ stuff! :) Just going there is good. Linking
    to it is even better! Thanks in advance!
     
    Alf P. Steinbach, Apr 30, 2009
    #2
    1. Advertising

  3. Andrew Tomazos

    Jerry Coffin Guest

    In article <341b1763-6882-41b4-ad20-9c8a3cad2104
    @b6g2000pre.googlegroups.com>, says...

    [ ... ]

    > Clearly when a new item is pushed onto the vector, the underlying
    > memory is not reallocated each time. If it were, the number of copy
    > constructor calls would be closer to 500,000. Instead they are closer
    > to 3,000.


    Right -- the standard requires that adding items to a vector be
    asymtotically constant. To accomplish this, a vector will normally
    multiply the size by some constant when it runs out of space (e.g.
    typically 1.5 or 2).

    > Furthermore as type A has no default constructor, we must conclude
    > that std::vector is heap allocating an uninitialized buffer beyond the
    > size that it requires, and leaving that extra area uninitialized.
    >
    > It must allocate its buffer with malloc and not with new[], as new[]
    > requires that the type be default constructable. (Is this correct?)


    No. It can (and usually does) use the global new operator to allocate
    unitialized space.

    > When a new item is pushed, it must be using placement new to copy
    > construct the items in-place over this uninitialized memory.


    Yes, that's typical anyway.

    > Now some types have certain alignment restrictions (such as being 4-
    > byte aligned or 16-byte aligned to the memory address space).


    [ ... ]

    > My question is this: How can std::vector use malloc and still respect
    > these alignment restrictions? By what method does std::vector detect
    > the alignment requirements of a certain type, and then by what method
    > does it allocate its array?


    The array form of the global new operator is required to return a
    pointer to the requested size of: "bytes of storage suitably aligned to
    represent any array object of that size or smaller." ($18.4.1.2/1).

    [ ... ]

    > Is this facility documented and available to user-defined container
    > types?


    Yes -- as noted above, the global new operator is required to return
    storage that's aligned as you need it.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
     
    Jerry Coffin, Apr 30, 2009
    #3
  4. Jerry Coffin wrote:
    >> It must allocate its buffer with malloc and not with new[], as new[]
    >> requires that the type be default constructable. (Is this correct?)

    >
    > No. It can (and usually does) use the global new operator to allocate
    > unitialized space.


    In fact std::vector, as all the other STL containers, allocates memory
    using the allocator you provided it. (If you didn't specify any
    allocator, it will default to std::allocator). Allocators are specified
    to allocate uninitialized memory (I suppose std::allocator in most
    implementations will call the global new operator for this, as you said).
     
    Juha Nieminen, Apr 30, 2009
    #4
  5. Andrew Tomazos

    James Kanze Guest

    On Apr 30, 2:29 am, (blargg) wrote:
    > Andrew Tomazos wrote:


    > [Basically asks how vector can allocate reserve space without
    > calling constructors, and ensure that the space is
    > appropriately aligned]


    > Any of the following allocates memory appropriately aligned
    > for n objects of any type T, without invoking any
    > constructors:


    > size_t size = n * sizeof (T);
    > void* p;
    > p = new char [size];
    > p = operator new ( size );
    > p = operator new [] ( size );
    > p = malloc( size );


    The current standard (ISO/IEC 14882:2003) requires the standard
    allocator to use ::eek:perator new( size_t ) to acquire the raw
    memory. None of the other techniques are permitted. (A user
    defined allocator can use anything it wishes.)

    > A pointer to a particular object i can be obtained trivially:


    > T* t = static_cast<T*> (p) + i;


    The implementations I've seen do the case directly on the return
    value of ::eek:perator new, and maintain the pointers as T*. Of
    course, they're very careful not to access any of the elements
    as T before they've been constructed, and after they've been
    destructed.

    The reason for this is probably because they use the internal
    pointers very much like iterators, which requires pointer
    arithmetic, and pointer arithmetic doesn't work on void*.

    I believe, too (although I'm too lazy to verify it) that the
    standard requires the containers to use the allocator member
    functions construct and destroy for construction and
    destruction. The default allocator is required to use placement
    new and an explicit call to the destructor; a user defined
    allocator can, again, use anything that works (but in this case,
    I don't know of anything else that would work).

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Apr 30, 2009
    #5
  6. Andrew Tomazos

    Jerry Coffin Guest

    In article <K2dKl.31$>, lid
    says...
    > Jerry Coffin wrote:
    > >> It must allocate its buffer with malloc and not with new[], as new[]
    > >> requires that the type be default constructable. (Is this correct?)

    > >
    > > No. It can (and usually does) use the global new operator to allocate
    > > unitialized space.

    >
    > In fact std::vector, as all the other STL containers, allocates memory
    > using the allocator you provided it. (If you didn't specify any
    > allocator, it will default to std::allocator). Allocators are specified
    > to allocate uninitialized memory (I suppose std::allocator in most
    > implementations will call the global new operator for this, as you said).


    Right -- a replacement allocator can use another source of memory (as
    long as it satisfies the requirements), but as long as you're using the
    default allocator, it's required ($20.4.1.1/6) to use global new to
    obtain the memory.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
     
    Jerry Coffin, Apr 30, 2009
    #6
  7. Andrew Tomazos

    Tony Guest

    James Kanze wrote:
    > On Apr 30, 2:29 am, (blargg) wrote:
    >> Andrew Tomazos wrote:

    >
    >> [Basically asks how vector can allocate reserve space without
    >> calling constructors, and ensure that the space is
    >> appropriately aligned]

    >
    >> Any of the following allocates memory appropriately aligned
    >> for n objects of any type T, without invoking any
    >> constructors:

    >
    >> size_t size = n * sizeof (T);
    >> void* p;
    >> p = new char [size];
    >> p = operator new ( size );
    >> p = operator new [] ( size );
    >> p = malloc( size );

    >
    > The current standard (ISO/IEC 14882:2003) requires the standard
    > allocator to use ::eek:perator new( size_t ) to acquire the raw
    > memory.
    > None of the other techniques are permitted.


    General Motors... next up: the std library committee. Afterwards:
    Ineffective Patterns in Programming (which will sell right up there with the
    GoF book).

    > (A user defined allocator can use anything it wishes.)


    Pffft. Lame container library offers the ability to use non-lame memory
    management. What's wrong with this picture??

    > I believe, too (although I'm too lazy to verify it) that the
    > standard requires the containers to use the allocator member
    > functions construct and destroy for construction and
    > destruction. The default allocator is required to use placement
    > new and an explicit call to the destructor; a user defined
    > allocator can, again, use anything that works (but in this case,
    > I don't know of anything else that would work).


    Imagine if you will... a college grad student, from Wisconsin, researches
    for his thesis, the goodness and quality of computer programming languages
    as evidenced by their "standard" libraries. Imagine a young and vibrant
    student's quest for freedom that becomes "so close one could taste it": so
    close that he makes good on his prior advances on a very svelte coed while
    he assembles his culmination of endeavor for academic perusal. Consider that
    elation and enlightenment do not coincide at the given place and time, and
    that the student finds himself in his "reseach", apart from any semblence of
    the "bricks of society" he was imminently preparing in his paper, for many
    more years... and that it continues ad infinitum... that the student, finds
    himself in... The Twilight Zone.
     
    Tony, Jun 24, 2009
    #7
  8. In message <v4i0m.5773$>, Tony
    <> writes

    [snip illucid rhetoric]

    What's your question about C++?

    --
    Richard Herring
     
    Richard Herring, Jun 24, 2009
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. SenderX
    Replies:
    2
    Views:
    883
    perry
    May 13, 2004
  2. Anonymous
    Replies:
    20
    Views:
    4,427
    Pete Becker
    Mar 30, 2005
  3. Jason Heyes
    Replies:
    8
    Views:
    767
    Andrew Koenig
    Jan 15, 2006
  4. Replies:
    8
    Views:
    1,998
    Csaba
    Feb 18, 2006
  5. Rune Allnor
    Replies:
    4
    Views:
    992
    Rune Allnor
    Dec 11, 2008
Loading...

Share This Page