www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Concurrent GC (for Windows)

reply Rainer Schuetze <r.sagitario gmx.de> writes:
Hi,

more GC talk: the last couple of days, I've been experimenting with 
implementing a concurrent GC on Windows inspired by Leandros CDGC. 
Here's a report on my experiments:

http://rainers.github.io/visuald/druntime/concurrentgc.html

tl;dr: there is a working(?) partially concurrent GC here: 
https://github.com/rainers/druntime/tree/concurrent_gc2
but it eats a whole lot of memory.

Rainer
Jun 03 2014
next sibling parent reply Benjamin Thaut <code benjamin-thaut.de> writes:
Am 03.06.2014 09:35, schrieb Rainer Schuetze:
 Hi,

 more GC talk: the last couple of days, I've been experimenting with
 implementing a concurrent GC on Windows inspired by Leandros CDGC.
 Here's a report on my experiments:

 http://rainers.github.io/visuald/druntime/concurrentgc.html

 tl;dr: there is a working(?) partially concurrent GC here:
 https://github.com/rainers/druntime/tree/concurrent_gc2
 but it eats a whole lot of memory.

 Rainer

This sounds quite promising. Did you think about using a write barrier instead of doing the chech per page? Because the way you propose will mean, that all writes, no matter if relevant for the GC or not, will cause the GC to reconsider the page. If we implement a write barrier into the front end that only gets called when a write through a pointer to a pointer happens, the GC could only rescan memory blocks that actually have changed pointers. Also the GC might be able to remember the old pointer value before the write is execued resulting in a consitent snapshot of the heap, which would eliminate the need to rescan after the background thread is finished. Kind Regards Benjamin Thaut
Jun 03 2014
parent reply Rainer Schuetze <r.sagitario gmx.de> writes:
On 04.06.2014 07:44, Benjamin Thaut wrote:
 Am 03.06.2014 09:35, schrieb Rainer Schuetze:
 Hi,

 more GC talk: the last couple of days, I've been experimenting with
 implementing a concurrent GC on Windows inspired by Leandros CDGC.
 Here's a report on my experiments:

 http://rainers.github.io/visuald/druntime/concurrentgc.html

 tl;dr: there is a working(?) partially concurrent GC here:
 https://github.com/rainers/druntime/tree/concurrent_gc2
 but it eats a whole lot of memory.

 Rainer

This sounds quite promising. Did you think about using a write barrier instead of doing the chech per page? Because the way you propose will mean, that all writes, no matter if relevant for the GC or not, will cause the GC to reconsider the page. If we implement a write barrier into the front end that only gets called when a write through a pointer to a pointer happens, the GC could only rescan memory blocks that actually have changed pointers. Also the GC might be able to remember the old pointer value before the write is execued resulting in a consitent snapshot of the heap, which would eliminate the need to rescan after the background thread is finished.

Yes, write barriers are a good addition to this, but is way more difficult to implement and will meet more resistance from Walter. It's still something I'd like to look into.
Jun 04 2014
parent Benjamin Thaut <code benjamin-thaut.de> writes:
Am 04.06.2014 22:26, schrieb Rainer Schuetze:
 Yes, write barriers are a good addition to this, but is way more
 difficult to implement and will meet more resistance from Walter. It's
 still something I'd like to look into.

I assume they are hard to implement because the backend no longer has type information when generating the writes? I remember that Walter stated a few weeks ago that he considered implementing write barriers.
Jun 04 2014
prev sibling next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 03/06/14 09:35, Rainer Schuetze wrote:
 Hi,

 more GC talk: the last couple of days, I've been experimenting with
 implementing a concurrent GC on Windows inspired by Leandros CDGC.
 Here's a report on my experiments:

 http://rainers.github.io/visuald/druntime/concurrentgc.html

 tl;dr: there is a working(?) partially concurrent GC here:
 https://github.com/rainers/druntime/tree/concurrent_gc2
 but it eats a whole lot of memory.

