Changes between Version 7 and Version 8 of SoC2016

Timestamp:

Jan 17, 2016, 9:26:35 PM (7 years ago)

Author:

Niall Douglas

Comment:

Improved static_map description

SoC2016

@@ -58 +58 @@
 ==== Background ====
 
-Even with all of Boost's facilities ![1] and using C++ 14, this program represents the currently best available method
+Even with all of Boost's facilities 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]):
+([http://melpon.org/wandbox/permlink/SEt61EAxVG4J5BnF play with it in an online compiler here] and
+[https://goo.gl/gTZOEp see the assembler generated here]):
 
 {{{
@@ -110 +111 @@
 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.
+or `O(1)` complexities respectively. Both these options generate very significant amounts of runtime code.
 
 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
+start, and is thereafter never modified. Given that C++ 14 can implement an associative map where key
+lookups are constexpr when possible, 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 seek consensus from the Boost Developer's mailing list on a suitable design for a Boost `static_map` class
+ with the following design features:
+ 1. Whose number of items and keys are completely fixed from construction onwards.
+ 2. All features of which can be used in constant expressions (i.e. all member functions are marked constexpr).
+ 3. Which can be completely statically initialised in the mind of the compiler, or in static global storage.
+ 4. Values, though not keys nor number of items, are modifiable.
+ 5. Which performs constexpr key to value lookup ''to the maximum possible extent''.
+
+ It turns out this list of requirements is in fact quite challenging to implement, and even seasoned Boost
+ programmers have to stop and ponder this one. To demonstrate the difficulty in code:
+
+ {{{
+#!c++
+constexpr std::pair<int, const char *> map_data[] = {
+  { 5, "apple" },
+  { 8, "pear" },
+  { 0, "banana" }
+};
+// Easy: generates no runtime code
+constexpr auto cmap = make_static_map(map_data);
+// Easy: generates no runtime code, this is as if literal "apple"
+constexpr const char *what_is_5 = cmap[5];
+
+// Challenging: needs to only generate code loading immediately from a memory location.
+// It must NOT generate any additional runtime overhead like hashing nor searching.
+const char *what_is_8 = cmap[8];
+}}}
+ 
+ The reason why the last statement is challenging is because of the rules of when a constexpr-capable code path is
+ executed by the compiler: the compiler only ''has'' to constexpr execute when all the inputs are constant
+ expressions '''and''' all the outputs will be used in constant expressions, and it only ''may'' constexpr execute
+ when all the inputs are constant expressions. Indeed empirical testing of clang 3.7 and VS2015 found both currently
+ do '''not''' constexpr execute when the result is not stored constexpr, so in a naive implementation the last
+ statement '''does''' generate a runtime lookup on current compiler technology despite the constant expression inputs.
+ If you'd like to see more detail about this specific problem, have a look at the assembler generated for a toy
+ static_map implementation at https://goo.gl/eO7ooa.
 
 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.
+  - Hopefully in C++ 14, however upcoming features in C++ 1z do make the problem considerably easier to fix.
 
 3. To implement a comprehensive unit test suite for the `static_map` class, including tests ensuring no
- runtime overhead is generated.
+ runtime overhead is generated for the challenging use case exampled above.
 
 4. To configure per-commit continuous integration for the unit test suite on at least one of the major public
@@ -139 +168 @@
 
 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.
+ guarantees and benchmarks, and exception guarantees for each API and each use of each API.
 
 ==== Potential project extension funded by Boost ====
 - `static_multimap` (keys are not unique)
 - `static_set` and `static_multiset` (keys only)
-- `static_ordered_map` and `static_ordered_multimap` (iteration is in order of keys)
+- `static_ordered_map` and `static_ordered_multimap` (iteration is in lexical order of keys)
 - `static_bimap` (values are also keys)
 - `static_index<T...>` (multi-column table with some columns being hash indexed)