16.03.2021 07:58
kiralexx 3 2000 Источник

При тестировании разрабатываемой библиотеки математических алгоритмов для автономного вождения нашей команде приходилось достаточно много манипулировать с кортежами (std::tuple): итерироваться по каждому элементу кортежа или в произвольном порядке, выбирать элементы, чьи индексы и/или значения удовлетворяют определенному условию, и т.д. Написание для каждого случая отдельной рекурсивной функции прохода по кортежу, во-первых, требует знания основ метапрограммирования и шаблонной магии, а во-вторых, отнимает существенное количество времени разработчика.

Мне в голову пришла идея: а что если получать доступ к элементам по индексу, не известному на этапе компиляции?

Теоретические предпосылки

Как известно, кортеж представляет из себя гетерогенный список, и в общем случае возвращаемое значение вышеупомянутой функции std::get может быть разным и зависит от переданного ей шаблонного параметра – индекса элемента в кортеже. Так, для типа std::tuple std::get<0> вернет int (на самом деле ссылку на int), а std::get<1> – double. Напишем объявление функции, которую мы хотим реализовать: 

template <class TupleT>
ReturnT get(TupleT && tuple, std::size_t index);

Шаблонный параметр TupleT – это тип передаваемого в функцию кортежа, а ReturnT – возвращаемое значение, которое нам необходимо определить. Данная функция возвращает элемент кортежа под номером index, значение которого мы не знаем во время компиляции, а следовательно, и не знаем тип элемента кортежа. Значит, нам нужен какой-то тип, который удовлетворяет всем типам, содержащимся в интересующем нас кортеже.

Возвращаемый тип

В 17 стандарте есть класс std::any, который может в себе хранить объект любого типа, однако хотелось бы избежать динамического выделения памяти для простого доступа элемента. Второй возможный тип – это шаблонный класс std::variant, параметры которого мы сейчас обсудим.

Но вначале надо определиться, что делать в случае, если нам передали невалидное значение индекса. Первый вариант, который приходит в голову, – это бросать исключение, например, объект типа std::out_of_range. Второй вариант – это возвращать какой-нибудь специальный тип, сигнализирующий невалидность переданного типа.

Первый вариант показался мне более предпочтительным, потому что возникновение исключительной ситуации в данном случае – это явно вина программиста, и ее, по идее, возникать не должно.

Теперь перейдем к возвращаемому значению. Первая мысль, которая пришла мне в голову – это возвращать std::variant с такими же шаблонными параметрами, как и подаваемый на вход кортеж. Напишем метафункцию на подобие type_traits стандартной библиотеки для этого:

template <class T>
struct ToVariant;

template <class T>
using ToVariantT = typename ToVariant<T>::type;

template <class... T>
struct ToVariant<std::tuple<T...>>
{
 using type = std::variant<T...>;
};

Эта метафункция определена только для типа std::tuple. Отлично, теперь у нас есть возвращаемый тип. Однако при каждом вызове нашей функции get происходит копирование имеющегося объекта, что в общем случае может быть достаточно дорогостоящей операцией.

Для решения этой проблемы мне показалось оптимальным использовать класс std::reference_wrapper из стандартной библиотеки, чтобы в нашем «варианте» хранить только ссылки на существующие объекты. Метафункция с учетом константности кортежа запишется так:

template <class T>
struct ToVariantRef;

template <class T>
using ToVariantRefT = typename ToVariantRef<T>::type;

template <class... T>
struct ToVariantRef<const std::tuple<T...>>
{
 using type = std::variant<std::reference_wrapper<std::add_const_t<T>>...>;
};

template <class... T>
struct ToVariantRef<std::tuple<T...>>
{
 using type = std::variant<std::reference_wrapper<T>...>;
};

Реализация функции get

Теперь я хочу привести реализации функции get в том порядке, в котором они приходили мне в голову. Первой идеей было использовать std::map, где ключам соответствовал бы индекс элемента, а значениям – непосредственно значения элементов кортежа. Реализация приведена ниже:

