Midterm project

The Question

The project is about changing a part in the Nut-compiler (nut3.txt) and measures the change in the speed of execution.

The most inefficient function in nut-compiler is the symbol table search.  It is a sequential search ( O(n)). See the function  (def install ...) in nut3.txt.  Now change it to use hash ( O(1) ).  You can use any simple hash function, such as adding all ascii together and modulo by the table size (must be a prime number to give a good spreading).    

The compiler will work as before without any noticeable difference.  Only the execution speed will be faster (but you may not be able to see it). To measure its effect, you have to instrument the nut-simulator (written in C) (the package nut31.zip).  The number of instruction executed can be counted in the function eval3() (in the source file eval3.c).  In fact, there is a counter there already to prevent a infinite loop.  Use it.

What you are expecting to do:

1)  Rewrite nut-compiler, (def install ...) to use a hash table.
2)  Instrument eval3.c  to report the number of instruction executed.
3)  You must run some benchmark, compiling a few programs and measured the number of instruction executed of both old compiler and your new compiler (please keep a copy of the original nut3.txt for comparison).

What to hand-in

1)  Your new (def install...)  with explanation how it work.
2)  Your description of the experiment.  What kind of program you use for benchmarking?  Why do you think it is a fair representative for your purpose?
3)  Discuss the result.  How much faster the search with hash table?  Does it depends on the hash function?  
4)  Suggest some other way to improve the speed of the nut3.txt compiler.  You don't have to implement anything, just think and write your idea.

Please use the latest version of nut31.zip and nut3.txt posted for this project.  If you have any trouble working with these source files (such as recompiling the simulator) please let me know.  I will try to help.  

Please note: the midterm project constitutes 30% of the total score.  Hand-in by next Tuesday 14 Aug. by 4pm.

The source

nut31.zip    nut3.txt

Prabhas Chongstitvatana
5 August 2007