Jump to page: 1 2
Thread overview
std.concurrency and fibers
Oct 04, 2012
Timon Gehr
Oct 04, 2012
Timon Gehr
Oct 04, 2012
Dmitry Olshansky
Oct 04, 2012
Sean Kelly
Oct 04, 2012
Dmitry Olshansky
Oct 05, 2012
Dmitry Olshansky
Oct 05, 2012
Johannes Pfau
Oct 04, 2012
Jonathan M Davis
Oct 04, 2012
Sean Kelly
Oct 05, 2012
Sean Kelly
Oct 05, 2012
deadalnix
October 04, 2012
Hi,

We currently have std.concurrency as a message-passing mechanism. We encourage people to use it instead of OS threads, which is great. However, what is *not* great is that spawned tasks correspond 1:1 to OS threads. This is not even remotely scalable for Erlang-style concurrency. There's a fairly simple way to fix that: Fibers.

The only problem with adding fiber support to std.concurrency is that the interface is just not flexible enough. The current interface is completely and entirely tied to the notion of threads (contrary to what its module description says).

Now, I see a number of ways we can fix this:

A) We completely get rid of the notion of threads and instead simply speak of 'tasks'. This trivially allows us to use threads, fibers, whatever to back the module. I personally think this is the best way to build a message-passing abstraction because it gives enough transparency to *actually* distribute tasks across machines without things breaking.
B) We make the module capable of backing tasks with both threads and fibers, and expose an interface that allows the user to choose what kind of task is spawned. I'm *not* convinced this is a good approach because it's extremely error-prone (imagine doing a thread-based receive inside a fiber-based task!).
C) We just swap out threads with fibers and document that the module uses fibers. See my comments in A for why I'm not sure this is a good idea.

All of these are going to break code in one way or another - that's unavoidable. But we really need to make std.concurrency grow up; other languages (Erlang, Rust, Go, ...) have had micro-threads (in some form) for years, and if we want D to be seriously usable for large-scale concurrency, we need to have them too.

Thoughts? Other ideas?

-- 
Alex Rønne Petersen
alex@lycus.org
http://lycus.org
October 04, 2012
On 10/04/2012 01:32 PM, Alex Rønne Petersen wrote:
> Hi,
>
> We currently have std.concurrency as a message-passing mechanism. We
> encourage people to use it instead of OS threads, which is great.
> However, what is *not* great is that spawned tasks correspond 1:1 to OS
> threads. This is not even remotely scalable for Erlang-style
> concurrency. There's a fairly simple way to fix that: Fibers.
>
> The only problem with adding fiber support to std.concurrency is that
> the interface is just not flexible enough. The current interface is
> completely and entirely tied to the notion of threads (contrary to what
> its module description says).
>
> Now, I see a number of ways we can fix this:
>
> A) We completely get rid of the notion of threads and instead simply
> speak of 'tasks'. This trivially allows us to use threads, fibers,
> whatever to back the module. I personally think this is the best way to
> build a message-passing abstraction because it gives enough transparency
> to *actually* distribute tasks across machines without things breaking.
> B) We make the module capable of backing tasks with both threads and
> fibers, and expose an interface that allows the user to choose what kind
> of task is spawned. I'm *not* convinced this is a good approach because
> it's extremely error-prone (imagine doing a thread-based receive inside
> a fiber-based task!).
> C) We just swap out threads with fibers and document that the module
> uses fibers. See my comments in A for why I'm not sure this is a good idea.
>
> All of these are going to break code in one way or another - that's
> unavoidable. But we really need to make std.concurrency grow up; other
> languages (Erlang, Rust, Go, ...) have had micro-threads (in some form)
> for years, and if we want D to be seriously usable for large-scale
> concurrency, we need to have them too.
>
> Thoughts? Other ideas?
>

