编译时间高效从 boost::hana 元组中删除重复项

Question

我使用 boost::hana to_map 函数从 boost::hana 类型的元组中删除重复项。请参阅 compiler explorer。该代码运行良好，但编译时间很长（~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);
}

Answer 1

我没有运行任何基准测试，但您的示例在 Compiler Explorer 上似乎不需要 10 秒。但是，我可以解释为什么它是一个相对较慢的解决方案，并建议一个替代方案，假设您只对获取唯一的类型列表感兴趣，而不是在结果中保留任何运行时间信息。

创建大型元组 and/or 实例化原型中具有大型元组的函数模板是昂贵的编译时操作。

只需调用 transform 即可为每个元素实例化一个 lambda，然后实例化对。本次调用的input/output都是大元组

对 to_map 的调用生成一个空的 map 并在每次生成新的 map 时为每个元素递归调用 insert，但在这种简单的情况下，中间结果将始终为 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

编译时间高效从 boost::hana 元组中删除重复项

Compile time efficient remove duplicates from a boost::hana tuple

c++

metaprogramming

boost-hana