How does other GC's handle these memory problems? I'm thinking of Java and C#, or do they have some advantage of being run in a virtual machine? -- /Jacob Carlborg
Jun 03 2014
next sibling parent reply "Paulo Pinto" <pjmlp progtools.org> writes:
On Wednesday, 4 June 2014 at 06:51:04 UTC, Jacob Carlborg wrote:
 On 03/06/14 09:35, Rainer Schuetze wrote:
 Hi,

 more GC talk: the last couple of days, I've been experimenting 
 with
 implementing a concurrent GC on Windows inspired by Leandros 
 CDGC.
 Here's a report on my experiments:

 http://rainers.github.io/visuald/druntime/concurrentgc.html

 tl;dr: there is a working(?) partially concurrent GC here:
 https://github.com/rainers/druntime/tree/concurrent_gc2
 but it eats a whole lot of memory.

How does other GC's handle these memory problems? I'm thinking of Java and C#, or do they have some advantage of being run in a virtual machine?

Note that there are native compilers for Java and C#.
Jun 04 2014
parent Jacob Carlborg <doob me.com> writes:
On 2014-06-04 09:14, Paulo Pinto wrote:

 Note that there are native compilers for Java and C#.

My question still remains :) -- /Jacob Carlborg
Jun 04 2014
prev sibling parent reply Rainer Schuetze <r.sagitario gmx.de> writes:
On 04.06.2014 08:51, Jacob Carlborg wrote:
 On 03/06/14 09:35, Rainer Schuetze wrote:
 Hi,

 more GC talk: the last couple of days, I've been experimenting with
 implementing a concurrent GC on Windows inspired by Leandros CDGC.
 Here's a report on my experiments:

 http://rainers.github.io/visuald/druntime/concurrentgc.html

 tl;dr: there is a working(?) partially concurrent GC here:
 https://github.com/rainers/druntime/tree/concurrent_gc2
 but it eats a whole lot of memory.

How does other GC's handle these memory problems? I'm thinking of Java and C#, or do they have some advantage of being run in a virtual machine?

All more sophisticated GCs have write or read barriers. That makes it much easier to keep track of modifications during concurrent collection. One reason for the huge memory foot print is that the application is allowed to continue to allocate during collection, but it will do this by getting more memory from the OS. It needs to be somehow throttled to avoid going too far with this. Most of the remaining pause time is sweeping garbage. I think about deferring sweeping into allocations by running finalizers just before reusing the memory for another object. This can throttle allocations a bit while at the same time reduce pauses.
Jun 04 2014
next sibling parent Jacob Carlborg <doob me.com> writes:
On 2014-06-04 22:37, Rainer Schuetze wrote:

 All more sophisticated GCs have write or read barriers. That makes it
 much easier to keep track of modifications during concurrent collection.

Right, now I start to remember. -- /Jacob Carlborg
Jun 05 2014
prev sibling parent reply Martin Nowak <code dawg.eu> writes:
On 06/04/2014 10:37 PM, Rainer Schuetze wrote:
 Most of the remaining pause time is sweeping garbage. I think about
 deferring sweeping into allocations by running finalizers just before
 reusing the memory for another object. This can throttle allocations a
 bit while at the same time reduce pauses.

That's pausing the thread which triggered the collection, right? Other threads don't need to wait for sweeping. Dividing the cost to run finalizers among many allocations is a charming idea.
Jun 15 2014
parent Rainer Schuetze <r.sagitario gmx.de> writes:
On 15.06.2014 23:30, Martin Nowak wrote:
 On 06/04/2014 10:37 PM, Rainer Schuetze wrote:
 Most of the remaining pause time is sweeping garbage. I think about
 deferring sweeping into allocations by running finalizers just before
 reusing the memory for another object. This can throttle allocations a
 bit while at the same time reduce pauses.

That's pausing the thread which triggered the collection, right? Other threads don't need to wait for sweeping.

