Final Report

Richard Jones

Introduction

The proposal for a Memory Management Network (MMnet) made notable claims. We stated that use of automatic memory management has consistently been demonstrated to be beneficial for software development, especially as programmers build large and more complex systems; that use of languages such as Java in substantial applications of commercial import would make garbage collection more important economically than ever before; and that all modern object-oriented languages (except C++) would require automatic memory management. Furthermore, we argued that garbage collection was a ‘hot’ topic that would continue to throw up new challenges as researchers throughout the spectrum of applications: from multiprocessor, multi-gigabyte servers to limited capabil­ity, real-time embedded devices.

The three years of the project’s lifetime have shown that we underestimated the importance of this field. Languages like C# are increasingly widely deployed. Java has pene­trated the consumer market, for example through games on middle to high-end mobile phones. Even the new Managed Extensions for C++ [1] mandates garbage collection [2] . Re­search in this field is intense: since the inception of the Network, approximately 200 directly relevant papers have been published, including 35 by MMnet members.

Aims of the Network

The aims of the network were:

1. To create a UK forum in the field of memory manage­ment in order to strengthen the UK's position and re­alise its potential in this area.
2. To involve participants from key UK organisations (academic and commercial).
3. To improve communication mechanisms between academia and industry, so that they can better understand each other's requirements in this field.
4. To initiate and/or improve collaborative projects.
5. To develop and improve standards by which work is reported through development and dissemination of benchmarks, metrics and program traces against which work can be reproduced, evaluated and compared.
6. To train postgraduate students and industrial developers in state-of-the-art techniques.

In order to realise these aims, the Network set itself the following measurable targets:

1. To construct a web site.
2. To hold two workshops.
3. To support visits between partners and to conferences.
4. To increase the number of jointly authored publications.
5. To facilitate collaborative projects.
6. To increase the membership of the Network.
7. To support the formation of consortia to bid for re­search funding.
8. To train developers and postgraduates, with a target of 4 postgraduates researching memory management and 20 developers and postgraduates trained through workshops.
9. To produce 3 annual reports.

These targets have been achieved.

Objective 1: To increase the membership of the Network.

This objective has been achieved. The Network has grown from 7 to 16 organisations.

The Network was established with the support of 7 UK organisations: the universities of Glasgow, Kent, South­ampton and St. Andrews, and IBM UK, Insignia Solutions and Microsoft Research. One of its prime objectives was to enlarge its membership. By the end of the project, 9 further organisations had joined, all playing an active part in the Network: Cambridge, Heriot-Watt, Imperial Col­lege, Leeds, Middlesex, Nottingham, QMUL and UCL universities, and Ravenbrook Ltd, a small consultancy firm. A mailing list, open to MMnet partners only, is hosted at Kent.

Two outcomes of the Network are particularly welcome. First, the Network, particularly through its workshops, has reunited researchers who had in many cases lost contact with each other.

“I've felt that MMnet has worked particularly well through the workshops which have given me a much better idea of other work going on in the UK.”

A second and largely unanticipated outcome has been the bringing together of theoretical computer scientists and practitioners. As the field matures, we expect the applica­tion of static analyses and new logics to memory manage­ment problems to be particularly fruitful.

“MMnet provided a setting in which people like myself with theoretical tendencies and backgrounds could be exposed to the practical problems and issues in the area. I have found this aspect quite valuable.”

Unfortunately, to the Network’s loss and Sun Micro­systems’ gain, Dr Printezis, the network’s Co-Investigator, moved to the latter’s Java Technology Research Group in Burlingham, MA in September 2001; Dr Dickman, also of Glasgow University, replaced him as Co-Investigator. The Java Virtual Machine business of Insignia Solutions, one of the original partners, was bought by the Swiss company Esmertec in 2003; since then, they have been largely pas­sive members of the Network. However, all other partners have participated actively.

Objective 2: To construct a web site

This objective has been achieved.

The Network acquired a domain, mm-net.org.uk, and has constructed an extensive web site, hosted by the University of Kent. The web site holds a number of re­sources and links useful to the members and other com­mercial and academic researchers.