namespace detail
{

template <class TupleTRef, std::size_t... Idx,
          class ReturnT = ToVariantRefT<std::remove_reference_t<TupleTRef>>>
std::map<std::size_t, ReturnT> buildVariantMap(TupleTRef&& tuple,
                                               std::index_sequence<Idx...>)
{
    std::map<std::size_t, ReturnT> variantMap;
    (variantMap.emplace(Idx, ReturnT{
        std::in_place_index_t<Idx>{},
        std::ref( std::get<Idx>( std::forward<TupleTRef>( tuple ) ) ) }), ...);
    return variantMap;
}

} // namespace detail

template <class TupleTRef>
auto variantMapGet(TupleTRef && tuple, std::size_t index)
    -> ToVariantRefT<std::remove_reference_t<TupleTRef>>
{
    using TupleT = std::remove_reference_t<TupleTRef>;
 
    auto variantMap = detail::buildVariantMap(
        std::forward<TupleTRef>(tuple),
        std::make_index_sequence<std::tuple_size_v<TupleT>>{});
    return variantMap.at(index);
}

Мы используем std::make_index_sequence, чтобы из размера кортежа N получить последовательность 0...N-1, а в функции buildVariantMap мы используем fold expressions, чтобы заполнить нашу «мапу» значениями. Минусы такого подхода очевидны – из-за динамического выделения памяти такой подход будет работать очень медленно.

Еще одной идеей для улучшения было использование std::array вместо std::map. Я решил не приводить реализацию, т.к. она схожа с реализацией, использующей std::map. В таком случае все наши данные будут лежать на стеке и данный подход намного быстрее использования std::map. Однако создавать массив на N элементов для доступа всего к одному из них все равно достаточно расточительно.

Следующей моей мыслью было использовать линейный поиск индекса элемента, реализация:

namespace detail
{
  
template <std::size_t Idx, class TupleTRef>
auto linearGetImpl(TupleTRef&& tuple, std::size_t index)
    -> ToVariantRefT<std::remove_reference_t<TupleTRef>>
{
    using TupleT = std::remove_reference_t<TupleTRef>;
    using ReturnT = ToVariantRefT<std::remove_reference_t<TupleTRef>>;

    if constexpr (Idx < std::tuple_size_v<TupleT>)
    {
        if (Idx == index)
        {
            return ReturnT{ std::in_place_index_t<Idx>{},
                            std::ref(std::get<Idx>(std::forward<TupleTRef>(tuple))) };
        }
        return linearGetImpl<Idx + 1>(std::forward<TupleTRef>(tuple), index);
    }
    else
    {
        throw std::out_of_range("Error! Tuple index is out of range!\n");
    }
}

} // namespace detail

template <class TupleTRef>
auto linearGet(TupleTRef&& tuple, std::size_t index)
    -> ToVariantRefT<std::remove_reference_t<TupleTRef>>
{
    using TupleT = std::remove_reference_t<TupleTRef>;

    if (index >= std::tuple_size_v<TupleT>)
    {
        throw std::out_of_range("Error! Tuple index is out of range!\n");
    }

    return detail::linearGetImpl<0>(std::forward<TupleTRef>(tuple), index);
}

Мы просто проверяем, равен ли index текущему значению шаблонного параметра Idx, и если нет, то вызываем функцию detail::linearGetImpl с параметром Idx + 1. Такой подход оказывается существенно быстрее использования std::array, но в таком случае у нас доступ к элементу имеет сложность O(N), что все равно недостаточно хорошо.

Затем я решил улучшить эту реализацию, используя бинарный поиск:

namespace detail
{

template <std::size_t FirstIdx, std::size_t LastIdx, class TupleTRef>
auto binaryGetImpl(TupleTRef && tuple, std::size_t index)
    -> ToVariantRefT<std::remove_reference_t<TupleTRef>>
{
    using TupleT = std::remove_reference_t<TupleTRef>;
    using ReturnT = ToVariantRefT<std::remove_reference_t<TupleTRef>>;

    constexpr auto MiddleIdx = (FirstIdx + LastIdx) / 2;
    if constexpr (FirstIdx == LastIdx)
    {
        return ReturnT{ std::in_place_index_t<MiddleIdx>{},
                        std::ref(std::get<MiddleIdx>(std::forward<TupleTRef>(tuple))) };
    }
    else
    {
        if constexpr (MiddleIdx > 0)
        {
            if (MiddleIdx > index)
            {
                return binaryGetImpl<FirstIdx, MiddleIdx - 1>(tuple, index);
            }
        }

        if (MiddleIdx < index)
        {
            return binaryGetImpl<MiddleIdx + 1, LastIdx>(tuple, index);
        }

        return ReturnT{ std::in_place_index_t<MiddleIdx>{},
                        std::ref(std::get<MiddleIdx>(std::forward<TupleTRef>(tuple))) };
    }
}

} // namespace detail

