Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Memory Alignment

align

  • Please log in to reply
7 replies to this topic

#1 RoboticForest

RoboticForest

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 130 posts
  • Location:Salem, OR
  • Programming Language:Java, C++

Posted 07 January 2009 - 06:13 PM

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.
  • 0

No trees were harmed in the sending of this message, but millions of electrons were severely inconvenienced.


#2 Lance

Lance

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 270 posts

Posted 07 January 2009 - 06:43 PM

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.
  • 0

#3 Lance

Lance

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 270 posts

Posted 07 January 2009 - 06:55 PM

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

Edited by Lance, 07 January 2009 - 07:01 PM.
example

  • 0

#4 RobotGymnast

RobotGymnast

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 132 posts

Posted 07 January 2009 - 07:04 PM

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.

Edited by RobotGymnast, 07 January 2009 - 07:47 PM.

  • 1

#5 Lance

Lance

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 270 posts

Posted 07 January 2009 - 07:23 PM

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

Edited by Lance, 07 January 2009 - 07:24 PM.
tag

  • 1

#6 Lance

Lance

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 270 posts

Posted 07 January 2009 - 07:29 PM

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.

Edited by Lance, 07 January 2009 - 07:31 PM.
grammer

  • 0

#7 RobotGymnast

RobotGymnast

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 132 posts

Posted 07 January 2009 - 07:42 PM

Tee hee.

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

#8 RoboticForest

RoboticForest

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 130 posts
  • Location:Salem, OR
  • Programming Language:Java, C++

Posted 07 January 2009 - 08:04 PM

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.
  • 0

No trees were harmed in the sending of this message, but millions of electrons were severely inconvenienced.






Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download