Stack vs heap in embedded context - Performance Comparison

Time Complexity: Stack vs heap in embedded context

O(1) for stack allocation, O(n) for heap allocation

Understanding Time Complexity

When working with embedded C, knowing how stack and heap memory behave helps us understand how fast our program runs.

We want to see how the time to allocate or free memory changes as the program runs.

Scenario Under Consideration

Analyze the time complexity of memory allocation on stack vs heap.

// Stack allocation example
void func() {
  int arr[100]; // allocated on stack
  // use arr
}

// Heap allocation example
#include 
void func() {
  int* arr = malloc(100 * sizeof(int)); // allocated on heap
  // use arr
  free(arr);
}
    

This code shows two ways to allocate memory: one on the stack and one on the heap.

Identify Repeating Operations

Look at what happens when memory is allocated or freed repeatedly.

• Primary operation: Memory allocation and deallocation
• How many times: Each time func() runs, allocation happens once

How Execution Grows With Input

Allocation on stack is very fast and stays almost the same time regardless of size.

Input Size (n)	Approx. Operations (Stack)	Approx. Operations (Heap)
10	Very few (simple pointer move)	More (search free block)
100	Very few (same as 10)	More (depends on fragmentation)
1000	Very few (same as 10)	Even more (longer search)

Stack allocation time stays almost constant; heap allocation time grows with size and fragmentation.

Final Time Complexity

Time Complexity: O(1) for stack allocation, O(n) for heap allocation

This means stack allocation is very fast and predictable, while heap allocation can take longer as more memory is used.

Common Mistake

[X] Wrong: "Allocating memory on the heap is always as fast as on the stack."

[OK] Correct: Heap allocation involves searching for free space and managing fragmentation, which takes more time than simple stack pointer moves.

Interview Connect

Understanding stack vs heap speed helps you write efficient embedded code and answer questions about memory management clearly.

Self-Check

"What if we used a custom memory pool instead of the standard heap? How would the time complexity of allocation change?"

Practice

1. In embedded C, where are local variables inside functions typically stored?

easy

A. On the stack

B. On the heap

C. In flash memory

D. In CPU registers only

Solution

1. Step 1: Understand local variable storage

   Local variables inside functions are temporary and exist only during function execution.

2. Step 2: Identify stack usage in embedded C

   The stack is used to store temporary data like local variables and return addresses.

3. Final Answer:

   On the stack -> Option A

4. Quick Check:

   Local variables = stack [OK]

Hint: Local variables go on stack, dynamic memory on heap [OK]

Common Mistakes:

• Confusing heap with stack for local variables
• Thinking local variables are stored in flash
• Assuming all variables are in CPU registers

2. Which of the following is the correct way to allocate memory dynamically in embedded C?

easy

A. int p = malloc(sizeof(int));

B. int *p = sizeof(int);

C. int *p = malloc(sizeof(int));

D. malloc(int p);

Solution

1. Step 1: Recall malloc syntax

   malloc returns a pointer to allocated memory, so pointer variable is needed.

2. Step 2: Check each option

   int *p = malloc(sizeof(int)); correctly assigns malloc's return to an int pointer. Others misuse types or syntax.

3. Final Answer:

   int *p = malloc(sizeof(int)); -> Option C

4. Quick Check:

   malloc returns pointer, assign to pointer [OK]

Hint: malloc returns pointer, assign to pointer variable [OK]

Common Mistakes:

• Assigning malloc result to non-pointer variable
• Using sizeof without malloc
• Incorrect function call syntax

3. What will happen if you declare a large array inside a function in embedded C on a system with limited stack size?

medium

A. Stack overflow may occur causing a crash

B. Heap memory will be used automatically

C. The array will be stored in flash memory

D. The compiler will convert it to a global variable

Solution

1. Step 1: Understand stack size limits

   Stack size is limited in embedded systems; large local arrays consume stack space.

2. Step 2: Consequence of large stack allocation

   Allocating large arrays locally can exceed stack size, causing overflow and crash.

3. Final Answer:

   Stack overflow may occur causing a crash -> Option A

4. Quick Check:

   Large local arrays risk stack overflow [OK]

Hint: Large local arrays risk stack overflow in embedded [OK]

Common Mistakes:

• Assuming heap is used automatically
• Thinking large arrays go to flash
• Believing compiler auto-converts locals to globals

4. Consider this code snippet in embedded C:

void func() {
  int *p = malloc(10 * sizeof(int));
  // ... use p ...
  // missing free(p);
}

What is the main problem here?

medium

A. Pointer p is not initialized

B. Stack overflow due to large local array

C. Syntax error in malloc usage

D. Memory leak because allocated heap memory is not freed

Solution

1. Step 1: Analyze malloc usage

   Memory is allocated on the heap with malloc but never freed.

2. Step 2: Identify consequences of missing free

   Not freeing heap memory causes memory leak, wasting limited embedded memory.

3. Final Answer:

   Memory leak because allocated heap memory is not freed -> Option D

4. Quick Check:

   Missing free causes memory leak [OK]

Hint: Always free malloc memory to avoid leaks [OK]

Common Mistakes:

• Confusing stack overflow with memory leak
• Thinking malloc syntax is wrong
• Assuming pointer is uninitialized

5. In an embedded system with 2KB stack and 4KB heap, which approach is best to safely allocate a 1KB buffer for temporary data?

hard

A. Declare a local array of 1KB inside a function

B. Use malloc to allocate 1KB on the heap and free after use

C. Declare a global 1KB array to avoid stack and heap

D. Use a static local array inside the function

Solution

1. Step 1: Evaluate stack usage for large buffer

   1KB local array uses half the stack, risking overflow in embedded systems.

2. Step 2: Consider heap allocation safety

   Allocating 1KB on heap with malloc is safer; heap is larger and managed manually.

3. Step 3: Compare global and static arrays

   Global/static arrays use fixed memory but reduce flexibility and increase RAM usage always.

4. Final Answer:

   Use malloc to allocate 1KB on the heap and free after use -> Option B

5. Quick Check:

   Heap allocation safer for large temporary buffers [OK]

Hint: Use heap malloc for large temporary buffers in embedded [OK]

Common Mistakes:

• Using large local arrays risking stack overflow
• Ignoring freeing heap memory
• Assuming global arrays are always best