Yes, the world is not stopped during sweeping. The GC lock still blocks any thread that tries to allocate, though.
 Dividing the cost to run finalizers among many allocations is a charming
 idea.

Another nice property: If memory is recycled during malloc, you can run the finalizers without the GC lock held just before returning, so there are less restrictions on what can happen in a destructor.
Jun 15 2014
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
03-Jun-2014 11:35, Rainer Schuetze пишет:
 Hi,

 more GC talk: the last couple of days, I've been experimenting with
 implementing a concurrent GC on Windows inspired by Leandros CDGC.
 Here's a report on my experiments:

 http://rainers.github.io/visuald/druntime/concurrentgc.html

 tl;dr: there is a working(?) partially concurrent GC here:
 https://github.com/rainers/druntime/tree/concurrent_gc2
 but it eats a whole lot of memory.

I'm not sure if how it would perform but what about the following idea for COW snapshotting. 1. Don't use the separate process and shared view, use background thread. 2. Allocate heap space with MapViewOfFile, but private not shared. During collection, creating a snapshot (during stop the world) as: 1. Make a new, read-write view of heap with MapViewOfFile, this is what background thread will use to scan memory. 2. Save base address of the original view, and unmap it. 3. MapViewOfFileEx with MAP_COPY and the old base address (that gives us back the same heap but in CoW mode). ... move on with application and let background thread do the marking. Once marking is done, do stop the world and: 1. VirtualQuery (or QueryWorkingSetEx) over the application's CoW view of the heap. See the ranges of pages that have flipped to PAGE_READWRITE, those are the one modified and duplicated. If new allocation are served from it then it will include newly allocated stuff. 2. Copy these ranges of pages over to the normal read-write view. 3. Close CoW mapping (thereby freeing duplicates) and remap it again as r-w view on the same address with MapViewOfFileEx. I wasn't able to get QueryWorkingSetEx to behave but I believe it must be a better way then VirtualQuery every page-range to death. See the sketch of the idea here : https://gist.github.com/DmitryOlshansky/5e32057e047425480f0e
 Rainer

-- Dmitry Olshansky
Jun 11 2014
parent reply Rainer Schuetze <r.sagitario gmx.de> writes:
On 11.06.2014 18:59, Dmitry Olshansky wrote:
 03-Jun-2014 11:35, Rainer Schuetze пишет:
 Hi,

 more GC talk: the last couple of days, I've been experimenting with
 implementing a concurrent GC on Windows inspired by Leandros CDGC.
 Here's a report on my experiments:

 http://rainers.github.io/visuald/druntime/concurrentgc.html

 tl;dr: there is a working(?) partially concurrent GC here:
 https://github.com/rainers/druntime/tree/concurrent_gc2
 but it eats a whole lot of memory.

I'm not sure if how it would perform but what about the following idea for COW snapshotting. 1. Don't use the separate process and shared view, use background thread. 2. Allocate heap space with MapViewOfFile, but private not shared. During collection, creating a snapshot (during stop the world) as: 1. Make a new, read-write view of heap with MapViewOfFile, this is what background thread will use to scan memory. 2. Save base address of the original view, and unmap it. 3. MapViewOfFileEx with MAP_COPY and the old base address (that gives us back the same heap but in CoW mode). .... move on with application and let background thread do the marking. Once marking is done, do stop the world and: 1. VirtualQuery (or QueryWorkingSetEx) over the application's CoW view of the heap. See the ranges of pages that have flipped to PAGE_READWRITE, those are the one modified and duplicated. If new allocation are served from it then it will include newly allocated stuff. 2. Copy these ranges of pages over to the normal read-write view. 3. Close CoW mapping (thereby freeing duplicates) and remap it again as r-w view on the same address with MapViewOfFileEx. I wasn't able to get QueryWorkingSetEx to behave but I believe it must be a better way then VirtualQuery every page-range to death. See the sketch of the idea here : https://gist.github.com/DmitryOlshansky/5e32057e047425480f0e

