September 05, 2010 [phobos] Parallelism in Phobos | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | Filed, now that I understand shared a little better and you reminded
me about this.
On 9/5/2010 3:08 AM, Andrei Alexandrescu wrote:
> I think both are wrong for different reasons. Did you file them to Bugzilla already?
>
> Andrei
>
> On 07/31/2010 11:45 PM, David Simcha wrote:
>> Also, the following doesn't compile:
>>
>> class Foo {
>>
>> shared void bar() {}
>> }
>>
>> void main() {
>> shared(void delegate()) d;
>> auto foo = new Foo;
>> d = &foo.bar;
>> }
>>
>> Error: cannot implicitly convert expression (&foo.bar) of type void
>> delegate() to shared(void delegate())
>>
>> But the following does:
>>
>> class Foo {
>>
>> void bar() {}
>> }
>>
>> void main() {
>> shared(void delegate()) d;
>> auto foo = new Foo;
>> d = &foo.bar;
>> }
>>
>> If these are just plain bugs, let me know and I'll file them in Bugzilla, but right now I feel like they're more likely my lack of understanding of shared.
>>
>>
>> On 7/31/2010 7:31 AM, Andrei Alexandrescu wrote:
>>> Hello,
>>>
>>> Here's a belated answer to your question (hectic times prevented me from tending to non-urgent email).
>>>
>>> I think a parallel library would be great to have as indeed phobos is geared at general concurrency. Such a lib would also expose bugs and weaknesses in our model and its implementation.
>>>
>>> Andrei
>>>
>>> Sent by shouting through my showerhead.
>>>
>>> On May 30, 2010, at 12:54 PM, David Simcha <dsimcha at gmail.com <mailto:dsimcha at gmail.com>> wrote:
>>>
>>>> I have a few questions/comments about the possible inclusion of a library for parallelism in Phobos:
>>>>
>>>> 1. What is the status of std.concurrency? It's in the source tree, but it's not in the documentation or the changelogs. It appears to have been checked in quietly ~3 months ago, and I just noticed now.
>>>>
>>>> 2. From reading the description of std.concurrency in TDPL it seemed more geared toward concurrency (i.e. making stuff appear to be happening simultaneously, useful for things like GUIs and servers) rather than parallelism (i.e. the use of multiple CPU cores to increase throughput, useful for things like scientific computing and video encoding). It seems fairly difficult (though I haven't tried yet) to write code that's designed for pull-out-all-stops maximal performance on a multicore machine, especially since immutability is somewhat of a straight jacket. I find implicit sharing and the use of small synchronized blocks or atomic ops to be very useful in writing parallel programs.
>>>>
>>>> 3. Most code where parallelism, as opposed to concurrency, is the goal (at least most that I write) is parallelized in one or two small, performance critical sections, and the rest is written serially. Therefore, it's easy to reason about things and safety isn't as important as the case of concurrency-oriented multithreading over large sections of code.
>>>>
>>>> 4. I've been eating my own dogfood for awhile on my ParallelFuture
>>>> library. (http://cis.jhu.edu/~dsimcha/parallelFuture.html
>>>> <http://cis.jhu.edu/%7Edsimcha/parallelFuture.html>;
>>>> http://dsource.org/projects/scrapple/browser/trunk/parallelFuture/parallelFuture.d)
>>>>
>>>> It's geared toward throughput-oriented parallelism on multicore machines, not concurrency for GUIs, servers, etc. and is higher level than std.concurrency. Is there any interest in including something like this in Phobos? If so, would we try to make it fit into the explicit-sharing-only model, or treat it as an alternative method of multithreading geared towards pull-out-all-stops parallelism on multicore computers?
>>>>
>>>> One last note: Walter claimed a while back on the NG that
>>>> Parallelfuture doesn't compile. I use it regularly and it compiles
>>>> for me. Walter, can you please point out what the issue was?
>>>> _______________________________________________
>>>> phobos mailing list
>>>> phobos at puremagic.com <mailto:phobos at puremagic.com>
>>>> http://lists.puremagic.com/mailman/listinfo/phobos
>>>
>>>
>>> _______________________________________________
>>> phobos mailing list
>>> phobos at puremagic.com
>>> http://lists.puremagic.com/mailman/listinfo/phobos
>>
>>
>>
>> _______________________________________________
>> phobos mailing list
>> phobos at puremagic.com
>> http://lists.puremagic.com/mailman/listinfo/phobos
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
>
|
September 10, 2010 [phobos] Parallelism in Phobos | ||||
---|---|---|---|---|
| ||||
Posted in reply to David Simcha | Andrei, Does my decision that std.parallelism should be a "here be dragons" module and there's no reasonably way to make it safe make it a non-starter for you, or have you just not gotten around to reviewing it? --Dave On Sun, Sep 5, 2010 at 11:05 AM, David Simcha <dsimcha at gmail.com> wrote: > It doesn't use std.concurrency. It just uses core.thread. For now, > core.thread doesn't take a shared delegate, meaning it bypasses the entire > shared system. Sean said a while back that eventually it would start taking > a shared delegate. When it does, I'll simply cast the workLoop delegate to > shared, thus bypassing the entire shared system again. As the warning at > the top of the module states, it does subvert the type system to achieve > completely unchecked sharing, though this doesn't require relying on > implementation bugs, just unsafe casts. > > I've thought about this enough that I think trying to improve the type system to make this lib use something other than completely unchecked sharing, while still being useful for pedal-to-metal parallelism, is a lost cause at least for D2. *Maybe* it's do-able in D3. Even if it's technically do-able, I think it would make the library so inefficient and/or the API so obtuse that for something like this I feel strongly that unsafe "here be dragons" + @system is the right answer. Those that want a safe multithreading model can simply not use this module. > > I am completely in favor of std.parallelism coming w/ a huge warning on it, being @system as opposed to @trusted, and not being considered the "flagship" multhreading model. However, even TDPL mentions the possibility of using casts to achieve unchecked sharing, which is exactly what this module will do when core.thread starts taking shared delegates. If D is still supposed to be a systems language, I think dangerous, pedal-to-metal libraries like this have their place in Phobos, as long as it's clear that that's what they are. > > -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.puremagic.com/pipermail/phobos/attachments/20100910/3a305602/attachment.html> |
September 10, 2010 [phobos] Parallelism in Phobos | ||||
---|---|---|---|---|
| ||||
Posted in reply to David Simcha | The latter. Anyway, my vetoing abilities are largely overrated.
Andrei
On 9/10/10 13:16 CDT, David Simcha wrote:
> Andrei,
>
> Does my decision that std.parallelism should be a "here be dragons" module and there's no reasonably way to make it safe make it a non-starter for you, or have you just not gotten around to reviewing it?
>
> --Dave
>
> On Sun, Sep 5, 2010 at 11:05 AM, David Simcha <dsimcha at gmail.com <mailto:dsimcha at gmail.com>> wrote:
>
> It doesn't use std.concurrency. It just uses core.thread. For now,
> core.thread doesn't take a shared delegate, meaning it bypasses the
> entire shared system. Sean said a while back that eventually it
> would start taking a shared delegate. When it does, I'll simply
> cast the workLoop delegate to shared, thus bypassing the entire
> shared system again. As the warning at the top of the module
> states, it does subvert the type system to achieve completely
> unchecked sharing, though this doesn't require relying on
> implementation bugs, just unsafe casts.
>
> I've thought about this enough that I think trying to improve the
> type system to make this lib use something other than completely
> unchecked sharing, while still being useful for pedal-to-metal
> parallelism, is a lost cause at least for D2. *Maybe* it's do-able
> in D3. Even if it's technically do-able, I think it would make the
> library so inefficient and/or the API so obtuse that for something
> like this I feel strongly that unsafe "here be dragons" + @system is
> the right answer. Those that want a safe multithreading model can
> simply not use this module.
>
> I am completely in favor of std.parallelism coming w/ a huge warning
> on it, being @system as opposed to @trusted, and not being
> considered the "flagship" multhreading model. However, even TDPL
> mentions the possibility of using casts to achieve unchecked
> sharing, which is exactly what this module will do when core.thread
> starts taking shared delegates. If D is still supposed to be a
> systems language, I think dangerous, pedal-to-metal libraries like
> this have their place in Phobos, as long as it's clear that that's
> what they are.
>
>
>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
|
September 10, 2010 [phobos] Parallelism in Phobos | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On Fri, Sep 10, 2010 at 2:20 PM, Andrei Alexandrescu <andrei at erdani.com>wrote: > The latter. Anyway, my vetoing abilities are largely overrated. > > Andrei > Yeah, it's just that I really want to make sure this lib isn't too narrowly tailored to scientific computing cases, especially in easily fixable ways. I want at least the high level design reviewed by you and Sean before I commit it, to make sure that it will be useful to people besides me, Lars Kyllingstad and Rob Jacques (the three scientific computing people involved with D, all of whom seem to like this library). I have yet to really have feedback from anyone anywhere about it besides scientific computing people. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.puremagic.com/pipermail/phobos/attachments/20100910/fdc9c48b/attachment.html> |
September 10, 2010 [phobos] Parallelism in Phobos | ||||
---|---|---|---|---|
| ||||
Posted in reply to David Simcha | Le 2010-09-10 ? 14:29, David Simcha a ?crit : > I have yet to really have feedback from anyone anywhere about it besides scientific computing people. Well, I'm not sure how useful is this feedback, but I want to say that the task-based approach you've implemented can be very useful for GUI applications that want to do something in the background. I'm working on such an application right not, it's not in D unfortunately so I can't test your library with it, but the pattern is always like this: main thread: start_task(&task, data, object_to_notify_in_main_thread) task (data, object_to_notify_in_main_thread): perform some operation with data (often IO operations) notify_in_main_thread(object, results) main thread: event loop receives notification and calls some function on the object So at first glance it seems your library implements the right pattern for me, at least the first part: spawning a task. The second part, the notify_in_main_thread operation, basically sends a message to the main thread's event loop that then calls some function on the given object. That said, on OS X I would probably try to use the system's built-in task library (libdispatch, or Cocoa's NSOperation) as it'll use feedback from the kernel to better manage the load (taking into account the load from other running processes and whether some tasks threads are blocked on IO to tell whether new threads should be spawned). So the question is: how easy would it be to use a different backend for the thread pool when you want it? -- Michel Fortin michel.fortin at michelf.com http://michelf.com/ |
September 10, 2010 [phobos] Parallelism in Phobos | ||||
---|---|---|---|---|
| ||||
Posted in reply to Michel Fortin | As far as I can tell, your needs might be better served by
std.concurrency.
On 9/10/2010 4:21 PM, Michel Fortin wrote:
> Le 2010-09-10 ? 14:29, David Simcha a ?crit :
>
>> I have yet to really have feedback from anyone anywhere about it besides scientific computing people.
> Well, I'm not sure how useful is this feedback, but I want to say that the task-based approach you've implemented can be very useful for GUI applications that want to do something in the background. I'm working on such an application right not, it's not in D unfortunately so I can't test your library with it, but the pattern is always like this:
>
> main thread:
> start_task(&task, data, object_to_notify_in_main_thread)
>
> task (data, object_to_notify_in_main_thread):
> perform some operation with data (often IO operations)
> notify_in_main_thread(object, results)
>
> main thread:
> event loop receives notification and calls some function on the object
>
> So at first glance it seems your library implements the right pattern for me, at least the first part: spawning a task. The second part, the notify_in_main_thread operation, basically sends a message to the main thread's event loop that then calls some function on the given object.
>
> That said, on OS X I would probably try to use the system's built-in task library (libdispatch, or Cocoa's NSOperation) as it'll use feedback from the kernel to better manage the load (taking into account the load from other running processes and whether some tasks threads are blocked on IO to tell whether new threads should be spawned).
>
> So the question is: how easy would it be to use a different backend for the thread pool when you want it?
>
|
September 10, 2010 [phobos] Parallelism in Phobos | ||||
---|---|---|---|---|
| ||||
Posted in reply to David Simcha | Le 2010-09-10 ? 17:13, David Simcha a ?crit : > As far as I can tell, your needs might be better served by std.concurrency. From what I can see, your parallel foreach is basically some syntactic sugar for queuing tasks inside a loop and then to block until the result is ready. While I'll admit I'm not sure I need that sugar or to block waiting for the result, queuing tasks in a loop is certainly something I need. With my app I can easily have 1000 of these tasks queued at a given time (I effectively have a couple of loops that can add tasks to a queue). They mostly read and parse files to extract some pieces of data. At the API level, std.concurency looks like it could do that, except it'd be creating one thread for each task. I don't want to create one thread for each task, so I need some sort of task queue and a thread pool. But maybe you're right, and maybe the thread pool should go in std.concurrency where creating and queuing a task could work like spawning a thread, perhaps like this: // send task to a specific thread to be executed there tid.perform(&taskFunc, "hello world"); // queue task for execution in a thread pool tpool.dispatch(&taskFunc, "hello world"); Those two things I'd find quite useful. And it'd be pretty much trivial to build a parallel foreach on top of this. And just to add weight to the argument that task based concurrency is used pretty much everywhere: I worked before on some industrial software that had this too. It basically had to perform some analysis every time new data came in, in real-time. A new task was created for each piece of data and dispatched to a thread pool, then a few seconds later the result was sent to another thread that'd take some action based on the analysis. -- Michel Fortin michel.fortin at michelf.com http://michelf.com/ |
September 10, 2010 [phobos] Parallelism in Phobos | ||||
---|---|---|---|---|
| ||||
Posted in reply to Michel Fortin | On 9/10/2010 8:05 PM, Michel Fortin wrote: > Le 2010-09-10 ? 17:13, David Simcha a ?crit : > >> As far as I can tell, your needs might be better served by std.concurrency. > > From what I can see, your parallel foreach is basically some syntactic sugar for queuing tasks inside a loop and then to block until the result is ready. While I'll admit I'm not sure I need that sugar or to block waiting for the result, queuing tasks in a loop is certainly something I need. It's slightly more complicated than that under the hood because: 1. If your range has a huge amount of stuff, you want to lazily add it to the queue, not add it all upfront. Parallel foreach does some magic under the hood so that you can parallel foreach over a range of size N in O(1) memory even if you want small work units. Modulo the workaround for a Linux-specific compiler bug, parallel foreach doesn't even heap allocate. 2. The parallel foreach works with non-random access ranges by buffer data for small work units in an array. > With my app I can easily have 1000 of these tasks queued at a given time (I effectively have a couple of loops that can add tasks to a queue). They mostly read and parse files to extract some pieces of data. At the API level, std.concurency looks like it could do that, except it'd be creating one thread for each task. I don't want to create one thread for each task, so I need some sort of task queue and a thread pool. > > But maybe you're right, and maybe the thread pool should go in std.concurrency where creating and queuing a task could work like spawning a thread, perhaps like this: > > // send task to a specific thread to be executed there > tid.perform(&taskFunc, "hello world"); > > // queue task for execution in a thread pool > tpool.dispatch(&taskFunc, "hello world"); > > Those two things I'd find quite useful. And it'd be pretty much trivial to build a parallel foreach on top of this. This is getting me thinking. I've given up making most of std.parallelism safe. Parallel foreach is the hardest thing to make safe, and for me personally the most useful part of std.parallelism. I wonder, though, if I can make Task @safe/@trusted provided: 1. The input args are either indirection-free, immutable, or shared. 2. The callable is a function pointer, not a delegate, alias or class with overloaded opCall. 3. The return type is either indirection-free, immutable or shared. (This is, unfortunately, necessary b/c the worker thread could in theory hold onto a reference to it in TLS after returning, even though doing so would be thoroughly idiotic in most cases.) I'm thinking I may add a safeTask() function that is marked @trusted, and creates a Task object iff these constraints are satisfied (and otherwise doesn't compile). I think the only sane way to do this is to have a separate safe function for creating tasks in addition to the more lenient "here be dragons" one. The only major thing I don't like about this is the idea of sprinkling a few safe functions in a mostly "here be dragons" module. It seems like it would complicate code reviews. > And just to add weight to the argument that task based concurrency is used pretty much everywhere: I worked before on some industrial software that had this too. It basically had to perform some analysis every time new data came in, in real-time. A new task was created for each piece of data and dispatched to a thread pool, then a few seconds later the result was sent to another thread that'd take some action based on the analysis. Glad to hear that this might be useful outside scientific computing. |
September 10, 2010 [phobos] Parallelism in Phobos | ||||
---|---|---|---|---|
| ||||
Posted in reply to David Simcha | Le 2010-09-10 ? 21:01, David Simcha a ?crit : > This is getting me thinking. I've given up making most of std.parallelism safe. Parallel foreach is the hardest thing to make safe, and for me personally the most useful part of std.parallelism. I wonder, though, if I can make Task @safe/@trusted provided: > > 1. The input args are either indirection-free, immutable, or shared. > > 2. The callable is a function pointer, not a delegate, alias or class with overloaded opCall. Couldn't it be a shared delegate too (a delegate to a shared member)? > 3. The return type is either indirection-free, immutable or shared. (This is, unfortunately, necessary b/c the worker thread could in theory hold onto a reference to it in TLS after returning, even though doing so would be thoroughly idiotic in most cases.) > > I'm thinking I may add a safeTask() function that is marked @trusted, and creates a Task object iff these constraints are satisfied (and otherwise doesn't compile). I think the only sane way to do this is to have a separate safe function for creating tasks in addition to the more lenient "here be dragons" one. The only major thing I don't like about this is the idea of sprinkling a few safe functions in a mostly "here be dragons" module. It seems like it would complicate code reviews. Perhaps the safe parts of tasks and thread pools could be put in std.concurrency, and the unsafe parts necessary for std.parallelism could be built on top of it and reside std.parallelism (which could just cast its delegates to shared delegates to bypass the safeties). -- Michel Fortin michel.fortin at michelf.com http://michelf.com/ |
September 17, 2010 [phobos] Parallelism in Phobos | ||||
---|---|---|---|---|
| ||||
Posted in reply to Michel Fortin | Ok, I've added support for safe tasks as an overload. Basically, in
@system mode tasks allow unsafe sharing, but in @safe mode they have the
same requirements as std.concurrency.
I've also added ref return for tasks.
Can we please get this module reviewed? I'd really like to get it into the next release (i.e. 2.050, not 2.049, which is already in beta.)
On 9/10/2010 9:31 PM, Michel Fortin wrote:
> Le 2010-09-10 ? 21:01, David Simcha a ?crit :
>
>> This is getting me thinking. I've given up making most of std.parallelism safe. Parallel foreach is the hardest thing to make safe, and for me personally the most useful part of std.parallelism. I wonder, though, if I can make Task @safe/@trusted provided:
>>
>> 1. The input args are either indirection-free, immutable, or shared.
>>
>> 2. The callable is a function pointer, not a delegate, alias or class with overloaded opCall.
> Couldn't it be a shared delegate too (a delegate to a shared member)?
>
>> 3. The return type is either indirection-free, immutable or shared. (This is, unfortunately, necessary b/c the worker thread could in theory hold onto a reference to it in TLS after returning, even though doing so would be thoroughly idiotic in most cases.)
>> I'm thinking I may add a safeTask() function that is marked @trusted, and creates a Task object iff these constraints are satisfied (and otherwise doesn't compile). I think the only sane way to do this is to have a separate safe function for creating tasks in addition to the more lenient "here be dragons" one. The only major thing I don't like about this is the idea of sprinkling a few safe functions in a mostly "here be dragons" module. It seems like it would complicate code reviews.
> Perhaps the safe parts of tasks and thread pools could be put in std.concurrency, and the unsafe parts necessary for std.parallelism could be built on top of it and reside std.parallelism (which could just cast its delegates to shared delegates to bypass the safeties).
>
|
Copyright © 1999-2021 by the D Language Foundation