Quantcast

[gsoc17] Project1: Static map: Can I implement the competency test in g++-7?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[gsoc17] Project1: Static map: Can I implement the competency test in g++-7?

Boost - Dev mailing list
Hi,

I'm Zheng Luo, a third-year undergraduate from Shanghai Jiaotong
University who have special interest in C++ programming(especially for
templates). This is my second year of applying Google Summer of Code and
I'm willing to contribute to Static Map project mentioned on SoC2017
page. Previously I worked for a company as a C++ intern for months on
Chromium-related projects where I gained some experience about C++ in
industry.

And my question is, am I allowed to implement the competency test of
static_map in g++-7? I have just implemented my own version of
static_map which supports the following operations:


constexpr StaticMap<int, const char *, 3> m(make_pair(2, "abc"),
make_pair(4, "def"), make_pair(6, "ghi"));

    if (!m[4])
      abort();
    const char *foo = m[2];
    return 0;


which is compiled into assembly as:

main:
        xorl    %eax, %eax
        ret

under g++-7 with -std=c++1z -O3

So I was wondering did I pass the test?

Thanks,

--
---------------------------------
Vic Luo
Shanghai Jiaotong University

Key fingerprint 0x98809ca08bf5662a

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gsoc17] Project1: Static map: Can I implement the competency test in g++-7?

Boost - Dev mailing list
Hi Zheng Luo,

My name is Ruoyun Jing, a third year student from Northwest University in
China, these is the first time i participate in GSoc. For we come from same
country, :) can i have your wechat or QQ to ask you some questions about
GSoC ?:)

Looking forward from you!!

Thanks.

2017-03-04 0:18 GMT+08:00 Vic Luo via Boost <[hidden email]>:

> Hi,
>
> I'm Zheng Luo, a third-year undergraduate from Shanghai Jiaotong
> University who have special interest in C++ programming(especially for
> templates). This is my second year of applying Google Summer of Code and
> I'm willing to contribute to Static Map project mentioned on SoC2017
> page. Previously I worked for a company as a C++ intern for months on
> Chromium-related projects where I gained some experience about C++ in
> industry.
>
> And my question is, am I allowed to implement the competency test of
> static_map in g++-7? I have just implemented my own version of
> static_map which supports the following operations:
>
>
> constexpr StaticMap<int, const char *, 3> m(make_pair(2, "abc"),
> make_pair(4, "def"), make_pair(6, "ghi"));
>
>     if (!m[4])
>       abort();
>     const char *foo = m[2];
>     return 0;
>
>
> which is compiled into assembly as:
>
> main:
>         xorl    %eax, %eax
>         ret
>
> under g++-7 with -std=c++1z -O3
>
> So I was wondering did I pass the test?
>
> Thanks,
>
> --
> ---------------------------------
> Vic Luo
> Shanghai Jiaotong University
>
> Key fingerprint 0x98809ca08bf5662a
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/
> mailman/listinfo.cgi/boost
>



--
Northwest University of China
Software Engineering
[hidden email] <[hidden email]>

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gsoc17] Project1: Static map: Can I implement the competency test in g++-7?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Hi,

I would like to share my progress on the competency project made
recently. I managed to implement:

  constexpr std::pair<const int, const char *> map_data[] = {
    { 5, "apple" },
    { 8, "pear" },
    { 0, "banana" }
};

   constexpr auto cmap = make_static_map(map_data);
    if (!has_str(cmap, "apple")) abort();
    if (!has_str(cmap, "pear")) abort();

    if(!cmap[8]) abort();
    const char *foo=cmap[5];
    const char *bar = std::get<2>(cmap);
    if (strcmp(bar, "banana")) abort();
   // system(cmap[8]);
 
    auto m = make_static_map(map_data);
     m[0] = "strawberry";
    system(m[0]);

with zero runtime overhead and O(1) compile-time complexity(measured by
template instantiation) on g++-6+ and clang-3.6+ with flag -std=c++14
and -O3. It is also experimented that zero runtime and O(1) compile-time
complexity could be achieved on constant path of g++-5. In the next few
days, I'm going to focus on MSVC2017 efficient implementation.

Regarding the design of static_map's interface, I doubt that is it
possible or worthwhile to implement a subscript-like operator/function
that checks boundary at compile time(given that key is a constant
expression)? Compilation errors tend to be more likely to be discovered
than runtime exception.

