wiki:SoC2016

Version 5 (modified by Niall Douglas, 7 years ago) ( diff )

slight improvements to project idea

  1. Boost Google Summer of Code 2016
      1. Quick summary of policies and processes for this year
      2. Github's for standalone GSoCs past and present
      3. Historical GSoC Ideas pages for years 2006 to now
  2. Suggested GSoC project proposals
      1. 1. Static map (`boost::static_map<Key, T, ConstExprHash = …
        1. Background
        2. GSoC project proposal
        3. Potential project extension funded by Boost
        4. Programming competency test

Boost Google Summer of Code 2016

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

Quick summary of policies and processes for this year

After two extremely successful years of GSoC at Boost during which even some of the old timers have been wowed by the C++ code some of the students have brought us, we are minded to keep in place the more rigorous candidate selection process which involves preferentially selecting over all others every GSoC Boost candidate who takes a C++ programming aptitude test or provides links to at least 1,000 lines (excluding comments and whitespace) non-coursework C++ library (not application nor solution) open source code. Note if following the second route, code should have been open sourced at least three months ago, and show a log of commits improving the library over time.

Students should review the list of ideas from previous GSoCs and the archives of the Boost developer's mailing list relating to GSoC (tip: try searching boost-dev for subjects tagged [gsoc16] or [gsoc15] etc). After reading other posts tagged [gsoc16], they should write a well researched message with [gsoc16] somewhere in the subject line to that developer's mailing list seeking a mentor, and be as flexible as possible in finding a topic that both they and the mentor is interested in upon which to base a GSoC project proposal text to be submitted to Google. That student written project proposal should follow this submission template.

Mentors may add project ideas with programming competency tests to this page below as GSoC approaches. These may prove useful in starting a discussion with potential mentor(s) whom the student should approach directly.

Github's for standalone GSoCs past and present

Since 2013 with Boost's transition to git we have kept a single umbrella org on github for those GSoCs which are fairly self standing. Incremental extensions to existing libraries usually enter that library's main git repo as an experimental branch. Here are those orgs:

Students may find examining past GSoC source code and commit histories of use.

Historical GSoC Ideas pages for years 2006 to now

Suggested GSoC project proposals

To any potential mentor adding a proposal HERE please use this template

1. Static map (boost::static_map<Key, T, ConstExprHash = boost::constexpr_hash<Key>, Pred = boost::constexpr_equal_to<Key>>)

Potential mentors: Niall Douglas

Background

Even with all of Boost's facilities [1] and using C++ 14, this program represents the currently best available method of implementing a static constant associative map of keys to values (​play with it in an online compiler here): 

#include <initializer_list>
#include <experimental/string_view>
#include <map>
#include <unordered_map>
#include <iostream>

using std::experimental::string_view;

enum class weekday { sunday, monday, tuesday, wednesday, thursday, friday, saturday };

// initializer_list, pair and string_view are constexpr, so this list can be constexpr
// (i.e. lives in the mind of the compiler only and has zero representation in generated code)
#define STRING_VIEW(str) { str, sizeof(str)-1 }
constexpr std::initializer_list<std::pair<const string_view, weekday>> string_to_weekday {
    { STRING_VIEW("sunday"),    weekday::sunday },
    { STRING_VIEW("monday"),    weekday::monday },
    { STRING_VIEW("tuesday"),   weekday::tuesday },
    { STRING_VIEW("wednesday"), weekday::wednesday },
    { STRING_VIEW("thursday"),  weekday::thursday },
    { STRING_VIEW("friday"),    weekday::friday },
    { STRING_VIEW("saturday"),  weekday::saturday }
};

int main(void)
{
  {
    // Calls malloc() at least 7 times
    static const std::map<string_view, weekday> to_weekday1 = string_to_weekday;
    std::cout << "'monday' maps to " << static_cast<int>(to_weekday1.at("monday")) << std::endl;
    std::cout << "'friday' maps to " << static_cast<int>(to_weekday1.at("friday")) << std::endl;
    // Calls free() at least 7 times
  }
  {
    // Calls malloc() at least 8 times
    static const std::unordered_map<string_view, weekday> to_weekday2 = string_to_weekday;
    std::cout << "'monday' maps to " << static_cast<int>(to_weekday2.at("monday")) << std::endl;
    std::cout << "'friday' maps to " << static_cast<int>(to_weekday2.at("friday")) << std::endl;
    // Calls free() at least 8 times
  }
  return 0;
}

As you can see, we have either the choice of linearly scanning the associative array string_to_weekday for keys (which has linear complexity to number of items per lookup), or we can copy at runtime the associative array into an associative map which can thereafter be queried at runtime in either O(log N) or O(1) complexities respectively.

Almost every seasoned C++ programmer has at least once (and often many times throughout a career) written a static constant associative map which is initialised once from static constant data usually at process start, and is thereafter never modified. Given that C++ 14 can very easily implement a static constant associative map container class, it would be a very worthwhile addition to Boost and C++ in general if we gained a high quality implementation of a static map class.

[1]: Probably Boost.Hana which is expected to enter Boost soon could be used to implement a static map which can be queried either at compile time or run time fairly easily. This project proposal does not require the use of Boost.Hana, though using it may be interesting.

GSoC project proposal

  1. To seek consensus from the Boost Developer's mailing list on a suitable design for a Boost static_map class. (The chances are high that the static_map class would be STL compliant much as other constexpr-capable STL containers such as std::array<> and std::initializer_list<>).
  1. To implement a static_map class which runs on at least two major C++ compilers.
    • The class should be entirely a compile-time implementation via constexpr and generate no runtime overhead whatsoever.
  1. To implement a comprehensive unit test suite for the static_map class, including tests ensuring no runtime overhead is generated.
  1. To configure per-commit continuous integration for the unit test suite on at least one of the major public open source CI services (e.g. Travis, Appveyor).
  1. To write documentation to Boost quality levels for the new container class, including time and space complexity guarantees and exception guarantees for each API and each use of each API.

Potential project extension funded by Boost

  • static_multimap
  • static_set and static_multiset
  • static_ordered_map and static_ordered_multimap

Programming competency test

Write a function which uses one of the compile time string hashing techniques at ​https://stackoverflow.com/questions/2111667/compile-time-string-hashing (or a constexpr hash function of your preference) to generate a constexpr std::array<unsigned> of its input strings. The function ought to have the following prototype: 

template<class... Strings> constexpr std::array<unsigned, sizeof...(Strings)> hash_strings(Strings&&... strings);

// Examples of usage
constexpr std::array<unsigned, 0> string_hashes0 = hash_strings();
constexpr std::array<unsigned, 2> string_hashes2 = hash_strings("niall", "douglas");
constexpr std::array<unsigned, 4> string_hashes4 = hash_strings("google", "summer", "of", "code");
// This should fail elegantly and usefully ...
//constexpr std::array<unsigned, 0> string_hashes_fail = hash_strings(5);

In your submission you should:

  1. Explain why you chose the constexpr string hash function you did and the strengths of your choice over other choices.
  2. Test that the output is identical whether executed by the compiler at compile time, or at runtime.
  3. Prove that the compile time constexpr implementation generates no runtime code whatsoever.

Submission of the programming test should be via copying and pasting the code you wrote into the end of the proposal you submit to Google Melange.

To any potential mentor adding a proposal HERE please use this template

Note: See TracWiki for help on using the wiki.