gmane.comp.programming.garbage-collection.general

Unusual techniques in HLVM and

Jon Harrop — 2012-04-01T19:19:13

I just wrote a blog post detailing some of the techniques I adopted in HLVM
that appear to be unusual:

http://flyingfrogblog.blogspot.co.uk/2012/03/gc-safe-points-mutator-suspensi
on-and.html

In particular, HLVM uses many techniques that are much simpler than existing
alternatives but appear to be just as efficient.

In the process of writing that I thought of an interesting way to avoid
unnecessary pushes to the shadow stack. A previous benchmark indicated that
shadow stack manipulations can account for up to 70% of the total running
time of a program:

http://flyingfrogblog.blogspot.co.uk/2009/03/current-shadow-stack-overheads-
in-hlvm.html

So this theoretically has the potential to dramatically improve HLVM's
performance under certain circumstances (although I don't want to exaggerate
the potential advantages because HLVM's current GC is poorly suited for
allocation-intensive programs like that benchmark).

I wanted to avoid both caller and callee pushing the same value onto the
shadow stack. Obviousl

Mmmm... 2012 MMnet workshop on Memory Management for Many- and Multicore

Richard Jones — 2012-03-18T16:55:33


I'd be grateful if you could draw this to the attention of any colleagues or students who might be interested

Richard


                              2012 MMnet Workshop

                MMMM: Memory Management for Many- and Multicore

               www.mm-net.org.uk

                Monday 23rd April 2012, Imperial College London



Call for participation
----------------------

Memory management remains an important research area as managed run-time
environments are increasingly widely adopted. Server requirements for
multi-gigabyte heaps, the ubiquitous use of multicore platforms and the
advent of many-core processors throw up new research challenges. This
one-day workshop aims to bring together UK academia and industry with the
aim of establishing new links and enhancing existing collaboration within
the framework of the UK Memory Management Network.

Participation is welcomed from both academic and industrial sectors.
Topics of interest include but are not limited to:

      * virtual machine impl

Simple worked examples

Jon Harrop — 2012-03-04T16:52:24

For anyone who is interested, I recently published an article about my
implementation of the Very Concurrent Garbage Collector (VCGC) in F#:

http://fsharpnews.blogspot.com/2012/02/very-concurrent-garbage-collector.htm
l

The idea of prototyping GCs using high-level languages this way seems to be
quite novel. I adopted an allocationless style of programming where the
(preallocated) heap is represented as a value type array so it is completely
unboxed and, consequently, the results will be much more representative of a
production GC implementation. Note that the heap is specialized for the
n-queens solver but the GC algorithm itself is generic.

Regarding the algorithm, the complete VCGC implementation is under 300 lines
of F# code and it achieves submillisecond pause times and throughput
comparable to .NET itself. I instrumented the code with time stamping in
order to visualize the phases the mutator and GC thread were going through,
which proved invaluable when debugging performance issues.

The exchange of

Call For Papers: Wodet-3 - Third Workshop on Determinism and Correctness in Parallel Programming

Emery Berger — 2011-11-30T22:46:43

CALL FOR PAPERS

Wodet-3 - Third Workshop on Determinism and Correctness in Parallel Programming

http://goo.gl/K78CQ
March 3, 2012Co-located with ASPLOS 12, London, England, UK
Unintentional non-determinism is the bane of multithreaded
softwaredevelopment. Defective software might execute correctly
hundreds oftimes before a subtle synchronization bug appears, and when
it does,developers often cannot readily reproduce it while
debugging.Nondeterminism also complicates testing as good coverage
requires botha wide range of program inputs and a large number of
possibleinterleavings for each input. These problems have taken on
renewedurgency as multicore systems have driven parallel programming
tobecome mainstream.
Determinism is emerging as an important research area, ranging
fromtechniques for existing code (including deterministic
executionmodels, parallelizing compilers, and deterministic replay
fordebugging) to new programming models (including deterministic
generalpurpose languages and run-time systems). D

RESoLVE 2012 workshop CFP

Alex Garthwaite — 2011-11-30T20:24:44

Hello All!

