Re: [boost] Boost.Thread project for GSoC 2014

Subject: Re: [boost] Boost.Thread project for GSoC 2014
From: Haoyue Wang (whyzidane_at_[hidden])
Date: 2014-03-11 00:50:58

Hi Vicente,

A follow-up on your questions.

> Do you have an thread-safe implementation of a map? Which 
> synchronization mechanism do you use? The ones in Boost.Thread? Can you 
> send it to me privately?

I am aware of several ways of implementing lock-based thread safe unordered
map:

1) warp std::unordered_map in a class, and lock a method whenever it modifies
the underlying map. There is no need of lock for concurrent read. However,
this approach has little granularity and adding <key, value> must be executed
one at a time.

2) (CCIA 6.3.1.) Basically, unordered map in the raw form of
vector<list<pair<Key, Value> > > is implemented. Each list has a 
boost::shared_lock<boost::shared_mutex> to ensure nonexclusive
read access, and std::unique_lock<boost::shared_mutex> is used
to ensure exclusive write. Since each list has its corresponding
lock, there is more concurrency compared to 1).

3) Inspired by 1) and 2),  I am thinking a structure of
vector<map<Key, Value>>. For each map, there is a corresponding
std::mutex to ensure exclusive write access. Hash function is
used to distribute data pairs in different maps evenly. In preliminary tests,
I found 6 fold speed up when concurrent puts are tested on a 12
core machine. My implementation can be found at:
https://github.com/whyzidane/threadsafe_map

4) If the overhead of one lock per list node is acceptable,
implementation 2) can be more granulized.

> Do you know how to build on Boost? How to run tests? How to build a 
> quickbook?
I know how to use header-only Libraries and separately built libraries.
I haven't used Unit Test Framework-Boost and quickbook before. I can
learn them soon though. 

Best,
Haoyue

Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:

> 
> Le 07/03/14 06:16, Haoyue Wang a écrit :
> > Hi Vicente,
> >
> > Thanks for your detailed reply. Here is some more background about me.
> >
> >> Are you familiar with thread-safe lock based data-structures?
> > Yes. I am comfortable with the implementation and usage of thread-safe lock
> > based data structures such as queue, stack, list, and map.
> Do you have an thread-safe implementation of a map? Which 
> synchronization mechanism do you use? The ones in Boost.Thread? Can you 
> send it to me privately?
> >> lock-free data structures?
> > No. But I can learn <atomic> quickly.
> > Is lock-free data structures going to be used a lot for this project?
> The work-stealing thread pool would have less contention if we use a 
> lock-free dequeue. Of course, we can use Boost.LockFree if it provides 
> already whatever we need.
> >> Which compiler(s) are you using?
> > gcc 4.8/Apple LLVM version 5.0
> >> Which platform(s)?
> > Linux/Mac OS X
> >> Do you use already Boost?
> > Only a bit.
> Do you know how to build on Boost? How to run tests? How to build a 
> quickbook?
> >
> > Following your suggestion, I will proceed to implement a prototype of
> > a thread pool having specific queue for each thread that make use
> > of the sync_queue in Boost.Thread as part of my proposal. Hopefully,
> > it will be in shape next week.
> >
> Great.
> 
> Vicente
> > Best,
> > Haoyue
> >
> > Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
> >
> >> Le 06/03/14 04:06, Haoyue Wang a écrit :
> >>> Hi,
> >> Hi,
> >>> I am Haoyue, a PhD student in geophysics at MIT. I used C++11 to
> >>> write parallel finite element codes in my research and had some
> >>> coursework on concurrent programming.
> >>>
> >>> Boost is such a powerful and efficient library. I sincerely hope I could
> >>> contribute to it this summer and beyond.
> >>>
> >>> I am interested in the standalone GSoC Projects under Boost.Thread.
> >>> Particularly, the Work-Stealing-Thread-Pool project is a great one
> >>> that I expect to learn a lot from.
> >>>
> >>> I understand that there could be much more to discuss once I have
> >>> a preliminary proposal. Here I just want to ask if I am heading in
> >>> the right direction.
> >>>
> >>> I think a good point to start is chapter 6, 7, and 9 of the book C++
> >>> Concurrency in Action: Practical Multithreading and the Executors
> >>> and Schedulers revision 3 from http://www.open-std.org/.
> >> Yes, this is a good starting point.
> >>> I haven't used Executor before but I am ware of its existence in Java
> >>> for a while. Maybe I could go through some Executor and fork/join
> >>> Java examples to see how they are used in practice.
> >> I don't think this is a good idea. Why not start with the executors
> >> included in Boost.Thread library (develop/master branches)
> >>> Finally, I will read and understand the executors codes on GitHub.
> >> The executors directory included already some executors. One of them the
> >> basic_thread_pool is a good starting point. The work-stealing
> >> thread_pool could be based on it and the implementation provided in
> >> CCIA  9.1.5.
> >>> I hope I could put up a good first draft proposal next Monday.
> >>> If there is any advice, please let me know.
> >>>
> >>>
> >> I would need to know more about your background. Are you familiar with
> >> thread-safe lock based data-structures? lock-free data structures?
> >>
> >> Your first proposal should be as complete as possible and you will need
> >> to probe that you are knowledgeable of the problem domain, of Boost
> >> environment and of C++11.
> >> Showing a prototype of a thread pool having specific queue for each
> >> thread (See CCIA 9.1.4) that make use of the sync_queue in Boost.Thread
> >> would be really nice.
> >>
> >> Which compiler(s) are you using? Which platform(s)?
> >> Do you use already Boost?
> >>
> >> Best,
> >> Vicente
> >>
> >> _______________________________________________
> >> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
> >>
> >>
> >
> >
> >
> >
> > _______________________________________________
> > Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost