Stack vs Heap Memory

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

┌─────────────────────────────────────────┐  High Address (e.g., 0xFFFFFFFF)
│              Kernel Space               │  (inaccessible to user programs)
├─────────────────────────────────────────┤
│                                         │
│               STACK                     │  ← Stack pointer (SP)
│          (grows downward ↓)             │  Function frames, local variables
│                                         │
├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─┤
│                                         │
│            Unused Space                 │  (grows into this region)
│                                         │
├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─┤
│                                         │
│                HEAP                     │  ← Break pointer (brk)
│          (grows upward ↑)               │  Dynamic allocations
│                                         │
├─────────────────────────────────────────┤
│           BSS Segment                   │  Uninitialized global/static variables
├─────────────────────────────────────────┤
│           Data Segment                  │  Initialized global/static variables
├─────────────────────────────────────────┤
│           Text Segment                  │  Executable code (read-only)
└─────────────────────────────────────────┘  Low Address (e.g., 0x00000000)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// Consider this call chain: main() -> processOrder() -> calculateTax()
 
function calculateTax(subtotal: number, taxRate: number): number {
    // STACK FRAME 3 (top of stack):
    // - Parameter: subtotal (copied value)
    // - Parameter: taxRate (copied value)
    // - Local variable: taxAmount
    // - Return address: back to processOrder()
    
    const taxAmount = subtotal * taxRate;  // Stack-allocated local
    return taxAmount;                       // Value returned, frame popped
}
 
function processOrder(items: OrderItem[]): OrderResult {
    // STACK FRAME 2:
    // - Parameter: items (reference to heap object, but reference itself on stack)
    // - Local variable: subtotal
    // - Local variable: tax
    // - Return address: back to main()
    
    const subtotal = items.reduce((sum, item) => sum + item.price, 0);
    const tax = calculateTax(subtotal, 0.08);  // Frame 3 pushed, then popped
    
    return { total: subtotal + tax, tax };      // Frame 2 popped after return
}
 
function main(): void {
    // STACK FRAME 1 (bottom of stack):
    // - Local variable: orderItems (reference)
    // - Local variable: result (reference)
    
    const orderItems: OrderItem[] = [           // Array object on HEAP
        { id: 1, name: "Widget", price: 25.00 },
        { id: 2, name: "Gadget", price: 50.00 }
    ];
    
    const result = processOrder(orderItems);    // Frame 2 pushed
    console.log(`Total: ${result.total}`);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

┌─────────────────────────────────────────┐
│         Previous Stack Frame            │
├─────────────────────────────────────────┤  ← Previous Frame Pointer
│         Return Address                  │  Where to continue after return
├─────────────────────────────────────────┤
│         Saved Frame Pointer             │  Points to caller's frame
├─────────────────────────────────────────┤  ← Current Frame Pointer (FP/EBP)
│         Local Variable n                │
├─────────────────────────────────────────┤
│         Local Variable n-1              │
├─────────────────────────────────────────┤
│              ...                        │
├─────────────────────────────────────────┤
│         Local Variable 1                │
├─────────────────────────────────────────┤  ← Stack Pointer (SP/ESP)
│         (Next frame would go here)      │
└─────────────────────────────────────────┘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

// ❌ PROBLEM 1: Deep Recursion
function fibonacci(n: number): number {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);  // O(2^n) calls!
}
// fibonacci(50) will likely overflow the stack
 
// ✅ SOLUTION 1A: Iterative approach
function fibonacciIterative(n: number): number {
    if (n <= 1) return n;
    let prev = 0, curr = 1;
    for (let i = 2; i <= n; i++) {
        [prev, curr] = [curr, prev + curr];
    }
    return curr;
}
 
// ✅ SOLUTION 1B: Tail recursion (if language supports TCO)
function fibonacciTailRecursive(
    n: number, 
    prev: number = 0, 
    curr: number = 1
): number {
    if (n === 0) return prev;
    if (n === 1) return curr;
    return fibonacciTailRecursive(n - 1, curr, prev + curr);
}
 
// ❌ PROBLEM 2: Large local arrays
function processLargeData(): void {
    // This allocates 40MB on the stack (10M * 4 bytes)
    // Will almost certainly overflow!
    const hugeArray: number[] = new Array(10_000_000).fill(0);
    // ... process
}
 
