Purpose of Structure Alignment Rules

[swapnaoe]

Hi,
I would like to know why structure alignment rules were introduced.
How does a structure with/without boundary alignments differ.

Regards
Swapna

[Banfa]

To make it easier and faster for the processor to access the data.

All processors will have a native data bus width and (normally) read data from memory aligned to this width. If, for instance, I have a 32 bit processor then it will read memory location aligned to 32 bits.

If I am reading a 32 bit integer from memory if that integer is aligned on a 32 bit (4 byte) boundry then the data can be read with a single instruction. However if the 32 bit integer is not aligned on a 32 bit boundary the data is spread across 2 locations as far as the processor is concerned. It would have to read both locations and them combine the 2 values read by discarding unwanted data and shifting what is left to re-create the 32 bit value take several processor instructions.

So structures (and classes) are packed so that their members appear at boundaries that make it easy for the processor to access. On some platforms this can be overridden forcing structure packing to a less optimal value. This results in moe efficient use of data (no wasted padding bytes) but slower access to the data.

[swapnaoe]

Hi
Explanation well understood. Thanks.
But padding of bytes create 'holes' and block memory usage.What do u have to say on this?

Regards
Swapna

[Banfa]

Hi
Explanation well understood. Thanks.
But padding of bytes create 'holes' and block memory usage.What do u have to say on this?

Regards
Swapna

Generally speaking this wastage is relatively low (a few bytes per structure) compared to the amount of memory systems tend to have today. So unless you have a lot of those structures the wastage is probably negligible.

If you have a very large number of structures or limited memory then reducing this wastage may be sensible. You can do this by crafting your structures carefully, take this example

[code=c]
struct example {
char c1;
short s;
char c2;
long l;
char c3;
};
[/code]
On a 32 bit machine this will most likely(but not necessarily) appear in memory as

Memory
Offset    Contents  Comments
   0      c1        size 1 byte
   1      padding   Next member is a short and must be 2 byte aligned
   2      s         size 2 bytes
   4      c2        size 1 byte
   5      padding   Next member is 
   6      padding   a long and must 
   7      padding   be 4 byte aligned
   8      l         size 4 bytes
   12     c3        size 1 byte
   13     padding   structure contains a 
   14     padding   long so it must be 4 
   15     padding   byte aligned in an array

This is 16 bytes long, 7 bytes (44%) of which are padding. However if I re-write the structure as

[code=c]
struct example {
long l;
short s;
char c1;
char c2;
char c3;
};
[/code]then this becomes

Memory
Offset    Contents  Comments
   0      l         size 4 bytes
   4      s         size 2 bytes
   6      c1        size 1 byte
   7      c2        size 1 byte
   8      c3        size 1 byte
   9      padding   structure contains a 
   10     padding   long so it must be 4 
   11     padding   byte aligned in an array

This holds exactly the same data but is only 12 bytes long, 3 bytes (25%) o which are padding. Notice that I have put the long first and the short second followed by the chars. That is the basic rule, if you are concerned about memory usage then put the members into your structure structure in size order.

Obviously I have written the example to illustrate the point and a 4 byte saving may not seem like much however I have had examples where I have saved 7 bytes in a structure that was in an array of 2000 structures for a 13.6k memory saving.

This may again not seem like much however the particular application was an embedded project with limited memory (a few MBytes) and had run out of ram. If you try you can do an awful lot with 13.6k of ram.

On some platforms you can eliminate all the padding by forcing the compiler to produce 1 byte aligned structures, however as I said before this incurs a performance penalty accessing the structures in memory. Re-arrranging the structures structure like this saves memory with no performance loss.

However before you attempt to do it you should make sure that you full understand the structure alignment rules of your current platform.

[swapnaoe]

Banfa,

Thanks again.
Request you to exaplin me the terminologies:

2 byte aligned
4 byte aligned

I understand that '2 byte aligned' means, a data type whose size is 2-bytes, has to be stored in memory only at even addresses(inclu ding 0) like 2,4,6....
4 byte aligned, means a data type whose size is 4-bytes has to be stored at memory addresses which are multiples of 4(including 0).

If what I understood is right then, on a 32 bit processors for example how can we genralize(for 2-byte , 4-byte) speed and performance in terms of data access.

Please let me know if my query is unclear.

Regards
Swapna

[Banfa]

Request you to exaplin me the terminologies:

2 byte aligned
4 byte aligned

I understand that '2 byte aligned' means, a data type whose size is 2-bytes, has to be stored in memory only at even addresses(inclu ding 0) like 2,4,6....
4 byte aligned, means a data type whose size is 4-bytes has to be stored at memory addresses which are multiples of 4(including 0).

This is half correct, the alignment does not actually give you any information about the size of the data type only the address that it needs to be stored at which you have correct.

For instance I have worked with on a platform where a specific piece of the hardware needed to be passed buffers that where 1600 bytes long and 16 byte aligned.

If what I understood is right then, on a 32 bit processors for example how can we genralize(for 2-byte , 4-byte) speed and performance in terms of data access.

The best trade off is what I said in my previous post. When creating a structure put the largest members first and the smallest members last in the structure. This way you will reduce the number of padding bytes that appear without effecting processor performance. You will be still wasting a little memory but removal of that wastage will result in a processor performance hit.

