Antonio Cunei

Precise Garbage Collection in Uncooperative Environments

A large class of memory management systems ("garbage collectors") require full knowledge of the set of references in use by the program at any given time. The algorithms that do not use precision must operate under conservative assumptions, and suffer from limitations in the way in which they handle memory. Compilers that target C code, in particular, are frequently restricted to conservative collectors, as the C language makes little distinction between references and integer values.

We developed and implemented a novel approach to supporting precision in compiler systems that use C/C++ as their target language; we offer full support for precise memory reclamation and management, enabling the use of fully moving garbage collectors and of precise real-time garbage collection systems. Our new technique significantly outperforms previous approaches. A paper describing the new approach and our results has been presented at the 16th International Conference on Compiler Construction (ETAPS 2007).

 

···•···

Real-Time Checkpointing

While working on the Ovm system, I noticed a previously unknown problem with existing real-time checkpointing techniques. When certain categories of programs are executing, the interaction between user code and real-time checkpointing may lead to long delays in serving high-priority threads, adversely affecting the real-time characteristics of the system. From that observation, I developed a new algorithm for concurrent real-time checkpointing that does not impact on the latency, even in the presence of pathologically uncooperative user programs: the maximum latency remains lower than 0.2 milliseconds even when checkpointing is in progress. A paper on this work has been presented at VEE 2006.

···•···

PolyD: A flexible dispatching framework

My most recent project is PolyD, a flexible dispatching infrastructure for the Java language developed at Purdue University. The tool can be used to implement visitor-like mechanisms, or general multiple dispatching, or more unusual dispatching policies. PolyD makes it also possible to customize many aspects of the dispatching process: the handling of null arguments, of missing methods, of ambiguities, of the method invocation, and so on.

PolyD is more fully described on a separate page.

Heap state extraction at every assembler instruction

Several operations (garbage collection, for instance, or data migration) can be performed in current computer systems only at selected points in the code. Using a preemptive approach, in fact, not enough information would be available about the thread and the memory state to perform all the complex manipulations needed. For instance, which values, contained at a certain point in the registers, are pointers? And which are scalar values?

My Ph.D. research revolved around the ability to extract enough information from a fully optimized and natively compiled code to be able to perform the mentioned system operations potentially at every assembler instruction. There are a number of potential advantages. First of all, preemptive thread-switching can be used freely since, when a heap manipulation is requested, there is no need to roll the various threads forward. Pointer information for every assembler instruction can be of use while performing debugging. Furthermore, certain implementation techniques can be simplified (for instance, the use of thread-local heaps).

According to this research, the intended result can be obtained, in most cases, simply generating automatically, during compilation, small and fairly compressible tables that associate every value of the program counter with the necessary information. My Ph.D. thesis contains an extensive review of the existing approaches known in literature, and of the various techniques that can be applied to this problem.

The main product of my research is a prototype composed by a modifier compiler and a toolbox. Every program compiled with the compiler and using the primitives offered by the toolbox, as long as a certain restrictions are respected, should gain the ability to perform garbage collection, thread migration or other memory manipulations at any assembler instruction, regardless of the high-level language used and without any run-time overhead. The environment I used was the popular GCC compiler suite (version 3.3), whose back-ends was customised to generate the needed information. The prototype, which shows in practice some of the techniques used in the research work, is able to compile and run test programs written in multiple languages. The resulting code can be interrupted at any moment, and the heap modified on-the-fly.

Supervisors for my Ph.D. research were Prof. David Watt and Dr. Simon Gay. The project was also supervised by Prof. Malcolm Atkinson and Dr. Tony Printezis.

···•···

 

Sun Tan

During my internship at Sun Microsystem Laboratories, in the summer 2001, I have worked in the context of the Mayhem project, which investigates the usefulness of alternative memory hierarchies when executing Java applications.

The simulation framework that is being used in the project to validate the memory hierarchy designs relies on the Tracing Java Virtual Machine (TJVM). The TJVM is an instrumented VM capable of generating, during the execution of a Java program, a trace file containing a rich set of information about creations and manipulations of objects, stack frames, classes, garbage collection roots, etc.