Thanks,


On 03/04/2017 12:18 AM, Vic Luo wrote:

> Hi,
>
> I'm Zheng Luo, a third-year undergraduate from Shanghai Jiaotong
> University who have special interest in C++ programming(especially for
> templates). This is my second year of applying Google Summer of Code and
> I'm willing to contribute to Static Map project mentioned on SoC2017
> page. Previously I worked for a company as a C++ intern for months on
> Chromium-related projects where I gained some experience about C++ in
> industry.
>
> And my question is, am I allowed to implement the competency test of
> static_map in g++-7? I have just implemented my own version of
> static_map which supports the following operations:
>
>
> constexpr StaticMap<int, const char *, 3> m(make_pair(2, "abc"),
> make_pair(4, "def"), make_pair(6, "ghi"));
>
>     if (!m[4])
>       abort();
>     const char *foo = m[2];
>     return 0;
>
>
> which is compiled into assembly as:
>
> main:
>         xorl    %eax, %eax
>         ret
>
> under g++-7 with -std=c++1z -O3
>
> So I was wondering did I pass the test?
>
> Thanks,
>

--
---------------------------------
Vic Luo
Shanghai Jiaotong University

Key fingerprint 0x98809ca08bf5662a



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gsoc17] Project1: Static map: Can I implement the competency test in g++-7?

Boost - Dev mailing list
> with zero runtime overhead and O(1) compile-time complexity(measured by
> template instantiation) on g++-6+ and clang-3.6+ with flag -std=c++14
> and -O3. It is also experimented that zero runtime and O(1) compile-time
> complexity could be achieved on constant path of g++-5. In the next few
> days, I'm going to focus on MSVC2017 efficient implementation.

The list should know I've been impressed with what candidate students
have sent me to prove their programming competency. It makes me feel old
and a little past it.

> Regarding the design of static_map's interface, I doubt that is it
> possible or worthwhile to implement a subscript-like operator/function
> that checks boundary at compile time(given that key is a constant
> expression)? Compilation errors tend to be more likely to be discovered
> than runtime exception.

So the list understands:

constexpr mapped_type &at(const key_type &key) const
{
   if(key_not_in_map)
       throw std::out_of_range();
}

This works under constexpr, but annoyingly causes the compiler to
generate code which throws std::out_of_range() which is a showstopper.
What would be much better:

constexpr mapped_type &at(const key_type &key) const
{
   static_assert(!key_not_in_map, "key not in map");
}

... but constexpr functions are not necessarily executed at compile
time, so we can't do this.

I believe C++ 17's if constexpr() would fix this, but having a C++ 14
solution would be nice.

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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gsoc17] Project1: Static map: Can I implement the competency test in g++-7?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Hi,

During the implementation of my static_map, I recently encountered a
problem: how to deal with string types?

For example:


    constexpr auto cmap_str = make_static_map({

        {"abc", 1},

        {"bcd", 2}

    });

    static_assert(cmap_str["abc"] == 1, "test");


In my implementation, KeyType requires

1. constexpr operator==, which is not provided by const char *

2. constexpr hash(const KeyType&). Since there is no such thing in
standard library, I have to implement some in this project.


Currently I would like to use string_view, since it looks like a general
solution for compile-time string with lots of constexpr functions, but I
don't know which of the following designs looks better:


Design A:

        template<typename KeyType,
        typename MappedType,
        typename EqualOp = StaticEqualOp<KeyType>,
        typename HashOp = StaticHashOp<KeyType>>
        class static_map;

        // StaticEqualOp: Specialize StaticEqualOp for those KeyTypes that

        // can construct string_view and use operator== of string_view,

        // otherwise we simply use operator== of KeyType

        // StaticHashOp: size_t operator()(const string_view&, const
string_view&)

        // for types that can construct string_view


Design B:

    We don't specialize any StaticEqualOp for const char*. Instead,
make_static_map({{"abc", 1}}) returns static_map<string_view, int>
instead of static_map<const char *, int>.


Which one is better? Or is there any more feasible design?

Thanks,

--
---------------------------------
Vic Luo
Shanghai Jiaotong University

Key fingerprint 0x98809ca08bf5662a


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gsoc17] Project1: Static map: Can I implement the competency test in g++-7?

