Hash Tables & Hash Functions | Compiler Design - Computer Science Engineering (CSE) PDF Download

Hash Tables and Hash Functions: ·
A hash table is an array with index range: 0 to TableSize – 1  

•  Most commonly used data structure to implement symbol tables    
•  Insertion and lookup can be made very fast – O(1)  
• A hash function maps an identifier name into a table index  
• A hash function, h(name), should depend solely on name
• h(name) should be computed quickly 
• h should be uniform and randomizing in distributing names 
• All table indices should be mapped with equal probability
• Similar names should not cluster to the same table index.   

Storage Allocation:  

• Compiler must do the storage allocation and provide access to variables and data  
• Memory management  
• Stack allocation
• Heap management  
•  Garbage collection   
  
  
  Storage Organization:
   

• Assumes a logical address space 

• Operating system will later map it to physical addresses, decide how touse cache memory, etc.  

 
• Memory typically divided into areas for

• Program code   
• Other static data storage, including global constants and compilergenerated data  
• Stack to support call/return policy for procedures
• Heap to store data that can outlive a call to a procedure  

Static vs. Dynamic Allocation:  

• Static: Compile time, Dynamic: Runtime allocation  
•  Many compilers use some combination of following
• Stack storage: for local variables, parameters and so on  
• Heap storage: Data that may outlive the call to the procedure that created it 
• Stack allocation is a valid allocation for procedures since procedure calls are nest   

 Example:
Consider the quick sort programint a[ll]

void readArray() { / Reads 9 integers into a[l],a[9j. */ int i;

> 

int partition (int m, int n) ■(

/* Picks a separator value v, and partitions a[m.. n] so that
a\m .. p — 1] are less than v, a\p\ = v, and a[p + 1.. n] are
equal to or greater than v. Returns >

void quicksort (int m, int n) -( int i;

if (n > m) -(

i = partition(m, n);
quicksort(m, i-1);
quicksort(i+1, n);

> 

> 

main() {

readArray() ; a[0] = -9999;
a [10] = 9999;
quicksort(1,9);

>

Activation for Quicksort

enter main()

enter readArray() 
leave readArray() 
enter quicksort(1,9)

enter partition(l,9)
leave partition(1,9)
enter quicksort(1,3)

leave quicksort(1,3)
enter quicksort(5,9)

leave quicksort(5,9)
leave quicksort(1,9)
leave main()

Activation tree representing calls during an execution of quicksort:

Activation records

• Procedure calls and returns are usually managed by a run-time stack called the control stack.  
• Each live activation has an activation record (sometimes called a frame)  
•  The root of activation tree is at the bottom of the stack  
• The current execution path specifies the content of the stack with the last  
• Activation has record in the top of the stack.
   

A General Activation Record

Activation Record

• Temporary values  
• Local data    
• A saved machine status  
• An “access link”  
• A control link
• Space for the return value of the called function  
• · The actual parameters used by the calling procedure    
• · Elements in the activation record:   
• Temporary values that could not fit into registers. 
• Local variables of the procedure.
  Saved machine status for point at which this procedure called. Includes return address  
  and contents of registers to be re  stored. 
• Access link to activation record of previous block or procedure in lexical scope chain.
• Control link pointing to the activation record of the caller.  
• Space for the return value of the function, if any.
• actual parameters (or they may be placed in registers, if possible)  

 Downward-growing stack of activation records:
 

Memory Manager: 

•  Two basic functions:   
• Allocation  
• Deallocation
• Properties of memory managers: 
• Space efficiency  
• Program efficiency  

Low overhead

Typical Memory Hierarchy Configurations:



Locality in Programs:

The conventional wisdom is that programs spend 90% of their time executing 10% of the code: 

• Programs often contain many instructions that are never executed.  
• Only a small fraction of the code that could be invoked is actually executed in atypical run of the program.  
• The typical program spends most of its time executing innermost loops and tight recursive cycles in a program.