October 19, 2012
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
> 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
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
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
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
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
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
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
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
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