// ✅ SOLUTION 2: Use heap allocation for large data
function processLargeDataSafe(): void {
    // In TypeScript/JS, arrays are heap-allocated by default
    // But in C++, we'd explicitly use: std::vector<int>* arr = new std::vector<int>(10000000);
    const hugeArray = new Array(10_000_000).fill(0);  // Heap-allocated
    // ... process
}
 
// ❌ PROBLEM 3: Mutual recursion without bounds
function isEven(n: number): boolean {
    if (n === 0) return true;
    return isOdd(n - 1);
}
 
function isOdd(n: number): boolean {
    if (n === 0) return false;
    return isEven(n - 1);
}
// isEven(1000000) will overflow
 
// ✅ SOLUTION 3: Use modular arithmetic
function isEvenSafe(n: number): boolean {
    return n % 2 === 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// In JavaScript/TypeScript, most non-primitive values are heap-allocated
 
class Customer {
    id: string;
    name: string;
    orders: Order[];        // Reference to another heap object
    
    constructor(id: string, name: string) {
        this.id = id;       // String on heap
        this.name = name;   // String on heap
        this.orders = [];   // Empty array on heap
    }
    
    addOrder(order: Order): void {
        this.orders.push(order);  // Array grows on heap
    }
}
 
function createCustomerReport(): Customer {
    // 'customer' is a REFERENCE on the stack
    // The Customer OBJECT is on the heap
    const customer = new Customer("C-001", "Acme Corp");
    
    // Each Order is a separate heap allocation
    customer.addOrder(new Order("O-001", 1000));
    customer.addOrder(new Order("O-002", 2500));
    
    // The Customer object SURVIVES this function
    // Only the 'customer' reference (on stack) is destroyed
    return customer;
}
 
// Heap objects can be referenced from multiple places
const report = createCustomerReport();  // report points to heap object
const cache = new Map<string, Customer>();
cache.set(report.id, report);           // TWO references to same heap object
 
// The Customer won't be garbage collected until
// BOTH report and the cache entry are gone

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

BEFORE ALLOCATION (Request: 64 bytes):
 
┌──────────┬────────────────┬──────────┬───────────────────────┐
│ In Use   │  FREE (128B)   │ In Use   │      FREE (256B)      │
│  (32B)   │   Suitable!    │  (64B)   │     Also suitable     │
└──────────┴────────────────┴──────────┴───────────────────────┘
 
AFTER ALLOCATION (First-Fit Strategy):
 
┌──────────┬─────────┬──────┬──────────┬───────────────────────┐
│ In Use   │ In Use  │ FREE │ In Use   │      FREE (256B)      │
│  (32B)   │  (64B)  │(64B) │  (64B)   │                       │
└──────────┴─────────┴──────┴──────────┴───────────────────────┘
            ↑ New     ↑ Remainder
            allocation  becomes free block

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

// Demonstrating the performance implications of allocation strategies
 
interface Point {
    x: number;
    y: number;
}
 
// ❌ HEAP-HEAVY: Creating many small objects on the heap
function processPointsHeapHeavy(count: number): number {
    let totalDistance = 0;
    
    for (let i = 0; i < count; i++) {
        // Each iteration creates a NEW heap object
        const point: Point = { x: Math.random(), y: Math.random() };
        totalDistance += Math.sqrt(point.x * point.x + point.y * point.y);
    }
    
    return totalDistance;
}
// For count = 10,000,000: Creates 10 million heap allocations
// Results in: GC pressure, cache misses, allocation overhead
 
// ✅ OPTIMIZED: Reuse objects (object pooling concept)
function processPointsOptimized(count: number): number {
    let totalDistance = 0;
    
    // Reuse a single object - amortize allocation cost
    const point: Point = { x: 0, y: 0 };
    
    for (let i = 0; i < count; i++) {
        point.x = Math.random();
        point.y = Math.random();
        totalDistance += Math.sqrt(point.x * point.x + point.y * point.y);
    }
    
    return totalDistance;
}
// For count = 10,000,000: Creates only 1 heap allocation
// Results in: No GC pressure, better cache locality, minimal overhead
 
// ✅ BEST: Use primitives directly (stack-friendly)
function processPointsPrimitive(count: number): number {
    let totalDistance = 0;
    
    for (let i = 0; i < count; i++) {
        // Primitives don't require heap allocation in many languages
        const x = Math.random();
        const y = Math.random();
        totalDistance += Math.sqrt(x * x + y * y);
    }
    
    return totalDistance;
}
// Primitives on stack, optimal performance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

// C# gives explicit control through struct vs class
 
// VALUE TYPE (struct) - Stored on stack when local variable
public struct Point3D
{
    public double X;
    public double Y;
    public double Z;
    
    public Point3D(double x, double y, double z)
    {
        X = x; Y = y; Z = z;
    }
    
    public double Magnitude => Math.Sqrt(X*X + Y*Y + Z*Z);
}
 
// REFERENCE TYPE (class) - Always stored on heap
public class Point3DClass
{
    public double X { get; set; }
    public double Y { get; set; }
    public double Z { get; set; }
    
    public Point3DClass(double x, double y, double z)
    {
        X = x; Y = y; Z = z;
    }
    
    public double Magnitude => Math.Sqrt(X*X + Y*Y + Z*Z);
}
 
public void ProcessPoints()
{
    // STACK: point is stored directly on the stack (24 bytes)
    Point3D point = new Point3D(1.0, 2.0, 3.0);
    
    // HEAP: reference on stack (8 bytes), object on heap (24+ bytes)
    Point3DClass pointObj = new Point3DClass(1.0, 2.0, 3.0);
    
    // For high-frequency operations, struct is dramatically faster
    // But structs are copied on assignment/parameter passing
    Point3D copy = point;  // Creates a full copy (24 bytes)
    Point3DClass refCopy = pointObj;  // Copies only reference (8 bytes)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// Rust provides explicit control over memory location
 
// Stack-allocated by default
struct Point {
    x: f64,
    y: f64,
}
 
// Explicit heap allocation with Box
fn create_points() {
    // Stack-allocated: Point is 16 bytes on the stack
    let stack_point = Point { x: 1.0, y: 2.0 };
    
    // Heap-allocated: Box<Point> puts Point on heap
    let heap_point: Box<Point> = Box::new(Point { x: 3.0, y: 4.0 });
    
    // Rust's ownership system ensures:
    // - stack_point is dropped when function exits
    // - heap_point's Box is dropped, freeing heap memory
    
    // No garbage collector - deterministic cleanup!
}
 
// Return by value moves ownership (efficient, no copy for large types)
fn create_large_struct() -> LargeStruct {
    let data = LargeStruct::new();  // Allocated inside function
    data  // Ownership transferred to caller - no copy needed
}
 
// Smart pointers for shared heap data
use std::rc::Rc;
use std::sync::Arc;
 
fn shared_ownership() {
    // Reference-counted heap allocation (single-threaded)
    let shared: Rc<Point> = Rc::new(Point { x: 1.0, y: 2.0 });
    let shared2 = Rc::clone(&shared);  // Increments reference count
    
    // Atomically reference-counted (thread-safe)
    let arc: Arc<Point> = Arc::new(Point { x: 3.0, y: 4.0 });
    // Safe to share across threads
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

// ❌ PROBLEMATIC: Returns internal mutable state
class UserService {
    private users: Map<string, User> = new Map();
    
    // Caller receives reference to internal heap object
    // Any modification affects internal state
    getUsers(): Map<string, User> {
        return this.users;  // Dangerous: exposes internal state
    }
}
 
// ✅ BETTER: Defensive copying (but has heap allocation cost)
class UserServiceSafe {
    private users: Map<string, User> = new Map();
    
    // Returns a copy - caller cannot affect internal state
    getUsers(): Map<string, User> {
        return new Map(this.users);  // New heap allocation
    }
}
 
// ✅ BEST: Return immutable view or specific data
class UserServiceOptimal {
    private users: Map<string, User> = new Map();
    
    // Return read-only iterator - no new allocation
    getUserIds(): IterableIterator<string> {
        return this.users.keys();
    }
    
    // Return specific user - bounded allocation
    getUser(id: string): User | undefined {
        return this.users.get(id);
    }
    
    // Return count - no allocation
    getUserCount(): number {
        return this.users.size;
    }
}
 
// ❌ PROBLEMATIC: Unbounded recursion
function processTree(node: TreeNode): void {
    // For deep trees, this will overflow the stack
    processTree(node.left);
    processTree(node.right);
    // ... process node
}
 
// ✅ BETTER: Iterative with explicit stack (on heap)
function processTreeIterative(root: TreeNode): void {
    const stack: TreeNode[] = [root];  // Heap-allocated stack
    
    while (stack.length > 0) {
        const node = stack.pop()!;
        // ... process node
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
    }
}