std::vector padding behavior and alignment

A

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

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

Alf P. Steinbach

* 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
 
J

Jerry Coffin

[ ... ]
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.
 
J

Juha Nieminen

Jerry said:
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).
 
J

James Kanze

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

Jerry Coffin

Jerry said:
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.
 
T

Tony

James said:
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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top