Below is the CFP for the RESoLVE 2012 workshop (collocated with 
ASPLOS 2012). The theme of the workshop is about coordinating
across layers (application, runtime, OS, hypervisor) and
memory-management is definitely one challenge in this space.
The deadline is December 10th and the workshop is looking
for 6-8-page works-in-progress with an intent to spark discussion
and get early feedback. Please consider submitting. Thanks!

                             -- Alex



                 Virtualized Environments
                      (RESoLVE'12)
     http://www.dcs.gla.ac.uk/conferences/resolve12/
  
ASPLOS 2012 Workshop, London, UK
March 3rd, 2012
UPDATE: Submission deadline extended to 10 Dec

Introduction:
Today's applications typically target high-level runtime systems and
frameworks. At the same time, the operating systems on which they run
are themselves increasingly being deployed on top of (hardware)
virtual machines. These trends are enabling applications to be
written, tested, and deployed

Re: Visualizing clumps

Nick Barnes — 2011-11-18T19:44:56


Every node is a cons cell? OK. Would you predict star-shaped clumps,
based on the algorithm?


Understood.  I'm very out-of-date here; does PolyML (or GHC) build via
a bootstrap, which could be used as a GC benchmark?

Nick B

Re: Divide and conquer GC algorithms

Jon Harrop — 2011-11-17T23:36:42

As an example, consider storing the heap topology in a k-D tree indexed by
the pair (a, b) where "a" points to the source object and "b" points to the
destination object that the source refers to.

the
Train
blocks
granularity.
concept of
a
partition
way
a
the
big a
as

Re: Visualizing clumps

Jon Harrop — 2011-11-17T23:36:38

when a

These are immutable singly-linked lists with sharing. So several different
list nodes (cons cells) can refer to the same tail but each list node can
only refer to zero or one other lists. For example, a "star" with three legs
might signify the deaths of the three different lists [2;1], [3;1] and [4;
1] that all shared the same physical tail list [1].

Until I zoomed in, I hadn't noticed that most of the 3-vertex components are
of the form x->y<-z rather than x->y->z, which is interesting...


Yes, I thought that might be the case. :-)

itself)
some

I'll do so if I can find the time but my objective was more to inspire than
to research thoroughly. Hopefully someone else is in a better position than
I to generate data from real programs.

Cheers,
Jon.

Re: Visualizing clumps

Nick Barnes — 2011-11-17T09:14:27

The arrows in your diagram appear to be pointing in the 'wrong'
direction.  For instance, I'd expect a star-shaped clump to be
produced when a central node dies which refers to several leaf nodes.
But your diagram appears to show stars with leaves pointing to the
centre.

Common benchmarks are all terrible for assessing GCs.  Run a real
program.  When I was working on MLWorks, I always used to use one
phase of our overnight build (i.e. our compiler compiling the whole
system including itself) which as I recall allocated about 10 GB.  I
would expect that to produce some much larger and more interesting
clumps.

Nick B

Visualizing clumps

Jon Harrop — 2011-11-16T20:26:58

I just posted this blog article:

http://flyingfrogblog.blogspot.com/2011/11/what-is-your-garbage-collector.ht
ml

I used Mathematica to visualize the structure of the clumps (weakly
connected components) being collected by my mark region collector whilst
running a list-based n-queens solver. In this case, 84% of unreachable
connected components are isolated 2-element lists and only a handful have
interesting topologies.

I'm curious if anyone can think of a common benchmark that is likely to
produce more interesting garbage. :-)

Re: Doubling up pointers

Florian Weimer — 2011-11-15T19:49:45

* Jon Harrop:


Cheng, Blelloch, "A Parallel, Real-Time Garbage Collector" (1999/2000)
uses wide pointers and a global flip switch to get an atomic update of
part of the root set, without special hardware support.


Pizlo et al.'s STOPLESS collector does something like this, but they
keep the additional pointer copy around only during concurrent
compaction.

The LMAX disruptor

Jon Harrop — 2011-11-15T20:09:43

People here might find this interesting:

http://flyingfrogblog.blogspot.com/2011/11/lmax-disruptor-and-bakers-treadmi
ll.html

I reread a paper about a new data structure designed for low latency servers
and noticed that it is quite similar to Baker's Treadmill GC (1992). I'd be
very interested to hear how more recent improvements to Baker's Treadmill
might be used to improve upon the LMAX disruptor! :-)

Re: Divide and conquer GC algorithms

Andrew Shi-hwa Chen — 2011-11-14T01:50:25

Some use of the "autorelease pool" concept found in many Objective-C environments gives programmer-defined coarser-grained bulk decrements, commonly used so that you can have things similar to scopes where you do a retain (increment) when you know you're using something in a scope, and you also send it an "autorelease" which sets it up to receive a release (decrement) when exiting the scope. This way the decrements get batched up. (But there is overhead in maintaining this list-of-things-to-be-decremented.)

Since these autorelease pools, similar to scopes, are often nested in a stack-like manner, one could actually replace all release (decrement) messages with autorelease, and then do the batch decrementing and reclamation then. The issues are when there are complicated finalizers to be run, or, if the decrementing of one object yields more to be decremented because of what it references and so on, limiting the amount of granularity to only the set of objects that were sent the autorelease message and are n

Using bitmasks to accelerate marking

Jon Harrop — 2011-11-12T18:57:30

I'm just playing around with some toy GCs I've written in C++ that use an
instrumented list-based n-queens solver as an example mutator. The fastest
I've got so far is a kind of mark-region collector that allocates into a
region and uses two external bitvectors to track the mark bits and allocated
bits, respectively. Sweeping is then just a case of ANDing the two
bitvectors (as I described before).