+1, but what about TLS?
October 04, 2012
On 04-10-2012 14:11, Timon Gehr wrote:
> On 10/04/2012 01:32 PM, Alex Rønne Petersen wrote:
>> Hi,
>>
>> We currently have std.concurrency as a message-passing mechanism. We
>> encourage people to use it instead of OS threads, which is great.
>> However, what is *not* great is that spawned tasks correspond 1:1 to OS
>> threads. This is not even remotely scalable for Erlang-style
>> concurrency. There's a fairly simple way to fix that: Fibers.
>>
>> The only problem with adding fiber support to std.concurrency is that
>> the interface is just not flexible enough. The current interface is
>> completely and entirely tied to the notion of threads (contrary to what
>> its module description says).
>>
>> Now, I see a number of ways we can fix this:
>>
>> A) We completely get rid of the notion of threads and instead simply
>> speak of 'tasks'. This trivially allows us to use threads, fibers,
>> whatever to back the module. I personally think this is the best way to
>> build a message-passing abstraction because it gives enough transparency
>> to *actually* distribute tasks across machines without things breaking.
>> B) We make the module capable of backing tasks with both threads and
>> fibers, and expose an interface that allows the user to choose what kind
>> of task is spawned. I'm *not* convinced this is a good approach because
>> it's extremely error-prone (imagine doing a thread-based receive inside
>> a fiber-based task!).
>> C) We just swap out threads with fibers and document that the module
>> uses fibers. See my comments in A for why I'm not sure this is a good
>> idea.
>>
>> All of these are going to break code in one way or another - that's
>> unavoidable. But we really need to make std.concurrency grow up; other
>> languages (Erlang, Rust, Go, ...) have had micro-threads (in some form)
>> for years, and if we want D to be seriously usable for large-scale
>> concurrency, we need to have them too.
>>
>> Thoughts? Other ideas?
>>
>
> +1, but what about TLS?

I think that no matter what we do, we have to simply say "don't do that" to thread-local state (it would break in distributed scenarios too, for instance).

Instead, I think we should do what the Rust folks did: Use *task*-local state and leave it up to std.concurrency to figure out how to deal with it. It won't be as 'seamless' as TLS variables in D of course, but I think it's good enough in practice.

-- 
Alex Rønne Petersen
alex@lycus.org
http://lycus.org
October 04, 2012
On 10/04/2012 02:22 PM, Alex Rønne Petersen wrote:
> On 04-10-2012 14:11, Timon Gehr wrote:
>> On 10/04/2012 01:32 PM, Alex Rønne Petersen wrote:
>>> Hi,
>>>
>>> We currently have std.concurrency as a message-passing mechanism. We
>>> encourage people to use it instead of OS threads, which is great.
>>> However, what is *not* great is that spawned tasks correspond 1:1 to OS
>>> threads. This is not even remotely scalable for Erlang-style
>>> concurrency. There's a fairly simple way to fix that: Fibers.
>>>
>>> The only problem with adding fiber support to std.concurrency is that
>>> the interface is just not flexible enough. The current interface is
>>> completely and entirely tied to the notion of threads (contrary to what
>>> its module description says).
>>>
>>> Now, I see a number of ways we can fix this:
>>>
>>> A) We completely get rid of the notion of threads and instead simply
>>> speak of 'tasks'. This trivially allows us to use threads, fibers,
>>> whatever to back the module. I personally think this is the best way to
>>> build a message-passing abstraction because it gives enough transparency
>>> to *actually* distribute tasks across machines without things breaking.
>>> B) We make the module capable of backing tasks with both threads and
>>> fibers, and expose an interface that allows the user to choose what kind
>>> of task is spawned. I'm *not* convinced this is a good approach because
>>> it's extremely error-prone (imagine doing a thread-based receive inside
>>> a fiber-based task!).
>>> C) We just swap out threads with fibers and document that the module
>>> uses fibers. See my comments in A for why I'm not sure this is a good
>>> idea.
>>>
>>> All of these are going to break code in one way or another - that's
>>> unavoidable. But we really need to make std.concurrency grow up; other
>>> languages (Erlang, Rust, Go, ...) have had micro-threads (in some form)
>>> for years, and if we want D to be seriously usable for large-scale
>>> concurrency, we need to have them too.
>>>
>>> Thoughts? Other ideas?
>>>
>>
>> +1, but what about TLS?
>
> I think that no matter what we do, we have to simply say "don't do that"
> to thread-local state (it would break in distributed scenarios too, for
> instance).
>
> Instead, I think we should do what the Rust folks did: Use *task*-local
> state and leave it up to std.concurrency to figure out how to deal with
> it. It won't be as 'seamless' as TLS variables in D of course, but I
> think it's good enough in practice.
>

If it is not seamless, we have failed. IMO the runtime should expose an
interface for allocating TLS, switching between TLS instances and
destroying TLS.

