[llvm-bugs] [Bug 47602] New: __internal::__lazy_and needs to be more lazy

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=47602

            Bug ID: 47602
           Summary: __internal::__lazy_and needs to be more lazy
           Product: parallel STL
           Version: unspecified
          Hardware: All
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: New
          Assignee: ldionne at apple.com
          Reporter: zilla at kayari.org
                CC: llvm-bugs at lists.llvm.org

In pstl/include/pstl/internal/execution_impl.h these function templates are
defined:

template <typename _Tp>
std::false_type __lazy_and(_Tp, std::false_type)
{
    return std::false_type{};
};

template <typename _Tp>
inline _Tp
__lazy_and(_Tp __a, std::true_type)
{
    return __a;
}

(There are also __lazy_or function template which seem to be completely
unused).

It gets used in code like this:

template <typename _ExecutionPolicy, typename... _IteratorTypes>
auto
__is_vectorization_preferred(_ExecutionPolicy&& __exec)
    -> decltype(__internal::__lazy_and(__exec.__allow_vector(),
                                       typename
__internal::__is_random_access_iterator<_IteratorTypes...>::type()))
{
    return __internal::__lazy_and(__exec.__allow_vector(),
                                  typename
__internal::__is_random_access_iterator<_IteratorTypes...>::type());
}


Where __allow_vector is a specialization of a relatively inexpensive class
template, and __is_random_access_iterator is a recursive class template:


template <typename _IteratorType, typename... _OtherIteratorTypes>
struct __is_random_access_iterator
{
    static constexpr bool value =
__internal::__is_random_access_iterator<_IteratorType>::value &&
                                 
__internal::__is_random_access_iterator<_OtherIteratorTypes...>::value;
    typedef std::integral_constant<bool, value> type;
};

template <typename _IteratorType>
struct __is_random_access_iterator<_IteratorType>
    : std::is_same<typename
std::iterator_traits<_IteratorType>::iterator_category,
std::random_access_iterator_tag>
{
};


Unless I'm mistaken, the only thing that is lazy here is the instantiation of
__allow_vector::value, which is cheap anyway.

In order to choose an overload of __lazy_and the second argument needs to be
complete, which instantiates
__is_random_access_iterator<_IteratorTypes...>::type which requires the
instantiation of __is_random_access_iterator<_IteratorTypes...>::value, which
is VERY UN-LAZY. It requires instantiating __is_random_access_iterator for
every element of the pack, even if the first element is not a random access
iterator.

A better implementation of __is_random_access_iterator would be:

template <typename _IteratorType, typename... _OtherIteratorTypes>
struct __is_random_access_iterator;

template <typename _IteratorType>
struct __is_random_access_iterator<_IteratorType>
    : std::is_same<typename
std::iterator_traits<_IteratorType>::iterator_category,
std::random_access_iterator_tag>
{
};

template <typename _IteratorType, typename... _OtherIteratorTypes>
struct __is_random_access_iterator
    : std::conjunction<__is_random_access_iterator<_IteratorType>,
                      
__is_random_access_iterator<_OtherIteratorTypes>...>::type
{
};

Personally I'd get rid of __lazy_and completely, make
__is_random_access_iterator non-variadic, and write the functions using it like
this (assuming bug 47601 gets fixed so the __alow_vector alias template works):

template <typename _ExecutionPolicy, typename... _IteratorTypes>
typename std::conjunction<__allow_vector<_ExecutionPolicy>,
           __is_random_access_iterator<_IteratorTypes>...>::type
__is_vectorization_preferred(_ExecutionPolicy&&)
{
    return {};
}


This is actually lazy. It never instantiates any __is_random_access_iterator
specialization if the __allow_vector trait is false, and only instantiates as
many as needed to determine the answer.

(N.B. the __exec parameter is redundant, since the _ExecutionPolicy type has to
be given explicitly anyway, and that already provides all the information
required, but changing that would require changes to every caller).

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20200921/a0a07462/attachment.html>