template <class TupleTRef>
auto binaryGet(TupleTRef && tuple, std::size_t index)
    -> ToVariantRefT<std::remove_reference_t<TupleTRef>>
{
    using TupleT = std::remove_reference_t<TupleTRef>;

    if (index >= std::tuple_size_v<TupleT>)
    {
        throw std::out_of_range("Error! Tuple index is out of range!\n");
    }

    return detail::binaryGetImpl<0, std::tuple_size_v<TupleT> - 1>(
        std::forward<TupleTRef>(tuple), index);
}

Суть бинарного поиска заключается в том, что мы делим исходный отрезок 0...N-1 каждый раз пополам и идем в ту часть, где находится искомый индекс index. Из-за использования двух шаблонных параметров std::size_t такая реализация, однако, может увеличить объем сгенерированного кода и, как следствие, бинарника.

Наконец, можно получить O(1) реализацию при условии, что сложность оператора switch не зависит от N. Реализация выглядит криво, но имеет место быть:

namespace detail
{
  
template <class TupleTRef>
auto switchCaseGetImpl(TupleTRef&& tuple, std::size_t index)
    -> ToVariantRefT<std::remove_reference_t<TupleTRef>>
{
    using TupleT = std::remove_reference_t<TupleTRef>;
    using ReturnT = ToVariantRefT<std::remove_reference_t<TupleTRef>>;
 
    static_assert(std::tuple_size_v<TupleT> < 100);

#define CASE_N(I)                                                                    case (I):                                                                        if constexpr ((I) < std::tuple_size_v<TupleT>)                                   {                                                                                    return ReturnT{ std::in_place_index_t<I>{},                                                      std::ref(std::get<I>(std::forward<TupleTRef>(tuple))) };     }                                                                                else                                                                             {                                                                                    break;                                                                       }

    switch (index)
    {
        CASE_N(0);
        CASE_N(1);
        ...
        CASE_N(98);
        CASE_N(99);
    }

#undef CASE_N

}

} // namespace detail

template <class TupleTRef>
auto switchCaseGet(TupleTRef&& tuple, std::size_t index)
    -> ToVariantRefT<std::remove_reference_t<TupleTRef>>
{
    using TupleT = std::remove_reference_t<TupleTRef>;

    if (index >= std::tuple_size_v<TupleT>)
    {
        throw std::out_of_range("Error! Tuple index is out of range!\n");
    }

    return detail::switchCaseGetImpl(std::forward<TupleTRef>(tuple), index);
}

Данная функция работает только с кортежами размера меньше 100 (выглядит как разумное допущение). А вместо ... в функции detail::switchCaseGetImpl идет набор CASE_N от 2 до 97. Для получения более красивого кода можно воспользоваться макросом из буста: BOOST_PP_REPEAT.

Бенчмарки

Для бенчмарков использовалась библиотека Google. Мы взяли std::tuple длиной 40, каждый тип которого – это int. Сложность каждой операции была порядка сложности нахождения целочисленного остатка от деления. Был выбран компилятор MSVC с флагом оптимизации O2. Результаты:

Benchmark

Time

CPU

Iterations

BmSwitchCaseGet

195 ns

195 ns

3733333

BmBinaryGet

258 ns

257 ns

2488889

BmLinearGet

492 ns

500 ns

1000000

BmVariantMapGet

169057 ns

168795 ns

4073

BmVariantArrayGet

1571 ns

1573 ns

407273

BmCompileTimeGet

124 ns

126 ns

6400000

