Clean up inside gate.h

[AJ13]

Well, I get to be the jerk to call out a piece of very confusing code inside TBB. This master-piece took a half hour to understand, and I'm still very confused as to what this function does. Inside function:

void try_update( intptr_t value, intptr_t comparand, bool flip=false )

There is this gem:

if( flip ? old!=comparand : old==comparand )

It took me a while to parse out how a ternary-operator was being used within an if statement. Once that was out of the way, I am still very confused as to why try_update takes a flip argument at all... the documentation says this:

//! Update state=value if state==comparand (flip==false) or state!=comparand (flip==true)

I am still very confused... so this function seems to be something that will flip around the logic... complement perhaps. Why can't this be split into two functions? Is there a really good performance reason for doing this? I don't want to clean up code inside TBB that is like that for a very good reason... so other than possibly minimizing the size of the instruction cache, why is the function this way?

Thanks,

AJ

[Dmitry_Vyukov]

Quoting - Arch Robison (Intel)

If someone is planning to rewrite the entire snapshot/gate logic, here is what we want to accomplish in a scalable manner:

1. A thread should sleep if there is no task in the system to work on.

Do you mean that threads must sleep on depth levels > 0? Currently I am no sure whether it's worth doing... it will definitely substantially complicate implementation.

Quoting - Arch Robison (Intel)

If someone is planning to rewrite the entire snapshot/gate logic, here is what we want to accomplish in a scalable manner:

1. A thread should sleep if there is no task in the system to work on.
2. If a thread puts a task in its pool, and there are worker threads asleep, one of the workers should be woken up.

Your solution gets extra credit if when a task is mailed to another thread, (2) wakes up that thread. (1) may get more complicated if(1) takes into account the restrictions discussed for solving multiple pipeline deadlock.

What exactly do you mean here? If threads don't sleep on depth levels > 0, then employing can't affect blocking logic, because sleeping threads will be unemployed. And if threads do sleep on depth levels > 0, then I think it (depth) will be cause of most difficulties.

Quoting - Arch Robison (Intel)

You may gain or lose points for the number of ternary operators used, depending on who is grading.

:)

[Dmitry_Vyukov]

Quoting - Arch Robison (Intel)

If someone is planning to rewrite the entire snapshot/gate logic, here is what we want to accomplish in a scalable manner:

1. A thread should sleep if there is no task in the system to work on.
2. If a thread puts a task in its pool, and there are worker threads asleep, one of the workers should be woken up.

Your solution gets extra credit if when a task is mailed to another thread, (2) wakes up that thread. (1) may get more complicated if(1) takes into account the restrictions discussed for solving multiple pipeline deadlock.

You may gain or lose points for the number of ternary operators used, depending on who is grading.

Also the interesting case is spawning of a list of tasks - spawn( task_list& list ) - and some of that tasks can be mailed to some mailboxes. The straightfowrard approach will be to handle each task individually, just like there are N independent spawn( task& child ) calls. But this can be suboptimal.

And another interesting moment is interaction of mailboxes, blocking and employment. Spawning thread is unable to determine whether target thread will have right employer at the time of dequeueing of task from mailbox. So it is unable to correctly decide whether it has to wake up another thread or not. It can only make prediction based on current target thread's employer.

[ARCH_R_Intel]

To clarify: The worker hreads only have to sleep at depth levels <= 0. I.e., the conditions under which the current logic in task.cpp calls "wait_while_pool_is_empty()".

[AJ13]

Quoting - Alexey Kukanov (Intel)

Wanna become one of those scheduler mavens? :):)

Yes I do actually :-) Could I ask you to blog on this topic? I've enjoyed your previous blogs on concurrent_vector, and task cancellation. I would like to understand the internals of the scheduler in detail, and this post has answered some of my questions.

Also, judging by this thread I sense that others have no issue with try_update and the ternary function. I'm glad I stimulated a conversation anyways. Many open source projects feature commit reviews, and my intention was simply to review a part of code that I felt could have been better. I accept that the majority disagrees with me, and I'll learn your way :-)

[Alexey-Kukanov]

Quoting - AJ

Yes I do actually :-) Could I ask you to blog on this topic? I've enjoyed your previous blogs on concurrent_vector, and task cancellation. I would like to understand the internals of the scheduler in detail, and this post has answered some of my questions.

Honestly, I did not write any of those blog topics. I will deliver your praise to Anton and Andrey, though:)

Internals of the scheduler could be the subject of a whole lot of blog posts, but I amnot sure whether those would be of interest for many people. Answering questions at the forum gives me the feeling that I directly address the need of those who asked. Writing a blog post about scheduler internals full of technical details seems much less useful because there is nofeeling of matching the audience needs, so no reward.

Quoting - AJ

Also, judging by this thread I sense that others have no issue with try_update and the ternary function. I'm glad I stimulated a conversation anyways. Many open source projects feature commit reviews, and my intention was simply to review a part of code that I felt could have been better. I accept that the majority disagrees with me, and I'll learn your way :-)

Thanks. In fact, that piececode might be made better - through better documentation, or reimplementing it wholly, e.g. as Dmitry V. suggested.

[Dmitry_Vyukov]

Quoting - Alexey Kukanov (Intel)

Honestly, I did not write any of those blog topics. I will deliver your praise to Anton and Andrey, though:)

Alexey, you've already described the TBB scheduler ;)

http://www.intel.com/technology/itj/2007/v11i4/5-foundations/4-tbb.htm

Also the MUST READ info is Grandfather Cilk's "Scheduling Multithreaded Computations by Work Stealing":

http://supertech.csail.mit.edu/papers/steal.pdf