Talk:Data structure alignment

The page gives no reason why this practise is used. --Anonymous

I replaced this, and left out the specific programs mentioned because I could not find any mention of trouble porting those specific programs: "A common problem in computer programming is called word alignement. One way to increase performance, especially in RISC processors which are designed to maximize raw performance is to require data to loaded or stored on a word boundary. So though memory is commonly addressed by 8 bit bytes, loading a 32 bit integer or 64 bit floating point number would be required to be start at every 64 bits on a 64 bit machine. The processor could flag a fault if it were asked to load a number which was not on such a boundary, or call a routine which would effectively figure out which word or words contained the data and extract the equivalent value. This caused difficulty when the team from Mosaic Software ported their Twin Spreadsheet to the 68000 based Atari ST. The Intel 8086 architecture had no such restrictions. It would also cause difficulties in porting Microsoft Office to Windows NT on MIPS and PowerPC for NEC and IBM. Since the software was not written with such restrictions in mind, designers had to set a bit in the O/S to enable non-aligned data. However since this bit was masked with other flags, it was impossible to keep the O/S from faulting on non-aligned data when other modules used the other flags. This may have been a major factor in abandoning Windows NT on non-Intel processors as they failed as platforms for hosting common Windows applications and one more reason for the baffling dominance of the x86 architecture over technologically elegant rivals. "

I hope to have provided sufficient background, but I think the article still needs some work. (but I need to sleep)

Aij 07:03, 29 May 2006 (UTC)

Packed array

What is a packed array? It redirects here, but I could not find it. 85.145.103.163 (talk) 15:52, 30 January 2008 (UTC)

In the section Data_Structure_Padding, the article talks about that. 0x6adb015 (talk) 14:07, 3 March 2008 (UTC)

Too verbose/jargon filled

I'm a 4th year Comp Sci student sitting a PhD next year...and don't think the description here is clear enough. It really doesn't explain it in any useful way. I think a diagram, an analogy, or something similar would help. In its current state it's no use to anyone who isn't a computer expert-I come pretty close, and I can't follow it. It needs to be much, much, simpler at first, instead of jumping right into details. —Preceding unsigned comment added by 130.209.241.193 (talk) 11:53, 27 April 2008 (UTC)

I agree, one thing which struck is why is the word datum used instead of data? I've seen the word used before but needed to look it up, only to see that it's apparantly just a synonym to data, which is significantly more well understod. —Preceding unsigned comment added by 195.84.66.198 (talk) 13:31, 7 June 2008 (UTC)

I rewrote the introduction, added a short example and removed the {{context}} tag. Virtlink^t•c 22:08, 28 July 2008 (UTC)

...due to how the CPU handles memory

I've read the article and, well I agree with the opinions above, but, in the introduction there's a part that says '...due to how the CPU handles memory'. Well if you Google that you're going to come up with thousands of hits... how 'bout a link or something that could explain the part of "how the CPU handles memory" that it's really important on the "Structure padding"? thanks. (I would do it myself but my knowledge doesn't extent that long :S) —Preceding unsigned comment added by 190.201.223.72 (talk) 01:31, 20 January 2009 (UTC)

Default packing and #pragma pack

The cited source for this section doesn't support the information presented. The linked MSDN article just talks about "default alignment" derived from member type, e.g. 4 bytes for an int. This is very different from /Zp packsize which basically wraps whole source file in #pragma pack(push, N) ... #pragma pack(pop). —Preceding unsigned comment added by 195.146.153.234 (talk) 16:14, 4 October 2010 (UTC)

least common multiple requires at least 2 args

The

Typical_alignment_of_C_structs_on_x86

section contains the sentence:

 It is important to note that the last member is padded with the
 number of bytes required that the total size of the structure should
 be a least common multiple of the size of a largest structure
 member.

However, from

 [the Least_common_multiple page]

the least common multiple operator (lcm) requires 2 arguments; hence, the cited sentence is confusing because it implies lcm is unary. It's also probably wrong because it makes no mention of the alignment of the largest structure member, it only mentions the size of the largest structure member.

Hence, according to this sentence, if the largest structure member is:

 char[1000] carray;

and the complete structure were:

 struct A{ char[1000] carray, char last};