• An explanation of the Network and its mission.
• A list of its members and links to their web pages.
• Details of MMnet projects.
• Programmes and proceedings of MMnet’s workshops and its Summer School.
• A list of memory management related publications by members of MMnet partner institutions.
• Garbage collection bibliographic databases.
• Links to freely available and commercial garbage collectors and other memory managers, tools for debugging and visualising memory managers.
• Benchmark suites for Java and C++ memory manager performance testing.
• A directory of UK researchers known to have memory management interests.
• MMnet annual reports, and reports of relevant conferences.

Table I shows the traffic volume of the website (meas­ured in successful page requests). We speculate that the decline in the use of bibliography may be due to increased take-up of the ACM’s and other digital libraries. On the other hand, the usage of other MMnet pages has increased substantially. Interestingly, the years with the highest ac­cess figures are those in which the main conference, ISMM, was held.

The on-line bibliography (gcbib) is the largest biblio­graphic database for garbage collection papers, with over 2000 entries. It is the standard bibliographic resource for garbage collection, used by researchers worldwide.

The directory of UK researchers includes those with int­erests in explicit and automatic memory management, implementation of virtual machines, tools for the analysis of memory performance and static analysis techniques for improving correctness of programs that manipulate heap-allocated data.

One of the aims of the Network was to develop and im­prove standards by which work is reported through use of more realistic benchmarks and better experimental meth­odologies. Some progress has been made in this area and the website provides links to benchmark suites. Although proposals have been made for standard trace specifica­tions, and tools provided, there has been no take-up by the wider community and owners of traces have proved re­luctant to share them. Nevertheless, the standard of reporting of experimental results in conference papers and journals has improved. This is partly due to the efforts of programme committees and reviewers, including MMnet partners.

Objective 3: To hold two workshops.

This objective has been surpassed.

The Network held four workshops (double the target set) and a residential Summer School. The response to these meetings has been positive beyond our expectations. The workshops were sufficiently successful that the partners have resolved to continue them beyond this project, whether or not funding becomes available (the first will be held during Glasgow’s Research Festival in summer 2005).

 “I found the workshops useful and inspiring in my work.”

“Gaining exposure to UK and the IBM T J Watson / Haifa, Sun Labs, Microsoft Research, etc, GC researchers has been fantastic and hopefully good for a career in this field!”

The workshops were held in different locations in the UK; two were generalist and two focussed on specific as­pects of memory management (Table II). All the work­shops were attended by a mixture of academics (A), postgraduates (P) and developers (D).

The Network’s very successful Summer School took place over two days in July 2004. Leading international researchers from industry and universities (Bacon, IBM TJ Watson; Berger, U. Massachusetts; Boehm, HP; Detlefs, Sun Microsystems; Hudson, Intel; Moss, U. Massachu­setts; and Sciampacone, IBM Ottawa) discussed the state of the art in both automatic and explicit memory manage­ment with 28 attendees (postgraduate students, academic and industrial researchers).

“The garbage collection school was a triumph, really outstanding.”

£9,534.61 (budget £5,000) was spent on MMnet work­shops, including its Summer School. Two of the work­shops were partly sponsored by industrial companies, Symbian and Intel, and some organisations provided free use of their facilities for meetings. In addition to the MMnet workshops, Jones and O’Hearn co-organised SPACE 2004, the Second Workshop on Semantics, Pro­gram Analysis and Computing Environments for Memory Management in Venice in 2004, in cooperation with ACM POPL; SPACE’04 was attended by 50 participants.

Objective 4: To support visits

This target has been achieved.

The greatest proportion of MMnet’s expenditure (see Table III) was spent on travel expenses to allow MMnet members to attend conferences in Europe, North America and Australia (ISMM, OOPSLA, PLDI, SPACE, SAC, IFIP WG 2.8), as well as MMnet workshops and its Summer School. It has also allowed visits between MMnet partners to work on particular projects, such as heap visualisation, new proof techniques for distributed garbage collection, memory management for embedded systems, cost analysis and garbage collection for embedded systems, and so on. A list of projects is given under Objec­tive 6 below.