I haven't profiled it at all but it occurs to me that I might be able to
accelerate the mark phase (which I assume is the bottleneck) significantly
by storing third bitvector where each bit is used to indicate whether the
first pointer in the corresponding heap block points to the heap block
immediately before it. A 2kB look up table could be used to find the length
of the chain of consecutive heap blocks reachable from the first one and
they could all be marked simultaneously using an OR. This is obviously
expected to be effective for my n-queens solver because it uses lots of
little immutable singly-linked list

Re: Divide and conquer GC algorithms

Jon Harrop — 2011-11-12T18:43:46

Yes, traditional reference counting is extremely fine-grained but what if it
could also handle coarser grains? For example, if values become unreachable
in clumps then it is surely valuable to be able to track the number of
references to either A or B in a pair (A, B) in order to deallocate both
simultaneously if they both die at the same time. There could be fewer
reference counts to increment and decrement and it would be possible to
reclaim multiple heap-allocated blocks in a single operation. It might even
be possible to replace the count of the number of direct references to each
value with a count of the number of values from which it is reachable...

reference
for
circular
dswise< at >cs.indiana.edu

Re: Divide and conquer GC algorithms

David S. Wise — 2011-11-12T15:26:28


Absent the intervening degrees of graularity but....
'Tis important to appreciate that, way down at or near each mutation,
reference counting is extremely granular and, therefore, remains
most interesting for supporting parallel processing.
And that is why---in the face of ubiquitous
"But it doesn't work for circular structures" dismissals---it is used every day
by each of us to sustain our persistent file systems (e.g. the Unix HFS).
d
====
David S. Wise +1(360)582-9233 ;  fax: +1(360)582-9233   dswise< at >cs.indiana.edu
Computer Science Emeritus, Indiana University
                    http://www.cs.indiana.edu/~dswise/

Re: Divide and conquer GC algorithms

David Chase — 2011-11-12T14:25:34

On 2011-11-12, at 7:31 AM, Jon Harrop wrote:



An inexact match for your question is the use of work stealing to parallelize and load-balance the work in some GCs.

http://scholar.google.com/scholar?q=work+stealing+GC&hl=en&as_sdt=0&as_vis=1&oi=scholart

"CH Flood" is "Christine", one door down at work :-).  Working less on GC now, more on making Fortress go faster.

Trying to shuffle stuff around to enhance locality is a general plan.

David

Divide and conquer GC algorithms

Jon Harrop — 2011-11-12T12:31:58

Reading Richard's excellent book, I was surprised to observe that none of
the major GC algorithms seem to be hierarchical. Some algorithms like the
Train collector, Beltway and Immix amortize costs by grouping heap-allocated
blocks together but they don't seem to use trees to gradually refine the
granularity.

I've also been looking at "dynamic" graph algorithms for the first time.
These algorithms allow a small change in the graph (add/remove one
edge/vertex) to be converted into a small change in their output. The
concept of a topology tree, a data structure used in some dynamic graph
algorithms, caught my attention because this conveys information about the
topology of a graph. For example, you might be able to determine quickly
that a 1/4 partition of the heap contained pointers to another 1/4 partition
but not the other way around so there were no cycles spanning the two
partitions. Could a GC use a topology tree to do some of its work in O(log
n) time? Furthermore, what if a dynamic graph algorithm wer

Re: Doubling up pointers

Jon Harrop — 2011-11-12T12:09:29

Right, that's exactly what I was thinking. I'm guessing the transition could
occur as a gradual phase transition (aka ragged barrier) in order to avoid
gross synchronization. Perhaps the first phase would write to the left-hand
pointer, the second phase would have mutators write to both left- and
right-hand pointers while the GC threads copied every left-hand pointer over
its right-hand pointer and the third phase would have mutators write just to
right-hand pointers. Once the third phase is reached the left-hand pointers
in the heap contain a snapshot of its topology. Note that this write barrier
would only be expensive during the second phase: in the first and third
phases it is just a single pointer write. Moreover, my measurements indicate
that the .NET write barriers is ~5x slower than a single pointer write so
I'd expect this double-write barrier to be a relatively fast write barrier
even in the worst case. OCaml's write barrier is even slower than .NET's (it
is a functional language). The main disadva

Review: The Garbage Collection Handbook

Jon Harrop — 2011-11-12T11:58:09

I finally found the time to read Richard Jones' new book and have posted my
review on Amazon:

http://www.amazon.co.uk/review/R2UYL7W7WG10K0/

"This book gives a thorough and detailed review of modern garbage collection
algorithms including the tricky subjects of parallel, concurrent and
real-time collectors and yet remains comprehensible throughout. Moreover,
the information contained within is presented as a fascinating narrative
littered with interesting observations and insightful remarks, making this
book a real gem.

Anyone developing software built upon a garbage collector would do well to
brush up on the theory that underlies this core subject and there is no
better way than to read this excellent book!"

John McCarthy

Hudson, Rick — 2011-10-26T14:41:35

http://www.nytimes.com/2011/10/26/science/26mccarthy.html

For those who have not yet heard, Professor John McCarthy, the inventor of garbage collection, passed yesterday.

Thoughts are with his family.