Changes between Version 3 and Version 4 of SoC2016

Timestamp:

Jan 10, 2016, 7:08:53 PM (7 years ago)

Author:

Niall Douglas

Comment:

Added first project idea

SoC2016

@@ -40 +40 @@
 = Suggested GSoC project proposals =
 
+'''[wiki:GSoCIdeaTemplate 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
+([http://melpon.org/wandbox/permlink/SEt61EAxVG4J5BnF play with it in an online compiler here]):
+
+{{{
+#!c++
+#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<>`).
+
+2. 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.
+
+3. To implement a comprehensive unit test suite for the `static_map` class, including tests ensuring no
+ runtime overhead is generated.
+
+4. 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).
+
+5. 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
+to generate a constexpr `std::array<unsigned>` of its input strings. The function ought to have the following
+prototype:
+
+{{{
+#!c++
+template<class... Strings> constexpr std::array<unsigned, sizeof...(Strings)> hash_strings(Strings&&... strings);
+
+// Example of usage
+constexpr std::array<unsigned, 4> string_hashes = hash_strings("google", "summer", "of", "code");
+}}}
+
+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.
+
 
 '''[wiki:GSoCIdeaTemplate To any potential mentor adding a proposal HERE please use this template]'''