README
Comp40: Spring 2016
Project 7: Optimizing the UM

Programming Partners: Ballard Blair and Siddharth Kapoor 

We received help from the Comp40 TAs, thanks you all rock. 

We believe our optimized universal machine has been correctly implemented.

----------------------------------------------------------------------------
--------------------------Routine takes up most time -----------------------
By looking at kcachegrind, we have identified that the handle_instruction() 
takes up the most time in our program. We analyzed the assembly code and 
found alot of mov and push/pop instructions. We believe this is because 
handle_instruction() makes alot of function calls which mandates that
function parameters are pushed/poped from the stack. Were we to substitute 
the function calls for all the UM instructions inside handle_instruction() 
with the actual code for the functions, it wouldn't guarantee an improvement 
in performance since handle_instruction() has more variables than can be
maintained in the registers.

We also encountered a lot of nopl and nopw instructions wihch are used by x86
for padding. Our hunch is that the need for this arises from the varied use of 
data types, most importantly, our usage of various structs, which have 
arbitrary non-standard sizes. The way to eliminate these instructions would 
essentially be to hardcode these data structures inside our code. We would 
venture that doing this would improve our program's performance manifold. Yet,
the effort required to achieve this for a non-commercially used program far 
outweigh the performance improvements that can be expected, especially for 
standard benchmark programs.

----------------------------------------------------------------------------
-------------------------- Hours Spent -------------------------------------
    Analyzing Problem:               3        
    Solving Problems after Analysis: ~15

----------------------------------------------------------------------------
-------------------------- Machine Used ------------------------------------
We consistently used the machines in Halligan 120, which can be identified as 
Intel(R) Core(TM) i5-4590 CPU @ 3.30GHz

----------------------------------------------------------------------------
-------------------------- Benchmarks used ---------------------------------
We used the following programs as benchmarks:

midmark.um - final run time   .26 sec
sandmark.umz - final run time 6.66 sec
advent.umz - final run time   2.20 sec

----------------------------------------------------------------------------
-------------------------- Things we learned -------------------------------
-Breaking abstraction barriers is fun!

-We created a version of our optimized machine that uses function pointers
to execute UM instructions instead of a big switch case.
 
We found this actually slowed our program down because as it turns out our 
compiler optimized switch cases to jump tables which is essentially the 
same as using function pointers, without the additional deferencing that 
we had to do.