| 9 | | This year, 2015, is going to be slightly different from preceding years of how Boost has operated GSoC. The first new change was that last year we trialled extending the really superb GSoC 2014 projects by an additional three month period funded by Boost, and in 2014 the project we selected for extension was [https://ldionne.github.io/hana/ proposed Boost.Hana] by student Louis Dionne mentored by Joel Falcou. If these extensions prove successful, we may continue to extend the really outstanding GSoC projects from 2015. Note that the Boost Steering Committee can only consider extensions where the mentor is more than happy to continue mentoring the project in an extension, and where the GSoC administrators and the other GSoC mentors and Boost Steering Committee members all unanimously agree on the merit of the extension. To reach such a standard is exceptionally hard, and students interested may wish to review [https://github.com/ldionne/hana Hana's source code] to see what is demanded for a GSoC extension. |
| | 9 | This year, 2015, is going to be slightly different from preceding years of how Boost has operated GSoC. The first new change was that last year we trialled extending the really superb GSoC 2014 projects by an additional three month period funded by Boost, and in 2014 the project we selected for extension was [https://ldionne.github.io/hana/ proposed Boost.Hana] by student Louis Dionne mentored by Joel Falcou. If these extensions prove successful, we may continue to extend the really outstanding GSoC projects in 2015. Note that the Boost Steering Committee can only consider extensions where the mentor is more than happy to continue mentoring the project in an extension, and where the GSoC administrators and the other GSoC mentors and Boost Steering Committee members all unanimously agree on the merit of the extension. To reach such a standard is exceptionally hard, and students interested may wish to review [https://github.com/ldionne/hana Hana's source code] to see what is demanded for a Boost funded GSoC extension. |
| 13 | | This runs the risk of excluding student proposals not suggested by this ideas page - in fact, Louis Dionne's Hana was not suggested here, it came entirely from Louis. We therefore add a second way of getting preferentially ranked: candidates who have written existing C++ libraries of at least 5,000 - 10,000 lines of code and who propose their own project, AND have prearranged a mentor through [http://www.boost.org/community/groups.html#main the Boost developer's mailing list], will also be preferentially ranked. |
| | 13 | This runs the risk of excluding student proposals not suggested by this ideas page - in fact, Louis Dionne's Hana was not suggested here, it came entirely from Louis. We therefore add a second way of getting preferentially ranked: candidates who have written existing C++ libraries of at least 1,000 lines of code (excluding comments and whitespace) and who propose their own project, AND have prearranged a mentor through [http://www.boost.org/community/groups.html#main the Boost developer's mailing list], will also be preferentially ranked. |
| | 44 | ==== Background ==== |
| | 45 | Strangely enough, Boost does not provide an implementation of thread safe concurrent associative sets and maps despite that the unordered implementation from Intel's Thread Building Blocks and Microsoft's Parallel Patterns Library was proposed for standardisation in [http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3425.html N3425 Concurrent Unordered Associative Containers for C++]. This is probably because that implementation (the split ordered list algorithm by Shalev and Shavit, 2006) had the serious shortcoming of not being thread safe for some operations, most importantly item deletion, and the workarounds proposed by N3425 did not appeal. Moreover, [https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf there are other concurrent hash table algorithms which do not have such shortcomings]. |
| | 46 | |
| | 47 | It is long overdue for Boost to gain a thread safe concurrent associative containers implementation, and to that end you will find a [https://github.com/ned14/boost.spinlock/blob/master/include/boost/spinlock/concurrent_unordered_map.hpp concurrent_unordered_map prototype here] with [https://ci.nedprod.com/view/Boost%20Thread-Expected-Permit/job/Boost.Spinlock%20Test%20Linux%20GCC%204.8/doxygen/classboost_1_1spinlock_1_1concurrent__unordered__map.html its doxygen documentation here]. This particular design provides a complete STL compliant interface with every operation being thread safe and most operations permitting concurrency, but sacrifices the constant time performance of empty() and size() to achieve this. Moreover, its find() is only completely wait free if compiled with a transactional memory compiler. |
| | 48 | |
| | 49 | ==== GSoC project proposal ==== |
| | 50 | 1. To refactor the implementation of the concurrent_unordered_map prototype into a generic, reusable layer from which the following containers can be implemented: |
| | 51 | a. boost::concurrent_unordered_set |
| | 52 | b. boost::concurrent_unordered_multiset |
| | 53 | c. boost::concurrent_unordered_map |
| | 54 | d. boost::concurrent_unordered_multimap |
| | 55 | |
| | 56 | 2. To complete the following missing functionality: |
| | 57 | a. Const iterators |
| | 58 | b. Const member functions |
| | 59 | c. Local iterators |
| | 60 | d. Copy and move construction plus copy and move assignment |
| | 61 | e. Better transactional memory C++ compiler support. |
| | 62 | |
| | 63 | 3. To write unit, functional and performance regression testing for all of the above, including exception safety testing and multi threaded testing, to a 100% code coverage level. |
| | 64 | |
| | 65 | 4. To write documentation to Boost quality levels for the new container classes, including time and space complexity guarantees and exception guarantees for each API and each use of each API. |
| | 66 | |
| | 67 | ==== Potential project extension funded by Boost ==== |
| | 68 | To implement ordered and/or nearly-ordered concurrent associative containers in addition to unordered ones. |
| | 69 | |
| | 70 | ==== Programming competency test ==== |
| | 71 | Implement item 2d (copy and move construction and copy and move assignment) for the concurrent_unordered_map prototype, and more importantly '''complete and thorough''' unit and functional and performance testing for the new functionality ([https://github.com/ned14/boost.spinlock/blob/master/test/unittests.cpp add the tests to this file]). You will find studying the rehash() implementation ought to make the implementation of this easy, but the true test of your competency will be in how well you design and write the testing for the new functionality. |
| | 72 | |
| | 73 | Submission of the programming test should be via copying and pasting the parts you wrote into the end of the proposal you submit to Google Melange. Do NOT copy and paste the entire class or whole files! |
| 53 | | Please do not simply arrive on the list and ask "I want to do GSoC Idea item no X because I don't want to do one of the predesigned GSoC projects on the list. Give me a mentor." as you will likely be ignored as a probable time waster. If you are to propose your own GSoC project, '''it must be of equivalent quality to the precanned GSoC project proposals written by mentors''' already on the ideas page, and by "equivalent", we really do mean '''equivalent''' i.e. very high. This is why mentors take the time to write project proposals for you, because for mentors who are domain experts in their field it is easier to write a high quality GSoC proposal likely to pass peer review and Google's own proposal review than for students who are not domain experts. If you are still really sure you want to invest the very considerable work to propose your own project, do the following before writing to the Boost mailing list with your own proposal: |
| | 88 | Please do not simply arrive on the list and ask "I want to do (insert some random project idea here) because I don't want to do one of the predesigned GSoC projects on the list. Give me a mentor." as you will likely be ignored as a probable time waster. If you are to propose your own GSoC project, '''it must be of equivalent quality to the precanned GSoC project proposals written by mentors''' already on the ideas page, and by "equivalent", we really do mean '''equivalent''' i.e. very high, and probably including a programming competency test of your own design. This is why mentors take the time to write project proposals for you, because for mentors who are domain experts in their field it is easier to write a high quality GSoC proposal likely to pass peer review and Google's own proposal review than for students who are not domain experts. If you are still really sure you want to invest the very considerable work to propose your own project, do the following before writing to the Boost mailing list with your own proposal: |
