Skip to main content
GameDev.net gamedev.net
🔒 Locked

Alignment when overloading new [C++]

Started by Hodgman May 5, 2009 at 7:16 AM 22 replies 6.5k views
Original Post
Hodgman
Hodgman
I'm writing a memory allocation class to be used for several "temporary" objects in my game. These objects only need to exist for a single frame, and don't do anything meaningful in their destructors. My class is designed to have a fixed size heap and an index of the first unused byte in the heap. Allocations increment the index, and at the end of the frame I clear the heap by resetting the index to 0 (the objects are "leaked", but the memory is reused). What I'm not quite sure about, is how exactly I should be aligning these allocations. I've been warned that you should only use placement new if you know how to handle alignment, so I'm kind of uneasy. At the moment, I'm aligning the allocations to 4-byte boundaries like so:
namespace {
	const static uint gs_Alignment = sizeof(int);
}
The allocation code:
//m_Heap is a std::vector<char>, m_Usage is an unsigned int.
CTempHeap::CTempHeap( size_t heap )
{
	m_Heap.resize( heap );
	m_Usage = 0;
}
void* CTempHeap::Alloc( size_t size )
{
	uint startByte = m_Usage;
	startByte = ((startByte+(gs_Alignment-1))/gs_Alignment)*gs_Alignment;
	uint newUsage = startByte + size;
	if( newUsage >= m_Heap.size() )
		return NULL;
	m_Usage = newUsage;
	return &m_Heap[startByte];
}
void CTempHeap::Clear()
{
	m_Usage = 0;
}

void* CTempObj::operator new( size_t size, CTempHeap& w )
{
	void* p = w.Alloc( size );
	if( !p )//TODO - use the new handler
		throw std::bad_alloc();
	return p;
}
Usage:
CTempHeap heap( 1024 );//1kb heap
CTempObj* pTest = new(heap) CTempObj;
pTest = 0;
heap.Clear();
[Edit:] I just realised that my code is aligning the offset from the beginning of my buffer, not the actual memory address! I'll have to fix this. [Edited by - Hodgman on May 6, 2009 12:58:42 AM]
SiCrane
SiCrane
Proper alignment for objects is platform and data type dependent. In general, align primitives to a multiple to their size and align classes to a multiple of the size of their largest primitive. So general case means a multiple of the size of the largest primitive. Depending on your platform, not using proper alignment will either be somewhat slower (ex: on x86) or will crash your program (especially on finicky embedded systems).
visitor
visitor
Wouldn't it be possible to put those instances on the stack instead?
Hodgman
Hodgman
Quote:
Original post by SiCrane
...So general case means a multiple of the size of the largest primitive. Depending on your platform, not using proper alignment will either be somewhat slower (ex: on x86) or will crash your program (especially on finicky embedded systems).
So assuming I had some cool meta-programming/reflection type stuff, I could do:
FindAlignment( obj ): if obj is primitive, then  return sizeof(obj) align = 1 for each member of obj  if member is class, align = max( align, FindAlignment(member) )  else,               align = max( align, sizeof(member) ) return align
Quote:
Original post by visitor
Wouldn't it be possible to put those instances on the stack instead?
Unfortunately there's an unpredictable number of different types of objects (polymorphic) required for any frame. This is actually for a multi-threading system - these temporary objects are actually structures representing delayed function calls to be scheduled on the next frame.
implicit
implicit
I've been using a hack like this in an "obstack" allocator:
#define alignof(type) (sizeof(struct { char p; type q; }) - sizeof(type))void *align_ptr(void *ptr, ptrdiff_t align) {	ptr += align - 1;	return (void *) ((intptr_t) ptr & -align));}
This seems to work fairly well in practice, though there obviously isn't any fully portable solution.
loufoque
loufoque
According to the C++ standard, operator new must return memory properly aligned for any type.

Yes, that sucks, but that's the way it is.

If you want to know alignment of some type, just do std::alignment_of::value.

To know "worse" alignment, just do std::alignment_of:value.

Note that on x86, worse alignment is typically 8 or 16, depending whether you take into account __m128 and stuff like that or not.
SiCrane
SiCrane
For people not using a time-tunneling modem to post from the future like loufoque does, alignment_of can be found in boost's type_traits.hpp or type_traits/alignment_of.hpp headers or if your compiler supports TR1, in the TR1 header type_traits in the std::tr1 namespace.
implicit
implicit
Quote:
Original post by SiCrane
For people not using a time-tunneling modem to post from the future like loufoque does, alignment_of can be found in boost's type_traits.hpp or type_traits/alignment_of.hpp headers or if your compiler supports TR1, in the TR1 header type_traits in the std::tr1 namespace.
Does the new standard come with guidelines as to how to use it to safely align pointers?
As I recall previous C/C++ standards gave few guarantees about what a pointer cast to an integer actually represented. And one might easily imagine byzantine architectures where intentionally misaligned pointers are used to signal something or other (I believe odd addresses are used to indicate Thumb-mode code on ARM processors for instance.)