Boost - Dev mailing list
> During the implementation of my static_map, I recently encountered a
> problem: how to deal with string types?

For the list's information, I wasn't sure what the best compile-time
string representation is currently considered to be, hence him asking here.

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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gsoc17] Project1: Static map: Can I implement the competency test in g++-7?

Boost - Dev mailing list
Besides, I found that boost::string_view is buggy regarding
constexpr(like many other STL implementation of std::string_view), thus
I opened a ticket at https://svn.boost.org/trac/boost/ticket/12897. This
makes this project even harder to tackle different types of constexpr
strings:-[


On 03/11/2017 12:29 AM, Niall Douglas via Boost wrote:
>> During the implementation of my static_map, I recently encountered a
>> problem: how to deal with string types?
> For the list's information, I wasn't sure what the best compile-time
> string representation is currently considered to be, hence him asking here.
>
> Niall
>

--
---------------------------------
Vic Luo
Shanghai Jiaotong University

Key fingerprint 0x98809ca08bf5662a




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

signature.asc (499 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gsoc17] Project1: Static map: Can I implement the competency test in g++-7?

Boost - Dev mailing list
On 13/03/2017 11:17, Vic Luo wrote:
> Besides, I found that boost::string_view is buggy regarding
> constexpr(like many other STL implementation of std::string_view), thus
> I opened a ticket at https://svn.boost.org/trac/boost/ticket/12897. This
> makes this project even harder to tackle different types of constexpr
> strings:-[

This is a long known issue. You should implement your own string
comparison routine which is constexpr. As you mention, Boost's
string_view is constrained by the STL's implementation of char_traits.

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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gsoc17] Project1: Static map: Can I implement the competency test in g++-7?

Boost - Dev mailing list
> This is a long known issue. You should implement your own string
> comparison routine which is constexpr. As you mention, Boost's
> string_view is constrained by the STL's implementation of char_traits.

Would it be OK to implement our own constexpr char_traits(just replace ::compare, ::length), then use
boost::basic_string_view<char, patched_char_traits<char>> as our CONSTEXPR_STRING_VIEW and compare views with
constexpr boost::string_view::compare(a, b) == 0? This way seems to work on my g++-6 which prevents
reinventing the wheel.

--
---------------------------------
Vic Luo
Shanghai Jiaotong University

Key fingerprint 0x98809ca08bf5662a




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

signature.asc (499 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gsoc17] Project1: Static map: Can I implement the competency test in g++-7?

Boost - Dev mailing list
On 13/03/2017 12:49, Vic Luo wrote:
>> This is a long known issue. You should implement your own string
>> comparison routine which is constexpr. As you mention, Boost's
>> string_view is constrained by the STL's implementation of char_traits.
>
> Would it be OK to implement our own constexpr char_traits(just replace ::compare, ::length), then use
> boost::basic_string_view<char, patched_char_traits<char>> as our CONSTEXPR_STRING_VIEW and compare views with
> constexpr boost::string_view::compare(a, b) == 0? This way seems to work on my g++-6 which prevents
> reinventing the wheel.

That's definitely one approach, if you're set on using string_view.

I had thought there was a proposed constexpr string container around,
but as nobody's mentioned anything, I guess string_view has superseded it.

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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [gsoc17] Project1: Static map: Can I implement the competency test in g++-7?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 03/13/17 15:49, Vic Luo via Boost wrote:
>> This is a long known issue. You should implement your own string
>> comparison routine which is constexpr. As you mention, Boost's
>> string_view is constrained by the STL's implementation of char_traits.
>
> Would it be OK to implement our own constexpr char_traits(just replace ::compare, ::length), then use
> boost::basic_string_view<char, patched_char_traits<char>> as our CONSTEXPR_STRING_VIEW and compare views with
> constexpr boost::string_view::compare(a, b) == 0? This way seems to work on my g++-6 which prevents
> reinventing the wheel.

First, it would make interaction with std::string (and its cousins)
problematic since they would still use std::char_traits, not
boost::char_traits.

Second, there is currently no way to select constexpr or runtime
implementation of a function depending on the arguments. This means that
the optimized versions of strlen/strcmp can't be used when the arguments
of string_view are runtime values.

IMO, the second problem is a showstopper for constexpr string_view.


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Loading...