Cool stuff! I remember trying something similar, but IIRC forcing the same address with MapViewOfFile somehow failed (maybe this was across processes). I tried your version on both Win32 and Win64 successfully, though. I implemented the QueryWorkingSetEx version like this (you need a converted psapi.lib for Win32): enum PAGES = 512; //SIZE / 4096; PSAPI_WORKING_SET_EX_INFORMATION[PAGES] info; foreach(i, ref inf; info) inf.VirtualAddress = heap + i * 4096; if (!QueryWorkingSetEx(GetCurrentProcess(), info.ptr, info.sizeof)) throw new Exception(format("Could not query info (%d).\n", GetLastError())); foreach(i, ref inf; info) writefln("flags page %d: %x", i, inf.VirtualAttributes); and you can check the "shared" field to get copied pages. This function is not supported on XP, though. A short benchmark shows that VirtualQuery needs 55/42 ms for your test on Win32/Win64 on my mobile i7, while QueryWorkingSetEx takes about 17 ms for both. If I add the actual copy into heap2 (i.e. every fourth page of 512 MB is copied), I get 80-90 ms more. The numbers are not great, but I guess the usual memory usage and number of modified pages will be much lower. I'll see if I can integrate this into the concurrent implementation.
Jun 11 2014
next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
12-Jun-2014 10:34, Rainer Schuetze пишет:
 On 11.06.2014 18:59, Dmitry Olshansky wrote:
 03-Jun-2014 11:35, Rainer Schuetze пишет:
 Hi,

 more GC talk: the last couple of days, I've been experimenting with
 implementing a concurrent GC on Windows inspired by Leandros CDGC.
 Here's a report on my experiments:

 http://rainers.github.io/visuald/druntime/concurrentgc.html



 See the sketch of the idea here :
 https://gist.github.com/DmitryOlshansky/5e32057e047425480f0e

Cool stuff! I remember trying something similar, but IIRC forcing the same address with MapViewOfFile somehow failed (maybe this was across processes). I tried your version on both Win32 and Win64 successfully, though.

 I implemented the QueryWorkingSetEx version like this (you need a
 converted psapi.lib for Win32):

Yes, exactly, but I forgot the recipe to convert COFF/OMF import libraries.
 enum PAGES = 512; //SIZE / 4096;
 PSAPI_WORKING_SET_EX_INFORMATION[PAGES] info;
 foreach(i, ref inf; info)
      inf.VirtualAddress = heap + i * 4096;
 if (!QueryWorkingSetEx(GetCurrentProcess(), info.ptr, info.sizeof))
      throw new Exception(format("Could not query info (%d).\n",
 GetLastError()));

 foreach(i, ref inf; info)
      writefln("flags page %d: %x", i, inf.VirtualAttributes);


 and you can check the "shared" field to get copied pages.

 This function
 is not supported on XP, though.

I wouldn't worry about it, it's not like XP users are growing in numbers. Also it looks like only 64bit version is good to go, as on 32bit it would reduce usable memory in half.
 A short benchmark shows that VirtualQuery needs 55/42 ms for your test
 on Win32/Win64 on my mobile i7, while QueryWorkingSetEx takes about 17
 ms for both.

Seems in line with my measurements. Strictly speaking 1/2 of pages, interleaved should give the estimate of the worst case. Together with remapping (freeing duplicated pages) It doesn't go beyond 250ms on 640Mb of heap.
 If I add the actual copy into heap2 (i.e. every fourth page of 512 MB is
 copied), I get 80-90 ms more.

Aye... this is a lot. Also for me it turns out that unmapping CoW view at the last step takes the most of time. It might help to split the full heap into multiple views. Also using VirtualProtect during the first step - turning a mapping into CoW one is faster then unmap/map (by factor of 2). One thing that may help is saving a pointer to the end of used heap at the moment of scan, then remaping only this portion as COW. Last issue I see is adjustment of pointers - in a GC, the mapped view is mapped at new address so it would need a fixup them during scanning.
 The numbers are not great, but I guess the usual memory usage and number
 of modified pages will be much lower. I'll see if I can integrate this
 into the concurrent implementation.

