View mode: basic / threaded / horizontal-split · Log in · Help
October 19, 2012
Re: Shared keyword and the GC?
On Friday, 19 October 2012 at 09:07:55 UTC, sclytrack wrote:
>
>> How does it deal with the problem where a pointer in TLS 
>> points to global data,
>
> Need to run stop-the-world for shared heap. But it would be 
> interesting to have blocks that have no shared pointers in them.
>
>
>> or worse yet, a pointer in the global heap points to TLS?
>>
>
> Could you give an example?
>


import std.stdio;

class Local
{
}

class Global
{
	Local data;
	int [] arr;
}

Local l2;
int [] arr;			//tls

int main()
{
	shared Global g = new shared(Global);		//global heap
	Local l1 = new Local();	//future local heap
	//	g.data = l1;	//disallowed
	l2 = new Local();
	//	g.data = l2;	//disallowed
	arr = new int[10];	//future local heap
	g.arr = cast(shared(int[])) arr; //bypassed.	
	writeln("Complete");
	return 0;
}
October 19, 2012
Re: Shared keyword and the GC?
> Thread-local GC is all about improving scalability by only 
> stopping threads that need to be stopped. If you can't even do 
> that, then any effort towards thread-local GC is quite 
> pointless IMO.

Maybe the goal is to run the thread local garbage collectors very 
frequently and the stop-the-world one's just occasionally. Once 
your thread has shared in it must participate in the 
stop-the-world ones. Maybe the threads needs to register to both 
the thread local garbage collector and the global stop-the-world 
garbage collector.
October 19, 2012
Re: Shared keyword and the GC?
On 2012-10-19 07:42:53 +0000, Jacob Carlborg <doob@me.com> said:

> On 2012-10-19 03:06, Michel Fortin wrote:
> 
>> All this is nice, but what is the owner thread for immutable data?
>> Because immutable is always implicitly shared, all your strings and
>> everything else that is immutable is thus "shared" and must be tracked
>> by the global heap's collector and can never be handled by a
>> thread-local collector. Even if most immutable data never leaves the
>> thread it was allocated in, there's no way you can know.
>> 
>> I don't think per-thread GCs will work very well without support for
>> immutable data, an for that you need to have a distinction between
>> immutable and shared immutable (just like you have with mutable data). I
>> complained about this almost three years ago when the semantics of
>> shared were being defined, but it got nowhere. Quoting Walter at the time:
> 
> Would it be any difference if the immutable data was collected from a 
> different collector than the shared or thread local?
> 
> In this case I guess the collector wouldn't try to make a difference 
> between shared and non-shared immutable data.

A thread-local GC would be efficient because it scans only one thread. 
The gain is that you minimize the load on the global GC, reducing 
collection cycles that need to stop all threads. Creating a second 
global GC for immutable data wouldn't free you from the need to stop 
all threads, but now you'd have two global collectors stopping all 
threads which would probably be worse. So I don't see the point in a 
second GC for immutable data.

Immutable data must always be handled by a global GC. There's no way 
around it as long as immutable and shared-immutable are the same thing. 
The more immutable data you have, the more irrelevant the performance 
gains from a thread-local GC becomes, because it get used less often. 
This creates a strange incentive to *not* make things immutable in 
order make things faster.

I'm all for a thread-local GC, but in the current state of the type 
system it'd just be ridiculous. But then, perhaps an implementation of 
it could convince Walter to change some things. So if someone is 
inclined to implement it, go ahead, I'm not here to stop you.

-- 
Michel Fortin
michel.fortin@michelf.ca
http://michelf.ca/
October 22, 2012
Re: Shared keyword and the GC?
On Oct 18, 2012, at 6:06 PM, Michel Fortin <michel.fortin@michelf.ca> wrote:
> 
> All this is nice, but what is the owner thread for immutable data? Because immutable is always implicitly shared, all your strings and everything else that is immutable is thus "shared" and must be tracked by the global heap's collector and can never be handled by a thread-local collector. Even if most immutable data never leaves the thread it was allocated in, there's no way you can know.

Yes.


> I don't think per-thread GCs will work very well without support for immutable data, an for that you need to have a distinction between immutable and shared immutable (just like you have with mutable data). I complained about this almost three years ago when the semantics of shared were being defined, but it got nowhere.

Yeah, that's unfortunate.  "shared" today really has two meanings: instance visibility and what happens when the instance is accessed.  By comparison, "immutable" just describes what happens when the instance is accessed.  The really weird part of all this being that immutable data is exempt from the transitivity requirement of "shared".  Though that makes me realize that casting a UDT to "shared" could mean traversing all data reachable by that instance and marking it as shared as well, which sounds absolutely terrible.

Perhaps something could be done in instances where the only place data is passed between threads in an app is via std.concurrency?  Allowing strings to be referenced by global shared references would still be problematic though.  I'll have to give this some thought.
October 22, 2012
Re: Shared keyword and the GC?
On Oct 18, 2012, at 11:56 PM, Alex Rønne Petersen <alex@lycus.org> wrote:
> 
> I'm not really sure how this solves the problem of having pointers from a thread-local heap into the global heap and vice versa. Can you elaborate on that?
> 
> The problem is that even if you know whether a piece of memory is flagged shared, you cannot know if some arbitrary number of threads happen to have pointers to it and can thus mutate anything inside it while a thread-local collection is in progress.

