Introduction

The goal of the advanced project is to complete a more complicated task than the ones of the previous projects, and with less guidance from our part. Unlike the previous projects, the advanced project is individual and cannot be completed in a group.

Several subjects are proposed below, and each student must choose exactly one project to complete. It is also possible for a student to propose a subject of his/her own choice, but that choice must be validated by the instructor, and must of course be related to the subject of the course.

Deliverables and evaluation

For this project, you must hand in both a short report explaining your work, and the full code that you produced.

Your report should be less than 10 pages long, written either in English (preferred) or in French, and in PDF format. The quality of this report will be the main criterion used to evaluate your work, so please take care in writing it. This includes spelling and grammar, especially for people writing in their mother tongue. Don't hesitate to use graphs to present your quantitative results, as they are often very effective.

Your code must at least compile and run on the IN machines. If you have to write C code, remember the problems that a 64 bits architecture can cause.

The report and the code should be packaged in a ZIP archive and sent as an attachment to michel.schinz+acca@gmail.com before 18:00, May 30th, 2008. No late submission will be tolerated for this part.

Benchmark programs

Since many of the projects below consist in optimising the compiler and/or virtual machine, we provide you with three simple benchmark programs. You are of course free to write additional benchmarks or test programs.

bignums.scm
Computes the factorial of any non-negative integer (good values for benchmarking start approximately at 2000). Requires the list library.
maze.scm
Generates a random maze of a given size (good sizes for benchmarking start approximately at 15). Requires the list library.
fib.scm
Naively computes a term of the Fibonacci sequence (good values for benchmarking start approximately at 30).

Continuations

The goal of this project is to add continuations to the minischeme language, using the two different techniques presented in the course. This amounts to providing a new primitive, call-with-current-continuation (abbreviated to call/cc below), that makes it possible to obtain the current continuation at any time during execution.

Part 1: machine continuations (2 points)

A first technique to define call/cc is to use what has been called machine continuations in the course. It is called the gc strategy in the paper by Clinger et al. referenced below, because it relies on the fact that stack frames are allocated from the heap and freed by the GC unless they belong to a saved continuation.

To implement these continuations for minischeme, the easiest solution is probably to augment the language with the get-machine-continuation and set-machine-continuation! primitives mentioned in the course, and then to provide call/cc as a library function based on these primitives.

Part 2: continuation-passing style (8 points)

A second technique to provide call/cc is to transform the whole program to continuation-passing style (CPS) and then provide the CPS version of call/cc (i.e. call/cc/cps) as a library function.

Transforming the whole program to CPS requires augmenting the K function presented in the course to handle the full language, and then adding it as a transformation phase in the compiler.

Deliverables

You should hand in two versions of the minischeme system supporting continuations. The first should support them using machine continuations, the second through transformation of the program to CPS. The fact that both work should be demonstrated using a program making non-trivial use of continuations, like the generator example presented in the course.

Your report should include a description of how you extended the K function presented in the course to handle the transformation to CPS of the full minischeme language. It should also contain detailed measurements of the performance of the two implementations of continuations on several benchmark programs.

References

  1. Clinger, William D. et al. Implementation Strategies for First-Class Continuations

Copying garbage collector

The goal of this project is to replace minivm's conservative garbage collector by a precise, copying one.

Part 1: tagging/boxing of integers (4 points)

Before starting your work on the garbage collector itself, you should modify the compiler and/or the virtual machine to make sure that integers can be distinguished from pointers at run time. As explained in the course, there are basically two techniques for that: boxing and tagging.

Boxing consists in storing all integers in the heap, e.g. in a vector of size 1. This has an important cost both in terms of memory usage and speed, but has the advantage of preserving the full range of integers.

Tagging consists in using the alignment constraint of pointers to differentiate them from integers at run time. For example, the integer n can be represented as 2n+1, which guarantees that its least-significant bit is always 1, while that of pointers is always 0. This is much faster than boxing, but halves the range of integers.

Once you have implemented either boxing or tagging of integers, verify that your minischeme system is still functional before proceeding to the next part.

Part 2: copying garbage collector (6 points)

With integer tagging or boxing in place, write a new memory module for your virtual machine that implements a copying garbage collector. Cheney's algorithm, presented in the course, is probably the easiest to implement, but you are free to implement another algorithm if you want.

After writing and testing your copying GC, measure its performance and compare it to the performance of the original conservative GC.

Deliverables

You should hand in a new version of the minivm virtual machine, with a copying garbage collector. As described above, your report should contain detailed measurements of the performance of the copying GC, compared to the conservative one.

References

  1. Wilson, Paul R. Uniprocessor Garbage Collection Techniques
  2. Jones, Richard and Lins, Rafael. Garbage Collection. Algorithms for Automatic Dynamic Memory Management

Full minischeme compiled implementation

The goal of this project is to modify the compiler and virtual machine so that the compiled code enjoys the same safety properties as the interpreted one. That is, the type of values should be checked dynamically, as well as the indexes used in vector operations. Errors should result in program termination, and not in virtual machine crashes.

