Эффективное время компиляции, удаление дубликатов из кортежа boost::hana

Я использую функцию boost::hana to_map для удаления дубликатов из boost::hana кортежа типов. См. его в обозревателе компилятора. Код работает очень хорошо, но компилируется очень долго (~10 секунд). Интересно, существует ли более быстрое решение, совместимое с кортежем boost::hana.

#include <boost/hana/map.hpp>
#include <boost/hana/pair.hpp>
#include <boost/hana/type.hpp>
#include <boost/hana/basic_tuple.hpp>
#include <boost/hana/size.hpp>

using namespace boost::hana;

constexpr auto to_type_pair = [](auto x) { return make_pair(typeid_(x), x); };

template <class Tuple>
constexpr auto remove_duplicate_types(Tuple tuple)
{
    return values(to_map(transform(tuple, to_type_pair)));
}


int main(){

    auto tuple = make_basic_tuple(
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
        , 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
        , 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
        , 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
        , 41, 42, 43, 44, 45, 46, 47, 48, 49, 50
        , 51, 52, 53, 54, 55, 56, 57, 58, 59, 60
        , 61, 62, 63, 64, 65, 66, 67, 68, 69, 70
        );

    auto noDuplicatesTuple = remove_duplicate_types(tuple);

    // Should return 1 since there is only one distinct type in the tuple
    return size(noDuplicatesTuple);
}

c++ metaprogramming boost-hana
person erikzenker    schedule 12.12.2020    source источник
comment
Важно ли использовать boost::hana? Это реальный случай или просто пример? Если в вашем кортеже есть только целые числа, вы, вероятно, могли бы просто использовать std::array, а затем реализовать простой алгоритм N^2 constexpr.   -  person Dmitry    schedule 13.12.2020
comment
Приведенный выше код является просто упрощенным примером. Мне нужна функция для библиотеки конечного автомата, где кортеж представляет собой кортеж типов состояния, а не просто целое число. Сам алгоритм не обязательно создавать с помощью boost::hana, но он должен взаимодействовать с кортежем boost::hana.   -  person erikzenker    schedule 13.12.2020
comment
Вы хотите сохранить соответствующее значение времени выполнения для первого из каждого уникального T в вашем кортеже?   -  person Jason Rice    schedule 13.12.2020
comment
Мне нужны обе версии. Так что я был бы рад, если бы для одной версии была более производительная версия.   -  person erikzenker    schedule 13.12.2020
comment
К сожалению, build-bench.com не поддерживает boost/hana (пока?)   -  person Jarod42    schedule 13.12.2020

Ответы (1)


arrow_upward
1
arrow_downward

Я не запускал никаких тестов, но ваш пример не занимает 10 секунд в Compiler Explorer. Однако я могу объяснить, почему это относительно медленное решение, и предложить альтернативу, которая предполагает, что вы заинтересованы только в получении уникального списка типов и не сохраняете никакой информации о времени выполнения в своем результате.

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

Просто ваш вызов transform создает экземпляр лямбда для каждого элемента, который, в свою очередь, создает экземпляр пары. Вход/выход этого вызова — большие кортежи.

Вызов to_map создает пустой map и рекурсивно вызывает insert для каждого элемента каждый раз, создавая новый map, но в этом простом случае промежуточным результатом всегда будет hana::map<int>. Я готов поспорить, что это взрывает ваше время компиляции, если ваш фактический вариант использования нетривиален. (Конечно, это была проблема, когда мы реализовывали hana::map, поэтому мы заставили hana::make_map избежать этого, так как все его входные данные находятся впереди).

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

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

#include <boost/hana/basic_tuple.hpp>
#include <boost/mp11/algorithm.hpp>

namespace hana = boost::hana;
using namespace boost::mp11;


int main() {
    auto tuple = hana::make_basic_tuple(
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
        , 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
        , 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
        , 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
        , 41, 42, 43, 44, 45, 46, 47, 48, 49, 50
        , 51, 52, 53, 54, 55, 56, 57, 58, 59, 60
        , 61, 62, 63, 64, 65, 66, 67, 68, 69, 70
        );

    hana::basic_tuple<int> no_dups = mp_unique<std::decay_t<decltype(tuple)>>{};
}

https://godbolt.org/z/EnTWf6

person Jason Rice    schedule 12.12.2020