wiki:SoC2014

Version 21 (modified by viboes, 9 years ago) ( diff )

--

  1. Google Summer of Code 2014
    1. Requirements
    2. Projects
      1. Boost.Math Generalized Hypergeometric Functions
      2. Boost.AFIO (proposed) Improvements
      3. Boost.odeint
        1. Implicit Routines
      4. Boost.Functional / Invoke
      5. Boost.Thread / Work-Stealing-Thread-Pool
      6. Boost.Thread / Scheduler-Executor
      7. Boost.Fixed-Point
      8. Boost.Chrono / Date
      9. Boost.Exception / Stack-Unwinding
      10. Boost.Pipelines
      11. Boost.XML
      12. Moving Boost to Boost.Move
    3. Ideas
      1. Boost libraries (extending/overhauling/finishing)
      2. Algorithms
      3. Data strutures
      4. Media
      5. Games
      6. Databases
      7. Math
      8. Memory
      9. File formats
      10. Communication
      11. GUI
      12. C++ "extensions"
      13. Hardware

Google Summer of Code 2014

Welcome to the Boost C++ Libraries' home page for Google Summer of Code (GSoC). This page provides information about student projects, proposal submission templates, advice on writing good proposals, and links to information on getting started writing with Boost.

This year Boost is looking to fund work on a number of different kinds of proposals:

  • toolkit-like extensions to existing libraries,
  • finishing or extending sandbox libraries,
  • new data structures and algorithms, and
  • multiple competing proposals for the same project.

For projects involving new or experimental libraries, the process of getting source code "Boost-branded" can take much longer than a single summer. In many cases, it can take much longer than a single year. Even if a library is accepted, there is an expectation that the original author will continue to maintain it. Building a library as part of Boost can easily entail a multi-year commitment. For this reason, we are willing to consider multi-year GSoC projects. However, prospective students must limit the scope of their work to a single summer. We may invite the most successful students to re-apply in 2015.

Requirements

Students must submit a proposal. A template for the proposal can be found here here. Hints for writing a good proposal can be found here.

We strongly suggest that students interested in developing a proposal for Boost discuss their ideas on the mailing list in order to help refine the requirements and goals. Students who actively discuss projects on the mailing list are also ranked before those that do not.

Projects

The following projects have been suggested by potential mentors. If the descriptions of these projects seem a little vague... Well, that's intentional. We are looking for students to develop requirements for their proposals by doing initial background research on the topic, and interacting with the community on the mailing list to help identify expectations.

Projects from previous years can be found here. There are still a number of interesting projects found in these pages.

Boost.Math Generalized Hypergeometric Functions

Boost.Math http://www.boost.org/doc/libs/1_55_0/libs/math/doc/html/index.html is a large well-established Boost library, but new and useful mathematical functions can always be added.

Generalized hypergeometric functions are convergent power series that have rational coefficients.

​http://en.wikipedia.org/wiki/Generalized_hypergeometric_function

Hypergeometric functions are remarkably versatile because many well-known functions of pure and applied mathematics are special cases of hypergeometric functions. These include various mathematical constants, elementary transcendental functions, Bessel functions, the incomplete gamma function, confluent hypergemetric functions, generalized Legendre functions, and (infinitely) many more.

Even though the theory of hypergeometric functions is well-established, very few programs or libraries support these fascinating and versatile functions.

In this project, we will implement fast, accurate calculations of certain generalized hypergeometric functions and establish convergent parameter ranges for these. We will write them with generic templates, as is suitable for Boost.Math.

Our work will make use of many numerical methods for special functions, including expansions in Chebyshev polynomials, rational approximations, Pade approximations, Taylor series, asymptotic series, and others.

The main goals of the project are:

  • Investigate calculation methods for hypergeometric_0f1, 1f0, 1f1, 1f2, 2f1.
  • Evaluate regions of parameter convergence for these.
  • Ensure that calculations are fast and accurate for all built-in types and some multiple-precision types.
  • Optional: Add support generalized Legendre functions of type-I to Boost.Math.
  • Optional: Replace certain internal calculations within Boost.Math with hypergeometric functions.

This project requires a passion for serious mathematical programming and at least some knowledge of advanced C++. In particular, we will be using templates which Boost.Math makes much use of to support not only built-in float, double and long double but also multiple-precision types. It will be helpful to have experience using Boost libraries, including Boost.Test, and a rudimentary knowledge of GIT.