Though at the end of the day I suppose malloc must be able to infer the proper alignment of a type from the size alone. Well, I suppose an intermediate cast to a void * pointer couldn't hurt at least.
Hodgman
Hodgman
Thanks for all the info guys, it's big help.
Quote:
Original post by SiCrane
For people not using a time-tunneling modem to post from the future
You're so harsh SiCrane, but it makes me laugh ;D
polypterus
polypterus
This is machine dependant. A lot of machines will throw a "bus error" if you don't align your data correctly. I believe that Intel processors will load and store data anyway with some performance hit. At least that's what used to happen. I'm not sure about the newer processors. If you align to 8 bytes you are fairly safe for stuff up to double precision. If you don't use doubles you can align to 4. I have noticed malloc aligns to 8 on a lot of machines so that's what I would tend to start with although you might waste some space in some cases. You can always go all out and make it a parameter.

By the way I have a library of about 10 different memory allocators for doing various things like you are up to. It's well worth the effort. The performance gain can be huge!
Zahlman
Zahlman
Quote:
Original post by Hodgman
Quote:
Original post by visitor
Wouldn't it be possible to put those instances on the stack instead?
Unfortunately there's an unpredictable number of different types of objects (polymorphic) required for any frame. This is actually for a multi-threading system - these temporary objects are actually structures representing delayed function calls to be scheduled on the next frame.


Then why not just put them in a std::queue or something?
Hodgman
Hodgman
Quote:
Original post by Zahlman
Quote:
Original post by Hodgman
Quote:
Original post by visitor
Wouldn't it be possible to put those instances on the stack instead?
Unfortunately there's an unpredictable number of different types of objects (polymorphic) required for any frame. This is actually for a multi-threading system - these temporary objects are actually structures representing delayed function calls to be scheduled on the next frame.
Then why not just put them in a std::queue or something?
Because they're polymorphic, so I would still have to dynamically allocate them and then put pointers in the queue, right?
Sc4Freak
Sc4Freak
I'm not sure I get it. Why is alignment important here?

The vector will use new, which guarantees that the entire memory block itself will be aligned correctly. But it's not the job of the allocator to ensure that the individual elements are aligned, is it?

Here's my reasoning:

If the class CTempObj has 3 bytes worth of data members, then it's the compiler's job to ensure that CTempObj is padded up to the nearest boundary. That is, if the alignment needs to be 4 bytes, it's the compiler's job to pad the class so that sizeof(CTempObj) is 4 bytes.

Otherwise, let's say we're on a platform where unaligned memory access raises a hardware exception. And the alignment boundary is 4 bytes. If the compiler didn't pad CTempObj to 4 bytes, then allocating 2 of these objects using new[] would allocate 6 bytes of memory. operator new[] guarantees that the start of the block is aligned. So accessing the zeroth element is fine, since it's aligned. But sizeof(CTempObj) bytes later - 3 bytes in - is not aligned. So accessing the first element would cause an exception. So the compiler needs to ensure that sizeof(CTempObj) is a multiple of 4 bytes.

So since the vector allocates using new, and the memory from new is guaranteed to be aligned, and it's up to the compiler to pad the objects you're allocating, why do you need to worry about alignment at all here?
polypterus
polypterus
Quote:
Original post by Sc4Freak
I'm not sure I get it. Why is alignment important here?

The vector will use new, which guarantees that the entire memory block itself will be aligned correctly. But it's not the job of the allocator to ensure that the individual elements are aligned, is it?

For the most part you are correct. However it does depend on exactly what kind of memory allocation you are writing. For a fixed sized object allocator it's generally not a problem except for you still need to align the first address of each block. So at least for this part you have to be a bit careful. Also you may be writing a more complex allocator that supports more than a single sized object and for this you need to be more careful.

Edit: I should add, even if you are using new or malloc to allocate your memory blocks you typically have some sort of block information at the beginning followed by your actually allocated memory. So depending on how you implement this you may have to align stuff yourself.
Zahlman
Zahlman
Quote:
Original post by Hodgman
Quote:
Original post by Zahlman
Quote:
Original post by Hodgman
Quote:
Original post by visitor
Wouldn't it be possible to put those instances on the stack instead?
Unfortunately there's an unpredictable number of different types of objects (polymorphic) required for any frame. This is actually for a multi-threading system - these temporary objects are actually structures representing delayed function calls to be scheduled on the next frame.
Then why not just put them in a std::queue or something?
Because they're polymorphic, so I would still have to dynamically allocate them and then put pointers in the queue, right?


If they're polymorphic and can vary in size, you could put them sequentially in a buffer, but (a) you'll lose random access (apparently not an issue here) and (b) you still have to figure out the size of each instance as you encounter it. Oh, and being polymorphic, they'll be non-POD - which means good luck implementing buffer resize. You're essentially re-implementing std::vector, but without the things like random-access and equal-sized elements that mke std::vector interesting.