then this sentence would require the A::last to have 999 padding characters after it. That's wrong, as shown by the program:

 struct A
 { char carray[1000];
   char last;
 };
 
 #include <iostream>
 
 int main(void)
 {
     std::cout<<"sizeof(A)="<<sizeof(A)<<"\n";
     return 0;
 }    

whose output is:

 sizeof(A)=1001

In addition, the page:

 cxx-data-alignment-portability

claims:

 The compiler always assumes that an instance of foo will start at an address 
 aligned to the most strict alignment requirement of all of foo’s members,

which suggests that the aforementioned Typical_alignment_of_C_structs_on_x86 section sentence should be modified to:

 It is important to note that the last member is padded with the
 number of bytes required that the total size of the structure should
 be a multiple of the largest alignment of the structure's members.

In addition, the reference:

 [1]

claims, on page 13:

 Structures and unions assume the alignment of their most strictly aligned component.

Also, the reference:

 [2]

makes a similar claim on page 3-38:

 The alignment of a non-packed structure is the maximum alignment required of any of its fields.

Both claims support the modification suggested above.

— Preceding unsigned comment added by Cppljevans (talk • contribs) 13:27, 16 February 2011 (UTC)

Yes I totally agree. And I have tested an example with a double to make sure that the structure was not sized a multiple of 8. As you say there is a logic error in any case since the largest element may be an arbitrarily sized array. I have made a change to replace 'least common multiple' with multiple and corrected my change to your correct interpretation of the largest alignment of the members not 'the platform' which I asserted initially. I have added 2 (compiled and tested) examples which should clear this up. Kerfuffle090 (talk) 22:50, 18 June 2011 (UTC)

calculation of whole structure alignment and size and all member paddings

Given the following pseudo-c++-code data structure:

 struct TheStructure
 {
     Type[1] member[1];
     Type[2] member[2];
     ...
     Type[N] member[N];
 };

composed of N members:

 member[1]...member[N]
 

of types:

 Type[1]...Type[N]
 

, and the following definitions:

   unsigned 
 alignof(SomeType)
   //Purpose:
   //  Returns the alignment of type, SomeType.
   //  Implementation defined.
   ;
 
   unsigned 
 sizeof(SomeType)
   //Purpose
   //  Returns the size of type, SomeType.
   //  Implementation defined.
   ;
 
   unsigned
 aligned_offset
   ( unsigned size
   , unsigned alignment
   )
   //Purpose:
   //  Returns minimum offset >= size such that
   //  offset%alignment == 0.
   //Ensures:
   //  for some unsigned q>=0
   //    offset == alignment*q
   //    size <= offset < size+alignment
   //Requires:
   //  1 <= alignment
   {
         unsigned 
       remainder = size%alignment
         //The following assertions from reference:
         //  http://en.wikipedia.org/wiki/Modulo_operation
         //
         //    r == a - n*floor(a/n)
         //    0 <= r < n
         //
         //when replaced with the corresponding variable names 
         //used here, become:
         //
         //  q == floor(size/alignment)
         //  remainder == size - alignment*q
         //  0 <= remainder < alignment
         //
         //These assertions are illustrated by the following
         //number-line diagram:
         //
         //  |<------- size ----------------------->|
         //                       |<-- remainder -->|
         //  |<-- alignment*q --->| 
         //
         ;
       unsiged offset 
         = remainder == 0
         ? size
           //In this case, the number-line diagram becomes:
           //
           //  |<------- size ----->|
           //                    -->|<-- remainder
           //  |<-- alignment*q --->| 
           //  |<----- offset ----->| 
           //
           //thus:
           //
           //  offset == alignment*q
           //  offset%alignment == 0
           //
         : size+alignment-remainder
           //In this case, the above number-line diagram
           //needs to be augmented to become:
           //
           //  |<------- size ----------------------->|
           //                       |<-- remainder -->|
           //  |<-- alignment*q --->|<---- alignment ---->|  
           //                  alignment-remainder -->|   |<--
           //  |<----- offset --------------------------->| 
           //
           //thus:
           //
           //  offset == alignment*(q+1)
           //  offset%alignment == 0
           //
         ;
       return offset;
   }
 
 align[i] = alignof(Type[i])//alignment of member[i]
   for i=1 to N
   ;
 
 size[i] = offset[i]+sizeof(Type[i])
   //Size of TheStructure truncated to just i members.
   for i=1 to N
   ;
   
 offset[1] = 0
   //offset from start of TheStructure to start of member[1]
   ;
   
 offset[i+1] = aligned_offset(size[i],align[i+1])
   //If i<N
   //  the offset from the start of TheStructure to the start of 
   //  member[i+1]
   //else if i==N
   //  the offset from the start of TheStructure to the start of
   //  the next contiguous TheStructure. IOW, this is
   //  sizeof(TheStructure).
   for i=1 to N
   ;
                   