A preliminary investigation carried out for this project can be found here: ​https://github.com/boostorg/multiprecision/blob/develop/example/hypergeometric_luke_algorithms.cpp

In this investigation, multiple-precision hypergeometric functions were calculated with three-term recursion series of Chebyshev polynomials. If this code leaves you utterly terrified, then this project is not for you. But if it only frightens you a little bit, yet also piques your interest, and if you have a passion for numerical programming, then you are the right candidate for this project!

If you would like to demonstrate your skills, use the functions in the file in the link above for multiple-precision calculations of cylindrical Bessel functions (i.e., cyl_bessel_j). Hint: Consider the relation between hypergeometric_0f1 and cyl_bessel_j. Use the multiple-precision data type cpp_dec_float_50 from Boost.Multiprecision. Discuss convergence properties and document some run-time characteristics. You can use any platform, Linux, Mac or Microsoft with your IDE of choice, perhaps Visual Studio, Eclipse, Code Blocks, or Net Beans.

This project will by mentored by Christopher Kormanyos, and also supported by Paul Bristow and John Maddock regarding algorithmic expertise and Boost infrastructure.

Boost.AFIO (proposed) Improvements

Proposed Boost.AFIO is a linear scalable, batch, chainable, asynchronous closure execution engine with an almost wait free implementation (it is wait free if the CPU supports memory transactions) extending Boost.ASIO and Boost.Thread specialised as a portable asynchronous file i/o implementation library. Proposed Boost.AFIO was successfully ported to Boost during GSoC 2013 by Paul Kirth, and entered the Boost peer review queue in October 2013. If it passes peer review, AFIO is thought likely to be the first C++ 11 only library to enter Boost. You can see AFIO's Boost documentation at ​https://ci.nedprod.com/job/Boost.AFIO%20Build%20Documentation/Boost.AFIO_Documentation and its current continuous integration buildbot status and source code at ​https://github.com/BoostGSoC/boost.afio (scroll to bottom for present CI buildbot status). You are encouraged to read the AFIO documentation extensively before writing a GSoC proposal, and ask questions on boost-dev where needed.

There are some interesting work items extending AFIO which would be ideal for a summer student project:

  1. POSIX async i/o support is limited to a threadpooled emulation. Proper support for Linux's kaio and POSIX's aio_* interfaces would be great. Note that these APIs are extremely tricky to get working right across all POSIX platforms, especially OS X. To propose this project the submitter would need developer access to Microsoft Windows, Linux, FreeBSD and preferably OS X. Difficulty level of this item is medium.
  1. Portable fast file locking which works across network shares, but can still utilise shared memory when possible. To propose this project the submitter would need developer access to Microsoft Windows, Linux, FreeBSD/OS X. Difficulty level of this item is medium.
  1. Fast, scalable portable directory contents change monitoring. It should be able to monitor a 1M entry directory experiencing 1% entry changes per second without using a shocking amount of RAM. To propose this project the submitter would need developer access to Microsoft Windows, Linux, FreeBSD/OS X. Difficulty level of this item is hard, there are professional software engineers with over a decade of experience who would take several attempts to get this right (luckily you have an experienced mentor to help you!).
  1. AFIO is also a closure execution engine, and API conformance with the current ​Executors and Schedulers proposal before the ISO C++ standards committee would be useful. I would also suggest bundling into this work item Fibers support such that both cooperative and preemptive threading models are supported. Difficulty level of this item is medium for those very comfortable with programming in asynchronous frameworks like WinRT, otherwise it is hard and very hard for some types of programmers who are not "async wired".
  1. By the time GSoC begins AFIO ought to have a finished async batch hash engine which provides SHA256, CityHash and SpookyHash. Additional hash implementations would be very useful. Before you think you can copy and paste in existing hash implementations, be aware that AFIO requires you to completely rewrite them into batch SIMD (SSE2, AVX and preferably ARM NEON) and implement considerable C++ metaprogramming to tell the compiler how to optimally assemble the implementation. Difficulty level of this item is hard, but very suitable for low level type programmers who like writing in assembly but also like C++ metaprogramming. The batch hash engine can be seen at ​https://github.com/BoostGSoC/boost.afio/blob/content_hashing_merge/boost/afio/hash_engine.hpp, and an example of the SIMD programming you'd have to do at ​https://github.com/BoostGSoC/boost.afio/blob/content_hashing_merge/boost/afio/detail/impl/hashes/4-sha256/sha256-neon.c.