Blocks flagged as shared would be completely ignored by the thread-local GC collection.  Since shared data may never reference unshared data, that should avoid anything being collected that's still referenced.  I hadn't thought about "immutable" though, which may turn out to be a problem.
October 22, 2012
Re: Shared keyword and the GC?
On 2012-10-22 19:44, Sean Kelly wrote:

> Blocks flagged as shared would be completely ignored by the thread-local GC collection.  Since shared data may never reference unshared data, that should avoid anything being collected that's still referenced.  I hadn't thought about "immutable" though, which may turn out to be a problem.

Funny thing, immutable was supposed to make it easier to do concurrency 
programming.

-- 
/Jacob Carlborg
October 22, 2012
Re: Shared keyword and the GC?
On 10/22/12 3:16 PM, Jacob Carlborg wrote:
> On 2012-10-22 19:44, Sean Kelly wrote:
>
>> Blocks flagged as shared would be completely ignored by the
>> thread-local GC collection. Since shared data may never reference
>> unshared data, that should avoid anything being collected that's still
>> referenced. I hadn't thought about "immutable" though, which may turn
>> out to be a problem.
>
> Funny thing, immutable was supposed to make it easier to do concurrency
> programming.

But not garbage collection.

Andrei
October 22, 2012
Re: Shared keyword and the GC?
On Oct 22, 2012, at 12:16 PM, Jacob Carlborg <doob@me.com> wrote:

> On 2012-10-22 19:44, Sean Kelly wrote:
> 
>> Blocks flagged as shared would be completely ignored by the thread-local GC collection.  Since shared data may never reference unshared data, that should avoid anything being collected that's still referenced.  I hadn't thought about "immutable" though, which may turn out to be a problem.
> 
> Funny thing, immutable was supposed to make it easier to do concurrency programming.

In the realm of shared data concurrency, immutable is definitely useful.  But where data is all thread-local I'm not entirely sure.  Either way though, immutable within the context of this discussion is a library optimization issue rather than anything to do with the type itself.
October 22, 2012
Re: Shared keyword and the GC?
Le 19/10/2012 08:49, Alex Rønne Petersen a écrit :
> On 17-10-2012 16:26, deadalnix wrote:
>> Why not definitively adopt the following (and already proposed) memory
>> scheme (some practice are now considered valid when this scheme is not
>> respected) :
>>
>> Thread local head (one by thread) -> shared heap -> immutable heap
>>
>> This model have multiple benefices :
>> - TL heap only can be processed by only interacting with one thread.
>> - immutable head can be collected 100% concurently if we allow some
>> floating garbage.
>> - shared heap is the only problem, but as its size stay small, the
>> problem stay small.
>
> Can you elaborate? I'm not sure I understand.
>

OK let me detail a little more.

First, I'll explain TL GC. You have to understand shared heap here as 
both shared and immutable heap.

TL collection can be done disturbing only one thread. When the TL 
collection is done, a set of pointer to shared heap is known.

Now, all new pointer in the TL heap to shared heap is either :
 - a new allocation.
 - a pointer read from the shared heap.

So, basically, at the end, we have a set of root to collect the shared 
heap. The thread can continue to run when the shared heap is collected.

Now let's consider the immutable heap. Given a set of root from TL and 
shared, the immutable heap can be collected concurrently. I think it is 
straightforward and will not elaborate.

So the problem is now the shared heap. Here is how I see its collection. 
When the GC want to collect shared it first signal itself to each thread 
that will GC TL data and give back a set of root. As of this point, the 
GC mark all new allocation as live and set a write barrier on shared : 
when a shared object is written, it is marked ive (obviously), its old 
value is scanned, and its new value is scanned too. The reason is pretty 
simple : the old value may have been read by a thread and stored 
locally. When the collection is done, the write barrier can be removed. 
Obviously, the write barrier is not needed for immutable object or any 
shared write that isn't a pointer write, which lead to a very nice way 
to collect things.

The obvious drawback is that pointer for TL to another TL or from shared 
to TL will confuse the GC. But it is already not @safe anyway.
October 22, 2012
Re: Shared keyword and the GC?
Le 18/10/2012 20:26, Sean Kelly a écrit :
> On Oct 17, 2012, at 1:55 AM, Alex Rønne Petersen<alex@lycus.org>  wrote:
>>
>> So, let's look at D:
>>
>> 1. We have global variables.
>> 1. Only std.concurrency enforces isolation at a type system level; it's not built into the language, so the GC cannot make assumptions.
>> 1. The shared qualifier effectively allows pointers from one thread's heap into another's.
>
> Well, the problem is more that a variable can be cast to shared after instantiation, so to allow thread-local collections we'd have to make cast(shared) set a flag on the memory block to indicate that it's shared, and vice-versa for unshared.  Then when a thread terminates, all blocks not flagged as shared would be finalized, leaving the shared blocks alone.  Then any pool from the terminated thread containing a shared block would have to be merged into the global heap instead of released to the OS.
>

This is already unsafe anyway. The clean solution is either to allocate 
the object as shared, then cast it to TL and back to shared of it make 
sense.

The second option is to clone the object.

Having a flag by object isn't a good idea IMO.

> I think we need to head in this direction anyway, because we need to make sure that thread-local data is finalized by its owner thread.  A blocks owner would be whoever allocated the block or if cast to shared and back to unshared, whichever thread most recently cast the block back to unshared.  Tracking the owner of a block gives us the shared state implicitly, making thread-local collections possible.  Who wants to work on this? :-)
1 2 3 4
Top | Discussion index | About this forum | D home