[spinlock] concurrent_unordered_map is ready for review
Dear Boost, CC: Howard, Jonathan for N3645 enhancements It has taken me far longer than I expected, however I believe that proposed boost::concurrent_unordered_map is ready for community feedback, with its unit test suite passing all green on the thread sanitiser and 92% coverage including exception safety tests. The main documentation page with the API and a lengthy explanation of the caveats in this design can be viewed at https://ci.nedprod.com/view/Boost%20Thread-Expected-Permit/job/Boost.S pinlock%20Test%20Linux%20GCC%204.8/doxygen/classboost_1_1spinlock_1_1c oncurrent__unordered__map.html Performance improves linearly to CPU cores at a slope of about 0.9. I only have four core hardware available to me, if someone could tell me how it scales to eight cores or more I would be very interested. Source code is at https://github.com/ned14/boost.spinlock. Tested on GCC 4.8, clang 3.4 and VS2013. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
Interesting. I don't see the implementation in the repository -- have you pushed it yet? Am I looking in the right place? I at least don't see a separate file for the concurrent_unordered_map implementation. Is this by design? Looking forward to seeing the magic here. Cheers On Mon Sep 01 2014 at 11:39:13 PM Niall Douglas <s_sourceforge@nedprod.com> wrote:
Dear Boost,
CC: Howard, Jonathan for N3645 enhancements
It has taken me far longer than I expected, however I believe that proposed boost::concurrent_unordered_map is ready for community feedback, with its unit test suite passing all green on the thread sanitiser and 92% coverage including exception safety tests. The main documentation page with the API and a lengthy explanation of the caveats in this design can be viewed at https://ci.nedprod.com/view/Boost%20Thread-Expected-Permit/job/Boost.S pinlock%20Test%20Linux%20GCC%204.8/doxygen/classboost_1_1spinlock_1_1c oncurrent__unordered__map.html
Performance improves linearly to CPU cores at a slope of about 0.9. I only have four core hardware available to me, if someone could tell me how it scales to eight cores or more I would be very interested.
Source code is at https://github.com/ned14/boost.spinlock. Tested on GCC 4.8, clang 3.4 and VS2013.
Niall
-- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost
Nevermind -- I see it in spinlock.hpp. Looking now. On Mon Sep 01 2014 at 11:42:59 PM Dean Michael Berris < mikhailberis@gmail.com> wrote:
Interesting. I don't see the implementation in the repository -- have you pushed it yet? Am I looking in the right place? I at least don't see a separate file for the concurrent_unordered_map implementation. Is this by design?
Looking forward to seeing the magic here.
Cheers
On Mon Sep 01 2014 at 11:39:13 PM Niall Douglas <s_sourceforge@nedprod.com> wrote:
Dear Boost,
CC: Howard, Jonathan for N3645 enhancements
It has taken me far longer than I expected, however I believe that proposed boost::concurrent_unordered_map is ready for community feedback, with its unit test suite passing all green on the thread sanitiser and 92% coverage including exception safety tests. The main documentation page with the API and a lengthy explanation of the caveats in this design can be viewed at https://ci.nedprod.com/view/Boost%20Thread-Expected-Permit/job/Boost.S pinlock%20Test%20Linux%20GCC%204.8/doxygen/classboost_1_1spinlock_1_1c oncurrent__unordered__map.html
Performance improves linearly to CPU cores at a slope of about 0.9. I only have four core hardware available to me, if someone could tell me how it scales to eight cores or more I would be very interested.
Source code is at https://github.com/ned14/boost.spinlock. Tested on GCC 4.8, clang 3.4 and VS2013.
Niall
-- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman /listinfo.cgi/boost
On 1 Sep 2014 at 13:45, Dean Michael Berris wrote:
Nevermind -- I see it in spinlock.hpp.
FYI it has messy source code because I expect it will be merged into some other Boost library. Also, because I very much personally favour weird source code formatting conventions no one else likes, but I do. Obviously it will all get clang style rewritten before entering Boost. You and others may find a description of the algorithm at https://plus.google.com/109885711759115445224/posts/KhbHhU5J19B of use. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
On Tue Sep 02 2014 at 1:23:23 AM Niall Douglas <s_sourceforge@nedprod.com> wrote:
On 1 Sep 2014 at 13:45, Dean Michael Berris wrote:
Nevermind -- I see it in spinlock.hpp.
FYI it has messy source code because I expect it will be merged into some other Boost library. Also, because I very much personally favour weird source code formatting conventions no one else likes, but I do.
That's fine, I can deal with weird formatting issues. Thankfully github has nice syntax highlighting features for making at least the code stand out from the comments.
Obviously it will all get clang style rewritten before entering Boost.
Do you intend this to be a separate library, or would it go into something like Boost.Container?
You and others may find a description of the algorithm at https://plus.google.com/109885711759115445224/posts/KhbHhU5J19B of use.
Awesome, I'll give that a read. I suspect this is very nice to dig into because it's using the new hotness (transactional memory, and C++11 atomics). Cheers
On 1 Sep 2014 at 15:27, Dean Michael Berris wrote:
Do you intend this to be a separate library, or would it go into something like Boost.Container?
Not sure yet. My next goal is no-alloc promise-future, also based on spinlocks. I don't intend to "finish" concurrent_unordered_map past what is already done, and I suspect no Boost library will accept it until I or someone else does. I do intend to develop a partial C++ 11 STL to Boost shim library, so one no longer needs the rest of Boost to use Boost.Thread standalone for example. That way we can push Boost.Thread ahead without needing Boost.
You and others may find a description of the algorithm at https://plus.google.com/109885711759115445224/posts/KhbHhU5J19B of use.
Awesome, I'll give that a read. I suspect this is very nice to dig into because it's using the new hotness (transactional memory, and C++11 atomics).
I originally started expecting to make great use of Intel TSX. Read this list's archives for how badly that fared. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
On 9/1/2014 12:35 PM, Niall Douglas wrote:
On 1 Sep 2014 at 15:27, Dean Michael Berris wrote:
Do you intend this to be a separate library, or would it go into something like Boost.Container?
Not sure yet. My next goal is no-alloc promise-future, also based on spinlocks.
I don't intend to "finish" concurrent_unordered_map past what is already done, and I suspect no Boost library will accept it until I or someone else does.
What do you mean by the last part of your sentence ?
On 1 Sep 2014 at 15:41, Edward Diener wrote:
Do you intend this to be a separate library, or would it go into something like Boost.Container?
Not sure yet. My next goal is no-alloc promise-future, also based on spinlocks.
I don't intend to "finish" concurrent_unordered_map past what is already done, and I suspect no Boost library will accept it until I or someone else does.
What do you mean by the last part of your sentence ?
I'm not sure what is unclear in the sentence. concurrent_unordered_map is missing things like all const overloads and iterators (they are aliased to non-const, so code compiles), or C++03 support, or local iterators or container copy and move support. Noexcept is always on too instead of being conditional. But I have no personal need for all that, and I need to get on with other things, so I leave it where it is at - it is still extremely useful, the code is of a very high quality and is extremely well unit tested, it scales linearly to CPU cores and it solves the problem of concurrent unordered maps without breaking STL compatibility or semantics, so concurrent erase finally works, unlike most other implementations! I hope a GSoC student finishes it in 2015 or 2016, but for me it's enough for me to move on, so I am. You will hear what I will be doing next later today in fact. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
Niall Douglas wrote
On 1 Sep 2014 at 15:41, Edward Diener wrote:
Do you intend this to be a separate library, or would it go into something like Boost.Container?
Not sure yet. My next goal is no-alloc promise-future, also based on spinlocks.
I don't intend to "finish" concurrent_unordered_map past what is already done, and I suspect no Boost library will accept it until I or someone else does.
I hope a GSoC student finishes it in 2015 or 2016, but for me it's enough for me to move on, so I am. You will hear what I will be doing next later today in fact.
What do you mean by "ready for review" exactly? Robert Ramey -- View this message in context: http://boost.2283326.n4.nabble.com/spinlock-concurrent-unordered-map-is-read... Sent from the Boost - Dev mailing list archive at Nabble.com.
On Tue, Sep 2, 2014 at 10:32 AM, Robert Ramey wrote:
What do you mean by "ready for review" exactly?
While the thread subject [now] confuses me also: Was the motivation for the thread to find someone who is interested in improving this concurrent_unordered_map implementation such that it would be accepted into some Boost library? Glen
On 2 Sep 2014 at 13:10, Glen Fernandes wrote:
On Tue, Sep 2, 2014 at 10:32 AM, Robert Ramey wrote:
What do you mean by "ready for review" exactly?
While the thread subject [now] confuses me also: Was the motivation for the thread to find someone who is interested in improving this concurrent_unordered_map implementation such that it would be accepted into some Boost library?
A number of people on this list were interested in knowing when I felt concurrent_unordered_map was ready for production use, and the algorithmic design I finally settled upon which is quite a mongrel. Posting here was the easiest way of doing that, and I am working with a number of people off-list who emailed me privately after the announcement. I also welcome comments on its algorithm and its choices of design tradeoffs here, as it is unconventional. I have no intention of submitting it for inclusion into the Boost libraries. A GSoC student can do that next year, he/she would benefit far more from the experience than I. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
On 2 Sep 2014 at 10:32, Robert Ramey wrote:
I don't intend to "finish" concurrent_unordered_map past what is already done, and I suspect no Boost library will accept it until I or someone else does.
I hope a GSoC student finishes it in 2015 or 2016, but for me it's enough for me to move on, so I am. You will hear what I will be doing next later today in fact.
What do you mean by "ready for review" exactly?
For those interested in a concurrent_unordered_map to comment on the design. Especially as it's a unique design compared to all the others as it can concurrent erase. I don't intend to submit it for Boost review to enter the Boost libraries. The feedback would be to finish the missing parts. I know that already. Besides, I'll be announcing the development of a major new Boost library probably next week which hopefully will have 2.5 full time developers on it, I'll be asking here and on the ASIO mailing list for feedback on the design which some would call "radical" seeing as it's all C++14 and integrates the proposed monadic continuations framework based on expected<T, E> with the future C++ 17 Networking library ASIO so it's all seamless. If you remember me saying to you Robert about a forthcoming easy programming generic DSEL for AFIO/ASIO/futures/all async in C++, the ball is finally rolling on that, assuming funding remains in place for it. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
Le 01/09/14 15:38, Niall Douglas a écrit :
Dear Boost,
CC: Howard, Jonathan for N3645 enhancements
Is this related to http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3732.pdf? Best, Vicente
On 1 Sep 2014 at 18:53, Vicente J. Botet Escriba wrote:
Dear Boost,
CC: Howard, Jonathan for N3645 enhancements
Is this related to http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3732.pdf?
If you're talking about my concurrent_unordered_map, then no I haven't implemented N3732 as that is a "post-STL" map API proposal i.e. such a container would not be STL compatible. My concurrent_unordered_map exactly follows the API of std::unordered_map, with all the same guarantees apart from the complexities of empty() and size(), so iterators work as expected etc. It should be drop in replaceable, and with little to no performance cost in single threaded usage either apart from empty() and size() being expensive. If you're talking about N3645 enhancements, they are different. N3645 adds new functions to the map API allowing one to, with very low overhead, detach items from one map and insert them into another, or to move allocation and deallocation of nodes outside any serialisation, thus enabling very low latency usage of containers shared between threads. concurrent_unordered_map already moves almost all memory allocation outside of locks, and in fact internally is implemented using the N3645 API i.e. insert/erase/emplace are all just convenience wrappers for the N3645 API. Consider N3645 more as a "map fundamentals" API from which the STL map containers can be constructed. I personally found it very valuable, and I would strongly recommend its immediate inclusion into the next Library TR from WG21. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
participants (6)
-
Dean Michael Berris -
Edward Diener -
Glen Fernandes -
Niall Douglas -
Robert Ramey -
Vicente J. Botet Escriba