std.parallelism changes done

Sönke Ludwig ludwig at informatik.uni-luebeck.de
Fri Mar 25 02:33:17 PDT 2011


Am 25.03.2011 05:14, schrieb dsimcha:
> On 3/24/2011 10:21 PM, Sönke Ludwig wrote:
>>>
>>> Can you elaborate and/or provide an example of the "general" problem?
>>> I'm not quite sure what you're getting at.
>>
>> I have one very specific constellation that I can only sketch.. Suppose
>> you have some kind of complex computation going on in the ThreadPool.
>> This computation is done by a large set of tasks where each tasks
>> depends on the result of one or more other tasks. One task is
>> responsible for coordinating the work - it is spawning tasks and waiting
>> for their completion to spawn new tasks for which the results are now
>> available.
>>
>
> As I've said before in related discussions, you are _probably_ better
> off using one of the high level primitives instead of using tasks
> directly in these cases. If not, I'd prefer to improve the higher level
> primitives and/or create new ones if possible. (Feel free to suggest one
> if you can think of it.) Tasks are, IMHO, too low level for anything
> except basic future/promise parallelism and implementing higher level
> primitives. Incidentally the situation you describe (a coordinator task
> creating lots of worker tasks) is exactly how amap(), reduce() and
> parallel foreach work under the hood. This complexity is completely
> encapsulated, though.

I would certainly agree that this belongs to a higher level structure. 
This structure would basically get a set of special tasks, where each of 
those tasks has a list of all the tasks it depends on. All tasks would 
then be executed in parallel on a thread pool in on order that 
statisfies their dependencies - possibly with some form of cost function 
that controls which task should come first if there are multiple orders 
possible.

One problem here is for example that for the system I have here, I need 
to execute several tasks in the main thread by sending a message to it 
(the main thread executes window messages in a loop). Specifically this 
is for tasks that use OpenGL or a similar API that has a single thread 
assigned - and the main thread is the most efficient one to use because 
it already has an OpenGL context.

The important thing is to either support such things or to make it 
general enough to let the user add it from the outside. Otherwise if you 
really need such things, the only option is to completely use a custom 
thread pool and thins means no parallel for, map, reduce and whatever 
might be added later.

>
>> First thing here is that you do not want to do the waitForce() kind of
>> waiting in the coordinator task because this might cause the coordinator
>> to be busy with an expensive taks while it could already spawn new tasks
>> because maybe in the meantime some other tasks have already finished.
>
> I assume you mean yieldForce().

Yes, sorry, got the names mixed up.

>
>>
>> However, if you wait for a condition variable instead (which is fired
>> after each finished task) and if you can have multiple computations of
>> this kind running in parallel, you can immediately run into the
>> situation that the thread pool is crowded with coordinator tasks that
>> are all waiting for their condition variables which will never be
>> triggered because no worker tasks can be executed.
>
> I assume you're talking about a condition variable other than the one
> yieldForce() uses. As mentioned previously, in the specific case of
> yieldForce() this is a solved problem. In the general case I can see the
> problem.
>

Yes, just the general problem with other condition variables.

>>
>> This is only one example and basically this problem can arise in all
>> cases where one task depends on another task by some form of waiting
>> that will not execute the dependency like waitForce() does.
>
> Hmm, ok, I definitely understand the problem now.
>
>>>> But what I wanted to say is, even if it may be difficult to implement
>>>> such thread caching now, putting means to execute a Task in its own
>>>> thread now into the ThreadPool allows for such an optimization later
>>>> (it
>>>> could even exist while still keeping Task.executeInNewThread()).
>>>
>>> I can't really comment because I still don't understand this very well.
>>
>> I hope I could make it a little more clear what I mean. The problem is
>> just that the system I'm talking about is quite complex and it's not
>> easy to find good and simple examples in that system. The problems of
>> course arise only in the most complex pathes of execution..
>>
>> What I'm not sure about is if executeInNewThread() is supposed to be
>> useful just because it is somtimes nice to have the fine-grained
>> parallelism of the OS scheduler as opposed to task granilarity, or if
>> the advantage is supposed to be efficiency gained because the thread
>> pool is not created. In the latter case the caching of some threads to
>> be reused for a executeInOwnThread()-method should lead to a better
>> performance in almost any case where thread creation overhead is
>> relevant.
>
> Ok, now I'm starting to understand this. Please correct me (once you've
> gotten a good night's sleep and can think again) wherever this is wrong:
>
> 1. As is currently the case, executeInNewThread() is _guaranteed_ to
> start the task immediately. There is never a queue involved.
>
> 2. Unlike the current implementation, executeInNewThread() may use a
> cached thread. It will **NOT**, however, put the task on a queue or
> otherwise delay its execution. If no cached thread is available, it will
> create a new one and possibly destroy it when the task is done.