What about the stack? Allocating a fixed-size stack per task is costly
and Walter opposes dynamic stack growth.
October 04, 2012
On 04-10-2012 14:48, Timon Gehr wrote:
> On 10/04/2012 02:22 PM, Alex Rønne Petersen wrote:
>> On 04-10-2012 14:11, Timon Gehr wrote:
>>> On 10/04/2012 01:32 PM, Alex Rønne Petersen wrote:
>>>> Hi,
>>>>
>>>> We currently have std.concurrency as a message-passing mechanism. We
>>>> encourage people to use it instead of OS threads, which is great.
>>>> However, what is *not* great is that spawned tasks correspond 1:1 to OS
>>>> threads. This is not even remotely scalable for Erlang-style
>>>> concurrency. There's a fairly simple way to fix that: Fibers.
>>>>
>>>> The only problem with adding fiber support to std.concurrency is that
>>>> the interface is just not flexible enough. The current interface is
>>>> completely and entirely tied to the notion of threads (contrary to what
>>>> its module description says).
>>>>
>>>> Now, I see a number of ways we can fix this:
>>>>
>>>> A) We completely get rid of the notion of threads and instead simply
>>>> speak of 'tasks'. This trivially allows us to use threads, fibers,
>>>> whatever to back the module. I personally think this is the best way to
>>>> build a message-passing abstraction because it gives enough
>>>> transparency
>>>> to *actually* distribute tasks across machines without things breaking.
>>>> B) We make the module capable of backing tasks with both threads and
>>>> fibers, and expose an interface that allows the user to choose what
>>>> kind
>>>> of task is spawned. I'm *not* convinced this is a good approach because
>>>> it's extremely error-prone (imagine doing a thread-based receive inside
>>>> a fiber-based task!).
>>>> C) We just swap out threads with fibers and document that the module
>>>> uses fibers. See my comments in A for why I'm not sure this is a good
>>>> idea.
>>>>
>>>> All of these are going to break code in one way or another - that's
>>>> unavoidable. But we really need to make std.concurrency grow up; other
>>>> languages (Erlang, Rust, Go, ...) have had micro-threads (in some form)
>>>> for years, and if we want D to be seriously usable for large-scale
>>>> concurrency, we need to have them too.
>>>>
>>>> Thoughts? Other ideas?
>>>>
>>>
>>> +1, but what about TLS?
>>
>> I think that no matter what we do, we have to simply say "don't do that"
>> to thread-local state (it would break in distributed scenarios too, for
>> instance).
>>
>> Instead, I think we should do what the Rust folks did: Use *task*-local
>> state and leave it up to std.concurrency to figure out how to deal with
>> it. It won't be as 'seamless' as TLS variables in D of course, but I
>> think it's good enough in practice.
>>
>
> If it is not seamless, we have failed. IMO the runtime should expose an
> interface for allocating TLS, switching between TLS instances and
> destroying TLS.

I suppose it could be done.

But keep in mind the side-effects of an approach like this: Some thread-local variables (for instance, think 'chunk' inside emplace) would break (or at least behave very weirdly) if you switch the *entire* TLS context when entering a task.

Sure, we could use the runtime interface for TLS switching only for task-local state, but then we're back to square one with it not being seamless.

>
> What about the stack? Allocating a fixed-size stack per task is costly
> and Walter opposes dynamic stack growth.

Yeah, I never understood why. It's essential for functional-style code running in constrained tasks. It's not just about conserving memory; it's to make recursion feasible.

In any case, fibers currently allocate PAGE_SIZE * 4 bytes for stacks.

-- 
Alex Rønne Petersen
alex@lycus.org
http://lycus.org
October 04, 2012
On 04-Oct-12 15:32, Alex Rønne Petersen wrote:
> Hi,
>
> We currently have std.concurrency as a message-passing mechanism. We
> encourage people to use it instead of OS threads, which is great.
> However, what is *not* great is that spawned tasks correspond 1:1 to OS
> threads. This is not even remotely scalable for Erlang-style
> concurrency. There's a fairly simple way to fix that: Fibers.
>
> The only problem with adding fiber support to std.concurrency is that
> the interface is just not flexible enough. The current interface is
> completely and entirely tied to the notion of threads (contrary to what
> its module description says).
>
> Now, I see a number of ways we can fix this:
>
> A) We completely get rid of the notion of threads and instead simply
> speak of 'tasks'. This trivially allows us to use threads, fibers,
> whatever to back the module. I personally think this is the best way to
> build a message-passing abstraction because it gives enough transparency
> to *actually* distribute tasks across machines without things breaking.

