Re: [boost] [review][mp11] Reminder of ongoing formal review

Subject: Re: [boost] [review][mp11] Reminder of ongoing formal review
From: Joaquin M López Muñoz (joaquinlopezmunoz_at_[hidden])
Date: 2017-07-24 10:05:26

El 23/07/2017 a las 14:42, Peter Dimov via Boost escribió:
>> Roberto Hinz wrote:
>> > Hi,
>> >
>> > not a review yet.
>> > I´m just wondering: would the implementation below perfom better 
>> than > the recursive version of mp_find_impl ?
>> > I think it should perform better when one uses mp_find several 
>> times in > the same list.
>> > It also compiles in vs2013.
>>
>> It performs better across the board (for repeated finds).
>
> Upon further experimentation, while it does perform very well for 
> repeated finds such as those done by this test case:
>
>    using L1 = mp_iota_c<300>;
>    template<class T> using F = mp_find<L1, T>;
>    using L2 = mp_transform<F, L1>;
>    static_assert( std::is_same<L1, L2>::value, "L1 != L2" );
>
> it has a large one-time cost in both time and heap space, making it 
> unsuitable for N in the thousands. 

The following alternative based on bool sequences seems to perform very 
well for the mp_iota_c case
(basically, mp_find runs out of heap space in my machine for 
mp_iota_c<300> whereas mp_find2 takes
4-5 s). Don't know if mp_find2 stands up for other scenarios:

   template<bool... B>
   struct mp_find2_bools{};

   template<bool... B>
   struct 
mp_find2_bools<false,false,false,false,false,false,false,false,false,false,B...>
   {static constexpr std::size_t value=10+mp_find2_bools<B...>::value;};

   template<>
   struct 
mp_find2_bools<false,false,false,false,false,false,false,false,false>
   {static constexpr std::size_t value=9;};

   template<>
   struct mp_find2_bools<false,false,false,false,false,false,false,false>
   {static constexpr std::size_t value=8;};

   template<>
   struct mp_find2_bools<false,false,false,false,false,false,false>
   {static constexpr std::size_t value=7;};

   template<>
   struct mp_find2_bools<false,false,false,false,false,false>
   {static constexpr std::size_t value=6;};

   template<>
   struct mp_find2_bools<false,false,false,false,false>
   {static constexpr std::size_t value=5;};

   template<>
   struct mp_find2_bools<false,false,false,false>
   {static constexpr std::size_t value=4;};

   template<>
   struct mp_find2_bools<false,false,false>
   {static constexpr std::size_t value=3;};

   template<>
   struct mp_find2_bools<false,false>
   {static constexpr std::size_t value=2;};

   template<>
   struct mp_find2_bools<false>
   {static constexpr std::size_t value=1;};

   template<>
   struct mp_find2_bools<>
   {static constexpr std::size_t value=0;};

   template<bool... B>
   struct 
mp_find2_bools<false,false,false,false,false,false,false,false,false,true,B...>
   {static constexpr std::size_t value=9;};

   template<bool... B>
   struct 
mp_find2_bools<false,false,false,false,false,false,false,false,true,B...>
   {static constexpr std::size_t value=8;};

   template<bool... B>
   struct 
mp_find2_bools<false,false,false,false,false,false,false,true,B...>
   {static constexpr std::size_t value=7;};

   template<bool... B>
   struct mp_find2_bools<false,false,false,false,false,false,true,B...>
   {static constexpr std::size_t value=6;};

   template<bool... B>
   struct mp_find2_bools<false,false,false,false,false,true,B...>
   {static constexpr std::size_t value=5;};

   template<bool... B>
   struct mp_find2_bools<false,false,false,false,true,B...>
   {static constexpr std::size_t value=4;};

   template<bool... B>
   struct mp_find2_bools<false,false,false,true,B...>
   {static constexpr std::size_t value=3;};

   template<bool... B>
   struct mp_find2_bools<false,false,true,B...>
   {static constexpr std::size_t value=2;};

   template<bool... B>
   struct mp_find2_bools<false,true,B...>
   {static constexpr std::size_t value=1;};

   template<bool... B>
   struct mp_find2_bools<true,B...>
   {static constexpr std::size_t value=0;};

   template<typename L,typename V>
   struct mp_find2_impl;

   template<template<typename...> class L,typename... T,typename V>
   struct 
mp_find2_impl<L<T...>,V>:mp_find2_bools<std::is_same<T,V>::value...>{};

   template<typename L,typename V> using 
mp_find2=mp_size_t<mp_find2_impl<L,V>::value>;

Joaquín M López Muñoz