Exactly.

>
> Thanks for this suggestion. Now that I (think I) understand it, it makes
> sense in principle. The devil may be in the details, though.
>
> 1. How many threads should be cached? I guess this could just be
> configurable with some reasonable default.

A configurable minimum number of threads sounds reasonable. The default 
could probably be a fixed small number like 1 or 2.

>
> 2. Should the cache be lazily or eagerly created? I'd assume lazily.

Lazy sounds good.

>
> 3. Where would these threads be stored? I think they probably belong in
> some kind of thread-safe global data structure, **NOT** in a TaskPool
> instance.

Thats a good question.. ThreadPool would be nice because it is the class 
of which maybe you are already dragging an instance through your code. 
Global would certainly work.

>
> 4. How would we explain to people what the cache is good for and how to
> use it? The fact that you're proposing it and even you find this
> difficult to convey makes me skeptical that this feature is worth the
> weight it adds to the API. Maybe you'll find it easier once you get some
> sleep. (I understand the problem it solves at an abstract level but have
> never encountered a concrete use case. It also took me a long time to
> understand it.)

I would basically just say its a faster way than to create a new thread 
each time you start a task. Use it whenever you need to have a task run 
outside of the thread pool threads - candidates are tasks that wait a 
lot, either because of IO or because of waiting primitives apart from 
the ones present in ThreadPool (message queues, condition variables).

But please don't make the mistake to dismiss the problem because it is 
complex. Beeing complex and maybe rare does not mean it cannot be 
important. Its like a bug that will delete your data but in very rare 
and complex use cases of the application. You would not want to ignore 
that just because of those reasons.

Also I'm not sure if using the primitives of std.concurrency is allowed 
within in a Task, maybe not. But if it is, it would be really easy to 
construct a higher level example without condition variables and stuff 
like that.

>
> 5. It would break some relaxations of what @safe tasks can do when
> started via executeInNewThread().

You mean because of TLS that is not reinitialized each time? I have to 
admit that I can't really gauge the impact of this.

>
> 6. This whole proposal might fit better in std.concurrency, by using a
> thread cache for spawn().

But isn't the previous problem (5.) even more relevant in 
std.concurrency? Putting it near ThreadPool could be a good idea because 
it still is some sort of thread pool in the abstract sense. It could 
also be something that std.concurrency uses for its spawn().

Anyway, I would be happy if there would be a place allocated for this 
wherever this fits. If it is std.concurrency, its fine as long as 
std.concurrency and std.parallelism play well together. One problem with 
std.concurrency is that it also does not really work well when you need 
to wait for other primitives than a message. To have something like 
WaitForMultipleObjects is critical in many cases, but thats another topic.

Having said all this, I just want to make sure that you don't get this 
wrong. I certainly to not want to push in complex changes for no reason 
and no complex changes at all for that matter. And in this case I see 
how it is _functionally_ independent from the ThreadPool itself.

My problem here is just that there is a executeInNewThread function that 
really should not be used for _many_ tasks and maybe in most other cases 
it would be cleaner to use spawn() - it may still have its place if you 
count in the @safe implications, but I would like to also see a function 
supporting the same threading guarantees but suitable for many tasks, if 
only to avoid bad usage patterns of executeInNewThread.

However it definitely is in the gray area between std.concurrency and 
std.parallelism.


More information about the Digitalmars-d mailing list