Cool, but currently it's a leaky abstraction. For instance if task is implemented with fibers static variables will be shared among threads.
Essentially I think Fibers need TLS (or rather FLS) synced with language 'static' keyword. Otherwise the whole TLS by default is a useless chunk of machinery.

> B) We make the module capable of backing tasks with both  threads and
> fibers, and expose an interface that allows the user to choose what kind
> of task is spawned. I'm *not* convinced this is a good approach because
> it's extremely error-prone (imagine doing a thread-based receive inside
> a fiber-based task!).
Bleh.

> C) We just swap out threads with fibers and document that the module
> uses fibers. See my comments in A for why I'm not sure this is a good idea.
Seems a lot like A but with task defined to be a fiber. I'd prefer this. However then it needs a user-defined policy for distributing fibers across real threads (pools). Btw A is full of this too.

> All of these are going to break code in one way or another - that's
> unavoidable. But we really need to make std.concurrency grow up; other
> languages (Erlang, Rust, Go, ...) have had micro-threads (in some form)
> for years, and if we want D to be seriously usable for large-scale
> concurrency, we need to have them too.
>
> Thoughts? Other ideas?
>
+1

-- 
Dmitry Olshansky
October 04, 2012
On 04-Oct-12 16:48, Timon Gehr wrote:
> On 10/04/2012 02:22 PM, Alex Rønne Petersen wrote:
>> On 04-10-2012 14:11, Timon Gehr wrote:
[snip]
>>
>> I think that no matter what we do, we have to simply say "don't do that"
>> to thread-local state (it would break in distributed scenarios too, for
>> instance).
>>
>> Instead, I think we should do what the Rust folks did: Use *task*-local
>> state and leave it up to std.concurrency to figure out how to deal with
>> it. It won't be as 'seamless' as TLS variables in D of course, but I
>> think it's good enough in practice.
>>
>
> If it is not seamless, we have failed. IMO the runtime should expose an
> interface for allocating TLS, switching between TLS instances and
> destroying TLS.
>
Agreed.

> What about the stack? Allocating a fixed-size stack per task is costly
> and Walter opposes dynamic stack growth.

Allocating a fixed-size stack is costly only in terms of virtual address space. Then running out of address space is of concern on 32-bits only. On 64 bits you may as well allocate 1 Gb per task it will only get reserved if it's used.

-- 
Dmitry Olshansky
October 04, 2012
On Thursday, October 04, 2012 13:32:01 Alex Rønne Petersen wrote:
> Thoughts? Other ideas?

std.concurrency is supposed to be designed such that it can be used for more than just threads (e.g. sending messages across the network), so if it needs to be adjusted to accomodate that, then we should do so, but we need to be careful to do it in a way that minimizes code breakage as much as reasonably possible.

- Jonathan M Davis
October 04, 2012
On Oct 4, 2012, at 4:32 AM, Alex Rønne Petersen <alex@lycus.org> wrote:

> Hi,
> 
> We currently have std.concurrency as a message-passing mechanism. We encourage people to use it instead of OS threads, which is great. However, what is *not* great is that spawned tasks correspond 1:1 to OS threads. This is not even remotely scalable for Erlang-style concurrency. There's a fairly simple way to fix that: Fibers.
> 
> The only problem with adding fiber support to std.concurrency is that the interface is just not flexible enough. The current interface is completely and entirely tied to the notion of threads (contrary to what its module description says).

How is the interface tied to the notion of threads?  I had hoped to design it with the underlying concurrency mechanism completely abstracted.  The most significant reason that fibers aren't used behind the scenes today is because the default storage class of static data is thread-local, and this would really have to be made fiber-local.  I'm reasonably certain this could be done and have considered going so far as to make the main thread in D a fiber, but the implementation is definitely non-trivial and will probably be slower than the built-in TLS mechanism as well.  So consider the current std.concurrency implementation to be a prototype.  I'd also like to add interprocess messaging, but that will be another big task.
October 04, 2012
On Oct 4, 2012, at 5:48 AM, Timon Gehr <timon.gehr@gmx.ch> wrote:
> 
> What about the stack? Allocating a fixed-size stack per task is costly and Walter opposes dynamic stack growth.

This is another reason I've been delaying using fibers.  The correct approach is probably to go the distance by reserving a large block, committing only a portion, and commit the rest dynamically as needed.  The current fiber implementation does have a guard page in some cases, but doesn't go so far as to reserve/commit portions of a larger stack space.
« First   ‹ Prev
1 2