Tuesday, January 27, 2009

c: alignment of structure

In this article I assume that the computer's word size is 4 bytes(IA32), because the main idea is the same for all architectures and I want to keep the article clean. You just have to adjust this article to your platform.

So, what's with the size of the structure?
You should know that members of data structure(represented by struct keyword in c) are aligned to the power of 2. Each element is stored in the closest(next) address with the appropriate alignment. The whole structure should be aligned as aligned its member with the longest alignment.
The type of each member of the structure usually has a default alignment(if you are not using #pragma pack directive). It's 1 byte for char, 2 bytes for short, 4 bytes for int. You should check this table for your arch.
So the structure

struct
{   
    char a;
    short b;
    int c;
} data;
should be 8 bytes long. How is it calculated? The structure has one char, one short and one int members. The alignment should look like
+-----------------------------------+
|char| XX |  short |       int      |
+-----------------------------------+
0         2        4                8
The short member is stored on the distance of 2 bytes from the address of char because the alignment of short is 2 bytes, the int member is stored just after the short, because the address from the beginning(in this case, or in general from the previously aligned members) is suitable for alignment of int.
But if you change the sequence of the members the whole picture could change, though the number of members and their sizes didn't change. The structure
struct
{   
    char a;
    int c;
    short b;
} data;
on the same platform should be 12 bytes long. Why? Let's calculate.
+---------------------------------------------+
|char| XX | XX | XX |       int      |  short |
+---------------------------------------------+
0         2        4                8         12
That's because the address of integer member is adjusted to its alignment.

Knowing these rules you can optimize the sizes of the structures just moving position of the members inside the structure. Let's add one char in the end to the previously declared structure:
struct
{   
    char a;
    short b;
    int c;
    char d;
} data;
The size of the structure is 12. It's easy to calculate. The size of the structure should be as aligned its member with the longest alignment. In this case the longest alignment is 4. Sequence of char, short, int is aligned to 8 bytes. Adding one char to the end you force compiler to align the structure to 12 bytes, it can't be 9 or anything else. If you look at the alignment of the original structure you could see unused byte that appeared because of the alignment. Let's move d just after(or before, doesn't matter) the a structure member:
struct
{   
    char a;
    char d;
    short b;
    int c;
} data;
The size of this structure should be 8 bytes.
+-----------------------------------+
|char|char|  short |       int      |
+-----------------------------------+
0         2        4                8
If you deal with embed devices where you have significantly small amount of memory it's good optimization. 8 bytes vs. 12 bytes, or 1K vs. 1.5K in case of 128 copies of the structure.

Another approach which is also platform and compiler dependent is to use #pragma pack directive. In general structure
struct
{   
    int c;
    short b;
} data;
should be 8 bytes long. But if you use #pragma pack with alignment to 2 bytes you may force the whole structure will be aligned to 2 bytes.
#pragma pack(push)
#pragma pack(2)

struct
{   
    int c;
    short b;
} data;

#pragma pack(pop)
This structure should be 6 bytes long.

The alignment can cause troubles especially if the data is transmitted between different platforms where alignment or size of type may differ. If it's possible strings(sequences of bytes/chars) should be used. Their alignment should always be 1 byte long.

9 comments:

Oscar said...

Hi,

I liked this article.

I recently done some tests about struct alignment using gcc 3.3.5 on a 32 bit debian box and found a problem that I cannot understand.

Googling a bit I found your blog.

What you say here and my tests shows what you explain (and what I thought) is correct. But testing with a type "long long" on the 32 bit box gives a different result:

typedef struct {
char a;
long long b;
} T1;

gcc 3.3.5 says sizeof(long long) = 8, so the offset of T1.b should be 8 bytes away from the offset of T1.a but, after compiling, offset of T1.b is *4* bytes after T1.a.

Do you know what cound cause this?

P.D: the compilation is done without any arguments passed to gcc:
# gcc test.c

Thanks

Ni@m said...

Hi, Oscar!
I'm pleased that you liked this article.

