News for hackers. Stuff that matters.
Re:Modern garbage collection by agumonkey on Tuesday December 20, 2016 @08:53AM (#13219726)
I'd love to know about other GC schemes. Between no GC and whole VM GC. By type GC, localized sub tree GC.

edit: thank you all for your answers, much appreciatedly

Re:Modern garbage collection by mike_hearn on Tuesday December 20, 2016 @11:45AM (#13221452)
Check out Singularity. It was a research effort from Microsoft Research to build a whole OS in a modified .NET

Singularity was a single address space OS, thus there were no "processes" in a traditional sense. They still had a notion of isolated spaces though partly to allow different heaps to be GCd independently, and to use different GC algorithms (with different barriers) exactly due to the lack of a one-size-fits-all approach. Messaging between these process-like-things was done by moving objects onto a "transfer heap" and back again, which boiled down to just a simple pointer write. There were no syscalls.

A very nice architecture, from a theoretical perspective. However it's not clear to me that for standard desktop-sized machines you really need segmented GC spaces these days. With an incremental collector you can probably get pause times in the milliseconds range for a 32GB heap and I guess 32GB is as much RAM as you need on a Pro-level machine. For servers of course you go bigger.

One interesting GC algorithm I came across did thread-local collections. Objects were tracked with write barriers to discover when they became 'globally reachable' and moved to a global heap. Threads could stop independently whilst others continued running to collect their thread local heaps. That opens up the possibility in desktop/mobile apps of having a main thread that's doing an animation of some kind in a low-garbage way, whilst the background thread does work as quickly as possible, with the background thread collecting independently whilst the animation thread still runs.

Re:Modern garbage collection by micmus on Tuesday December 20, 2016 @09:20AM (#13219966)
Erlang has a per-process GC - each Erlang process has it's own heap and it's own garbage collector. There's no VM-wide GC. This usually means the GC pauses apply only to a small part of your system, while the other parts are running completely normally. There's a good article that describes it in depth: https://www.erlang-solutions.com/blog/erlang-19-0-garbage-co...
Re:Modern garbage collection by noss on Tuesday December 20, 2016 @11:30AM (#13221281)
Also if you have a lot of data you use an ets table which is more or less an in-process but off-gc-heap key-value database.
Re:Modern garbage collection by staticassertion on Tuesday December 20, 2016 @12:08PM (#13221686)
Thanks, I've been wondering how Erlang does GC.
Re:Modern garbage collection by AstralStorm on Tuesday December 20, 2016 @12:24PM (#13221829)
Of course, the cost is extra heap fragmentation.
Re:Modern garbage collection by dfox on Tuesday December 20, 2016 @12:36PM (#13221974)
In Erlang case, that is not so much of a problem as most allocated objects have essentially same size. On the other hand this causes another problem that GC's and allocators in Erlang VMs tend to have enormous overhead because most most GC'd objects are very small with sizes comparable to per-object GC overhead.
Re:Modern garbage collection by agumonkey on Tuesday December 20, 2016 @05:54PM (#13225085)
I joked once that in lisp, a vast majority of memory allocation are basically malloc(2). I wondered if it made fragmentation irrelevant.
Re:Modern garbage collection by mpweiher on Tuesday December 20, 2016 @11:57AM (#13221582)
You might be interested in:

"A Unified Theory of Garbage Collection"

https://pdfs.semanticscholar.org/91dc/a25f8cb407fc68218f7d5a...

Basic idea is that tracing and reference counting are duals of each other. Reference counting finds dead objects, tracing finds live objects. Optimized variants of each of these tend to approach the other side.

Re:Modern garbage collection by twic on Tuesday December 20, 2016 @10:10AM (#13220418)
I used to idly browse papers from programming language conferences, and there was often interesting GC stuff. PLDI is probably your bet bet - here's 2016:

http://dl.acm.org/citation.cfm?id=2908080&picked=prox

When there were two GC papers:

Idle time garbage collection scheduling - "We implemented idle time garbage collection scheduling in V8, an open-source, production JavaScript virtual machine running within Chrome. We present performance results on various benchmarks running popular webpages and show that idle time garbage collection scheduling can significantly improve latency and memory consumption."

Assessing the limits of program-specific garbage collection performance - "We demonstrate that there is considerable promise to reduce garbage collection costs by developing program-specific collection policies."

Or going back to 2012:

And then there were none: a stall-free real-time garbage collector for reconfigurable hardware - "We present the first implementation of a complete garbage collector in hardware (as opposed to previous "hardware-assist" techniques), using an FPGA and its on-chip memory. Using a completely concurrent snapshot algorithm, it provides single-cycle access to the heap, and never stalls the mutator for even a single cycle, achieving a deterministic mutator utilization (MMU) of 100%."

That's by David Bacon, one of the runtime implementation greats, who has been after low-pause GC for years. A golden oldie from him is:

A Pure Reference Counting Garbage Collector - "When processor or memory resources are limited, the Recycler usually runs at about 90% of the speed of the mark-and-sweep collector. However, with an extra processor to run collection and with a moderate amount of memory headroom, the Recycler is able to operate without ever blocking the mutators and achieves a maximum measured mutator delay of only 2.6 milliseconds for our benchmarks. End-to-end execution time is usually within 5%."

As for by-type GC, i remember reading a paper years (decades?) ago, perhaps from Microsoft, where they'd tried putting every class in its own region, the idea being that when you wanted to collect some particular region, you could exploit your knowledge of types and their fields to only scan regions which could possibly have pointers to it (eg to collect BlogPost, you have to scan User). Clever, but didn't work well in practice, because so much garbage is lists or strings that can be pointed to from a lot of places.

Re:Modern garbage collection by scott_s on Tuesday December 20, 2016 @10:28AM (#13220608)
ISMM, http://dl.acm.org/event.cfm?id=RE149, is also likely to have papers on garbage collection. The table of contents from 2016: http://dl.acm.org/citation.cfm?id=2926697
Re:Modern garbage collection by twic on Tuesday December 20, 2016 @07:36PM (#13225759)
Nice! There's a paper in there called 'Block-free concurrent GC: stack scanning and copying' which opens by claiming that "on-the-fly Garbage Collectors (GCs) are the state-of-the-art concurrent GC algorithms today". I'd never heard of on-the-fly GC, so i've learned something!

However, on googling, i find that Edsger Dijkstra wrote about it in 1975:

https://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/E...

Hey, maybe that's old enough that Go can use it?

Re:Modern garbage collection by staticassertion on Tuesday December 20, 2016 @12:11PM (#13221713)
I believe MS does in fact use a typed heap in IE, but for security reasons (some sort of UAF mitigation iirc).
Re:Modern garbage collection by osi on Tuesday December 20, 2016 @09:19AM (#13219959)
Look at what Erlang's BEAM VM does. It has per-"process" heaps iirc.
Re:Modern garbage collection by me2i81 on Tuesday December 20, 2016 @02:41PM (#13223231)
Take a look at The Garbage Collection Handbook by Jones et. al. ISBN-13 is 978-1420082791.