console-dev.de

Earlier this day, while reading my daily forum threads, I came across a rather quirky C/C++ struct, that reminded me on some of my own evil doings when I worked on HEL Library, where I came up with the following struct for the new sprite system introduced in HEL 2 Library:

1
2
3
4
5
6
7
8

struct StupidMemberAlignment
{
  unsigned short Attr[3];
  unsigned short Flags;
  unsigned char Next;
  unsigned char Prev;
  const void* pSrc;
};

After I pushed out the first release candidate of HEL 2, Jasper Vijn was kind enough to sent me an email to let me know I can reduce the size of the struct by 4 bytes, by simply reorder its members.

Now you might think: 4 bytes, hello?! Please keep in mind, HEL Library was built for the Game Boy Advance and 128 of those structs were instantiated all the time. Once I reordered the struct members, I had 512 bytes more memory available. This is more than 3% of the internal work RAM!

Jasper suggested to change the struct to the following:

1
2
3
4
5
6
7
8

struct BetterMemberAlignment
{
  unsigned short Attr[3];
  unsigned char Next;
  unsigned char Prev;
  unsigned long Flags;
  const void* pSrc;
};

Why should the struct get smaller, when I reorder its members and even change Flags from short to long, which is two bytes larger?

It happens, because the compiler inserts padding bytes, when one of the members is not aligned on the members type size. In other words, when your struct contains a type larger than one byte, make sure the member is aligned on its type size, otherwise the compiler will do this for you automatically (except you turned off alignment or specified the packed attribute).

Let’s take a look at the StupidMemberAlignment struct again. This time, I added how you might think at which byte offset each member is located:

1
2
3
4
5
6
7
8
9
10

// PLEASE NOTE THE BYTE OFFETS ARE WRONG!
// I EXPLAIN WHY IN THE TEXT BELOW!
struct StupidMemberAlignment
{
  unsigned short Attr[3]; // byte offset 0
  unsigned short Flags; // byte offset 6
  unsigned char Next; // byte offset 7
  unsigned char Prev; // byte offset 8
  const void* pSrc; // byte offset 9
};

Summing up all members, the struct should be 14 bytes, but sizeof(StupidMemberAlignment) tells me it’s 16 bytes!

The reason why is quite simple: pSrc is 32bit wide, but not aligned on a 32bit boundary! The compiler silently inserts padding bytes, to ensure correct alignment, because the ARM7TDMI target CPU doesn’t support accessing mis-aligned addresses.

The compiler generated instead:

1
2
3
4
5
6
7
8
9
10
11

struct StupidMemberAlignmentPadded
{
  unsigned short Attr[3]; // byte offset 0
  unsigned short Flags; // byte offset 6
  unsigned char Next; // byte offset 7
  unsigned char Prev; // byte offset 8
  unsigned char _padding0; // byte offset 9
  unsigned char _padding1; // byte offset 10
  unsigned char _padding2; // byte offset 11
  const void* pSrc; // byte offset 12
};

I could had specified attributes to pack the struct as well, but the compiler generates usually more and even slower code for parts where objects or members of packed structs are accessed, so this was no option for me on a 16Mhz target device. Reordering the members was the proper solution in my opinion.

Keep that in mind next time you design struct’s that have to be efficient!

Follow up material:

• Wikipedia: Data Structure Padding
• Wikipedia: Data Structure Alignment
• GBATEK: CPU Memory Alignments
• GCC: Type Attribute(s)