[mps-discussion] MPS news, 2014-03-12

[Richard Brooksby]

On irc.freenode.net #memorypoolsystem, Bruce Mitchener said:

> what would be cool is some sort of regular (weekly?) email to the public list about what's happening on master or Interesting Branches.

Your wish is my command, Bruce.  I'm not sure about weekly updates, but there has been quite a lot going on that might interest people on mps-discussion.

The main thing driving MPS development is scaling up to big heaps on 64-bit.  The MPS has supported 64-bit processors since Alpha OSF/1 and Alpha Win NT, but the capability was dormant for a long time.  We revived 64-bit support last year for our commercial client, Configura, and we were also contracted to develop a 64-bit back end for the Configura Magic compiler.  Some of Configura's customers are running on multi-gigabyte heaps, and everything needs to scale up.

I won't reveal details without my client's permission, but we're achieving some significant speed-ups.  What I can tell you about is some of the changes, and if you want you can see all the details of the changes to the open-source portions of the MPS on GitHub <https://github.com/Ravenbrook/mps-temporary/>.  You can also see a summary of current and recent branches and what they're for here <https://info.ravenbrook.com/project/mps/branch/>.

Firstly, there's been a lot of clean-up of the garbage collection code that handles chains -- the structures that support the generational GC strategy.  Various pools had hard-wired ways of relating to chains, and relied on the behaviour of the VM arena to co-locate objects with the same generation number.  I'm not sure why this happened, since it was after my time at Harlequin, but it's all cleaned up now.  The arena no longer maintains any idea of generations, and memory pools explicitly subscribe to chains in order to take part in GC strategy together.  This is the first step on a planned rework of the whole GC "brain", aimed at support for ever larger heaps.  (See <http://www.ravenbrook.com/project/mps/issue/job003670/> for more background.)

Secondly, the MPS's hysteresis on returning memory to the operating system has been improved.  The MPS design is very diligent about actually freeing up memory and backing store for use by other processes.  This is something that other memory managers are often poor at.  In order to avoid being *too* eager and thrashing the OS's backing store allocator, the MPS retains some memory and then purges it back to the OS when it exceeds a threshold.  This wasn't being done very efficiently.  It involved a bit-table scan (poor scalability) and would always purge all the held memory at GC reclaim time.  Now it's using a queue structure with an LRU strategy and can afford to consider purging every time a page is freed.  It's both more prompt and more efficient.  In particular, during frequent GC cycles it reallocates memory back to GC pools very rapidly.  (See <https://info.ravenbrook.com/project/mps/issue/job003654/> and <https://info.ravenbrook.com/project/mps/issue/job003674/> for more background.)

Thirdly, the MPS's low-level page allocator was designed nearly 20 years ago when heaps were a lot smaller and we could afford to manage pages using bit table scans.  This is still fairly efficient, but eventually O(heap size) factors will kick in at really large heap sizes.  So the entire page allocator has been ripped out and replaced with a "coalescing block structure" (CBS) based on splay trees.  (Incidentally, splay and red-black trees are used in the OS X and Linux kernels for address space allocation.)  A lot of intensive reworking and experimenting has gone on since January and the arena allocator is now both faster and has worst-case complexity O(log(fragments)).  But more importantly, the whole system is architecturally much more flexible and we can drop in various other CBS implementations to meet customer requirements.  (See <https://info.ravenbrook.com/project/mps/issue/job003554/> for more background.)

For any of the old Harlequin MM Group that are still reading and put hard work into CBSs and Splay Trees, your work is paying off, though probably not in the way you imagined.

Another new feature just in code review is a new nailboard implementation to support ambiguous interior pointers efficiently <https://info.ravenbrook.com/project/mps/issue/job003359/>.  This will support the work of Christian Schafmeister who's been integrating the MPS with his Common Lisp on C++ implementation, and should make the MPS safe with some of LLVM's more aggressive optimisations.

I hope this is of some interest.  Your feedback and questions are always welcome.


---
Richard Brooksby <rb at ravenbrook.com>
Senior Consultant
Ravenbrook Limited <http://www.ravenbrook.com/>
Office: +44 1223 519215  Mobile: +44 777 999-6245