Objective 5: To increase the number of jointly authored publications.

We believe that this target has been achieved.

39 papers have been published by MMnet members since the start of the project. 6 papers had industrial co-authors, and 13 had international co-authors. 10 publications were the result of collaborations between MMnet academic partners (Glasgow, Kent, Southampton; Imperial. Middlesex, QMUL; Heriot-Watt, St. Andrews) and 2 between industrial and academic partners. Overall, the authors of 19 publications were drawn from different organisations. Several of these publications were in conferences and journals of the highest international quality [1 ,2 ,3 ,14 ,25 ,16 ,31 ,32 ]. While any estimate of the number of jointly authored publications that might be produced without MMNET must be speculation, we are confident that the Network has promoted collaboration between partners.

Network members have published software as well as papers. The GCspy heap visualisation framework (devel­oped by Kent and Glasgow/Sun Microsystems) is freely available, as is a port to IBM’s JikesRVM virtual machine (Kent). GCspy will be available for Microsoft’s Rotor platform by September 2005.

Objective 6: To facilitate collaborative projects.

This target has been achieved.

15 projects, including 7 collaborations between MMnet partners, were undertaken during the period of this grant.

1. The GCspy heap visualisation framework, developed by Kent and Glasgow, provides an architectural framework for the collection, transmission, storage and replay of memory management behaviour, as well as a novel visualisation tool to present this information. It has been incorporated into Sun Microsystems’ ResearchVM and Hotspot virtual machines; IBM’s production and JikesRVM research VMs (including Blackburn’s VM-neutral MMTk garbage collection kit); work supported by Microsoft Research is under­way to incorporate it into Rotor, their Shared Source Common Language Infrastructure. [31 ,34 ]
2. Glasgow, Kent and Southampton’s work on formalising descriptions of distributed garbage collection algorithms has uncovered and corrected flaws in the account of a widely used technique [1].
3. Heriot-Watt’s and St. Andrews’ have developed novel and world-leading automatic analyses for costing recursive, higher-order and polymorphic pro­grams. One particular goal has been to permit automatic dynamic memory allocation and collection, and other high-level language features in languages that can be used to meet hard real-time and real-space requirements [7,8,9,18].
4. Collaboration between Imperial, Middlesex and QMUL universities (and others) has shown how separation logic can be used to reason about programs in the presence of garbage collection [12,13,14,16,25 ]. Local reasoning allows a specification and proof to concentrate on a circumscribed collection of resources that a program actually acts upon, instead of the entire conceivable state space of a system. The key tools underlying this project are the logic of bunched implications and separation logic.
5. UCL has been investigating new memory allocation algorithms for “smartphones” that promise both high memory efficiency and very fast worst-case time performance — theoretical analyses and prototype simu­lations demonstrate worst-case response times that are an order of magnitude better than the state of the art, together with a doubling of memory efficiency. UCL is closely collaborating with Symbian Software Ltd. over the Symbian OS allocator, and are receiving in­formal assistance from Microsoft Research at Cambridge for the Windows CE allocator. If the experiments are successful, Symbian may incorporate the new memory management algorithms into the Symbian OS.
6. Imperial College and Microsoft Research have improved barrier techniques for incremental, generational garbage collection for Haskell [10 ].
7. Cambridge and IBM sought to elide write barriers for concurrent collectors for Java [11 ].

