COP4020 Programming Languages Names, Scopes, and Bindings Prof.

COP4020 Programming Languages Names, Scopes, and Bindings Prof. Xin Yuan

Overview Object storage management 02/28/24 Static allocation Stack allocation Heap allocation COP4020 Spring 2014 2

Object Lifetime and Storage Objects (program data and code) have to be stored in memory during their lifetime. In general there are three types of objects in a program The objects that are alive throughout the execution of a program E.g. global variables The objects that are alive within a routine E.g. local variables The objects whose lifetime can be dynamically changed. 02/28/24 The objects that are managed by the ‘new/delete’ constructs. COP4020 Spring 2014 3

Object Lifetime and Storage The three types of objects correspond to three principal storage allocation mechanisms. Static objects have an absolute storage address that is retained throughout the execution of the program Stack objects are allocated in last-in first-out order, usually in conjunction with subroutine calls and returns Actual arguments passed by value to a subroutine Local variables of a subroutine Heap objects may be allocated and deallocated at arbitrary times, but require an expensive storage management algorithm 02/28/24 Global variables and data Subroutine code and class method code Dynamically allocated data in C . Java class instances are always stored on the heap COP4020 Spring 2014 4

Typical Program and Data Layout in Memory Upper addr Virtual memory address space stack Program code is at the bottom of the memory region (code section) heap static data The code section is protected from run-time modification by the OS Static data objects are stored in the static region Stack grows downward Heap grows upward code 0000 02/28/24 COP4020 Spring 2014 5

Static Allocation Program code is statically allocated in most implementations of imperative languages Statically allocated variables are history sensitive Global variables keep state during entire program lifetime Static local variables in C/C functions keep state across function invocations Static data members are “shared” by objects and keep state during program lifetime Advantage of statically allocated object is the fast access due to absolute addressing of the object Can static allocation be used for local variables? 02/28/24 Statically allocated local variables has only one copy of each variable. Cannot deal with the cases when multiple copies of a local varabile are alive!!! When does this happen? COP4020 Spring 2014 6

Static Allocation in Fortran 77 Temporary storage (e.g. for expression evaluation) Local variables Bookkeeping (e.g. saved CPU registers) Return address Subroutine arguments and returns 02/28/24 Typical static subroutine frame layout Fortran 77 has no recursion Global and local variables are statically allocated as decided by the compiler Global and local variables are referenced at absolute addresses Avoids overhead of creation and destruction of local objects for every subroutine call Each subroutine in the program has a subroutine frame that is statically allocated This subroutine frame stores all subroutine-relevant data that is needed to execute COP4020 Spring 2014 7

Stack Allocation Each instance of a subroutine that is active has a subroutine frame (sometimes called activation record) on the run-time stack Compiler generates subroutine calling sequence to setup frame, call the routine, and to destroy the frame afterwards Method invocation works the same way, but in addition methods are typically dynamically bound Subroutine frame layouts vary between languages, implementations, and machine platforms 02/28/24 COP4020 Spring 2014 8

Typical Stack-Allocated Subroutine Frame Lower addr Temporary storage (e.g. for expression evaluation) Local variables Bookkeeping (e.g. saved CPU registers) Return address fp Subroutine arguments and returns Higher addr 02/28/24 Typical subroutine frame layout Most modern processors have two registers: fp (frame pointer) and sp (stack pointer) to support efficient execution of subroutines in high level languages A frame pointer (fp) points to the frame of the currently active subroutine at run time Subroutine arguments, local variables, and return values are accessed by constant address offsets from the fp COP4020 Spring 2014 9

Subroutine Frames on the Stack Stack growth sp Temporaries Local variables A Bookkeeping Return address fp Arguments Temporaries Local variables B Bookkeeping Return address Arguments Temporaries Local variables A Bookkeeping Return address Arguments Temporaries Local variables M Bookkeeping Return address Higher addr 02/28/24 Subroutine frames are pushed and popped onto/from the runtime stack The stack pointer (sp) points to the next available free space on the stack to push a new frame onto when a subroutine is called The frame pointer (fp) points to the frame of the currently active subroutine, which always the topmost frame on the stack The fp of the previous active frame is saved in the current frame and restored after the call In this example: M called A A called B B called A Arguments COP4020 Spring 2014 10

