Re: Shared keyword and the GC?
On Tuesday, 23 October 2012 at 22:33:13 UTC, Araq wrote: OCmal's GC is one of the fastest GC ever made. And it is the case because it uses immutability to great benefice. According to which benchmarks? And does the fact that an object is immutable really need to be known at compile time for GC related optimizations? I haven't seen proper benchmarks but some time ago I wrote in D and OCaml basically the same simple program which read and parsed some text and performed some calculations, allocating a lot of temporary arrays or lists: https://gist.github.com/2902247 https://gist.github.com/2922399 and OCaml version was 2 times faster than D (29 and 59 seconds on input file of 1 million lines). After disabling GC on reading/parsing stage and doing calculations without allocations and using std.parallelism I made D version work in 4.4 seconds. One place where immutability really helps is in a generational GC: runtime needs to track all the pointers from old generation to the young generation, if most of the data is immutable there are not so many such pointers, this makes collection faster. When all data is immutable there is no such pointers at all, each object can only have pointers to older ones.
Re: Shared keyword and the GC?
I haven't seen proper benchmarks but some time ago I wrote in D and OCaml basically the same simple program which read and parsed some text and performed some calculations, allocating a lot of temporary arrays or lists: https://gist.github.com/2902247 https://gist.github.com/2922399 and OCaml version was 2 times faster than D (29 and 59 seconds on input file of 1 million lines). After disabling GC on reading/parsing stage and doing calculations without allocations and using std.parallelism I made D version work in 4.4 seconds. And that makes it the fastest GC ever made? One place where immutability really helps is in a generational GC: runtime needs to track all the pointers from old generation to the young generation, if most of the data is immutable there are not so many such pointers, this makes collection faster. When all data is immutable there is no such pointers at all, each object can only have pointers to older ones. That's true. But you don't need to know about immmutability at compile time to get this benefit.
Re: Shared keyword and the GC?
On Wednesday, 24 October 2012 at 17:42:50 UTC, Araq wrote: And that makes it the fastest GC ever made? No, not that, of course. As I said, I haven't seen proper benchmarks. But OCaml's GC is notorious for its speed and it performed very well in all comparisons I saw. One place where immutability really helps is in a generational GC: runtime needs to track all the pointers from old generation to the young generation, if most of the data is immutable there are not so many such pointers, this makes collection faster. When all data is immutable there is no such pointers at all, each object can only have pointers to older ones. That's true. But you don't need to know about immmutability at compile time to get this benefit. I agree.
Re: Shared keyword and the GC?
On Monday, 22 October 2012 at 21:19:53 UTC, deadalnix wrote: Funny thing, immutable was supposed to make it easier to do concurrency programming. But not garbage collection. OCmal's GC is one of the fastest GC ever made. And it is the case because it uses immutability to great benefice. OCaml, I suppose. It is single threaded (there is no thread-level parallelism in OCaml) and there is nothing in its GC that uses immutability really. It's so fast because of the memory model: to tell if a word is a pointer one just needs to look at its least significant bit, if it's 0 it's a pointer, if it's 1 it's not. That's why native ints are 31-bit in OCaml. With this scheme they don't need to store type layout info and pointer bitmaps. And it is generational (2 gens), which also adds much speed. A GC which really relies on immutability you can find in Erlang.
Re: Shared keyword and the GC?
OCmal's GC is one of the fastest GC ever made. And it is the case because it uses immutability to great benefice. According to which benchmarks? And does the fact that an object is immutable really need to be known at compile time for GC related optimizations?
Re: Shared keyword and the GC?
On Oct 18, 2012, at 6:06 PM, Michel Fortin michel.for...@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.
Re: Shared keyword and the GC?
On Oct 18, 2012, at 11:56 PM, Alex Rønne Petersen a...@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.
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
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
Re: Shared keyword and the GC?
On Oct 22, 2012, at 12:16 PM, Jacob Carlborg d...@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.
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.
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 Petersena...@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? :-)
Re: Shared keyword and the GC?
Le 22/10/2012 22:44, Andrei Alexandrescu a écrit : 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. OCmal's GC is one of the fastest GC ever made. And it is the case because it uses immutability to great benefice. As immutable data can only refers to immutable data, I don't see a single problem here. When collection shared and TL, you get a set of root pointer to immutable. All immutable can be collected from such set. All object allocated during the collection is supposed to be live.
Re: Shared keyword and the GC?
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. -- Alex Rønne Petersen a...@lycus.org http://lycus.org
Re: Shared keyword and the GC?
On 17-10-2012 13:51, Jacob Carlborg wrote: On 2012-10-17 10:55, Alex Rønne Petersen wrote: Let's step back for a bit and think about what we want to achieve with thread-local garbage collection. The idea is that we look only at a single thread's heap (and stack/registers, of course) when doing a collection. This means that we can -- theoretically -- stop only one thread at a time and only when it needs to be stopped. This is clearly a huge win in scalability and raw speed. With a scheme like this, it might even be possible to get away with a simple mark-sweep or copying GC per thread instead of a complicated generational GC, mainly due to the paradigms the isolation model induces. Rust, as it is today, can do this. Tasks (or threads if you will - though they aren't the same thing) are completely isolated. Types that can potentially contain pointers into a task's heap cannot be sent to other tasks at all. Rust also does not have global variables. 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. It's important to keep in mind that in order for thread-local GC (as defined above) to be possible at all, *under no circumstances whatsoever must there be a pointer in one thread's heap into another thread's heap, ever*. If this happens and you apply the above GC strategy (stop one thread at a time and scan only that thread's heap), you're effectively dealing with something very similar to the lost object problem on concurrent GC. To clarify with regards to the shared qualifier: It does absolutely nothing. It's useless. All it does is slap a pretty I can be shared arbitrarily across threads label on a type. Even if you have this knowledge in the GC, it's not going to help you, because you *still* have to deal with the problem that arbitrary pointers can be floating around in arbitrary threads. (And don't even get me started on the lack of clear semantics (and even the few semi-agreed-upon but flawed semantics) for shared.) All TLS data is handled by collectors running in their one single thread, as you describe above. Any non-TLS data is handled the same way as the GC currently works. This is how the, now deprecated, Apple GC used by Objective-C works. How does it deal with the problem where a pointer in TLS points to global data, or worse yet, a pointer in the global heap points to TLS? I'm pretty sure it can't without doing a full pass over the entire heap, which seems to me like it defeats the purpose. But I may just be missing out on some restriction (type system or whatever) Objective-C has that makes it feasible. -- Alex Rønne Petersen a...@lycus.org http://lycus.org
Re: Shared keyword and the GC?
On 18-10-2012 20:26, Sean Kelly wrote: On Oct 17, 2012, at 1:55 AM, Alex Rønne Petersen a...@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. 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? :-) 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. -- Alex Rønne Petersen a...@lycus.org http://lycus.org
Re: Shared keyword and the GC?
On 2012-10-18 22:29, Sean Kelly wrote: It's different in that a variable's address never actually changes. When a thread completes it hands all of its pools to the shared allocator, and then per-thread allocators request free pools from the shared allocator before going to the OS. This is basically how the HOARD allocator works. Ah, now I see. -- /Jacob Carlborg
Re: Shared keyword and the GC?
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. -- /Jacob Carlborg
Re: Shared keyword and the GC?
On 2012-10-19 08:48, Alex Rønne Petersen wrote: How does it deal with the problem where a pointer in TLS points to global data, or worse yet, a pointer in the global heap points to TLS? I'm pretty sure it can't without doing a full pass over the entire heap, which seems to me like it defeats the purpose. But I may just be missing out on some restriction (type system or whatever) Objective-C has that makes it feasible. I'm not sure how this is handled. But the GC is only used for the Objective-C allocations, i.e. [NSObject alloc] and not for C allocations, i.e. malloc. -- /Jacob Carlborg
Re: Shared keyword and the GC?
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? I'm pretty sure it can't without doing a full pass over the entire heap, which seems to me like it defeats the purpose. Yeah. But I may just be missing out on some restriction (type system or whatever) Objective-C has that makes it feasible.
Re: Shared keyword and the GC?
On 19-10-2012 11:07, 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.
The problem with D is that we have a (more or less) stable language that
we can't make major changes to at this point.
or worse yet, a pointer in the global heap points to TLS?
Could you give an example?
I don't know Objective-C, so in D:
void* p; // in TLS
void main()
{
p = GC.malloc(1024); // a pointer to the global heap is now in TLS
}
Or the more complicated case (for any arbitrary graph of objects):
Object p; // in TLS
class C
{
Object o;
this(Object o)
{
this.o = o;
}
}
void main()
{
p = new C(new Object); // the graph can be arbitrarily complex and
any part of it can be allocated with the GC, malloc, or any other mechanism
}
I'm pretty sure it can't without doing a full pass over the entire
heap, which seems to me like it defeats the purpose.
Yeah.
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.
But I may just be missing out on some restriction (type system or
whatever) Objective-C has that makes it feasible.
--
Alex Rønne Petersen
a...@lycus.org
http://lycus.org
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;
}
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.
Re: Shared keyword and the GC?
On 2012-10-19 07:42:53 +, Jacob Carlborg d...@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.for...@michelf.ca http://michelf.ca/
Re: Shared keyword and the GC?
On Oct 17, 2012, at 1:55 AM, Alex Rønne Petersen a...@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. 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? :-)
Re: Shared keyword and the GC?
On 2012-10-18 20:26, Sean Kelly wrote: 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. Or move the shared data to the global heap when it's casted. Don't know that's best. This way all data in a give pool will be truly thread local. -- /Jacob Carlborg
Re: Shared keyword and the GC?
On Oct 18, 2012, at 11:48 AM, Jacob Carlborg d...@me.com wrote: On 2012-10-18 20:26, Sean Kelly wrote: 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. Or move the shared data to the global heap when it's casted. Don't know that's best. This way all data in a give pool will be truly thread local. And back down to a local pool when shared is cast away. Assuming the block is even movable. I agree that this would be the most efficient use of memory, but I don't know that it's feasible.
Re: Shared keyword and the GC?
On 2012-10-18 20:54, Sean Kelly wrote: And back down to a local pool when shared is cast away. Assuming the block is even movable. I agree that this would be the most efficient use of memory, but I don't know that it's feasible. You said the thread local heap would be merged with the global on thread termination. How is that different? Alternative it could stay in the global heap. I mean, not many variables should be shared and even fewer should be casted back and forth. -- /Jacob Carlborg
Re: Shared keyword and the GC?
On Oct 18, 2012, at 12:22 PM, Jacob Carlborg d...@me.com wrote: On 2012-10-18 20:54, Sean Kelly wrote: And back down to a local pool when shared is cast away. Assuming the block is even movable. I agree that this would be the most efficient use of memory, but I don't know that it's feasible. You said the thread local heap would be merged with the global on thread termination. How is that different? Alternative it could stay in the global heap. I mean, not many variables should be shared and even fewer should be casted back and forth. It's different in that a variable's address never actually changes. When a thread completes it hands all of its pools to the shared allocator, and then per-thread allocators request free pools from the shared allocator before going to the OS. This is basically how the HOARD allocator works.
Re: Shared keyword and the GC?
On 2012-10-18 18:26:08 +, Sean Kelly s...@invisibleduck.org said: 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. 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? :-) 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: As for a shared gc vs thread local gc, I just see an awful lot of strange irreproducible bugs when someone passes data from one to the other. I doubt it's worth it, unless it can be done with compiler guarantees, which seem doubtful. I think you'll have a hard time convincing Walter it is worth changing the behaviour of type modifiers at this point. Reference: http://lists.puremagic.com/pipermail/dmd-concurrency/2010-January/000132.html http://lists.puremagic.com/pipermail/dmd-concurrency/2010-January/000146.html -- Michel Fortin michel.for...@michelf.ca http://michelf.ca/
Shared keyword and the GC?
Hello, in the discussions thread in the recent blog post which summarized how GC works(*), the topic of thread-local GC was further discussed and I pointed out that by default global variables in D are thread local but I was answered that the types doesn't tell which global variable are thread local and which are shared so the GC cannot use this information, is-it true? It seems like a wasted opportunity.. BR, renoX *: http://xtzgzorex.wordpress.com/2012/10/11/demystifying-garbage-collectors/
Re: Shared keyword and the GC?
On 17-10-2012 10:29, renoX wrote: Hello, in the discussions thread in the recent blog post which summarized how GC works(*), the topic of thread-local GC was further discussed and I pointed out that by default global variables in D are thread local but I was answered that the types doesn't tell which global variable are thread local and which are shared so the GC cannot use this information, is-it true? It seems like a wasted opportunity.. BR, renoX *: http://xtzgzorex.wordpress.com/2012/10/11/demystifying-garbage-collectors/ Let's step back for a bit and think about what we want to achieve with thread-local garbage collection. The idea is that we look only at a single thread's heap (and stack/registers, of course) when doing a collection. This means that we can -- theoretically -- stop only one thread at a time and only when it needs to be stopped. This is clearly a huge win in scalability and raw speed. With a scheme like this, it might even be possible to get away with a simple mark-sweep or copying GC per thread instead of a complicated generational GC, mainly due to the paradigms the isolation model induces. Rust, as it is today, can do this. Tasks (or threads if you will - though they aren't the same thing) are completely isolated. Types that can potentially contain pointers into a task's heap cannot be sent to other tasks at all. Rust also does not have global variables. 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. It's important to keep in mind that in order for thread-local GC (as defined above) to be possible at all, *under no circumstances whatsoever must there be a pointer in one thread's heap into another thread's heap, ever*. If this happens and you apply the above GC strategy (stop one thread at a time and scan only that thread's heap), you're effectively dealing with something very similar to the lost object problem on concurrent GC. To clarify with regards to the shared qualifier: It does absolutely nothing. It's useless. All it does is slap a pretty I can be shared arbitrarily across threads label on a type. Even if you have this knowledge in the GC, it's not going to help you, because you *still* have to deal with the problem that arbitrary pointers can be floating around in arbitrary threads. (And don't even get me started on the lack of clear semantics (and even the few semi-agreed-upon but flawed semantics) for shared.) -- Alex Rønne Petersen a...@lycus.org http://lycus.org
Re: Shared keyword and the GC?
On Wednesday, 17 October 2012 at 08:55:55 UTC, Alex Rønne Petersen wrote: On 17-10-2012 10:29, renoX wrote: Hello, in the discussions thread in the recent blog post which summarized how GC works(*), the topic of thread-local GC was further discussed and I pointed out that by default global variables in D are thread local but I was answered that the types doesn't tell which global variable are thread local and which are shared so the GC cannot use this information, is-it true? It seems like a wasted opportunity.. BR, renoX *: http://xtzgzorex.wordpress.com/2012/10/11/demystifying-garbage-collectors/ Let's step back for a bit and think about what we want to achieve with thread-local garbage collection. The idea is that we look only at a single thread's heap (and stack/registers, of course) when doing a collection. This means that we can -- theoretically -- stop only one thread at a time and only when it needs to be stopped. This is clearly a huge win in scalability and raw speed. With a scheme like this, it might even be possible to get away with a simple mark-sweep or copying GC per thread instead of a complicated generational GC, mainly due to the paradigms the isolation model induces. Rust, as it is today, can do this. Tasks (or threads if you will - though they aren't the same thing) are completely isolated. Types that can potentially contain pointers into a task's heap cannot be sent to other tasks at all. Rust also does not have global variables. 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. It's important to keep in mind that in order for thread-local GC (as defined above) to be possible at all, *under no circumstances whatsoever must there be a pointer in one thread's heap into another thread's heap, ever*. If this happens and you apply the above GC strategy (stop one thread at a time and scan only that thread's heap), you're effectively dealing with something very similar to the lost object problem on concurrent GC. To clarify with regards to the shared qualifier: It does absolutely nothing. It's useless. All it does is slap a pretty I can be shared arbitrarily across threads label on a type. Even if you have this knowledge in the GC, it's not going to help you, because you *still* have to deal with the problem that arbitrary pointers can be floating around in arbitrary threads. (And don't even get me started on the lack of clear semantics (and even the few semi-agreed-upon but flawed semantics) for shared.) Introduce the noshared keyword.
Re: Shared keyword and the GC?
On 17-10-2012 11:50, sclytrack wrote: On Wednesday, 17 October 2012 at 08:55:55 UTC, Alex Rønne Petersen wrote: On 17-10-2012 10:29, renoX wrote: Hello, in the discussions thread in the recent blog post which summarized how GC works(*), the topic of thread-local GC was further discussed and I pointed out that by default global variables in D are thread local but I was answered that the types doesn't tell which global variable are thread local and which are shared so the GC cannot use this information, is-it true? It seems like a wasted opportunity.. BR, renoX *: http://xtzgzorex.wordpress.com/2012/10/11/demystifying-garbage-collectors/ Let's step back for a bit and think about what we want to achieve with thread-local garbage collection. The idea is that we look only at a single thread's heap (and stack/registers, of course) when doing a collection. This means that we can -- theoretically -- stop only one thread at a time and only when it needs to be stopped. This is clearly a huge win in scalability and raw speed. With a scheme like this, it might even be possible to get away with a simple mark-sweep or copying GC per thread instead of a complicated generational GC, mainly due to the paradigms the isolation model induces. Rust, as it is today, can do this. Tasks (or threads if you will - though they aren't the same thing) are completely isolated. Types that can potentially contain pointers into a task's heap cannot be sent to other tasks at all. Rust also does not have global variables. 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. It's important to keep in mind that in order for thread-local GC (as defined above) to be possible at all, *under no circumstances whatsoever must there be a pointer in one thread's heap into another thread's heap, ever*. If this happens and you apply the above GC strategy (stop one thread at a time and scan only that thread's heap), you're effectively dealing with something very similar to the lost object problem on concurrent GC. To clarify with regards to the shared qualifier: It does absolutely nothing. It's useless. All it does is slap a pretty I can be shared arbitrarily across threads label on a type. Even if you have this knowledge in the GC, it's not going to help you, because you *still* have to deal with the problem that arbitrary pointers can be floating around in arbitrary threads. (And don't even get me started on the lack of clear semantics (and even the few semi-agreed-upon but flawed semantics) for shared.) Introduce the noshared keyword. Not a practical solution. -- Alex Rønne Petersen a...@lycus.org http://lycus.org
Re: Shared keyword and the GC?
On 2012-10-17 10:55, Alex Rønne Petersen wrote: Let's step back for a bit and think about what we want to achieve with thread-local garbage collection. The idea is that we look only at a single thread's heap (and stack/registers, of course) when doing a collection. This means that we can -- theoretically -- stop only one thread at a time and only when it needs to be stopped. This is clearly a huge win in scalability and raw speed. With a scheme like this, it might even be possible to get away with a simple mark-sweep or copying GC per thread instead of a complicated generational GC, mainly due to the paradigms the isolation model induces. Rust, as it is today, can do this. Tasks (or threads if you will - though they aren't the same thing) are completely isolated. Types that can potentially contain pointers into a task's heap cannot be sent to other tasks at all. Rust also does not have global variables. 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. It's important to keep in mind that in order for thread-local GC (as defined above) to be possible at all, *under no circumstances whatsoever must there be a pointer in one thread's heap into another thread's heap, ever*. If this happens and you apply the above GC strategy (stop one thread at a time and scan only that thread's heap), you're effectively dealing with something very similar to the lost object problem on concurrent GC. To clarify with regards to the shared qualifier: It does absolutely nothing. It's useless. All it does is slap a pretty I can be shared arbitrarily across threads label on a type. Even if you have this knowledge in the GC, it's not going to help you, because you *still* have to deal with the problem that arbitrary pointers can be floating around in arbitrary threads. (And don't even get me started on the lack of clear semantics (and even the few semi-agreed-upon but flawed semantics) for shared.) All TLS data is handled by collectors running in their one single thread, as you describe above. Any non-TLS data is handled the same way as the GC currently works. This is how the, now deprecated, Apple GC used by Objective-C works. -- /Jacob Carlborg
Re: Shared keyword and the GC?
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.
