Struct packing and alignment in Embedded C - Time & Space Complexity

Time Complexity: Struct packing and alignment

O(n)

Understanding Time Complexity

When working with structs in embedded C, how the data is packed and aligned affects how fast the program runs.

We want to see how the program's speed changes as the struct size or layout changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Data {
  char a;
  int b;
  char c;
};

void process(struct Data *arr, int n) {
  for (int i = 0; i < n; i++) {
    arr[i].b += 1;
  }
}
    

This code loops through an array of structs and updates one field in each struct.

Identify Repeating Operations

• Primary operation: Looping through each struct in the array.
• How many times: Exactly once for each element, so n times.

How Execution Grows With Input

As the number of structs grows, the loop runs more times, so the work grows directly with n.

Input Size (n)	Approx. Operations
10	10 updates
100	100 updates
1000	1000 updates

Pattern observation: The work grows in a straight line as n increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows directly with the number of structs you process.

Common Mistake

[X] Wrong: "Changing struct packing will change how many times the loop runs."

[OK] Correct: The loop count depends only on n, not on how the struct fields are arranged or padded.

Interview Connect

Understanding how struct layout affects memory but not loop count helps you explain performance clearly and confidently.

Self-Check

"What if we added a nested loop inside process that compares each struct to every other struct? How would the time complexity change?"

Practice

1. What does struct packing do in embedded C?

easy

A. Removes extra spaces between fields to save memory

B. Adds extra spaces to align data on memory boundaries

C. Changes the data types of struct members

D. Automatically initializes struct members to zero

Solution

1. Step 1: Understand struct packing purpose

   Struct packing removes padding bytes between fields to reduce memory usage.

2. Step 2: Compare with alignment

   Alignment adds padding for faster access, packing removes it to save space.

3. Final Answer:

   Removes extra spaces between fields to save memory -> Option A

4. Quick Check:

   Struct packing = removes padding [OK]

Hint: Packing removes spaces, alignment adds spaces [OK]

Common Mistakes:

• Confusing packing with alignment
• Thinking packing changes data types
• Assuming packing initializes values

2. Which of the following is the correct syntax to pack a struct in embedded C using GCC?

easy

A. struct MyStruct { int a; char b; } __packed;

B. struct MyStruct __packed { int a; char b; };

C. struct MyStruct { int a; char b; } __attribute__((aligned));

D. struct __attribute__((packed)) MyStruct { int a; char b; };

Solution

1. Step 1: Recall GCC packing syntax

   GCC uses __attribute__((packed)) after struct keyword or at end of struct definition.

2. Step 2: Identify correct placement

   struct __attribute__((packed)) MyStruct { int a; char b; }; places __attribute__((packed)) correctly after struct keyword.

3. Final Answer:

   struct __attribute__((packed)) MyStruct { int a; char b; }; -> Option D

4. Quick Check:

   GCC packing syntax = __attribute__((packed)) [OK]

Hint: Use __attribute__((packed)) after struct keyword [OK]

Common Mistakes:

• Using __packed keyword which is not standard GCC
• Placing __attribute__((aligned)) instead of packed
• Putting attributes in wrong position

3. Consider this struct without packing:

struct Example {
  char a;
  int b;
};

sizeof(struct Example);

What is the likely output on a 32-bit system where int is 4 bytes and alignment is on 4-byte boundaries?

medium

A. 5

B. 8

C. 12

D. 16

Solution

1. Step 1: Analyze struct member sizes and alignment

   char a = 1 byte, int b = 4 bytes aligned on 4-byte boundary.

2. Step 2: Calculate padding and total size

   After char a, 3 bytes padding added to align int b. Total size = 1 + 3 + 4 = 8 bytes. Struct size must be multiple of largest alignment (4), which 8 satisfies.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   Size with padding = 8 bytes [OK]

Hint: Add padding after smaller types to align next member [OK]

Common Mistakes:

• Ignoring padding bytes
• Adding padding after last member unnecessarily
• Assuming size is sum of member sizes only

4. Given this code snippet:

struct Data {
  char c;
  int i;
} __attribute__((packed));

struct Data d;
printf("%zu", sizeof(d));

The output is 5, but the program crashes when accessing d.i. What is the likely cause?

medium

A. Accessing unaligned int causes crash on some systems

B. The struct is not actually packed

C. char c is not initialized

D. printf format specifier is incorrect

Solution

1. Step 1: Understand packing effect on alignment

   Packing removes padding, so int i may not be aligned on 4-byte boundary.

2. Step 2: Recognize hardware alignment requirements

   Some systems crash or fault when accessing unaligned int variables.

3. Final Answer:

   Accessing unaligned int causes crash on some systems -> Option A

4. Quick Check:

   Unaligned access = crash risk [OK]

Hint: Packed structs can cause unaligned access crashes [OK]

Common Mistakes:

• Blaming printf format specifier
• Assuming packing always safe
• Ignoring hardware alignment rules

5. You have a struct with members:

char a;
short b;
int c;

On a 32-bit system, how can you arrange and pack this struct to minimize memory size without causing unaligned access faults?

hard

A. Order members as char a; int c; short b; and use packing

B. Order members as char a; short b; int c; without packing

C. Order members as int c; short b; char a; and use packing

D. Order members as short b; char a; int c; without packing

Solution

1. Step 1: Understand alignment requirements

   int requires 4-byte alignment, short 2-byte, char 1-byte.

2. Step 2: Arrange members largest to smallest

   Ordering int c; short b; char a; places largest first, minimizing padding.

3. Step 3: Use packing carefully

   Packing removes padding but can cause unaligned access; here, ordering avoids unaligned access.

4. Final Answer:

   Order members as int c; short b; char a; and use packing -> Option C

5. Quick Check:

   Largest to smallest + packing = minimal size safe [OK]

Hint: Order largest to smallest type, then pack [OK]

Common Mistakes:

• Ordering members smallest to largest causing padding
• Packing without considering alignment faults
• Ignoring hardware alignment rules