Such a trace file can be used for a variety of purposes and is ideal to gather some statistical information about the memory behaviour of Java programs. Under the supervision of Mario Wolczko, the leader of the Mayhem project and my manager during the internship, I was given the task of writing a tool that parsed the trace file to generate statistical information.

The result (named "Tan", from Trace ANalyser) ended up being quite a flexible instrument that can be used to simulate the memory behaviour of the original Java program that generated the trace. The memory state, simulated step by step, can be easily inspected to determine various program properties. It is also possible to run the memory simulation over and over using different garbage collectors, so that their effect can be analysed.

A statistical package was also written, which is able to extract automatically a wide range of information about objects and other program characteristics (distribution according to object size over time, object creation and destruction rate, number of active threads, lifetimes vs number of reads/writes/lock operations, etc.)

A particular new algorithm was used to determine the exact lifetime of objects without performing a complete garbage collection at every step of the simulation. The idea for the algorithm was originally by Mario Wolczko. We have worked on the idea and I subsequently implemented it as a real system. A patent was obtained as a result of this research work ("Fast lifetime analysis of objects in a garbage-collected system", US Patent No. 6,728,738).

···•···

 

Dynamic Profiling & Thread-local Heaps

During my second internship in Sun Labs, I investigated the use of dynamic profiling with thread-local heaps in order to preallocate objects directly in the shared or the local heaps, relying on information acquired at run-time. My research showed a marked correlation between the last portion of the dynamic call chain and the chance that an object has to become reachable by multiple threads. A report containing the obtained results will be posted here shortly, but in the meantime, if you are interested, just send me an email to obtain more data. Update -- a paper on the same subject, by researchers at IBM Haifa Research Laboratory, has appeared in the meantime.

···•···

 

BOH: Basic Object Handler

A programming language entirely based on objects. Similar to C in the basic syntax, it is characterised by, among other intriguing features, an extensive use of multimethods similar to those found in CLOS. Special techniques are developed, however, to allow for an entirely static type checking, even with multimethods, and other related techniques are used to show a way to use multiple inheritance effectively without the problems and the lack of clarity usually involved in other languages. The final result is a language that is simple to use and entirely object-based.

The project was developed as a final thesis for my "Laurea" degree in Computer Science (roughly equivalent to a M.Sc.). A PDF version of the original thesis (in Italian) can be downloaded from here.

Much of the same information is available in English from the technical report mentioned in the next project.

···•···

 

Orthogonally Persistent BOH

As a subsequent development of the project, an orthogonally persistent version of the same language was created during the following year. Relying on the Sphere persistent object store, the programs written with this experimental version of the BOH language perform automatic checkpoints of data and thread state, and can be seamlessly resumed following an unexpected interruption.

A comprehensive description of the final system was published as a Technical Report by the Dept. of Computing Science of the University of Glasgow and can be downloaded in PDF format from the publications page.

···•···

 

OOPLog: an Object Oriented extension for Prolog

Developed quite a few years ago in collaboration with Marino Miculan at the University of Udine, OOPLog is a software layer that effectively allows for an object-oriented usage of Prolog. Its main characteristic is the preservation of the peculiar logic style of the language, avoiding imperative behaviours. Special care has been taken to allow, whenever possible, for a pure logic usage of messages, that is, for instance, the ability of obtaining the past status of an object given the future one and the message, and so on. Particular attention is paid to the preservation of logical coherency of definitions whenever multiple inheritance is used.

No file is available for download at this moment, but I have recently retrieved a copy of the original code. If you are interested in this work, let me know!

···•···

 

Fast Ion Imaging

I have also worked in the past in a joint project between the International School for Advanced Studies (SISSA) and the International Centre for Theoretical Physics (ICTP): the Fast Ion Imaging project.

Purpose of the project was the development of a fast imaging system suitable for biological applications. Core of the project was the development of a very fast digital camera, capable of acquiring 800 frames/second at a resolution of 12 bits per pixel. The whole system is described in detail on this page, and here is a low-resolution movie of a fly recorded with the custom camera (a high-resolution version is also available.)

I am quite interested in developer tools and runtime environments, and their interaction. My future research will revolve around compilers, virtual machines, simulators/emulators, support for new chipsets and architectures, and so on. I hope to to create tools and technologies that can be of interest to people, and useful on a practical level. More details in the near future.