Heap state extraction at every assembler
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.
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.
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
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
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
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.
Object Oriented extension for Prolog
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):
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.)