The only unknown in the above is align[N+1]; hence, the problem is:

 Find:

   align[N+1] //alignment for TheStructure
 
 constrained_by:
 
   (m*align[N+1]+offset[i]) % align[i] == 0 
     //member[i] is properly aligned
     //This constraint is labelled the "member_constraint[i]".
     , for i=1 to N
     , for any unsigned m>=0
     
   (align[N+1]+offset[N+1]) % align[N+1] == 0 
     //If two TheStructure's are contiguous in memory,
     //the second is properly aligned.
     //This constraint is labelled the "structure_constraint".

For the particular case when 1==i, the member_constraint[1] is:

   (m*align[N+1]+offset[1])%align[1] == 0
       , for any unsigned m>=0
       
 After substituting in the definition of offset[1], this becomes:

   (m*align[N+1])%align[1] == 0
       , for any unsigned m>=0
       
 Any solution has the form:
 
   align[N+1] == j*align[1]
     , for any unsigned j>=1.
 
 IOW, the set of solutions for align[N+1] for member_constraint[1]
 is: 
 
   soln[1] = {j*align[1]|unsigned j>= 1}
   

For the particular cases when 1<i<=N, the member_constraint[i] is:

   (m*align[N+1]+offset[i]) % align[i] == 0
     , for any unsigned m>=0
     
 After substituting in the definition of offset[i-1], this becomes:

   (m*align[N+1]+aligned_offset(size[i-1],align[i]) % align[i] == 0
     , for any unsigned m>=0
     
 After substituting in Ensures: assertion from aligned_offset, this becomes:

   (m*align[N+1]+align[i]*q) % align[i] == 0
     , for any unsigned m>=0
     , for some unsigned q>=0
     
 Any solution has the form:
 
   align[N+1] == j*align[i]
     , for any unsigned j>=1.
 
       
 IOW, the set of solutions for align[N+1] for member_constraint[i]
 for 1<i<=N  is:
   
   soln[i] = {j*align[i]|unsigned j>= 1}
   

Thus, there's a sequence of solutions, one for each member:

 soln[1], soln[2], ... soln[N]
 

For the structure_constraint:

 (align[N+1]+offset[N+1]) % align[N+1] == 0 
   

after substituting in the definition of offset[N+1], this becomes:

 (align[N+1]+aligned_offset(size[N],align[N+1]) % align[N+1] == 0

After substituting in Ensures: assertion from aligned_offset, this becomes:

 (m*align[N+1]+align[N+1]*q) % align[N+1] == 0
   , for any unsigned m>=0
   , for some unsigned q>=0
   

which, after simplification, becomes:

 (align[N+1]*(m+q)) % align[N+1] == 0
   , for any unsigned m>=0
   , for some unsigned q>=0
   

which is obviously true as long as 0 < align[N+1].

To handle the boundary case when N==0(no members), define:

 align[0] = 1
 soln[0] = {j*align[0]|unsigned j>=1}
         = {j|unsigned j>=1}
 

So, there are n+1 partial solutions, all of the form:

 soln[i] = {j*align[i]|unsigned j>=1}
   for i=0 to N

To satisfy all of soln[0],soln[1]...soln[N], align[N+1] has to be in the intersection of soln[0],soln[1]...soln[N]. IOW, align[N+1] has to be a multiple of all of align[0],align[1]...align[N]. The least solution satisfying this constraint is the least common multiple of align[0],align[1],align[2],...,align[N].

In summary, using haskell foldl

 alignof(TheStructure) = foldl lcm align[0] [align[1],align[2],...,align[N]]

In case N==0, then:

 alignof(TheStructure) = foldl lcm align[0] [] == align[0] == 1.
 

In case all of the alignments are of the form:

 align[i] = 2**n[i], for some unsigned n[i],
 

where 2**k is 2 raised to the k-th power, then max can be used in place of lcm since lcm(2**k,2**(k+n)) = 2**(k+n).

Cppljevans (talk) 13:05, 17 February 2011 (UTC)