Garbage Collector

[antongulenko]

Hello llgo contributors,

I am joining the team and I would like to look into adding garbage collection to the llgo runtime.
This issue is intended for discussions related to that.
I am no expert in this field, so please correct me whenever necessary!!

I will try to define some requirements for an llgo garbage collector.

Go needs very close integration with native programs. This renders several garbage collection techniques unusable.

• pointers cannot be tagged to be distinguished from integers.
• memory objects should be "pure data", so no headers containing GC metadata like reference counts or tag bits.
• allocated data should probably not be moved in case native libraries are still holding references.

Are there any plans to make llgo compatible with other Go compilers?
I.e. linking a library compiled with llgo into another runtime, or vice versa.
I think this could be quite interesting.
In any case, the garbage collector should be able to coexist with other garbage collectors in the same address space.
That's not such a hard requirement anyways, as long as they all use malloc.

The garbage collector should be portable, at least in the first version(s).
I do not know how to implement root scanning in a machine independent manner. Fortunately there's enough research and implementations available.

The garbage collector has to deal with concurrent and parallel programs.
I think this is a pretty advanced requirement, and should be at least implemented very simply at first.

This means, the garbage collector would be:

• not reference-counting, not copying, not generational
• either conservative (not precise) or relying on runtime information about the data layout
  • From the language perspective, Go allows a precise collector.
    Especially since information about the data types has to be available for the runtime package.
  • there are also hybrid models that treat certain data (like []byte) specially

... That's what I can come up with right now.

I would proceed with the following in order to get some more insights. Let me know what you think.

