[gsoc16] Can I quickly check if the below really is the best approach?
Dear Boost, In the prototype https://svn.boost.org/trac/boost/wiki/SoC2016 at https://goo.gl/1CQAuQ I claim "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" and you can find either the code at the link or pasted below. Can I quickly check here if that claim is true? Is there a better way than my example program? BTW by static constant associative map of keys to values I mean the thing me and Tony van Eerd were speaking about here last year and the year before, and indeed frequently at BlackBerry! Niall [1]: I believe Boost.Hana could implement a static constan associative map quite easily, but I'd be fairly sure Hana will likely be beyond most students. --- cut --- #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; } -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
AMDG On 01/12/2016 01:09 PM, Niall Douglas wrote:
In the prototype https://svn.boost.org/trac/boost/wiki/SoC2016 at https://goo.gl/1CQAuQ I claim "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" and you can find either the code at the link or pasted below.
Can I quickly check here if that claim is true? Is there a better way than my example program?
<snip> int main(void) { { // Calls malloc() at least 7 times
If malloc is your biggest concern, try boost::container::flat_map.
static const std::map<string_view, weekday> to_weekday1 = string_to_weekday; <snip>
In Christ, Steven Watanabe
On 12 Jan 2016 at 13:55, Steven Watanabe wrote:
Can I quickly check here if that claim is true? Is there a better way than my example program? [snip]
If malloc is your biggest concern, try boost::container::flat_map.
Sorry, the problem being solved was likely poorly specified by me. What the project idea is for is a boost::[container::]static_map<Key, T> which: 1. Like std::array<T, N>, it is a fixed size after construction. 2. Like std::array<T, N>, all member functions are constexpr, thus allowing constexpr use where Key and T allow that. 3. Keys or the number of items cannot be modified, but values can be. 4. The primary use case example is something like this: // At global scope, allocates no memory whatsoever static const constexpr static_map<int, const char *> map { { 5, "apple" }, { 8, "pear" }, { 0, "banana" }, ... }; // Works, constexpr "apple" constexpr const char *what_is_5 = map[5]; // Works assert(map[5] && !strcmp(map[5], "apple"); // Works map[5]="orange"; assert(map[5] && !strcmp(map[5], "orange"); // Throws exception as there is no key 6 map[6]; map.at(6); Does this make more sense? I know this may seem to be too trivially easy to be worth adding to Boost, but if you've ever seen code where people embed large automatically generated data sets into C arrays and then do linear lookups, the proposed static_map is *exactly* for that use case - and ~O(1) lookup complexity to boot. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
On 14/01/2016 00:57, Niall Douglas wrote:
4. The primary use case example is something like this:
// At global scope, allocates no memory whatsoever static const constexpr static_map<int, const char *> map { { 5, "apple" }, { 8, "pear" }, { 0, "banana" }, ... };
This seems at least superficially similar to the enum conversion library that was discussed briefly last year. Have you taken a look at that?
On 19 Jan 2016 at 13:18, Gavin Lambert wrote:
On 14/01/2016 00:57, Niall Douglas wrote:
4. The primary use case example is something like this:
// At global scope, allocates no memory whatsoever static const constexpr static_map<int, const char *> map { { 5, "apple" }, { 8, "pear" }, { 0, "banana" }, ... };
This seems at least superficially similar to the enum conversion library that was discussed briefly last year. Have you taken a look at that?
If the proposed map didn't allow value modification or indeed non-constexpr constructible values, then they would be very similar yes, just a different use-syntax. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
At Tue, 12 Jan 2016 20:09:02 -0000 Niall Douglas wrote:
Dear Boost,
In the prototype https://svn.boost.org/trac/boost/wiki/SoC2016 at https://goo.gl/1CQAuQ I claim "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" and you can find either the code at the link or pasted below.
Can I quickly check here if that claim is true? Is there a better way than my example program?
AFAIK your code is the current best practice for generating a constant static map with runtime lookups, unless there is some project hiding on Github. If using external processes is an option, I've seen the entire initialization at compile-time done by generating a static table using Perl (or similar) to generate code. That solution works even when C is a target language. A constexpr map would be convenient in many use cases. I think the most common case involves a string key, which has gotten me thinking about a constexpr X3 symbol table (ternary tree). The one difficulty is getting optimal efficiency in the static memory usage - I think this requires a compile-time string (similar to metaparse). In the past I've used an approach similar to yours with `spirit::symbols<>`, with the usual downsides from dynamic (runtime) initialization.
[1]: I believe Boost.Hana could implement a static constan associative map quite easily, but I'd be fairly sure Hana will likely be beyond most students.
If using Hana is beyond most GSoC students, it seems like writing a `constexpr` associative map will be too. For example, computing the amount of storage space needed for the map must be done _before_ entering the constexpr function in its return type, which I think is harder to grasp than the purely runtime components of Hana. And if the student can understand that level of TMP, then Hana should not be an issue.
#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 } };
The macro `STRING_VIEW` seems unnecessary because the `string_view` constructor taking a single NULL-terminated string is also `constexpr`. Although, it could reduce the amount of computation done by the C++ interpreter in the compiler. Lee
On 13 January 2016 at 12:25, Lee Clagett <forum@leeclagett.com> wrote:
The macro `STRING_VIEW` seems unnecessary because the `string_view` constructor taking a single NULL-terminated string is also `constexpr`.
While the templated constructor for basic_string_view is constexpr, this constructor for string_view cannot be used in a constexpr context because char_traits<char>::length isn't constexpr. :-( See LWG 2232 <http://cplusplus.github.io/LWG/lwg-active.html#2232>. I've been told it works this way by design... So yes, we do need the macro. -- Nevin ":-)" Liber <mailto:nevin@cplusplusguy.com <nevin@eviloverlord.com>> +1-847-691-1404
On Wed, Jan 13, 2016 at 1:56 PM, Nevin Liber <nevin@cplusplusguy.com> wrote:
On 13 January 2016 at 12:25, Lee Clagett <forum@leeclagett.com> wrote:
The macro `STRING_VIEW` seems unnecessary because the `string_view` constructor taking a single NULL-terminated string is also `constexpr`.
While the templated constructor for basic_string_view is constexpr, this constructor for string_view cannot be used in a constexpr context because char_traits<char>::length isn't constexpr. :-( See LWG 2232 <http://cplusplus.github.io/LWG/lwg-active.html#2232>.
I've been told it works this way by design...
So yes, we do need the macro.
Can it be a constexpr function that returns an initializer list? Or something, anything,... I hate macros :-(
On 1/14/2016 2:45 PM, Gottlob Frege wrote:
On Wed, Jan 13, 2016 at 1:56 PM, Nevin Liber <nevin@cplusplusguy.com> wrote:
On 13 January 2016 at 12:25, Lee Clagett <forum@leeclagett.com> wrote:
The macro `STRING_VIEW` seems unnecessary because the `string_view` constructor taking a single NULL-terminated string is also `constexpr`.
While the templated constructor for basic_string_view is constexpr, this constructor for string_view cannot be used in a constexpr context because char_traits<char>::length isn't constexpr. :-( See LWG 2232 <http://cplusplus.github.io/LWG/lwg-active.html#2232>.
I've been told it works this way by design...
So yes, we do need the macro.
Can it be a constexpr function that returns an initializer list?
No, because initializer lists are backed by arrays of automatic storage, so the returned `initializer_list` would immediately dangle.
Or something, anything,... I hate macros :-(
Yes, templates, as usual: template <typename CharT, std::size_t N> constexpr std::experimental::basic_string_view<CharT> make_string_view(CharT const (&str)[N]) noexcept { return {str, N - 1}; } constexpr string_view sv = make_string_view("hello"); static_assert(sv.size() == 5); Regards, -- Agustín K-ballo Bergé.- http://talesofcpp.fusionfenix.com
On 14 January 2016 at 11:54, Agustín K-ballo Bergé <kaballo86@hotmail.com> wrote:
On 1/14/2016 2:45 PM, Gottlob Frege wrote:
On Wed, Jan 13, 2016 at 1:56 PM, Nevin Liber <nevin@cplusplusguy.com> wrote:
On 13 January 2016 at 12:25, Lee Clagett <forum@leeclagett.com> wrote:
The macro `STRING_VIEW` seems unnecessary because the `string_view`
constructor taking a single NULL-terminated string is also `constexpr`.
While the templated constructor for basic_string_view is constexpr, this constructor for string_view cannot be used in a constexpr context because char_traits<char>::length isn't constexpr. :-( See LWG 2232 <http://cplusplus.github.io/LWG/lwg-active.html#2232>.
I've been told it works this way by design...
So yes, we do need the macro.
Can it be a constexpr function that returns an initializer list?
No, because initializer lists are backed by arrays of automatic storage, so the returned `initializer_list` would immediately dangle.
Or
something, anything,... I hate macros :-(
Yes, templates, as usual:
template <typename CharT, std::size_t N> constexpr std::experimental::basic_string_view<CharT> make_string_view(CharT const (&str)[N]) noexcept { return {str, N - 1}; }
constexpr string_view sv = make_string_view("hello"); static_assert(sv.size() == 5);
That does not do the same thing if the literal has embedded '\0' characters or if you pass it an array that isn't a '\0'-terminated string. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> +1-847-691-1404
On 1/14/2016 2:59 PM, Nevin Liber wrote:
On 14 January 2016 at 11:54, Agustín K-ballo Bergé <kaballo86@hotmail.com> wrote:
On 1/14/2016 2:45 PM, Gottlob Frege wrote:
On Wed, Jan 13, 2016 at 1:56 PM, Nevin Liber <nevin@cplusplusguy.com> wrote:
On 13 January 2016 at 12:25, Lee Clagett <forum@leeclagett.com> wrote:
The macro `STRING_VIEW` seems unnecessary because the `string_view`
constructor taking a single NULL-terminated string is also `constexpr`.
While the templated constructor for basic_string_view is constexpr, this constructor for string_view cannot be used in a constexpr context because char_traits<char>::length isn't constexpr. :-( See LWG 2232 <http://cplusplus.github.io/LWG/lwg-active.html#2232>.
I've been told it works this way by design...
So yes, we do need the macro.
Can it be a constexpr function that returns an initializer list?
No, because initializer lists are backed by arrays of automatic storage, so the returned `initializer_list` would immediately dangle.
Or
something, anything,... I hate macros :-(
Yes, templates, as usual:
template <typename CharT, std::size_t N> constexpr std::experimental::basic_string_view<CharT> make_string_view(CharT const (&str)[N]) noexcept { return {str, N - 1}; }
constexpr string_view sv = make_string_view("hello"); static_assert(sv.size() == 5);
That does not do the same thing if the literal has embedded '\0' characters or if you pass it an array that isn't a '\0'-terminated string.
"The same thing" than what? It does the exact some thing the macro in this context would do: #define STRING_VIEW(str) { str, sizeof(str)-1 } Regards, -- Agustín K-ballo Bergé.- http://talesofcpp.fusionfenix.com
On 14 January 2016 at 12:09, Agustín K-ballo Bergé <kaballo86@hotmail.com> wrote:
"The same thing" than what? It does the exact some thing the macro in this context would do:
#define STRING_VIEW(str) { str, sizeof(str)-1 }
Good point. The question is: what should it do? There are three interpretations: C-string literal ('\0'-terminated array that may have embedded '\0' bytes) array (no sentinel terminates the array) C-string (terminate the string at the first '\0' encountered) I suppose the one that makes the most sense is C-string literal (which is what the macro and your code does). Doesn't Boost.Range have to deal with this also? -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> +1-847-691-1404
On 14 January 2016 at 11:45, Gottlob Frege <gottlobfrege@gmail.com> wrote:
On Wed, Jan 13, 2016 at 1:56 PM, Nevin Liber <nevin@cplusplusguy.com> wrote:
On 13 January 2016 at 12:25, Lee Clagett <forum@leeclagett.com> wrote:
The macro `STRING_VIEW` seems unnecessary because the `string_view` constructor taking a single NULL-terminated string is also `constexpr`.
While the templated constructor for basic_string_view is constexpr, this constructor for string_view cannot be used in a constexpr context because char_traits<char>::length isn't constexpr. :-( See LWG 2232 <http://cplusplus.github.io/LWG/lwg-active.html#2232>.
I've been told it works this way by design...
So yes, we do need the macro.
Can it be a constexpr function that returns an initializer list? Or something, anything,... I hate macros :-(
You should be able to write a constexpr length() function, then a constexpr factory function which will return a string_view (calling the same constructor that the macro does). It just won't use strlen() in non-constexpr contexts, but we probably don't care for this use case. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> +1-847-691-1404
On 13 Jan 2016 at 13:25, Lee Clagett wrote:
Can I quickly check here if that claim is true? Is there a better way than my example program?
AFAIK your code is the current best practice for generating a constant static map with runtime lookups
Cool, thanks for having a look.
[1]: I believe Boost.Hana could implement a static constan associative map quite easily, but I'd be fairly sure Hana will likely be beyond most students.
If using Hana is beyond most GSoC students, it seems like writing a `constexpr` associative map will be too. For example, computing the amount of storage space needed for the map must be done _before_ entering the constexpr function in its return type, which I think is harder to grasp than the purely runtime components of Hana. And if the student can understand that level of TMP, then Hana should not be an issue.
All absolutely true, but you're forgetting the time it takes to master a Boost library and a Boost/STL idiomatic practice. As a general rule, if they are extending a Boost library they just about get going by the end of the summer after a lot of help, whereas if it's new code you tend to see more get accomplished because they are more psychologically invested for them to build their own thing rather than build atop someone else's thing (despite that the latter is almost certainly better for them in terms of training).
#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 } };
The macro `STRING_VIEW` seems unnecessary because the `string_view` constructor taking a single NULL-terminated string is also `constexpr`. Although, it could reduce the amount of computation done by the C++ interpreter in the compiler.
Sadly, the current proposal for string_view does not provide a default Traits length function which is constexpr for const char *. Yes, I find that very daft as a default design choice for a string_view, but the macro at least makes it not too irritating. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
I've experimented with static_map quite a bit. But never with C++11/14, unfortunately. Some thoughts: - once you have static_map<A,B>, the next thing you immediately want is bi_map<A,B> - to offer two way lookup. - and from there, you want multiple keys and columns: <A,B,C> - and maybe projection functions as well: <A,B,C, key(B)> I'm not sure, however, what the usage looks like for the bimap and multimap cases. It is no longer the simple syntax of mapvar[a] = b; - I had static_map<A, B> was not copyable, but static_map<A, const B> was copyable (but didn't actually do a copy, since it is immutable - just stored a reference). Not really sure about the benefit of that design decision, however. Possibly due to limitations with pre-11 C++, I had a two-step process for declaring/defining the map: // the map is this type typedef static_map<A,B> ab_map; // but the data/table is an array of this type: // using the inner element_type means you don't repeat A,B (more robust to changes) static ab_map::table_entry_type ab_table[] = { { a1, b1 }, { a2, b2 }, ... }; // the actual map: ab_map theMap = ab_table; // constructor does magic Doing a bi-map is fairly easy above, as table_entry_type can actually be { A, B, reverse_index } but the { a1, b1 } initialization is still valid as the reverse_index gets initialized to 0. The reverse_index is basically an extra hidden column. Constexpr probably gets rid of many of those problems. On Wed, Jan 13, 2016 at 2:43 PM, Niall Douglas <s_sourceforge@nedprod.com> wrote:
On 13 Jan 2016 at 13:25, Lee Clagett wrote:
Can I quickly check here if that claim is true? Is there a better way than my example program?
AFAIK your code is the current best practice for generating a constant static map with runtime lookups
Cool, thanks for having a look.
[1]: I believe Boost.Hana could implement a static constan associative map quite easily, but I'd be fairly sure Hana will likely be beyond most students.
If using Hana is beyond most GSoC students, it seems like writing a `constexpr` associative map will be too. For example, computing the amount of storage space needed for the map must be done _before_ entering the constexpr function in its return type, which I think is harder to grasp than the purely runtime components of Hana. And if the student can understand that level of TMP, then Hana should not be an issue.
All absolutely true, but you're forgetting the time it takes to master a Boost library and a Boost/STL idiomatic practice. As a general rule, if they are extending a Boost library they just about get going by the end of the summer after a lot of help, whereas if it's new code you tend to see more get accomplished because they are more psychologically invested for them to build their own thing rather than build atop someone else's thing (despite that the latter is almost certainly better for them in terms of training).
#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 } };
The macro `STRING_VIEW` seems unnecessary because the `string_view` constructor taking a single NULL-terminated string is also `constexpr`. Although, it could reduce the amount of computation done by the C++ interpreter in the compiler.
Sadly, the current proposal for string_view does not provide a default Traits length function which is constexpr for const char *. Yes, I find that very daft as a default design choice for a string_view, but the macro at least makes it not too irritating.
Niall
-- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 14 Jan 2016 at 13:02, Gottlob Frege wrote:
I've experimented with static_map quite a bit. But never with C++11/14, unfortunately.
Some thoughts:
- once you have static_map<A,B>, the next thing you immediately want is bi_map<A,B> - to offer two way lookup. - and from there, you want multiple keys and columns: <A,B,C> - and maybe projection functions as well: <A,B,C, key(B)>
Added to the project idea at https://svn.boost.org/trac/boost/wiki/SoC2016, thank you.
I'm not sure, however, what the usage looks like for the bimap and multimap cases. It is no longer the simple syntax of mapvar[a] = b;
Easy if type Key != type Value OR if type Key == type Value and key != value, but implicit in a bimap is you can't modify anything at all, the map is 100% const. That still has wide use cases.
Possibly due to limitations with pre-11 C++, I had a two-step process for declaring/defining the map:
// the map is this type typedef static_map<A,B> ab_map;
// but the data/table is an array of this type: // using the inner element_type means you don't repeat A,B (more robust to changes) static ab_map::table_entry_type ab_table[] = { { a1, b1 }, { a2, b2 }, ... };
// the actual map:
ab_map theMap = ab_table; // constructor does magic
Doing a bi-map is fairly easy above, as table_entry_type can actually be { A, B, reverse_index } but the { a1, b1 } initialization is still valid as the reverse_index gets initialized to 0. The reverse_index is basically an extra hidden column.
Constexpr probably gets rid of many of those problems.
Very interesting, especially as you've tapped exactly where I got this GSoC project idea from. In the post peer review AFIO v2 rewrite I have this new concept of "storage profiles" which is an empirically determined set of characteristics about file i/o on some given combination of filing system, disk drive, disk controller, motherboard, CPU and OS version. Each storage profile is a static map of const char *keys to some type T which can be any of std::string, unsigned long long, unsigned int, float etc. and can be written or loaded from a YAML database. The concept is that a "standard" YAML database can be kept in the AFIO distro for quick lookup of common system configurations, but for uncommon configurations a suite of tests can be run to figure out the profile for some given storage combo. This lets AFIO v2 become less conservative on some systems. For example, if a system guarantees atomic updates for 4Kb write bursts if and only if on a 4Kb aligned boundary (this is very common on PCIe systems) but otherwise only guarantees atomic updates to a 64 byte burst on a 64 byte aligned boundary, AFIO can dispense with explicit byte range locking in a much wider range of use cases. Anyway, AFIO v2's storage_profile looks a bit like this: //! A (possibly incomplet) profile of storage struct BOOST_AFIO_DECL storage_profile { ... item<unsigned long long> mem_quantity = { "system:mem:quantity", &system::mem }; item<float> mem_in_use = { "system:mem:in_use", &system::mem }; // Controller characteristics item<std::string> controller_type = { "storage:controller:kind", &storage::device }; item<unsigned> controller_max_transfer = { "storage:controller:max_transfer", storage::device, "The maximum number of bytes the disk controller can transfer at once" }; item<unsigned> controller_max_buffers = { "storage:controller:max_buffers", storage::device, "The maximum number of scatter-gather buffers the disk controller can handle" }; ... }; So what we are doing is to use in-class initialisation to default construct all these member variables to their YAML section plus key, an address of a function capable of figuring out that value through testing, and an optional description text. This syntax makes it dead easy to add new items to the profile, simply add another in-class initialised member variable and voila it's done. Now as much as the above is great, I am still not happy with this design of storage_profile because I have to duplicate the YAML text key and the variable name which seems unnecessary in C++ 14. I would much prefer a static map of text keys to type erased value instead where storage_profile["storage:controller:max_buffers"].set_value(5); ... does *exactly* the right thing because the compiler, entirely at compile time, turns the string key lookup into a storage location of an unsigned value in storage_profile, so I would expect the assembler generated by the compiler by the above statement to look something like: mov r0, #5 str r0, [storage_profile + #offset ] ... and that is entirely it. A proposed constexpr static map would deliver exactly what I am looking for, and I for one would be pleased. tl;dr; I think we are on exactly the same page with the same use case and problem to be solved here. Unsurprising seeing as we used to work in the same team :) Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
On 14 Jan 2016 at 13:02, Gottlob Frege wrote: I had a crack this weekend at a toy static_map to see if I could improve on Louis' toy solution from https://gist.github.com/ldionne/f7ff609f00dc7025a213. I learned many very interesting things.
Possibly due to limitations with pre-11 C++, I had a two-step process for declaring/defining the map:
It turns out this restriction remains in C++ 14, and currently C++ 17. The problem is that nested braced init of heterogeneous types is basically only possible via a C array, so either you do this: constexpr std::pair<int, const char *> map_data[] = { { 5, "apple" }, { 8, "pear" }, { 0, "banana" } }; constexpr auto cmap = make_static_map(map_data); ... or you do as Louis did: constexpr auto cmap = make_static_map( std::make_pair(5, "apple"), std::make_pair(8, "pear"), std::make_pair(0, "banana") ); I personally think the first form looks nicer. If C++ 17 could gain the ability to convert nested braced init sequences of heterogeneous types in a set of nested std::make_tuple()'s, I think that would be a great language addition for C++ 17.
Constexpr probably gets rid of many of those problems.
Unfortunately, constexpr as currently implemented by at least clang 3.7 and VS2015 is lazy not greedy, so currently even if all the inputs to a constexpr expression are constexpr but the returned value is not stored constexpr, right now the expression is not executed constexpr by any major compiler. In code: // No output in assembler, so constexpr except on GCC 5.3 constexpr auto cmap = make_static_map(map_data); // No abort() appears in assembler except on GCC 5.3, so this // was executed constexpr if(!cmap[8]) abort(); // This however does cause code implementing a lookup to be generated // on all compilers, so this was NOT executed constexpr. The cause is // storing the result in a non-constexpr variable. const char *foo=cmap[5]; If you'd like to play with this yourselves, see https://goo.gl/eO7ooa. I was not aware of that constexpr is currently implemented lazy not greedy before, and I still find it a highly surprising choice to not avail of an optimisation. GCC is particularly conservative in not making use of constexpr execution at all, even VS2015 matches clang 3.7. Note that the C++ standard, in so far as I can tell, gives compiler implementors the choice of what to do if the results from a constant expression are not used in a constant expression - they can either execute constexpr, or not. I therefore assume the compiler vendors have good reasons for choosing to generate code when the standard says they don't have to. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
Hi Niall Douglas,
If it is constexpr, it can only be modified in a constexpr evaluation context, and otherwise not.
When a variable is declared as constexpr, it seems it’s also const, constexpr int foo() { constexpr int i = 5; i = 6; return i; } int main () { constexpr int j = foo(); return 0; } foo is a constexpr evaluation context, but modification of i in it will still leads to compile error.
• Values, though not keys nor number of items, are modifiable.
So I think this feature is also challenging. In your crack, https://goo.gl/eO7ooa <https://goo.gl/eO7ooa>, if I add cmap[0] = “orange”; in main function, it will leads to compile error.
// 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];
I find some macro which can force constexpr function evaluation (Add it in your crack) #define AT_CONSTEXPR_KEY(_MAP, _KEY) [&_MAP, &_KEY](){constexpr auto value = _MAP[_KEY]; return value;}() #define AT_TEMP_KEY(_MAP, _KEY) [&_MAP](){constexpr auto value = _MAP[_KEY]; return value;}() constexpr int key = 5; const char* foo1 = AT_CONSTEXPR_KEY(cmap, key); const char* foo2 = AT_TEMP_KEY(cmap, 8); It indeed generates no additional code, but I don’t know how to unify these two macros. In addition, following expression will leads to compile error as lambda function can’t be constexpr now. constexpr const char* foo1 = AT_CONSTEXPR_KEY(cmap, key); constexpr const char* foo2 = AT_TEMP_KEY(cmap, 8); Shangtong Zhang, Senior Student, School of Computer Science, Fudan University, PRC.
On 18 Jan 2016 at 21:17, Shangtong Zhang wrote:
If it is constexpr, it can only be modified in a constexpr evaluation context, and otherwise not.
When a variable is declared as constexpr, it seems it’s also const,
constexpr int foo() { constexpr int i = 5; i = 6; return i; }
int main () { constexpr int j = foo(); return 0; }
foo is a constexpr evaluation context, but modification of i in it will still leads to compile error.
I admit surprise the code above is disallowed, but I haven't studied the text of the C++ 14 ISO standard like I did the C++ 11 standard. What definitely does work in C++ 14 is that non-const constexpr member functions are allowed to mutate *this, and I've made extensive use of this in my own code.
• Values, though not keys nor number of items, are modifiable.
So I think this feature is also challenging. In your crack, https://goo.gl/eO7ooa <https://goo.gl/eO7ooa>, if I add cmap[0] = “orange”; in main function, it will leads to compile error.
Correct, because cmap has constexpr storage. I meant that if and only if you store the static map into a non-constexpr variable (like the "map" variable in my code example), values become mutable but key-lookup-to-value remains constexpr. In other words, the implementation becomes 100% constexpr when the map is stored constexpr, but only key lookup to value is 100% constexpr when the map is not stored constexpr. This part is the challenging part, and what makes this GSoC project idea non-trivial to implement. This is why a successful candidate for this project idea will need excellent constexpr programming skills. See https://svn.boost.org/trac/boost/wiki/SoC2016 for a recently expanded project idea description. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
On 1/13/2016 9:43 PM, Niall Douglas wrote:
#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 } };
The macro `STRING_VIEW` seems unnecessary because the `string_view` constructor taking a single NULL-terminated string is also `constexpr`. Although, it could reduce the amount of computation done by the C++ interpreter in the compiler. Sadly, the current proposal for string_view does not provide a default Traits length function which is constexpr for const char *. Yes, I find that very daft as a default design choice for a string_view, but the macro at least makes it not too irritating.
Perhaps you can get rid of the macro this way: template <int Len> constexpr string_view str_view(const char (&s)[Len]) { return string_view(s, Len); }
Why not: { "sunday"_literal, weekday::sunday }, { "monday"_literal, weekday::monday }, { "tuesday"_literal, weekday::tuesday }, { "wednesday"_literal, weekday::wednesday }, { "thursday"_literal, weekday::thursday }, { "friday"_literal, weekday::friday }, { "saturday"_literal, weekday::saturday } Where: constexpr basic_literal<char> operator"" _string(const char* s, std::size_t n) { return basic_literal<char>(s, n); } Where basic_literal<T> can only be constructed via the UDL operators. Glen -- View this message in context: http://boost.2283326.n4.nabble.com/gsoc16-Can-I-quickly-check-if-the-below-r... Sent from the Boost - Dev mailing list archive at Nabble.com.
Why not: { "sunday"_literal, weekday::sunday }, { "monday"_literal, weekday::monday }, { "tuesday"_literal, weekday::tuesday }, { "wednesday"_literal, weekday::wednesday }, { "thursday"_literal, weekday::thursday }, { "friday"_literal, weekday::friday }, { "saturday"_literal, weekday::saturday } Where: constexpr basic_literal<char> operator"" _literal(const char* s, std::size_t n) { return basic_literal<char>(s, n); } Where basic_literal<T> can only be constructed via the UDL operators. Glen -- View this message in context: http://boost.2283326.n4.nabble.com/gsoc16-Can-I-quickly-check-if-the-below-r... Sent from the Boost - Dev mailing list archive at Nabble.com.
On Wed, Jan 13, 2016 at 11:43 AM, Niall Douglas <s_sourceforge@nedprod.com> wrote:
Sadly, the current proposal for string_view does not provide a default Traits length function which is constexpr for const char *. Yes, I find that very daft as a default design choice for a string_view, but the macro at least makes it not too irritating.
It uses the existing char_traits classes, which, as you note, are not constexpr. (for some *very odd* reasons).
But writing your own traits class that has constexpr len/compare/etc is really, really simple. Maybe I'll do that this weekend, and add it to boost. :-) -- Marshall
On 14 January 2016 at 22:41, Marshall Clow <mclow.lists@gmail.com> wrote:
On Wed, Jan 13, 2016 at 11:43 AM, Niall Douglas <s_sourceforge@nedprod.com
wrote:
Sadly, the current proposal for string_view does not provide a default Traits length function which is constexpr for const char *. Yes, I find that very daft as a default design choice for a string_view, but the macro at least makes it not too irritating.
It uses the existing char_traits classes, which, as you note, are not constexpr. (for some *very odd* reasons).
But writing your own traits class that has constexpr len/compare/etc is really, really simple. Maybe I'll do that this weekend, and add it to boost. :-)
Because it gets passed in as a template parameter, it isn't really all that general a solution, as it makes your string and string_view types different than std::string and std::experimental_string_view. If it is only used for initializing the static_map, that would probably be fine, but if it appears anywhere else in the interface, it just makes the static_map harder to use. You really want static_map<std::experimental::string_view, value> to just work so that you can do runtime lookups using C string literals and std:string directly. -- Nevin ":-)" Liber <mailto:nevin@cplusplusguy.com <nevin@eviloverlord.com>> +1-847-691-1404
On 1/15/2016 7:00 PM, Nevin Liber wrote:
On 14 January 2016 at 22:41, Marshall Clow <mclow.lists@gmail.com> wrote:
On Wed, Jan 13, 2016 at 11:43 AM, Niall Douglas <s_sourceforge@nedprod.com
wrote:
Sadly, the current proposal for string_view does not provide a default Traits length function which is constexpr for const char *. Yes, I find that very daft as a default design choice for a string_view, but the macro at least makes it not too irritating.
It uses the existing char_traits classes, which, as you note, are not constexpr. (for some *very odd* reasons).
But writing your own traits class that has constexpr len/compare/etc is really, really simple. Maybe I'll do that this weekend, and add it to boost. :-)
Because it gets passed in as a template parameter, it isn't really all that general a solution, as it makes your string and string_view types different than std::string and std::experimental_string_view.
This is a very good point. However, nothing stops us from internally mapping `std::char_traits<CharT>` to `boost::detail::constexpr_char_traits<CharT>` when the compiler supports C++14 constexpr. Regards, -- Agustín K-ballo Bergé.- http://talesofcpp.fusionfenix.com
Niall Douglas <s_sourceforge <at> nedprod.com> writes:
Dear Boost,
In the prototype https://svn.boost.org/trac/boost/wiki/SoC2016 at https://goo.gl/1CQAuQ I claim "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" and you can find either the code at the link or pasted below.
Can I quickly check here if that claim is true? Is there a better way than my example program?
I don't see an __easy__ way to do better, i.e. without writing your own map.
BTW by static constant associative map of keys to values I mean the thing me and Tony van Eerd were speaking about here last year and the year before, and indeed frequently at BlackBerry!
Niall
[1]: I believe Boost.Hana could implement a static constan associative map quite easily, but I'd be fairly sure Hana will likely be beyond most students.
Only if the keys are known at compile-time. Otherwise, it's out of Hanaland. Anyway, here's an attempt to implement such a map: https://gist.github.com/ldionne/f7ff609f00dc7025a213 I don't know if it's worthwhile, but it's there. Don't hesitate to let me know what you think. Regards, Louis
At Fri, 15 Jan 2016 00:46:51 +0000 (UTC) Louis Dionne wrote:
Niall Douglas <s_sourceforge <at> nedprod.com> writes:
Dear Boost,
In the prototype https://svn.boost.org/trac/boost/wiki/SoC2016 at https://goo.gl/1CQAuQ I claim "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" and you can find either the code at the link or pasted below.
Can I quickly check here if that claim is true? Is there a better way than my example program?
I don't see an __easy__ way to do better, i.e. without writing your own map.
BTW by static constant associative map of keys to values I mean the thing me and Tony van Eerd were speaking about here last year and the year before, and indeed frequently at BlackBerry!
Niall
[1]: I believe Boost.Hana could implement a static constan associative map quite easily, but I'd be fairly sure Hana will likely be beyond most students.
Only if the keys are known at compile-time. Otherwise, it's out of Hanaland.
Anyway, here's an attempt to implement such a map:
https://gist.github.com/ldionne/f7ff609f00dc7025a213
I don't know if it's worthwhile, but it's there. Don't hesitate to let me know what you think.
Regards, Louis
This mockup did highlight that a constexpr hash function needs to be implemented for this potential GSoC project. `std::hash` and the boost equivalent are not constexpr. `find_if`, also not constexpr (mentioned in comments), should be easier to implement. Also, seeing this code made me think about a collision threshold, which would trigger a compile-time error if reached. A user could then tweak the load-factor, hash function, keys, or readjust their target. The threshold would be useful in reducing the scanning during a miss on a dense hash map, since the max collisions would be known at compile-time. Although, static maps are generally going to be smaller in the number of keys than the dynamic counterparts, and increasing the load factor will leave gaps in the hash map (which identify a miss), so maybe this won't be useful. Lee
On 15 Jan 2016 at 0:46, Louis Dionne wrote:
[1]: I believe Boost.Hana could implement a static constan associative map quite easily, but I'd be fairly sure Hana will likely be beyond most students.
Only if the keys are known at compile-time. Otherwise, it's out of Hanaland.
Anyway, here's an attempt to implement such a map:
https://gist.github.com/ldionne/f7ff609f00dc7025a213
I don't know if it's worthwhile, but it's there. Don't hesitate to let me know what you think.
Yep, you've pretty much got the bones of the completed GSoC idea there Louis, and interesting how there is no Hana in there. I like how it only took you a few hours rather than a summer! If only GSoC students like you came along every year ... my word would we make some amazing progress in Boost libraries. Anyway, I still reckon if a student completes in a summer what took you a few hours (much of the summer will go on writing tests and docs of course) then I would be very pleased with that student. You were and still are very unusual Louis. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
Niall Douglas <s_sourceforge <at> nedprod.com> writes:
On 15 Jan 2016 at 0:46, Louis Dionne wrote:
[1]: I believe Boost.Hana could implement a static constan associative map quite easily, but I'd be fairly sure Hana will likely be beyond most students.
Only if the keys are known at compile-time. Otherwise, it's out of Hanaland.
Anyway, here's an attempt to implement such a map:
https://gist.github.com/ldionne/f7ff609f00dc7025a213
I don't know if it's worthwhile, but it's there. Don't hesitate to let me know what you think.
Yep, you've pretty much got the bones of the completed GSoC idea there Louis, and interesting how there is no Hana in there.
Hana is really about heterogeneous data structures and algorithms. While technically possible, using Hana would incur a higher compile-time cost, and the solution would most likely end up being more difficult to properly optimize for the compiler. The bottom line really is that if you don't need heterogeneity, you're probably better off using a bare bones solution than Hana.
I like how it only took you a few hours rather than a summer!
If only GSoC students like you came along every year ... my word would we make some amazing progress in Boost libraries. Anyway, I still reckon if a student completes in a summer what took you a few hours (much of the summer will go on writing tests and docs of course) then I would be very pleased with that student. You were and still are very unusual Louis.
Do not forget that I have spent a significant amount of time working on Hana, without which it would have taken me much longer to write this prototype. But thanks for the kind words anyway. Regards, Louis
participants (13)
-
Agustín K-ballo Bergé -
Boris Rasin -
Gavin Lambert -
Glen Fernandes -
Gottlob Frege -
Lee Clagett -
Louis Dionne -
Marshall Clow -
Nevin Liber -
Nevin Liber -
Niall Douglas -
Shangtong Zhang -
Steven Watanabe