Memory Alignment

[roboticforest]

To an extent I understand -how- memory alignment works, but I think my mind is lagging today, because I can't seem to get -why- it works.

My questions are:

Why is there a speed boost on aligned data?

Why was padding added to these places in this structure?

struct MixedData  /* after compilation */
{
    char Data1;
    char Padding0[1]; /* For the following 'short' to be aligned on a 2 byte boundary */
    short Data2;
    int Data3;  
    char Data4;
    char Padding1[3];
};

This lovely structure was taken from this Wikipedia entry I just finished reading. Data structure alignment - Wikipedia, the free encyclopedia

Perhaps the answers to my questions are in there, but I missed them.

[Lance]

Without padding, what would happen if you have an array of MixedData objects?

struct MixedData  /* after compilation */
{
    char Data1;
    char Padding0[1]; /* For the following 'short' to be aligned on a 2 byte boundary */
    short Data2;
    int Data3;  
    char Data4;
    // char Padding1[3]; with out without this, MixedData will take up same space
   
};

consider,

struct B{
       char c;
       int    iData;
};

Without padding, iData could be on an odd address, many CPU cannot handle that.

try this code:

char buff[]={3,8,7,9,6};

std::count<<reinterpret_cast<int&>(buff[1]);

Generally, WORD are required to have even address, DWROD are required to have multiple of 4 address (0x80000, 0x80004, etc), QUADROWORD are required to have multiple of 8 address. If in a struct, some member requires more stringent alignment, compiler will try to satisfy it, often by padding.

[Lance]

Gosh, I am supprised the code actually word and generate correct result on my machine. Maybe indeed it's for speed concern only. Sorry for the misinformation.

Here is my test code:

#include <iostream>
#include <string.h>

int i=1234567890;
char buff[10];


int main()
{
	memcpy(buff+1, &i,  sizeof(int));
	std::cout<<"If the following 2 lines are the same, int can have odd address!"<<std::endl;
	std::cout<<reinterpret_cast<int&>(buff[1])<<std::endl;
	std::cout<<i<<std::endl;
	std::cout<<"If the following line is same the 2nd line, void * can have odd address!"<<std::endl;
	
	int * p=&i;
	memcpy(buff+1, &p, sizeof(void *));
	std::cout<<**reinterpret_cast<int **>(buff+1)<<std::endl;
}

And here is the output

If the following 2 lines are the same, int can have odd address!
1234567890
1234567890
If the following line is same the 2nd line, void * can have odd address!
1234567890

[RobotGymnast]

It isn't so much that the CPU can't read un-padded variables, it's just much more efficient to pad it.

CONSIDER THE FOLLOWING:

struct foo {
    BYTE a;
    UINT b;
};

foo f[2];
f[0].a = 0x7;
f[0].b = 0x8;
f[1].a = 0x9;
f[1].b = 0xA;

Now remember that a CPU can only read (on x86) a DWORD at a time. No more, no less. The structure of the memory if this snippet is not aligned is...

00400000: 0700 0000
00400004: 0809 0A00
00400008: 0000 0000

Now let's say you wanted to read f[0]. First you would have to get the data at address 00400000 to get .a, then you would need to read address 00400004 to get the value of .b. Then to get f[1].a, you'd need to read 00400004, then right shift it 4 places and AND it with 0xFF. Then to get .b, you'd need to read in 00400004, AND it with 0xFFFF, then OR it with 00400008, after it is right shifted 4 places.

As you can see, it's extremely confusing and there'd be way too much overhead for it to be worth it.

The moral of the story:
PAD YOUR STRUCTURES.

[Lance]

The following excerpts are from the Wiki page link of which has been posted by roboticforest.

RISC

Most RISC processors will generate an alignment fault when a load or store instruction accesses a misaligned address. This allows the operating system to emulate the misaligned access using other instructions.

x86 and x86-64

While the x86 architecture originally did not require aligned memory access and still works without it, SSE2 and x86-64 instructions on x86 CPUs do require the data to be 128-bit (16-byte) aligned and there can be substantial performance advantages from using aligned data on these architectures.

Most of the time, the padding will be done by a compiler when necessary. check sizeof(foo) (foo as defined in RobotGymnast's post), you will most likely get 8 instead of 5, because the compiler has done padding for you.

What a struct/class designer can do is to put similarly aligned data together, for example

struct Bar{
     char a;
     int i;
     char c;
     int j;
     short s;
};

would be a lot bigger than

struct Bar{
     char a;
     char c;
     short s;
     int i;
     int j;
};

Padding is something you need to know but rarely need to do it by yourself

[Lance]

RobotGymnast's post did explain why padding makes memory access more efficient, even though I don't agree with his MORAL OF THE STORY part.

[RobotGymnast]

Tee hee.

I had fun with that post. Trying to procrastinate a careers project.

[roboticforest]

Thank you all, I get it now.

I just needed a rewording, and quoting the wiki I read helped too. I guess I needed to reread those parts.