[swapnaoe]

You said the best way to minimize the number of padding bytes, the structure members should be declared in the descending order of their sizes.
I executed a structure declared its members in the follwoing orders.

char,short,int, char,long 16 bytes(structure size)
long,short,char ,char,int 12 bytes
char,long,char, short,int 20 bytes
long, short,int,char, char 16 bytes
char,char,short ,int,long 12 bytes (ascending order)

As you see, the members declared in ascending order give the best solution and in descending order occupy 16 bytes.

I ran this on a 32-bit intel processor with VC++ 6.0.
short occupies- 2 bytes
int and long occupy- 4 bytes
I think what you said is not always right. May be a optimal padding can be achieved.

[smalpani]

your example does not contain a descending order which is optimal too

And while creating your structure you should be less worried about your padding rules, unless there is a real memory constain.

Why I am saying is apart from optimization there is something called code-readability.

So if you have some un-related/related data in your structure. So it is better to arrange the structure in such a way that while reading the structure some one should be able to understand what you are trying to achieve or rather, some one should be able to find the required field at a sensible place. Otherwise the person has to scroll through the struct.

[Banfa]

char,short,int, char,long 16 bytes(structure size)
long,short,char ,char,int 12 bytes
char,long,char, short,int 20 bytes
long, short,int,char, char 16 bytes
char,char,short ,int,long 12 bytes (ascending order)

As you see, the members declared in ascending order give the best solution and in descending order occupy 16 bytes.

long, short,int,char, char 16 bytes

is not decsending order because sizeof(int) >= sizeof(short) and on a 32 bit system then probably sizeof(int) == 4 and sizeof(short) == 2.

Decsending order would have been

long,int,short, char,char 12 bytes


Having a quick think about it I suspect that ascending order and decending order are actually always going to give the same result for size. For memory efficiency what you need to avoid is putting the members in the structure in random size order.

[swapnaoe]

I am very sorry about it... :)
Yeah u very right...
long
int
short
char
char

Gives 12 bytes.

Regards

[mohammadazim]

Actual reason of struct padding is that on some platforms a variable can be placed and accessed only on memory address multiple of size of that variable. That is why if next variable is bigger then the previous one in a struct then some bytes may be inserted to reach required address.

Take following example to understand struct padding

struct padding
{
char ch1,
short s1,
char ch2
long l1
}

First thing to understand from above explanation is that our struct will occupy memory multiple of size of largest var. In our case it is size of long i.e. 4 bytes.
Second, we can proceed by making 4 bytes memory blocks

***1st 4byte block********** ***
1 byte for char ch1.
1 byte of padding. Since it can come on address multiple of 2.
2 bytes for short s1.
*************** *************
***1st 4byte block********** ***
1 byte for ch2.
3 of padding since next long can’t be accommodated in remaining 2 bytes of this block.
*************** *************
***1st 4byte block********** ***
4 bytes for long.
*************** *************
Total = 12 bytes.

Now lets see what happens when we make struct padding as

struct padding
{
1ong l1,
short s1,
char ch1,
char ch2
}


***1st 4byte block********** ***
4 bytes for l1.
*************** *************
***1st 4byte block********** ***
2 byte for s1.
1 byte for ch1.
1 byte for ch2.
*************** *************
Total = 8 bytes.

So here we saved 4 bytes.

And Banfa is absolutely right on ascending descending.

I came to know about this while coding encode-decode functions for an application. And want to give a fair suggestion that never directly copy structs on messages because if you have change any thing in future then it may become a backward compatibilty issue. Try writing bytes simply.

[swapnaoe]

Actual reason of struct padding is that on some platforms a variable can be placed and accessed only on memory address multiple of size of that variable. That is why if next variable is bigger then the previous one in a struct then some bytes may be inserted to reach required address.

Take following example to understand struct padding

struct padding
{
char ch1,
short s1,
char ch2
long l1
}

First thing to understand from above explanation is that our struct will occupy memory multiple of size of largest var. In our case it is size of long i.e. 4 bytes.
Second, we can proceed by making 4 bytes memory blocks

***1st 4byte block********** ***
1 byte for char ch1.
1 byte of padding. Since it can come on address multiple of 2.
2 bytes for short s1.
*************** *************
***1st 4byte block********** ***
1 byte for ch2.
3 of padding since next long can’t be accommodated in remaining 2 bytes of this block.
*************** *************
***1st 4byte block********** ***
4 bytes for long.
*************** *************
Total = 12 bytes.

Now lets see what happens when we make struct padding as

struct padding
{
1ong l1,
short s1,
char ch1,
char ch2
}


***1st 4byte block********** ***
4 bytes for l1.
*************** *************
***1st 4byte block********** ***
2 byte for s1.
1 byte for ch1.
1 byte for ch2.
*************** *************
Total = 8 bytes.

So here we saved 4 bytes.

And Banfa is absolutely right on ascending descending.

I came to know about this while coding encode-decode functions for an application. And want to give a fair suggestion that never directly copy structs on messages because if you have change any thing in future then it may become a backward compatibilty issue. Try writing bytes simply.

Thanks to all. That was very informative on structures.