You could put smart pointers in the queue instead. Or maybe something like boost::ptr_list would be more to your liking.
implicit
implicit
Quote:
Original post by Zahlman
If they're polymorphic and can vary in size, you could put them sequentially in a buffer, but (a) you'll lose random access (apparently not an issue here) and (b) you still have to figure out the size of each instance as you encounter it. Oh, and being polymorphic, they'll be non-POD - which means good luck implementing buffer resize. You're essentially re-implementing std::vector, but without the things like random-access and equal-sized elements that mke std::vector interesting.
I'd say he's trying to implement a fast memory allocator, not a container. Think the type of allocation offered in garbage collected languages or from GNU obstacks.
No one expects random access, automatic object destruction or pointer relocation from malloc or the new operator after all. And as for relocation you'd typically allocate new chunks of memory as needed, there's little need to keep the memory contiguous.
This is especially nice if you've got a bunch of objects not using any external resources since they can be freed simply by releasing the buffer. Say for any temporary objects you create while rendering each frame for instance.
polypterus
polypterus
Quote:
Original post by Zahlman
If they're polymorphic and can vary in size, you could put them sequentially in a buffer, but (a) you'll lose random access (apparently not an issue here) and (b) you still have to figure out the size of each instance as you encounter it. Oh, and being polymorphic, they'll be non-POD - which means good luck implementing buffer resize. You're essentially re-implementing std::vector, but without the things like random-access and equal-sized elements that mke std::vector interesting.

You could put smart pointers in the queue instead. Or maybe something like boost::ptr_list would be more to your liking.

He is essentially putting them sequentially in a buffer. It's just a cleaner way of doing it. I assume what you mean by loose random access is loose the ability to randomly delete. He can access the same way he normally does. However it doesn't sound like he needs to delete until the end of his frame in which case he deletes everything. Also he can resize his buffer upwards no problem. Usually you just set a block size and allocate memory in large chunks. When one runs out, you just add the next on. I even go so far as to save the blocks in a block manager so I can reuse them next frame. There are a bunch of strategies for this stuff, but typically they are independent of the data structures, however they are often dependant of the data life-span.
Zahlman
Zahlman
Quote:
Original post by implicit
I'd say he's trying to implement a fast memory allocator, not a container.


He seems to want to allocate sequentially from a pool, and then be able to extract the allocated things from the pool in order. That makes the pool, in effect, a container. :)
implicit
implicit
Quote:
Original post by Zahlman
Quote:
Original post by implicit
I'd say he's trying to implement a fast memory allocator, not a container.

He seems to want to allocate sequentially from a pool, and then be able to extract the allocated things from the pool in order. That makes the pool, in effect, a container. :)
Ah. I think you mistook freeing the objects for 'extracting' them.

edit: Wait, he did say something about stored function calls.
No mention about the order of execution though, there might be some scheduling involved for all I know. But suppose it might be considered a container either way.
Hodgman
Hodgman
Quote:
Original post by polypterus
For a fixed sized object allocator it's generally not a problem except for you still need to align the first address of each block. So at least for this part you have to be a bit careful. Also you may be writing a more complex allocator that supports more than a single sized object and for this you need to be more careful.
Yes, objects of different sizes may be put in here. E.g. a class using a single int, followed by a class using _m128's.
Quote:
you typically have some sort of block information at the beginning followed by your actually allocated memory.
Yeah, especially in debug builds there will be extra information stored both before and after the memory allocated for the object.


Quote:
Original post by Zahlman
If they're polymorphic and can vary in size, you could put them sequentially in a buffer, but (a) you'll lose random access (apparently not an issue here)
When I write
C* p = new (...) C
, then "p" allows me to access the element within the buffer. This pointer, "p", may in turn be stored in an actual container elsewhere for sorting, iterating, etc...
Quote:
and (b) you still have to figure out the size of each instance as you encounter it.
That's what the size_t argument for operator new is for...
Quote:
Oh, and being polymorphic, they'll be non-POD - which means good luck implementing buffer resize.
What makes you think that I want to resize my heap while there are objects allocated inside it?? Now it seems you're just trolling.
Quote:
You're essentially re-implementing std::vector,
No, I'm using std::vector to implement a very simple heap for transient allocations.
Quote:
You could put smart pointers in the queue instead. Or maybe something like boost::ptr_list would be more to your liking.
That completely destroys the purpose of being a simple, very low overhead allocator...
Quote:
Original post by Zahlman
Quote:
Original post by implicit
I'd say he's trying to implement a fast memory allocator, not a container.

He seems to want to allocate sequentially from a pool, and then be able to extract the allocated things from the pool in order. That makes the pool, in effect, a container. :)
No, it's an allocator. I don't want to iterate through the heap (it's just "used memory" as far as the allocator is concerned). All I want to do is (logically) free the memory once a frame.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.