[Compiler] 10. Runtime Environments - Stack, Heap, and Garbage Collection

High Address
+------------------+
|      Stack       |  <- Function call info, local variables
|        |         |
|        v         |
|                  |
|        ^         |
|        |         |
|      Heap        |  <- Dynamically allocated data
+------------------+
| Static Data      |  <- Global variables, constants
+------------------+
| Code             |  <- Program instructions
+------------------+
Low Address

High Address
+---------------------------+
|  Actual parameters (args) |
+---------------------------+
|  Return value             |
+---------------------------+
|  Control link             |  <- Caller's frame pointer
+---------------------------+
|  Access link              |  <- For static scope support
+---------------------------+
|  Saved registers          |
+---------------------------+
|  Local variables          |
+---------------------------+
|  Temporary variables      |
+---------------------------+
Low Address

1. Evaluate actual parameters and push onto the stack
2. Save the return address
3. Transfer control to the callee (call instruction)

1. Push registers that need saving onto the stack
2. Save previous frame pointer (FP) (control link)
3. Set new frame pointer (FP)
4. Allocate space for local variables (move SP)

1. Store return value in designated location
2. Restore SP to FP
3. Restore saved registers
4. Restore previous FP
5. Jump to return address

void main() {             void foo(int x) {
    foo(10);                  int y = x + 1;
    // ...                    bar(y);
}                         }

                          void bar(int a) {
                              int b = a * 2;
                          }

Stack changes:

[1] When main called    [2] When foo(10) called  [3] When bar(11) called

+-------+              +-------+              +-------+
| main  |              | main  |              | main  |
+-------+              +-------+              +-------+
                       | foo   |              | foo   |
                       | x=10  |              | x=10  |
                       | y=11  |              | y=11  |
                       +-------+              +-------+
                                              | bar   |
                                              | a=11  |
                                              | b=22  |
                                              +-------+

// Pascal-like code
procedure A;
    var x: integer;

    procedure B;
        var y: integer;

        procedure C;
        begin
            x := y + 1;  // Access A's x and B's y
        end;

    begin
        C;
    end;

begin
    B;
end;

Stack (calls: A -> B -> C):

+-------+
| A     |  <- Access link: none (outermost)
| x     |
+-------+
| B     |  <- Access link: points to A's record
| y     |
+-------+
| C     |  <- Access link: points to B's record
|       |
+-------+

C accessing x: follow access links 2 times (C -> B -> A)
C accessing y: follow access links 1 time (C -> B)

Display array:
  display[1] = pointer to A's activation record
  display[2] = pointer to B's activation record
  display[3] = pointer to C's activation record

C accessing x: direct access via display[1] (O(1))
C accessing y: direct access via display[2] (O(1))

1. First Fit:
   Use the first free block that is large enough

   [In use][  Free block  ][In use][ Free block ]
                ^
            Allocate here

2. Best Fit:
   Use the free block closest in size to the request
   -> Higher possibility of external fragmentation

3. Buddy System:
   Split/merge blocks of power-of-2 sizes
   -> Possible internal fragmentation but fast merging

External Fragmentation:
  Total free space is sufficient, but no contiguous block is large enough

  [Used][Free][Used][Free][Used][Free]
        ^^^       ^^^       ^^^
    100B each, but 200B request cannot be fulfilled

Internal Fragmentation:
  Unused space within an allocated block

  Request: 100B, Allocated: 128B -> 28B wasted

Root set: stack variables, global variables, registers

    [Root] --> [Object A] --> [Object B]
                 |
                 v
              [Object C]

              [Object D] --> [Object E]   <- Unreachable = Garbage!

a = new Object();   // Object refcount = 1
b = a;              // Object refcount = 2
a = null;           // Object refcount = 1
b = null;           // Object refcount = 0 -> Reclaim!

Pros:
  - Immediate reclamation: memory returned as soon as reference hits 0
  - No pauses: no GC stop-the-world
  - Simple implementation

Cons:
  - Cannot handle circular references:
    [A] --> [B]
     ^       |
     +-------+
    A.refcount = 1, B.refcount = 1 (never reaches 0)

  - Count update overhead: count updated on every assignment
  - Cache efficiency degradation: remote memory access on reference updates

Mark Phase:
  1. Start from root set
  2. Mark all reachable objects
  3. Traverse object graph using DFS or BFS

Sweep Phase:
  1. Traverse all objects in the heap
  2. Reclaim unmarked objects
  3. Clear marks on marked objects

Before marking:
  [A*] -> [B*] -> [C*]
                    |
                    v
  [D ] -> [E ]    [F*]

  * = reachable from root

After sweeping:
  [A] -> [B] -> [C]
                  |
                  v
  [Free] -> [Free]  [F]

  D, E are reclaimed

Pros:
  - Correctly reclaims circular references
  - Overhead proportional to the amount of garbage

Cons:
  - Stop-the-World: program pauses during GC execution
  - Fragmentation: memory becomes fragmented after reclamation

[From Space]             [To Space]
+---------+              +---------+
| A  B  C |  copy -->    | A  C    |
| (free) D|              | (free)  |
+---------+              +---------+

Only live objects are copied to the To space
-> No fragmentation, contiguous memory

1. Set scan and free pointers at the start of To space
2. Copy objects referenced from roots to To space
3. Process references of the object pointed to by scan:
   - If referenced object is in From, copy to To
   - Update reference to new location
4. Complete when scan meets free

Pros:
  - No fragmentation (compaction effect)
  - Very fast allocation (just pointer increment)
  - Cost incurred only for live objects

Cons:
  - Only half the memory is usable
  - High copy cost if many objects are live
  - Pointer updates required

+------------------+
|  Old Generation  |  (long-lived objects)
|  (Major GC target)|  <- Low GC frequency
+------------------+
|                  |
| Young Generation |  (newly created objects)
|  (Minor GC target)|  <- High GC frequency
|  +----+ +------+ |
|  |Eden| |Survivor||
|  +----+ +------+ |
+------------------+

1. New objects are allocated in the Young generation
2. When Young generation is full, Minor GC runs:
   - Copies live objects to Survivor area
   - Objects surviving multiple collections are promoted to Old generation
3. When Old generation is full, Major GC runs:
   - GC over the entire heap (expensive)

If object A in Old generation references object B in Young generation:
  -> Add A to the remembered set
  -> Treat remembered set objects as roots during Minor GC

This allows Minor GC to avoid scanning the entire Old generation.

Java HotSpot JVM:
  Young: Eden + Survivor0 + Survivor1 (copying collection)
  Old: Mark-Compact or CMS/G1/ZGC

Go:
  Concurrent mark-and-sweep without generations
  Uses tri-color marking

Python:
  Reference counting + generational GC (for circular reference handling)

[Program threads]  -------run-------run-------run------->
[GC threads]       --mark--|-sweep--|---------|-mark--|-->

-> Minimizes Stop-the-World time

[Program] [GC] [Program] [GC] [Program] [GC] [Program]
   10ms   2ms    10ms    2ms    10ms    2ms    10ms

-> Multiple short pauses instead of one long pause

Java G1 (Garbage First):
  - Divides heap into equal-sized regions
  - Collects regions with the most garbage first
  - Configurable pause time target

Java ZGC / Shenandoah:
  - Very short pauses (within a few milliseconds)
  - Supports large heaps (multiple terabytes)
  - Concurrent compaction