3
votes

Usually data is aligned at power of two addresses depending on its size.

How should I align a struct or class with size of 20 bytes or another non-power-of-two size?

I'm creating a custom stack allocator so I guess that the compiler wont align data for me since I'm working with a continuous block of memory.

Some more context:

I have an Allocator class that uses malloc() to allocate a large amount of data. Then I use void* allocate(U32 size_of_object) method to return the pointer that where I can store whether objects I need to store. This way all objects are stored in the same region of memory and it will hopefully fit in the cache reducing cache misses.

6
"Usually data is aligned at power of two addresses depending on its size." -- Where did you get that from?? There aren't that many powers of two in your usual address space, maybe 20-50... I sure hope we can allocate a few more objects than that! - Kerrek SB
You don't typically need to worry about alignment anyway. - GManNickG
What are you actually trying to do? Your compiler will automatically take care of many alignment considerations. Are you trying to use SSE instructions or something that has alignment constraints? - Darren Engwirda
Since when is the size of an object a power of two? That's not even true for my trusted long double over here... Also, that is not at all what you said in your question. The words "multiple" and "power" mean different things. - Kerrek SB
@Tiago Costa: "power of two"?? Are you sure they didn't say "multiple of two" because those things are very different... - Darren Engwirda

6 Answers

3
votes

C++11 has the alignof operator specifically for this purpose. Don't use any of the tricks mentioned in other posts, as they all have edge cases or may fail for certain compiler optimisations. The alignof operator is implemented by the compiler and knows the exact alignment being used.

See this description of c++11's new alignof operator

2
votes

Although the compiler (or interpreter) normally allocates individual data items on aligned boundaries, data structures often have members with different alignment requirements. To maintain proper alignment the translator normally inserts additional unnamed data members so that each member is properly aligned. In addition the data structure as a whole may be padded with a final unnamed member. This allows each member of an array of structures to be properly aligned. http://en.wikipedia.org/wiki/Data_structure_alignment#Typical_alignment_of_C_structs_on_x86

This says that the compiler takes care of it for you, 99.9% of the time. As for how to force an object to align a specific way, that is compiler specific, and only works in certain circumstances.

MSVC: http://msdn.microsoft.com/en-us/library/83ythb65.aspx

__declspec(align(20)) 
struct S{ int a, b, c, d; };
//must be less than or equal to 20 bytes

GCC: http://gcc.gnu.org/onlinedocs/gcc-3.4.0/gcc/Type-Attributes.html

struct S{ int a, b, c, d; } 
__attribute__ ((aligned (20)));

I don't know of a cross-platform way (including macros!) to do this, but there's probably neat macro somewhere.

1
votes

Unless you want to access memory directly, or squeeze maximum data in a block of memory you don't worry about alignment -- the compiler takes case of that for you.

1
votes

Due to the way processor data buses work, what you want to avoid is 'mis-aligned' access. Usually you can read a 32 bit value in a single access from addresses which are multiples of four; if you try to read it from an address that's not such a multiple, the CPU may have to grab it in two or more pieces. So if you're really worrying about things at this level of detail, what you need to be concerned about is not so much the overall struct, as the pieces within it. You'll find that compilers will frequently pad out structures with dummy bytes to ensure aligned access, unless you specifically force them not to with a pragma.

1
votes

Since you've now added that you actually want to write your own allocator, the answer is straight-forward: Simply ensure that your allocator returns a pointer whose value is a multiple of the requested size. The object's size itself will already come suitably adjusted (via internal padding) so that all member objects themselves are properly aligned, so if you request sizeof(T) bytes, all your allocator needs to do is to return a pointer whose value is divisible by sizeof(T).

If your object does indeed have size 20 (as reported by sizeof), then you have nothing further to worry about. (On a 64-bit platform, the object would probably be padded to 24 bytes.)

Update: In fact, as I only now came to realize, strictly speaking you only need to ensure that the pointer is aligned, recursively, for the largest member of your type. That may be more efficient, but aligning to the size of the entire type is definitely not getting it wrong.

0
votes

How should I align a struct or class with size of 20 bytes or another non-power-of-two size?

Alignment is CPU-specific, so there is no answer to this question without, at least, knowing the target CPU.

Generally speaking, alignment isn't something that you have to worry about; your compiler will have the rules implemented for you. It does come up once in a while, like when writing an allocator. The classic solution is discussed in The C Programming Language (K&R): use the worst possible alignment. malloc does this, although it's phrased as, "the pointer returned if the allocation succeeds shall be suitably aligned so that it may be assigned to a pointer to any type of object."

The way to do that is to use a union (the elements of a union are all allocated at the union's base address, and the union must therefore be aligned in such a way that each element could exist at that address; i.e., the union's alignment will be the same as the alignment of the element with the strictest rules):

typedef Align long;
union header {
    // the inner struct has the important bookeeping info
    struct {
        unsigned size;
        header* next; 
    } s;
    // the align member only exists to make sure header_t's are always allocated
    // using the alignment of a long, which is probably the worst alignment
    // for the target architecture ("worst" == "strictest," something that meets
    // the worst alignment will also meet all better alignment requirements)
    Align align;
};

Memory is allocated by creating an array (using somthing like sbrk()) of headers large enough to satisfy the request, plus one additional header element that actually contains the bookkeeping information. If the array is called arry, the bookkeeping information is at arry[0], while the pointer returned points at arry[1] (the next element is meant for walking the free list).

This works, but can lead to wasted space ("In Sun's HotSpot JVM, object storage is aligned to the nearest 64-bit boundary"). I'm aware of a better approach that tries to get a type-specific alignment instead of "the alignment that will work for anything."

Compilers also often have compiler-specific commands. They aren't standard, and they require that you know the correct alignment requirements for the types in question. I would avoid them.