This project would be mentored by Niall Douglas (​http://www.nedprod.com/). Due to limits on free time, I would only be able to mentor one student this summer, and I generally provide a programming test based on AFIO to students whose have submitted proposals to ensure that their coding ability is minimally sufficient to be able to attempt a GSoC. Benefits for the student of a successful GSoC in this area are many: high performance async programming experience is very desirable in the marketplace right now, and getting your name attached to authorship of a Boost library is a shining bright light on a resume which will stand to your career for years to come. You will gain bleeding edge experience programming exclusively in C++11 across the main toolsets of Visual Studio, GCC and clang AND writing portable code for the main operating system platforms of Microsoft Windows, Linux, and BSD/OS X - again, all very desirable skills to have in the marketplace. For those of you looking at a career in computer science research, and depending on the success of your outcomes, you may even be able to pass peer review to present your work at the C++ Now conference held annually in May. Good luck with your GSoC applications!

Boost.odeint

Boost.odeint ​http://www.odeint.com is a library devoted to finding numerical solutions of ordinary differential equations (ODEs). It is developed in a generic way using Template Metaprogramming which leads to extraordinary high flexibility at top performance. It is widely used in academic and industrial projects. Boost.odeint has been a Google Summer of Code project in 2011 ​http://google-melange.appspot.com/gsoc/project/google/gsoc2011/mulansky/14001 and we would like again to see students involved in the development of this numerical library. Therefore, we offer the two following projects:

Implicit Routines

The current focus of odeint is on explicit routines, namely the Runge-Kutta schemes or the multi-step methods. However, we would like to expand odeint by adding implicit routines in the same flexible manner. Implicit routines are important when dealing with stiff systems, but also ensure stability in some cases of discretized partial differential equations (PDEs). At the moment, odeint provides an implicit Euler and Rosenbrock algorithm, but the implementation is restricted to Boost.uBlas. As one of the main objectives of odeint is to provide highly flexible algorithms, we want to change this implementation to have a greater flexibility and interchangeability similar to that of the explicit routines. This project would not only require pure coding, but first also a considerable amount of design work.

  • Develop a design on how the requirements on implicit routines can be modularized
  • Implement a prototype showing the usability of the design
  • Change the existing routines to the new design
  • Implement other backends (MTL, eigen,...) to demonstrate the flexibility
  • Provide examples and documentation
  • (Add more implicit routines, if time permits)

This project does not only require profound knowledge on C++ and generic programming, but we would also like to see some experience on numerical algorithms and solving ODEs, if possible.

The project will be mentored by Karsten Ahnert and Mario Mulansky.

Boost.Functional / Invoke

Provide a boost::invoke function implementation of the c++11 definition of INVOKE for c++11 and C++03 compilers based on the interface defined in [1]. [2] could be taken in consideration.

Provide a boost::invoker template class that stores a function and its arguments and make it a nullary function. This can be used in Boost.Thread to implement C++11 compatible boost::thread construction, boost::async, boost::future:then(). This class is quite similar to the result of the function bind, but it doesn't use boost::ref.

Make use of invocation_traits (see[3] in Boost.Thread to make it possible an More perfect forwarding in functions as boost::thread construction, boost::async, boost::future:then().

This project could be mentored by Vicente J. Botet Escriba

[1] ​http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3727.html

[2] ​https://github.com/boostorg/thread/tree/develop/include/boost/thread/detail/invoke.hpp

[3] ​http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3866.html

Boost.Thread / Work-Stealing-Thread-Pool

Provide a boost::work_stealing_thread_pool class scheduling arbitrary functions based on the interface defined in [1]. [2] should be taken in consideration.

[1] ​https://github.com/boostorg/thread/tree/develop/include/boost/thread/executors

[2] ​http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3562.pdf

This project could be mentored by Vicente J. Botet Escriba

Boost.Thread / Scheduler-Executor

Provide boost::scheduled_executor implementations base on the C++ proposal [1] and the draft implementation in [2].

[1] ​http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3562.pdf

[2] ​https://github.com/boostorg/thread/tree/develop/include/boost/thread/executors

This project could be mentored by Vicente J. Botet Escriba

Boost.Fixed-Point

Provide an implementation of a Fixed-Point library based on [1].

A prototype with a different interface is available at [2]

[1] ​http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html

[2] ​https://svn.boost.org/svn/boost/sandbox/fixed_point/

Boost.Chrono / Date

Provide an implementation of a Date library based on [1].

A prototype with a different interface is available also at [2].

[1] ​https://svn.boost.org/svn/boost/sandbox/chrono_date/libs/date/doc/date.html

[2] ​https://svn.boost.org/svn/boost/sandbox/chrono_date/

This project could be mentored by Vicente J. Botet Escriba

Boost.Exception / Stack-Unwinding

Make a real Boost library the Stack-Unwinding library [1] from Evgeny Panasyuk ready for review.

[1] ​https://github.com/panaseleus/stack_unwinding#d-style-scope-guardsactions

Boost.Pipelines

Provide boost::pipelines implementations base on the C++ Pipelines proposal [1] and the Google implementation in [2]

[1] ​http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3534.html

[2] ​https://code.google.com/p/google-concurrency-library/source/browse/include/pipeline.h

This project could be mentored by Vicente J. Botet Escriba

Boost.XML

Define a set of XML APIs (DOM, SAX, XMLReader, etc.) for C++.

There are a couple of good XML libraries available with C and C++ interfaces. So the focus shouldn't be yet another XML library implementation, but rather, a clean and robust set of APIs, with bindings to the existing implementations. A good starting point for the API is [1], as well as [2]. The latter also already provides multiple backends (such as [3], [4], [5]).

[1] ​https://github.com/stefanseefeld/boost.xml

[2] ​https://github.com/jezhiggins/arabica/

[3] ​http://www.xmlsoft.org/

[4] ​http://xerces.apache.org/xerces-c/

[5] ​http://msdn.microsoft.com/en-us/data/bb190600.aspx

This project could be mentored by Stefan Seefeld

Moving Boost to Boost.Move

There a re a lot of Boost libraries that don't support move semantics. It would be nice if one student propose to adapt the some of the existing libraries.

The idea is to use Boost.Move so that an emulation is provided for compilers not supporting rvalue references.

Some of the libraries (let me know if I'm wrong are). My priority is given between [], lower numbers means higher priority. Of course others would have others priorities:

C++11

  • [0] Tuple or * Fusion/tuple (it seems that it support or will support c++11 move semantics but don't use Boost.Move)
  • [0] Bind
  • [1] Function
  • [2] SmartPtr
  • [8] Array ?

Accepted for C++14

Having an active proposal for C++1y

Other

Please help me to complete this list.

Adding constexpr and noexcept would be welcome also.

This project could be mentored by Vicente J. Botet Escriba

Ideas

Here you find a lot of ideas which have been mentioned on the Boost mailing list. Boost developers can use these ideas to create new projects (and add them to the list of projects above). And students can use them as start points to propose projects themselves. While these ideas are by far not as concrete as projects in the list above, they give students an idea what else they can work on within Boost. They also give students a chance to propose exactly the kind of project they'd like to work on instead of picking one from the predefined projects from above.

Boost libraries (extending/overhauling/finishing)

Algorithms

  • Radix sort
  • Approximate string matching
  • Full text search
  • Near Duplicate Detection (shingling)
  • Parallel algorithms (sort, for_each)
  • Algorithms for gpgpu
  • Kinetic scrolling

Data strutures

  • Trie data structure, extending the work done during GSoC 2013.
  • B-tree data structure
  • Concurrent containers (unordered_map, unordered_set, vector, forward_list)
  • Slim string (as opposed to the fat std::string interface, maybe immutable, maybe policy based)

Media

  • Hardware graphics (OpenGL/OpenGL ES/DirectX abstraction)
  • Audio library (OpenAL/FMOD/etc)
  • Video processing library (gil for video)

Games

  • Physics library (ODE/Havok/PhysX/etc abstraction)
  • Input library (like DirectInput/XInput)
  • Ranking algorithms (elo/TrueSkill)

Databases

Math

  • Geometry library (convince the developers to submit Eigen 3 to Boost)
  • Investigate exporting multiple-precision types to Python via Boost.Python and interoperability with "symbolic python". See: ​http://sympy.org/en/index.html

Memory

  • Memcache library
  • Memswap algorithm

File formats

  • JSON parsing libary
  • XML library

Communication

GUI

  • GUI library

C++ "extensions"

Hardware

  • CPUID
Note: See TracWiki for help on using the wiki.