How do I make the following C structure more memory efficient?

Question

I am trying to solve a rather challenging programming task. We are given the following 64-bit structure, which allows us to store a point in time accurate to the minute:

typedef struct
{
  unsigned char day;  //1 Byte
  unsigned char month; //1 Byte
  unsigned int year;  //4 Bytes
  unsigned char hours; //1 Byte
  unsigned char minutes; //1 Byte
} Time; //4 Bytes are probably used for padding

This structure has the size of 12 Bytes (I checked this and the struct really does use so much space). The task is to reduce the size to 8 Bytes and we are not allowed to use unions. We are supposed to use a lot of these structures, hence why we want to reduce the memory size.

The only thing I can think of is to change the unsigned int to unsigned short, but how can we get rid of the other two Bytes?

Kind regards

Answer 1

The main problem here is that char have no alignment requirement, but int has a requirement of 4 byte alignment (on a 32 bit system). Meaning it must start at an address divisible by 4. Structs are guaranteed to start at an aligned address, so what you get is likely this:

unsigned char day;  //1 Byte
unsigned char month; //1 Byte
// 2 byte padding!
unsigned int year;  //4 Bytes
unsigned char hours; //1 Byte
unsigned char minutes; //1 Byte
// 2 byte padding!

The first two padding bytes are there to ensure that the int is aligned, the last two are there to ensure that the next struct in an array of structs start at an aligned address.

The fix is simple, just move year to the top of the struct:

unsigned int year;  //4 Bytes
unsigned char day;  //1 Byte
unsigned char month; //1 Byte
unsigned char hours; //1 Byte
unsigned char minutes; //1 Byte

And now the struct should be 8 bytes large with zero padding.

Answer 2

Your current struct, since sizeof(Time) == 12 and sizeof(unsigned int) == 4 is layed out like this:

typedef struct
{
  unsigned char day;  //1 Byte
  unsigned char month; //1 Byte
// 2 bytes padding to align the `unsigned int`
  unsigned int year;  //4 Bytes
  unsigned char hours; //1 Byte
  unsigned char minutes; //1 Byte
// 2 bytes padding
} Time; 

You can reduce the size to 8 by moving year first. No padding needed here:

typedef struct
{
  unsigned int year;  //4 Bytes
  unsigned char day;  //1 Byte
  unsigned char month; //1 Byte
  unsigned char hours; //1 Byte
  unsigned char minutes; //1 Byte
} Time; 

Answer 3

The compiler aligns the data based on the alignment of the next field of a structure, in your case you have two char fields that have alignment of 1 (any address is valid to hold a char) but the int type (32bit) has an alignment requirement of 4bytes, so, as the offset when the second char element is 2, it needs to add two alignment spaces to make it properly aligned (to an address multiple of 4) and it also makes the whole struct to be 4 aligned, so when the struct end arrives, there's an alignment of 4 for the next structure of this type (to properly conserve the alignment of the full structure in arrays) and so, it needs to add two more bytes to the end of the structure. This makes the four bytes you observe in your code.

To optimize, just put the large fields first on the structure, and fill it later at the end with the smaller data (that has less alignment requirements) This way, the structure aligns better with the bigger fields and the fields tend to fill the holes made by alignment. if you had used, instead:

struct my_struct {
    double        time_as_double;  // normally 8 byte alignment
    char         *timezone;        // 8 byte alignment in 64bit architectures.
    int           year;            // 4 byte alignment
    unsigned char month,           // one byte alignment
                  mday,            // one byte alignment
                  hour,            // one byte alignment
                  min,             // one byte alignment
                  sec;             // one byte alignment
    // seven more bytes of alignment to comply with 8 byte alignment for the
    // full structure (to allow it to form arrays)
};

you will get a 32 byte structure (a worst case, as it resulted in 25 packed bytes, so the next multiple of 8 is 32)

#include <stdio.h>

struct my_struct {
    double        time_as_double;  // normally 8 byte alignment
    char         *timezone;        // 8 byte alignment in 64bit architectures.
    int           year;            // 4 byte alignment
    unsigned char month,           // one byte alignment
                  mday,            // one byte alignment
                  hour,            // one byte alignment
                  min,             // one byte alignment
                  sec;             // one byte alignment
    // seven more bytes of alignment to comply with 8 byte alignment for the
    // full structure (to allow it to form arrays)
};

int main()
{
    printf("sizeof (struct my_struct) == %zu\n", sizeof (struct my_struct));
}

which produces:

$ a.out
sizeof (struct my_struct) == 32
$ _