Wish you luck, I'm still not sure if it will help. -- Dmitry Olshansky
Jun 12 2014
parent reply Rainer Schuetze <r.sagitario gmx.de> writes:
On 13.06.2014 02:38, Dmitry Olshansky wrote:
 12-Jun-2014 10:34, Rainer Schuetze пишет:
 I implemented the QueryWorkingSetEx version like this (you need a
 converted psapi.lib for Win32):

Yes, exactly, but I forgot the recipe to convert COFF/OMF import libraries.

Grab coffimplib.exe.
 This function
 is not supported on XP, though.

I wouldn't worry about it, it's not like XP users are growing in numbers. Also it looks like only 64bit version is good to go, as on 32bit it would reduce usable memory in half.

There could also be the fallback to VirtualQuery if QueryWorkingSetEx doesn't exist.
 A short benchmark shows that VirtualQuery needs 55/42 ms for your test
 on Win32/Win64 on my mobile i7, while QueryWorkingSetEx takes about 17
 ms for both.

Seems in line with my measurements. Strictly speaking 1/2 of pages, interleaved should give the estimate of the worst case. Together with remapping (freeing duplicated pages) It doesn't go beyond 250ms on 640Mb of heap.
 If I add the actual copy into heap2 (i.e. every fourth page of 512 MB is
 copied), I get 80-90 ms more.

Aye... this is a lot. Also for me it turns out that unmapping CoW view at the last step takes the most of time.

Maybe the memory needs to be actually flushed to the file if no mapping exists. If that is the case, we could avoid that if we create another temporary mapping.
 It might help to split the full heap into multiple views.

The current GC uses pools of max 32 MB, so that already exists.
 Also using VirtualProtect during the first step - turning a mapping into
 CoW one is faster then unmap/map (by factor of 2).

 One thing that may help is saving a pointer to the end of used heap at
 the moment of scan, then remaping only this portion as COW.

The pool architecture already does this if scanning just ignores new pools during collection. Another optimization is to segregate the heap into memory with references and memory with plain data (NO_SCAN) at page/pool granularity. NO_SCAN-pages won't need COW. My hope is that this reduces necessary duplicate memory addresses considerably.
 Last issue I see is adjustment of pointers - in a GC, the mapped view is
 mapped at new address so it would need a fixup them during scanning.

Agreed, that's a slight additional cost for scanning, but I don't think it will be too difficult to implement.
 The numbers are not great, but I guess the usual memory usage and number
 of modified pages will be much lower. I'll see if I can integrate this
 into the concurrent implementation.

Wish you luck, I'm still not sure if it will help.

Jun 13 2014
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
13-Jun-2014 12:22, Rainer Schuetze пишет:
 On 13.06.2014 02:38, Dmitry Olshansky wrote:
 12-Jun-2014 10:34, Rainer Schuetze пишет:
 I implemented the QueryWorkingSetEx version like this (you need a
 converted psapi.lib for Win32):

Yes, exactly, but I forgot the recipe to convert COFF/OMF import libraries.

Grab coffimplib.exe.

Cool, thanks.
 If I add the actual copy into heap2 (i.e. every fourth page of 512 MB is
 copied), I get 80-90 ms more.

Aye... this is a lot. Also for me it turns out that unmapping CoW view at the last step takes the most of time.

Maybe the memory needs to be actually flushed to the file if no mapping exists. If that is the case, we could avoid that if we create another temporary mapping.

I thought that's what I do by keeping original view mapped. The time taken is ~ proportional to the number of pages modified in the CoW view, since these are private copies I think it might take this much to recycle them. It's ~1 ms if no changes are made. -- Dmitry Olshansky
Jun 13 2014
parent reply Rainer Schuetze <r.sagitario gmx.de> writes:
On 13.06.2014 12:08, Dmitry Olshansky wrote:
 13-Jun-2014 12:22, Rainer Schuetze пишет:
 If I add the actual copy into heap2 (i.e. every fourth page of 512
 MB is
 copied), I get 80-90 ms more.

