Re: [boost] [gsoc-2013] Boost.Thread/ThreadPool project

I have to admit I'm struggling to see where your block is, but Dave Abrahams often found the same with me, so it must be me. A central asynchronous dispatcher is the loop which sends callbacks/events to be invoked/processed by other execution contexts. Every OS has at least one in the kernel. Most GUI toolkits like Qt have one. Boost has at least one in the form of Boost.ASIO. The central means one execution context does the dispatch. The asynchronous means that callbacks are processed by recipients asynchronous to the dispatcher. And dispatcher, well that dispatches. the
Multi-word Compare-And-Swap (MCAS) is one of the biggest gains from Transactional Memory. Indeed WG21 has SG5 dedicated to integrating TM into C++17. Some models of Intel's Haswell come with hardware TM assist. I'd take a reasonable guess that MCAS will benefit centralized kernel-based threading primitives architectures such as Windows NT more than decentralized threading primitive architectures such as POSIX. That said, I could see Linux using TM for batch multi-kernel-futex ops, though I'd have to say implementing that without breakage would be daunting. Either way, a central asynchronous dispatcher has information a decentralized implementation does not. That opens more scope for optimization.
Boost.ASIO provides a per-thread capable event loop implementation. That automatically makes it an example of a thread pool manager. You may find N3562 Executors and schedulers coproposed March 2013 for Bristol by Google and Microsoft of use to you in understanding the relation between thread pools and Boost.ASIO (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3562.pdf). My proposed Boost.AFIO library is an implementation of that same N3562 idea, albeit I extend Boost.ASIO which is IMHO more C++-y whereas Google and Microsoft have gone with proprietary implementations. Also, they include timing and many other more general purpose features, and mine does not (currently) as it's mainly aimed at maximising input/ouput with highly jittery random latency storage. Niall --- Opinions expressed here are my own and do not necessarily represent those of BlackBerry Inc.

Le 01/05/13 20:39, Niall Douglas a écrit : the exchange here if you prefer, or you could continue to explaining me the things I don't know/understand.
In order to be sure I understand what you say could you tell me how a decentralized asynchronous dispatcher behaves? What are the differences?
Are you saying that current TM technology should be much more useful for centralized than decentralized asynchronous dispatchers? Does this means that the whole application would improve its performances using always centralized asynchronous dispatchers?
I know this proposal. Could you explain me how it is related to Boost.Asio? Could you point me where in the Asio documentation could I find related information?
Thanks Niall for all the explanations and sorry if all this is trivial for you. Vicente

Le 01/05/13 23:08, Vicente J. Botet Escriba a écrit :
I have just read N3388 - Using Asio with C++11 and a think I start to understand the ASIO design. Could we say the completion handlers are continuations? And that the user use to master which thread executes the continuation by calling the io_service::run() function? And that io_service can have associated also several threads (to form a thread pool). And that in order to avoid data races the user uses strands to serialize the completion handlers that have access to shared data? While continuation passing style could be well adapted to protocols (and surely it is) , there are other domains that would prefer to write his code in a more linear way. It is true that with C++11 lambdas the continuation passing style is less opaque. I hope that now I would be able to understand your concerns better. Vicente

Hello, I have updated my proposal following your guide and tried to answer and give solution to most of the problems. I have tried to separate the interface with the implementation details so when choosing an interface a feature can be easily added by following the exact interface header so multiple implementations can be used without affecting the user(ex: scheduling algorithm for dynamic thereads, bounded/unbounded queues etc). I hope this approach is better. You can find the pdf version here [1]. The previous version of the proposal can be found here [2]. Thank you very much for the feedback, suggestions, guidance and the really fast answers. [1] http://danlincan.3owl.com/gsoc/final-proposal.pdf [2] http://danlincan.3owl.com/gsoc/Proposal.pdf Regards, Dan

Le 02/05/13 11:58, Dan Lincan a écrit :
Hi Dan,
*The new proposal contains:*
*Waitable tasks*
This feature gives the user the option to wait for a task to finish and
retrieve its result.
Drawback is that maybe the user is not interested in the result of the task.
Interface
template

Hi Vincente,
I'm sorry but I can't give you proper answers now because l don't have
internet access on my computer at my current location. I will get back home
in 2 days.
Regards,
Dan
On May 2, 2013 6:16 PM, "Vicente J. Botet Escriba"

What techniques from boost::async() are you referring to?
Well I thought about adding priorities this way to achieve close to O(1) performance. I had in mind something similar to counting sort. As long as we know that we have at most x priorities level ( in this case x=3: low, medium, high ), we can store the tasks in an array of containers(queue/lock-free queue/others) so submitting a task to the threadpool can be done in O(1). The only problem after this is having to deal with fair scheduling. This can be done in O(1) too so O(1) performance overall.
This is what I had in mind with this feature. I should have been more clear as this is the reason I have added [1] as reference.
Then I would prefer the first alternative, extending boost::future. For the user it would be really nice to use just result.interrupt() where result is a future.
I will search it and get back with an answer. [1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3558.pdf Regards, Dan

Dan wrote on Thursday, May 2, 2013 at 13:58:35:
Hello,
You can find the pdf version here [1]. The previous version of the proposal can be found here [2].
Thank you very much for the feedback, suggestions, guidance and the really fast answers.
[1] http://danlincan.3owl.com/gsoc/final-proposal.pdf [2] http://danlincan.3owl.com/gsoc/Proposal.pdf
perhaps not _this_ time, that is not this 2013 GSOC, but eventually you may want to consider a lock-free priority queue algorithm for storing tasks and not use locks although lock-free algorithms are somewhat hard to comprehend, all the more so about _priority_ queues, but in the end that's, beside other things, what one would expect from modern implementation of thread pool moreover, you, as a student loving algorithms and analysis, may like to dig into the lock-free algorithms in general good luck -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out

Vicente wrote on Thursday, May 2, 2013 at 22:40:06:
dan write in his proposal (the first link above) about task scheduling priority and that the implementation may require a priority queue with locks i just pointed out that it will be interesting to use particularly lock-free priority queue for that purpose instead of locking algorithm certainly, if boost.lockfree already had priority queue, one must have been (re)used that implementation, and in fact it's a pity that boost.lockfree hasn't one (as well as some kind of map/set) as for priority task scheduling -- i consider it an essential feature of a threadpool facility that certainly should be there and yes, boost absolutely needs a threadpool implementation i hope this project will be a good start -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out

Hi Pavel, I have read a bit about lock-free data structures in Concurrency in Action by Anthony Williams. Depending on the frozen interfaces and the time on hand I will most likely implement and do some performance tests for lock-free queues. Thank you, Dan

Hi Vincente,
On Wed, May 1, 2013 at 11:42 PM, Vicente J. Botet Escriba
Pretty much, except that multiple threads can call io_service::run concurrently. Basically Boost.Asio is a work sharing queue plus a collection of waitqueues to wait for specific events.
And that io_service can have associated also several threads (to form a thread pool).
The associated threads are exactly those that are currently calling io_service::run.
And that in order to avoid data races the user uses strands to serialize the completion handlers that have access to shared data?
That's one way, but not the only way.
That's orthogonal. Boost.Asio provides the funding blocks. A nicer interface that doesn't require an explicit continuation passing style transformation can be built with Boost.Context or a similar library. But it probably needs a future implementation that integrates with ASIO, which is one of the point of Niall Douglas. See the recent discussion about "library support for async/await pattern". -- gpd
participants (5)
-
Dan Lincan
-
Giovanni Piero Deretta
-
Niall Douglas
-
pavel
-
Vicente J. Botet Escriba