Из приведенных результатов видно, что switch-case реализация самая быстрая из вышеприведенных, а разница между std::get и нашей реализацией составляет приблизительно 50%. Такая разница, по-видимому, обусловлена лучшей способностью компилятора оптимизировать код в случае доступа к элементам во время компиляции, а также созданием объекта std::ref на каждый вызов нашей функции get. Однако, если выполнять какие-то нетривиальные действия с элементами кортежа, то разница, скорее всего, окажется незначительной. Разница в 70 ns – это разница для прохождения по всем элементам кортежа, то есть разница для доступа к одному элементу составляет порядка 2 ns.

Заключение

В итоге мы разработали функциональность, которая позволяет итерироваться по элементам кортежа в произвольном порядке и не писать отдельную функцию для каждого случая. Это существенно экономит время разработчика – надеюсь, сэкономит время и вам. В заключении хочу привести код того, как можно пользоваться разработанной функцией.

Допустим, мы хотим вывести все элементы кортежа в поток std::cout . Код будет выглядит следующим образом:

using TupleT = std::tuple<int, double, std::string>;
int main()
{
    const TupleT tuple{ 5, 3.0, "str"};
    for (std::size_t idx{}; idx < std::tuple_size_v<TupleT>; ++idx)
    {
       std::visit([](auto && tupleValue) { std::cout << tupleValue.get() << " "; },
                  rttg::get(tuple, idx));
    }
}

Для того, чтобы в лямбде не писать каждый раз .get(), мы будем использовать обертку над функцией std::visit:

template <class CallableT, class... VariantTs>
auto visit(CallableT && callable, VariantTs && ... variants)
{
    return std::visit(
        [&callable](auto && value)
        {
            return std::invoke(std::forward<CallableT>(callable), value.get());
        },
        std::forward<VariantTs>(variants)...);
}

Таким образом, финальный вариант можно записать без лишних .get():

using TupleT = std::tuple<int, double, std::string>;
int main()
{
    const TupleT tuple{ 5, 3.0, "str"};
    for (std::size_t idx{}; idx < std::tuple_size_v<TupleT>; ++idx)
    {
        rttg::visit([](auto && tupleValue) { std::cout << tupleValue << " "; },
                    rttg::get(tuple, idx));
    }
}

Для перегрузки работы с различными типами можно использовать overload trick:

/**
* Agregator of callables with operator()
*/
template <class... CallableTs>
struct Overloader : CallableTs...
{
    using CallableTs::operator()...;
};

/**
* Class template argument deduction guide
*/
template <class... CallableTs> Overloader(CallableTs ...) -> Overloader<CallableTs...>;

В таком случае пример можно переписать в виде:

using TupleT = std::tuple<int, double, std::string>;
int main()
{
    const TupleT tuple{ 5, 3.0, "str"};
    for (std::size_t idx{}; idx < std::tuple_size_v<TupleT>; ++idx)
    {
        rttg::visit(
            rttg::Overloader
            {
                [](auto arg) { std::cout << arg << ' '; },
                [](double arg) { std::cout << std::fixed << arg << ' '; },
                [](const std::string & arg) { std::cout << std::quoted(arg) << ' '; }
            },
            rttg::get(tuple, idx));
    }
}

Для такого простого примера, конечно, можно было воспользоваться функцией на подобие for_each. Однако наша функция позволяет итерироваться в произвольном порядке, а не обязательно в возрастающем/убывающем:

using TupleT = std::tuple<std::string, int, std::string, int, std::string, int>;
std::vector<std::size_t> getIterableIndices()
{
    // some non-trivial logic here
    return std::vector<std::size_t>{ 2U, 3U, 0U, 1U };
}

int main()
{
    const TupleT tuple{ "str1", 1, "str2", 2, "str3", 3 };
    for (const auto idx : getIterableIndices())
    {
        rttg::visit([](auto && tupleValue) { std::cout << tupleValue << " "; },
                    rttg::get(tuple, idx));
    }
}

> Ссылка на репозиторий

P.S. В итоге было решено оставить бинарную версию функции get из-за относительно небольшой разницы в производительности и более удобоваримой реализации по сравнению со switch-case.

P.S.S. Для кортежей размера < 7 линейный поиск работает быстрее бинарного и приблизительно наравне с реализацией switch-case.