Example Subroutine Frame Lower addr Temporaries -36: foo (4 bytes) fp-32 -32: bar (8 bytes) -24: p (4 bytes) Bookkeeping (16 bytes) fp Return address to the caller of P (4 bytes) 0: a (4 bytes) fp 4 Higher addr 02/28/24 4: b (4 bytes) The size of the types of local variables and arguments determines the fp offset in a frame Example Pascal procedure: procedure P(a:integer, var b:real) (* a is passed by value b is passed by reference, pointer to b's value *) var foo:integer;(* 4 bytes *) bar:real; (* 8 bytes *) p: integer; (* 4 bytes *) begin . end COP4020 Spring 2014 11

Heap Allocation Heap is used to store objects who lifetime is dynamic Implicit heap allocation: Explicit heap allocation: 02/28/24 Done automatically Java class instances are placed on the heap Scripting languages and functional languages make extensive use of the heap for storing objects Some procedural languages allow array declarations with run-time dependent array size Resizable character strings Statements and/or functions for allocation and deallocation Malloc/free, new/delete COP4020 Spring 2014 12

Heap allocation problem Heap is a large block of memory (say N bytes) Requests for memory of various sizes may arrive randomly: program runs ‘new’ Each request may ask for 1 to N bytes If a request of X bytes is granted, a continuous X bytes in the heap is allocated for the request. The memory will be used for a while and then return to the system (when the program runs ‘delete’ The problem: how to allocate memory so that as many request can be satisfied as possible. 02/28/24 COP4020 Spring 2014 13

Heap allocation example Example How to do it makes a difference!! Internal fragment: unused memory within a block 10KB memory to be managed r1 req(1K); r2 req (2K); r3 req(4k); free(r2); free(r1); r4 req(4k); Asking for 100 bytes and get a 512 bytes block External fragment: unused memory between blocks 02/28/24 Even when the total available memory is more than a request, the request cannot be satisfied as in the example. COP4020 Spring 2014 14

Heap Allocation Algorithms Heap allocation is performed by searching the heap for available free space For example, suppose we want to allocate a new object E of 20 bytes, where would it fit? Object A Free Object B Object C Free Object D Free 30 bytes 8 bytes 10 bytes 24 bytes 24 bytes 8 bytes 20 bytes Deletion of objects leaves free blocks in the heap that can be reused Two questions 02/28/24 How to keep track of free blocks? How to find the right free block for each request? COP4020 Spring 2014 15

Heap Allocation Algorithms (cont’d) How to keep track of free blocks? Maintain a linked list of free heap blocks To satisfy a request (new), search the list to find one block whose size is equal to or larger than the requested size If the size is equal, remove the block from the free list If the size is larger, modify the size to (size – requested size). When an object is deleted (freed), the block of memory is returned to the heap. 02/28/24 Insert a new block to the free list. If new block can be merged with its neighboring blocks to be a larger block, merge the blocks. COP4020 Spring 2014 16

Heap Allocation Algorithms (cont’d) How to pick which block to be used for each request? There can be many choices. First-fit: select the first block in the list that is large enough Best-fit: search the entire list for the smallest free block that is large enough to hold the object O(N) for both ‘new’ and ‘delete’operations 02/28/24 COP4020 Spring 2014 17

Other Heap Allocation Algorithms Buddy system: use heap pools of standard sized blocks of size 2k If no free block is available for object of size between 2k-1 1 and 2k then find block of size 2k 1 and split it in half, adding the halves to the pool of free 2k blocks, etc. Fibonacci heap: use heap pools of standard size blocks according to Fibonacci numbers 02/28/24 More complex but leads to slower internal fragmantation COP4020 Spring 2014 18

Garbage Collection Explicit manual deallocation errors are among the most expensive and hard to detect problems in real-world applications If an object is deallocated too soon, a reference to the object becomes a dangling reference If an object is never deallocated, the program leaks memory Automatic garbage collection removes all objects from the heap that are not accessible, i.e. are not referenced 02/28/24 Used in Lisp, Scheme, Prolog, Ada, Java, Haskell Disadvantage is GC overhead, but GC algorithm efficiency has been improved Not always suitable for real-time processing COP4020 Spring 2014 19

Garbage Collection How does it work roughly? The language defines the lifetime of objects. The runtime keeps track of the number of references (bindings) to each object. 02/28/24 1 when a new reference is made, -1 when the reference is destroyed Can delete when the reference count is 0. Need to determine when a variable is alive or dead based on language specification. COP4020 Spring 2014 20

Storage Allocation Compared Static Stack Heap N/A local variables and subroutine arguments of fixed size implicit: local variables of variable size; explicit: new (destruction with garbage collection or explicit with unchecked deallocation) C global variables; static local variables local variables and subroutine arguments explicit with malloc and free C Same as C, and static class members Same as C explicit with new and delete Java N/A only local variables of primitive types implicit: all class instances (destruction with garbage collection) global variables (in common blocks), local variables, and subroutine arguments (implementation dependent); SAVE forces static allocation local variables and subroutine arguments (implementation dependent N/A global variables (compiler dependent) global variables (compiler dependent), local variables, and subroutine arguments Explicit: new and dispose Ada Fortran77 Pascal 02/28/24 COP4020 Spring 2014 21

Summary Object storage management Static allocation Stack allocation 02/28/24 What type of objects are allocated with stack allocation? Heap allocation What type of objects are allocated with static allocation? Why not static allocation for everything? What type of objects are allocation with heap allocation? Garbage collection COP4020 Spring 2014 22