• Take the Böhm conservative collector (http://www.hpl.hp.com/personal/Hans_Boehm/gc/) and just attach it to llgo.
  This collector is stable, portable and has been used by many compiler projects.
  The main selling point is that it can just be attached to any runtime by linking malloc-calls to GC_malloc and turning free-calls into no-ops.
  It seems highly customizable. Even though it's conservative, it is possible to optionally insert some type-information.
  There are considerations about parallel programs, including locks and how/where to use them.
  Also, there are some pretty sophisticated techniques to avoid confusing arbitrary data for pointers.
  I think a collector like this could even turn out to be completely sufficient for llgo, at least for quite a while.
  I read about a benchmark in a paper today that stated the average heap overhead of a conservative collector is in the 10-12% range.
• Write some kind of memory benchmark program. Maybe somebody can point me to one?
  It just should keep allocating random data objects and doing random stuff to them.
  I would then try to output some stats about the memory state, like total working set of the process,
  memory allocated by the collector, memory allocated by the program, leaked memory, etc.
  Then plot that over time, like here:
• See how the Böhm collector performs.
• Investigate LLVM shadow-stack functionality.
  That should allow us to implement our own collector in a very portable way.
  It's supposed to be pretty slow, though.
  It could still be used to experiment with different approaches.
• I think once these things are in place we can experiment with different approaches, plug other gc runtimes into llgo, and so on.

I have not investigated the runtimes of GC and gccgo yet.
Here are some facts about the GC collector:
http://stackoverflow.com/questions/7823725/what-kind-of-garbage-collection-does-go-use
The C-code for their runtime package looks pretty huge and sophisticated, so I think it would be hard or impossible to extract and reuse that part... Might be worth checking out, though.

Cheers,
Anton

[axw]

Thanks for writing this up, Anton. I just wanted to add one thing: it's possible that we'll later move to using libgo for the runtime, in which case the gc garbage collector could be used. Identifying stack roots and so on would still be using LLVM, of course.

[antongulenko]

Is libgo designed to be reused? I read on the golang-nuts that it's tightly coupled to the gofrontend part of gccgo in some parts.

[axw]

Is libgo designed to be reused? I read on the golang-nuts that it's tightly coupled to the gofrontend part of gccgo in some parts.

I don't know, nor do I know how feasible it is; it just seems like the most practical of any possible reuse. Tight coupling is to be expected for Go, since quite a lot is done in the runtime. This doesn't necessarily rule out reuse, it just means llgo would have to emit code in the same way that gccgo does.

[antongulenko]

Hi,

Here's a little status report.
As described, I plugged the Böhm collector into llvm. The source-code changes necessary for this are minimal, as predicted.
Basically I just just inserted 6 characters (two times 'GC_') into the files memory.ll and memory.go.
That replaces the usage of the system malloc/free with GC_malloc and GC_free.
To link an llgo output against the GC library, I just built the library manually and added the linker option to llgo-build.

What would be the best way to handle this? Put the whole GC source tree somewhere under pkg/runtime/ and let llgo-build compile it?
I'll check how straight-forward the build-process of that thing is, but it might need special compiler-flags and such.
Would that be possible?
I would probably make this thing optional (compiler flag for llgo-build). What do you think?

I wrote a small program to test this. It just allocates a lot of []int with random sizes, but keeps only a certain number of those around in a local [][]int.
Old references are overwritten. It does this until it allocates a gigabyte or so.
I execute the program (called test) the following way:

/usr/bin/time -f 'Max resident set size: %M' `pwd`/test -mem 500 -rand -randsize

This output the maximum number of KB used throughout the lifetime of the program.
It's a primitive method, but if the collector is doing it's job we should see something significantly lower than 1 gigabyte.

And indeed:

Allocated 12704 buffers, total storage: 524,311,152.
working set 20,480,000.
Max resident set size: 54640

The program has allocated 524 MB of []int, but the program memory has only grown to 55 MB.
It also shows that in average 20 MB worth of []int have been kept around at the same time ("working set" reported by the test program).
This means that the collector allocates approximately two times the storage that is actually necessary.

I also noticed that the collector does leak memory.
I am not sure about the cause, but if I run the program for a longer time, it reports higher 'Max resident set sizes' in the end:

Allocated 25519 buffers, total storage: 1,048,603,264.
working set 20,480,000.
Max resident set size: 60156

You can also monitor this using:

watch -n1 ps -C test -o cmd,args,%cpu,%mem,size

I don't know if the leak becomes constant after a while or if it will keep growing. I will try to investigate that.

That's all so far. Let me know what you think about pulling this in.
Cheers,
Anton

[antongulenko]

Can't figure out how to attach a non-image file to a comment here... I was going to attach the test program, so just let me know if you want take a look at it.
Also - I have not run it with the original llgo-build yet, because removing the GC requires re-running llgo-dist. I'll update on this.

[antongulenko]

Hello,

Sorry for the lengthy update messages, I will keep this one short.
I think I added GC support for llgo in a satisfactory way.
I will explain what I did in the pull request. But I would like you to have a look before that, because I am not quite sure about one thing.
You can see the changes over at my fork:
antongulenko/llgo@axw:master...master
The only issue I see is that I had to check in copies of two other github repositories (the GC implementation).
The problem is that go get does not check out submodules recursively. And for the GC to be integrated nicely with the runtime, its sources have to be in the pkg/runtime directory.
This way, I managed to compile it into the runtime quite nicely (just llgo-dist), and make it optional at link-time with the switch -gc to llgo-build.
What do you think? If nothing else, the 100k additions would look weird in the project stats...

Cheers,
Anton

[axw]

@antongulenko Thanks for writing up your findings. Sorry it took me a while to reply, I've been pretty tired after the flight back home.

I had a chat with some of the core Go developers while I was in CA, and came to the conclusion that libgo is the only sensible way to go forward with llgo. We can continue writing a new runtime, and it might even work, but it's unlikely to be as high quality as libgo. I originally started this project as a learning exercise, but it's outgrown that; I want it to be something useful to everyone, and I don't have the time or frankly the knowledge to do all that myself. It's great that you're offering help, but I still think the amount of work is going to be overwhelming and not really that useful to duplicate. So, I think perhaps we should refocus.

Your changes look fine, but they would become redundant when moving to libgo. I don't think it makes sense to merge it in, especially given that the master branch is not likely to see any more updates until the ssa work is merged over.

If you're keen, there are a few related things you could look into:

• What needs to be done to get libgo integrated in general. Anything other than dealing with the plan9 C?
• What changes are required in llgo to support garbage collection via libgo.
• What needs to be done with LLVM specifically to get precise garbage collection working.

I intend to keep working on ssa bits for now. Once I've got that working as well as or better than the master branch, I'll merge over and then start work on ripping out the current runtime.

[tmc]

@axw could you elaborate a bit on the future plans? I wonder if via build flags or a branch a pure-go runtime could continue to exist as an option.

[axw]

@tmc What's the goal?

A pure-Go runtime has several problems:

• at some point you need to escape from Go, to do system calls.
• some low-level things are awkward to do in Go, where you don't want garbage collection to get involved. pkg/unsafe can get you there, but then you may as well be writing C.

Some parts of the runtime could perhaps be written in Go, but I don't think it's worth writing a majority of it in Go.

Having said that: the runtime package can be thought of as an ordinary package with a (currently undocumented) API required by the compiler. With that in mind, one could potentially maintain a separate runtime that implements that API.

But anyway, I am interested to know: what would be the primary goal of having one? Ease of hacking? Exercising the compiler? Both noble goals, I think, but not instead of a good runtime, and not instead of sleeping ;)

[raichu]

gc compilers are indeed headed into the pure-go direction:
http://golang.org/s/go13compiler (also http://talks.golang.org/2014/go1.3.slide#19)
As for reasoning: http://talks.golang.org/2014/go1.3.slide#21
libgo might follow this move.

[axw]

@raichu Indeed, and this is very good news! However, the compiler and runtime are separate things.

I expect parts of the runtime will be replaced with Go over time, however it remains be seen whether all of it will be. I would love for it to be pure Go, save for system calls and so on which will have to be in assembler.

[raichu]

Indeed, but I actually mean both the compiler set and runtime package. From the first link I mentioned above:

Package runtime. Most of the runtime is written in C, for many of the same reasons that the Go compiler is written in C. However, the runtime is much smaller than the compilers and it is already written in a mix of Go and C. It is plausible to convert the C to Go one piece at a time. The major pieces are the scheduler, the garbage collector, the hash map implementation, and the channel implementation. (The fine mixing of Go and C is possible here because the C is compiled with 6c, not gcc.)