Aye... this is a lot. Also for me it turns out that unmapping CoW view at the last step takes the most of time.

Maybe the memory needs to be actually flushed to the file if no mapping exists. If that is the case, we could avoid that if we create another temporary mapping.

I thought that's what I do by keeping original view mapped. The time taken is ~ proportional to the number of pages modified in the CoW view, since these are private copies I think it might take this much to recycle them. It's ~1 ms if no changes are made.

I added COW to the concurrent GC ( https://github.com/rainers/druntime/tree/concurrent_gc2 ) and it seems more stable with respect to pause times than the version with reading write watches. I also see considerable time spent during unmapping the CoW view, about as much as copying the data. One issue with calling OS functions while the world is stopped: if these function require a lock on some synchronization object, and this object is locked by another thread that is suspended, we create a dead lock. Do you know if MapViewOfFileEx and UnmapViewOfFile are lock free? The same can happen with GetWriteWatch and ResetWriteWatch, though.
Jun 14 2014
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
14-Jun-2014 20:34, Rainer Schuetze пишет:
 On 13.06.2014 12:08, Dmitry Olshansky wrote:
 13-Jun-2014 12:22, Rainer Schuetze пишет:
 If I add the actual copy into heap2 (i.e. every fourth page of 512
 MB is
 copied), I get 80-90 ms more.

Aye... this is a lot. Also for me it turns out that unmapping CoW view at the last step takes the most of time.

Maybe the memory needs to be actually flushed to the file if no mapping exists. If that is the case, we could avoid that if we create another temporary mapping.

I thought that's what I do by keeping original view mapped. The time taken is ~ proportional to the number of pages modified in the CoW view, since these are private copies I think it might take this much to recycle them. It's ~1 ms if no changes are made.

I added COW to the concurrent GC ( https://github.com/rainers/druntime/tree/concurrent_gc2 ) and it seems more stable with respect to pause times than the version with reading write watches.

How do I run benchmarks and what are the newest results for you?
 I also see considerable time spent during unmapping the CoW view, about
 as much as copying the data.

 One issue with calling OS functions while the world is stopped: if these
 function require a lock on some synchronization object, and this object
 is locked by another thread that is suspended, we create a dead lock.

 Do you know if MapViewOfFileEx and UnmapViewOfFile are lock free?

No idea. It may also depend on OS version, given the fuzz about Win7 being the first with lock-free thread scheduler there may be giant-locks in memory-mapping at least in some versions.
 The same can happen with GetWriteWatch and ResetWriteWatch, though.

-- Dmitry Olshansky
Jun 14 2014
parent Rainer Schuetze <r.sagitario gmx.de> writes:
On 14.06.2014 20:17, Dmitry Olshansky wrote:
 I added COW to the concurrent GC (
 https://github.com/rainers/druntime/tree/concurrent_gc2 ) and it seems
 more stable with respect to pause times than the version with reading
 write watches.

How do I run benchmarks and what are the newest results for you?

The benchmarks have been recently merged into druntime. Compile and run runbench.d in the benchmark folder. I have updated the report and added new benchmarks at http://rainers.github.io/visuald/druntime/concurrentgc.html
Jun 15 2014
prev sibling parent Martin Nowak <code dawg.eu> writes:
On 06/12/2014 08:34 AM, Rainer Schuetze wrote:
 If I add the actual copy into heap2 (i.e. every fourth page of 512 MB is
 copied), I get 80-90 ms more.

 The numbers are not great, but I guess the usual memory usage and number
 of modified pages will be much lower. I'll see if I can integrate this
 into the concurrent implementation.

Is there a chance that we can pause mutator threads when they trigger to many page copies?
Jun 15 2014