The alignment of data type is not equal to the size of given data type.
The alignment of data type is defined by target arch.

The alignment of (long long) is 4 bytes on IA32. The maximum alignment on IA32 is 32bits, on IA64 is 64bits. So (double) will be also aligned to 2^2.

IA32 processor works with 4 bytes long data. When you fetch from memory 2 bytes and then write it back the processor will fetch 4 bytes and then will write 4 bytes again. That's why alignment is so important.
Of course there are some optimization which allows to fetch 2, 4 or more words from the memory per 'fetch cycle'(not CPU cycle since there are circumstances which do not allow to fetch from memory that fast). That's depends on prefetching policies, memory controller, northbridge, etc.

If you want to have alignment 8 bytes long you may use 'align' attribute with gcc:
typedef struct {
char a;
double b;
} __attribute__ ((aligned (8))) T1;
In this case size of T1 is 16 bytes.

If you are interested how you can manipulate align properties with gcc please follow http://gcc.gnu.org/onlinedocs/gcc-3.1.1/gcc/Type-Attributes.html and http://gcc.gnu.org/onlinedocs/gcc-3.1.1/gcc/Alignment.html

Oscar said...

:)

OMG! Ok, ok, ok. I think my head is going crazy (being working on some machines at the same time. Swiching from one to another is terrbile for me). Thank you very much!

Well, so, do you know if there is way to know something like a "default" alignment? Maybe something like __alignof__() but more generic, relative to the architecture you are compiling on?

If all this I am asking is stupid, what about using __WORDSIZE as a way to make up a default alignment manually?

What do you think?

Thak you very much.

Ni@m said...

Hello, Oscar!

The default alignment is smth defined by arch of the processor. C/C++ can't tell you what's is the default alignment. The trick you can do with sizeof operator:
struct T {
char c;
long long ll;
};
short alignmentOfLL = sizeof(struct T) - sizeof(long long);

The __WORDSIZE is something which will define the behavior of your application on the compilation stage. If you want to get the wordsize dynamically also look into getpagesize glibc function or sysconf(_SC_PAGESIZE).

What's you purpose of knowing alignment?

Oscar said...

The problem is I don´t have the struct yet. I need to calculate all the alignment and size stuff dinamically.

I'm playing around with libffi, so if I want to pass struct arguments to a function through ffi I need to make everything manually.

I was looking at ctypes for python. They use something like a base alignment (I think), but I didn´t have the time to know exactly where that value come from.

Thanks.

Ni@m said...

I'm not sure how dynamically calculated alignment might help you here but I suppose it's better do define structure in the way you don't need to do anything with with alignment in runtime.
If you want the same ABI between different arches you probably should define your structure this way:
struct T {
char c;
char __hidden0[7];
long long ll;
};
You will fill the padding by yourself. What do you think?

Oscar said...

I'm taking note of your comments as I think will be helpful for me in the future for sure. The problem is that I don't have a struct defined and then compiled, I only have a buffer filled by ffi.

So, thinking a bit and looking at ffi, I realize I was misunderstanding everything:

FFI *provides* all the information needed, like the alignment of the members of the structure and the size of each one.

Once you have prepared the structure layout for ffi and initialize it, you get the alignment and size for each member of the struct depending on the ABI used for the initialization (here was where I was confused and I asked about the dinamic alignment)

Then, with all that info and using the same approach as ctypes for example, you are able to calculate the offsets for each member easily just to get access to the value of each member.

Ni@m said...

Oscar, I'm sorry for the delay here. Too much work lately.
I haven't ever worked with either libffi nor with ctypes so I can't really suggest you anything here.
I'm looking into libffi call and it seems like you indeed don't have to bother about struct alignment. You construct the structure with ffi_prep_cif routine.
Oscar, I'm curious what's your purpose of using libffi or ctypes?

Oscar said...

Hi Dmytro!

Sorry for being so late.

You are correct, libffi does everything for me :).

Well, there is an "addon" for the Io language called CFFI. The addon is incomplete and I am trying to add the missing stuff.

That's all :)