Part 1: tagging/boxing of integers (4 points)

This first part is the same as for the copying garbage collector project. Please refer directly to it.

Part 2: complete minischeme implementation (6 points)

Once tagging is in place, it is possible to distinguish pointers from integers at run time. Moreover, code pointers can be distinguished from data pointers, by comparing them to the starting address of the heap. Provided some technique is found to check that the indices used for array indexing are valid, and that the number of arguments passed to a function is correct, it should be relatively straightforward to guarantee that compiled programs never crash the virtual machine in case of error, but exit gracefully. Make sure that you do not forget a case! The source code of the interpreter can serve as a good checklist.

Notice that you are allowed to add instructions to the virtual machine, for example to make sure that the checks are not too costly.

Once your safe compiled implementation of minischeme is finished, evaluate the cost of the additional safety by comparing the running time of several benchmarks when run on the original system and on your variant.

Deliverables

You should hand in a modified minischeme system (compiler and virtual machine) that guarantees that erroneous programs do not crash the virtual machine, but rather make it exit gracefully—i.e. with at least a terse error message. Your report should detail the modifications made to the compiler and/or the virtual machine, and the rationale behind your implementation choices. Moreover, detailed measurements of the cost of the additional safety should be presented.

Improved conservative garbage collector

The goal of this project is to improve as much as possible the efficiency and memory usage of minivm's conservative garbage collector.

The following aspects could be improved:

  1. allocation speed, by using a more efficient data structure for the free list (e.g. some variant of segregated free lists),
  2. memory overhead, for example by grouping all blocks of a given size in a memory area, thereby removing the need for a per-object size header,
  3. pause time, for example by sweeping the heap lazily,
  4. incorrect identification of pointers, for example by ensuring that blocks are cleared before being returned to the program, and possibly using a black-listing technique as described by Boehm et al. (see references).

The articles referenced below can be used as inspiration, but you are of course free to design your own improvements.

A very important aspect of this project is that all improvements made must be justified by profiling analysis, using a tool like gprof, and their effect on several benchmark programs must be documented.

Deliverables

You should hand in a new version of the minivm virtual machine, with an improved garbage collector. As described above, your report should contain very detailed measurements of the effect of the various improvements you made.

References

  1. Boehm, Hans-J. and Weiser, Mark. Garbage Collection in an Uncooperative Environment
  2. Boehm, Hans-J. Space efficient conservative garbage collection

Native code generator (through LLVM)

The goal of this project is to modify the compiler to make it produce native code through LLVM.

Part 1: LLVM code generation, without GC (6 points)

The first part of this project is to change the compiler to make it emit LLVM code instead of minivm code. Do not worry about garbage collection yet, and simply allocate memory using a call to malloc.

Notice that, despite its name, LLVM is more high-level than our minivm. You should exploit this fact to translate minischeme functions to LLVM functions, and to allocate activation frames from the stack instead of the heap. Only vectors (and therefore closures) should be allocated from the heap.

Part 2: garbage collector (4 points)

Once the LLVM code generation works, add a garbage collector to your system. An easy way to do that is to simply use the Boehm-Demers-Weiser conservative collector for C and C++. Alternatively, you could try to make use of LLVM's support for precise garbage collection, and link with an existing GC, like the one of Objective Caml.

Deliverables

You should hand in a working version of the minischeme compiler that produces native code through LLVM. You should demonstrate that it works by running several benchmarks compiled using it, and report on the obtained performance gain.

References

  1. The LLVM Compiler Infrastructure (Web site)
  2. Boehm, Hans A garbage collector for C and C++ (Web site)

Super instructions

The goal of this project is to improve the efficiency of the virtual machine using super instructions. Two approaches must be compared for this project: a static one, and a dynamic one.

Part 1: static super instructions (4 points)

One technique to improve the efficiency of an interpreter is to try to find sequences of two or more instructions that are frequently executed, and to combine them in a new "super" instruction. Provided that the compiler is then modified to make use of those super instructions, the resulting code should be both smaller and faster.

For this project part, you should first instrument your virtual machine to collect statistics about instruction sequences that appear often. Then, given the results of those measures, you should propose and add at least three super instructions to your virtual machine. Finally, you should measure the speed gain offered by those super instructions on a set of benchmark programs.

Part 2: dynamic super instructions (6 points)

Another technique to speed up interpreters is to use dynamic super instructions. This idea is explained in the paper by Piumarta and Riccardi referenced below. The goal of this second project part is to implement their technique in your virtual machine. Once this is done, you should again measure the speed gain offered on the same set of benchmark program

Deliverables

You should hand in two versions of the virtual machine: one with at least three static super-instructions added, one with dynamic super-instructions. The first version should be accompanied by a modified minischeme compiler able to take advantage of the additional super-instructions.

Your report should include the statistical results that you obtained in part 1, as well as detailed measurements of the improvements brought by the two kinds of super-instructions, both in terms of speed and code size (for the static super-instructions).

References

  1. Piumarta, Ian and Riccardi, Fabio Optimizing Direct Threaded Code by Selective Inlining