runtime: replace free list with direct bitmap allocation

[aclements]

All current releases of Go up to and including Go 1.5 use a mark-sweep garbage collector. As of Go 1.5, this works by alternating between a mostly-concurrent mark phase and a concurrent sweep phase. The mark phase finds all reachable objects and marks them, leaving all unreachable objects unmarked. The sweep phase walks through the entire heap, finds all unmarked objects, and adds them to free lists, which the allocator in turn uses to allocate new objects.

However, this sweep phase is, in a sense, redundant. It primarily transforms one representation of the free heap—the mark bits—into another representation of the free heap—the free lists. Not only does this take time, but the free list representation is unfriendly to modern CPUs since it is not very cacheable and accesses to it are hard to predict. Furthermore, the current mark representation is also cache-unfriendly, which adds even more to the cost of sweeping. All told, typical Go programs spend about 5% of their CPU time in the sweeper or in cache misses induced by the free list representation.

I propose eliminating the sweeper by foregoing the free list representation entirely and finding free objects directly using the mark bitmap. This can be done efficiently using a dense representation for mark bits separate from the current heap bitmap that enables fast scanning and clearing. This separate mark bitmap will also make it easy to maintain multiple mark bitmaps simultaneously, which is important for future GC improvements.

[aclements]

I've uploaded the design doc CL at https://golang.org/cl/15210

@RLH

[gopherbot]

CL https://golang.org/cl/15210 mentions this issue.

[aclements]

The design doc can now be viewed in its native habitat at https://github.com/golang/proposal/blob/master/design/12800-sweep-free-alloc.md

[Dragomir-Ivanov]

@aclements Hi Austin, what is the plan for this? Is there will be proof of concept implementation. E.g. modify the GC, pass all the tests, etc. Thanks for all the work.

[RLH]

We have a partial prototype that still has bugs and is laden with
validation code. It is planned for 1.6, which means the CL will need to be
available before the end of the month. No numbers yet. It is going to
happen for 1.6.

On Fri, Oct 2, 2015 at 5:54 PM, Dragomir Ivanov notifications@github.com
wrote:

@aclements https://github.com/aclements Hi Austin, what is the plan for
this? Is there will be proof of concept implementation. E.g. modify the GC,
pass all the tests, etc. Thanks for all the work.

—
Reply to this email directly or view it on GitHub
#12800 (comment).

[gopherbot]

CL https://golang.org/cl/15560 mentions this issue.

[rsc]

Accepting proposal. Certainly this is fine to implement and see how it works.

[aclements]

Bitmap allocation was merged in April with commit 56b5491 (plus a few follow-ups after the merge).