In addition, MMNET partners have collaborated with a number of organisations outside the Network (St. Andrews and U. Adelaide [15,26,27 ]; Cornell, DIKU, Kent, QMUL organised SPACE’04; Sun Microsystems part-funded Printezis at Glasgow; ANU, Kent, U. Massachusetts and U. Texas on the Beltway garbage collection framework [32 ]; Kent and Sun Microsystems on removing GC synchronisation [4,5,18,30 ]; DIKU and Kent’s GC tutorial for OOPSLA’03; Glasgow and Spartan Solutions (a local SME). Further details can be found on the Network’s web­site.

We believe that the Network has been useful, and in some cases certainly instrumental, in facilitating these projects. On the other hand, the goal of a portfolio of instructive case studies has not been achieved.

Objective 7: To support the formation of consortia to bid for funding.

This objective has been achieved.

Members of the Network have successfully sought funding for their memory management related research from industry (including MMnet partners, EPSRC and the EU). The total support amounts to £1,519,668 (details are given in the Final Report Form). The following areas suc­cessfully sought funding from the EPSRC, EU and private industry:

• Visiting Fellowships at St Andrews for researchers from U. Adelaide working on distributed garbage collection (EPSRC GR/R84881/01, EPSRC EP/C003454/1).
• Separation logic at QMUL (EPSRC GR/S53961/01, EPSRC GR/S53978/01)
• Techniques for costing resource requirements of func­tional languages, St. Andrews and Heriot-Watt, (EP/C001346/0, FP6 IST-2004-510255)
• Object demographics (funded by IBM), novel garbage collection techniques (funded by IBM) and heap visual­isation (funded by Microsoft) at Kent.

Further bids for support (Kent, Middlesex, St. Andrews) are in preparation. The MMnet partners have resolved to continue the activities of the Network. In particular, we shall continue to hold occasional workshops (the first will be held during Glasgow’s Research Festival in summer 2005) and Kent will continue to support the website and mailing list.

Objective 8: To train developers and postgraduates.

This target has been surpassed.

The Network’s target was for 4 postgraduates research­ing memory management and to train 20 developers and postgraduates through its workshops. This target has been exceeded. 4 PhDs (Cambridge, Glasgow, Kent) in this field have been completed and 7 more PhDs (Cambridge, Imperial, Kent, Nottingham, QMUL, St. Andrews) and 4 MSc’s (Glasgow, UCL) are in progress in the partner uni­versities. Numbers of postgraduate students and developers attending the Network’s workshops and Summer School are shown in Table II,

Objective 9: To produce three Annual Reports.

This objective has been met.

Three annual reports have been produced and are available from the MMnet website.

Expenditure.

Actual expenditure has diverged substantially from the original budget in 4 respects (Table III). Encouraged by the partners’ reception of the workshops, we held twice as many as planned.

Table III: Major expenditure divergences from budget (excluding overheads).

The Summer School was an excellent platform for al­lowing postgraduates and developers to interact with leading international researchers; we subsidised attendance to encourage participation. We commend this strategy to other networks.

The original proposal sought support for a contribution to the cost of disk space for the website. Instead, the space was donated by the University of Kent. However, we found a need for tools to produce a high-quality website. The Network bought a laptop running Windows XP for the Principal Investigator; website and graphics software were provided under the University of Kent’s site license. A laptop was bought so that it could also be used by speakers at MMnet workshops and its Summer School.

Finally, these virements were made possible because demand for travel expenses was less than anticipated. The activity of the partners suggests that alternative funding sources were available in many cases.

Conclusion.

The Network has achieved all the targets set in the initial proposal.

An effective forum has been created, with active participation of most of the key UK organisations in the field of memory management.

The Network’s workshops and its Summer School have proved particularly successful. Its website holds links to a number of valuable resources for researchers in this field, and is well used.

The target for training postgraduate students and developers has been exceeded.

We are confident that MMnet has facilitated an impressive number of new projects and collaborations. The publication record of its members demonstrates collaboration between academic and industrial, and international, co-authors.

The Network has been found to be sufficiently useful that its members intend to continue its activities beyond the end of the project. MMnet members have won follow-on support for projects of over £1.5 million.  

Publications

1. L. Moreau, P. Dickman and R.E. Jones. Birrell's distributed reference listing revisited. To appear in ACM Transactions on Programming Languages and Systems (TOPLAS), 53 pages. 2005.
2. R. Bornat, C. Calcagno, P. O'Hearn, Matthew Parkinson. Permission Accounting in Separation Logic. ACM Symposium on Principles of Programming Languages (POPL05). ACM Press, 2005.
3. C. Calcagno, P. Gardner, U. Zarfaty. Context Logic and Tree Update. ACM Symposium on Principles of Programming Languages (POPL05). ACM Press, 2005.
4. R.E. Jones and A.C. King. Collecting the garbage without blocking the traffic. Technical Report 18-04, University of Kent, September 2004
5. A.C. King. Removing garbage collector synchronisation. PhD thesis, University of Kent at Canterbury, September 2004.
6. A. Cunei. Use of pre-emptive program services with optimised native code. PhD dissertation. Glasgow 2004.
7. G.J. Michaelson, K. Hammond and J. Sérot. Hume: Programming Resource-Limited Systems using Bounded Automata. ACM Symposium on Applied Computing (SAC 2004), Nicosia, Cyprus. ACM Press. February 2004.
8. K. Hammond and P. Vasconcelos. Inferring Cost Equations for Recursive, Polymorphic and Higher-Order Functional Programs. Implementation of Functional Languages, Edinburgh, Scotland, Springer-Verlag Lecture Notes in Computer Science, 2004, pp 86-101. Nominated for the Peter Landin Prize for best paper.
9. G.J. Michaelson, K. Hammond, and J. Sérot. The Finite-Stateness of FSM-Hume. Trends in Functional Programming 4, Intellect, 2004.
10. A. Cheadle, A. Field, S. Marlow, S. Peyton Jones, L. While. Exploring the Barrier to Entry - Incremental Generational Garbage Collection for Haskell. International Symposium on Memory Management (ISMM04), Vancouver, October 2004. ACM Press, 2004.
11. M.T. Vechev and D.F. Bacon. Write Barrier Elision for Concurrent Garbage Collectors. International Symposium on Memory Management (ISMM04), Vancouver, October 2004. ACM Press, 2004.
12. J. Berdine, C. Calcagno, P. O’Hearn. A Decidable Fragment of Separation Logic. Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2004), pp. 97-110, LNCS Volume 3328, Springer-Verlag, 2004.
13. R. Bornat, C. Calcagno, P. O’Hearn. Local Reasoning, Separation and Aliasing. Semantics, Program Analysis and Computing Environments for Memory Management (SPACE 2004), Venice, 2004.
14. D. Pym, P. O'Hearn, H. Yang, Possible worlds and resources: The semantics of BI, Theoretical Computer Science 315(1), pp257-305, 2004.
15. S. Norcross, R. Morrison, D.S. Munro, H. Detmold and K. Falkner. Implementing a Family of Distributed Garbage Collectors. Journal of Research and Practice in Information Technology 36 (3), pp. 69-88. August 2004.
16. P.W. O'Hearn, H. Yang and J.C. Reynolds. Separation and Information Hiding. ACM Symposium on Principles of Programming Languages (POPL04), pages 268-280. ACM Press, 2004.
17. N. Nethercote and J. Fitzhardinge. Bounds-Checking Entire Programs Without Recompiling. Semantics, Program Analysis, and Computing Environments for Memory Management (SPACE 2004), Venice, 2004.
18. H.-W. Loidl, F. Rubio, N. Scaife, K. Hammond, S. Horiguchi, U. Klusik, R. Loogen, G.J. Michaelson, R. Peña, S. Priebe, A.J. Rebón Portillo, P.W. Trinder. Comparing Parallel Functional Languages: Programming and Performance. Higher Order and Symbolic Computation 16(3), pp 203-251. 2003.
19. A. C. King. Removing GC synchronisation (extended version). Winner (Graduate Division) ACM Student Research Competition. Also Technical Report 11-03, University of Kent, April 2003.
20. K. Hammond and G.J. Michaelson. Hume: a Domain-Specific Language for Real-Time Embedded Systems. Generative Programming and Component Engineering (GPCE 2003), Erfurt, Germany, September 2003, Springer-Verlag Lecture Notes in Computer Science, 2003, pp. 37-56. One of two papers selected for fast-track submission to the ACM Transactions on Software Engineering Methodology.
21. K. Hammond and G.J. Michaelson. Predictable Space Behaviour in FSM-Hume. Implementation of Functional Languages, Madrid, Spain, Springer-Verlag Lecture Notes in Computer Science 2670, 2003, pp. 1-16.
22. A.J. Rebón Portillo, K. Hammond, H.-W. Loidl and P. Vasconcelos. Cost Analysis using Automatic Size and Time Inference. Implementation of Functional Languages, Madrid, Spain, Springer-Verlag Lecture Notes in Computer Science 2670, pp. 232-247. 2003.
23. H.-W. Loidl, F. Rubio, N. Scaife, K. Hammond, S. Horiguchi, U. Klusik, R. Loogen, G.J. Michaelson, R. Peña, S. Priebe, A.J. Rébon Portillo, and P.W. Trinder. Comparing Parallel Functional Languages: Programming and Performance. Higher Order and Symbolic Computation 16(3): 203-251, 2003.
24. M.T. Vechev and P.D. Petrov. Class Unloading with a Concurrent Garbage Collector in an Embedded Java VM. Embedded Systems and Applications (ESA'03). CSREA Press. 2003.
25. C. Calcagno, P.W. O'Hearn, R.Bornat. Program Logic and Equivalence in the Presence of Garbage Collection. Theoretical Computer Science 98(3), pp557-581. 2003.
26. S. Norcross. Deriving Distributed Garbage Collectors for Distributed Termination Algorithms. PhD thesis, University of St Andrews, 2003.
27. S. Norcross, R. Morrison, D.S. Munro, H. Detmold and K. Falkner. Implementing a Family of Distributed Garbage Collectors. Australasian Computer Science Conference (ACSC 2003), Adelaide, Australia, pp 161-170. 2003.
28. N. Nethercote and J. Seward. Valgrind: A Program Supervision Framework. Third Workshop on Runtime Verification (RV'03), Boulder, Colorado, USA, July 2003.
29. N. Nethercote and A. Mycroft. Redux: A Dynamic Dataflow Tracer. Third Workshop on Runtime Verification (RV'03), Boulder, Colorado, USA, July 2003.
30. A.C. King. Removing GC synchronisation. OOPSLA'02 ACM Conference on Object-Oriented Systems, Languages and Applications (Companion), pp112-113, Seattle, WA, November 2002. ACM. Winner of the ACM SIGPLAN Student Research Competition 2002.
31. T. Printezis and R.E. Jones. GCspy: An adaptable heap visualisation framework. OOPSLA'02 ACM Conference on Object-Oriented Systems, Languages and Applications, Seattle, WA., November 2002. ACM Press.
32. S.M. Blackburn, R.E. Jones, K.S. McKinley, and J.E.B. Moss. Beltway: Getting around garbage collection gridlock. PLDI'02 Programming Language Design and Implementation, Berlin, June 2002. ACM Press.
33. F. Reig. Compiler Architecture using a Portable Intermediate Language PhD dissertation. Glasgow 2002.
34. T. Printezis and A. Garthwaite. Visualising the Train Garbage Collector. International Symposium on Memory Management (ISMM’02), pp50-63, Berlin, Germany, July 2002.
35. P.D. Petrov and M.T. Vechev. Embedded JVM Concurrent Garbage Collector Internals. IASTED Networks, Parallel and Distributed Processing, and Applications (NPDPA'02). ACTA Press, 2002.
36. N. Nethercote and A. Mycroft. The Cache Behaviour of Large Lazy Functional Programs on Stock Hardware. Workshop on Memory System Performance (MSP 2002), pp44-55, Berlin, Germany, July 2002.
37. P.M. Hill and F. Spoto. A Foundation of Escape Analysis. 9th International Conference on Algebraic Methodology and Software Technology (AMAST 2002), St. Gilles les Bains, Reunion Island, France, September 9-13, 2002, vol. 2422 of Lecture Notes in Computer Science, pp. 380--395. Springer-Verlag 2002.
38. H.-W. Loidl. The Virtual Shared Memory Performance of a Parallel Graph Reducer. DSM 2002: International Workshop on Distributed Shared Memory on Clusters, Berlin, pp. 311-318, May 2002. IEEE Press.
39. P.M. Hill and F. Spoto. A Refinement of the Escape Property. Verification, Model Checking and Abstract Interpretation (VMCAI’02), Venice, Italy, January 2002, Lecture Notes in Computer Science 2294, pp 154-166. Springer-Verlag 2002.     
    
    

    ---