编译时二分查找的编译时间

Question

编译时二分查找的编译时间

4

看了一下Boost MP11中mp_with_index的实现，它似乎通过二分搜索将运行时的值映射到编译时的常量。对于较小的值，比如遍历变体，这似乎运行良好。但是，当我用较大的值进行测试时，编译器似乎无法及时编译代码。虽然我没有对编译时间进行基准测试，但在测试5位数整数值时遇到了编译器超时值，这似乎表明编译器需要比我预期的更多的工作量。

#include <boost/mp11/algorithm.hpp>

inline constexpr auto m = unsigned{99'999u};
inline constexpr auto n = unsigned{m - 1};

static_assert(boost::mp11::mp_with_index<m>(n,
     [](auto r){ return decltype(r)::value == n; }));

由于mp_with_index使用二分搜索算法，因此时间复杂度为对数级别，我预计对于一个5位整数值，最多需要18步才能完成映射。为什么编译器似乎需要做更多的工作，而不仅仅是一些模板实例化和整数值比较呢？实际示例

- 303

根据Cppinsights的说法，似乎对于0...m有所有的实例化。所以在你的情况下，这将导致100k个函数。但我不确定Cppinsights使用的确切版本的boost... - undefined

@Quimby 看起来CppInsights正在使用Boost v1.83，根据他们的信息页面。所以我会期望使用相同的库代码。CppInsights似乎只显示了在传递一个通用lambda时的模板调用运算符的实例化。当传递一个非通用lambda（例如：[](int){ return true; }）时，显示的生成代码很少，并且似乎不受m的大小影响。然而，当增加m时，编译时间仍然显著增加，同时在m=99999时超时。 - undefined

1

mp_with_index_impl_::call函数中的i不是constexpr的。（函数参数从不是constexpr的）。其中的if语句也不是if constexpr。（它不能是）。因此，if语句的两个分支都会被实例化。然后，这两个实例化中的每个分支都会被实例化，以此类推，直到其中一个小型N的特化接管---然后该特化中的所有case分支都会被实例化。 - undefined

这正是我忽视的地方。由于if分支没有标记为constexpr，函数体中的每个模板实体都必须被实例化，这实际上导致了模板实例化的指数增长。这个对数函数的指数特性在这个上下文中相当微妙地隐藏起来了。 - undefined

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Artyer · Accepted Answer

无论如何，`boost::mp11::mp_with_index(f, n)` 都需要实例化 `f(mp_size_t{})`，其中 `K` 的值不同，总共实例化 `m` 次。

在评估过程中，实际上最多只会执行 18 个分支，但编译器需要实例化其他分支，以防其中一个分支有失败的 `static_assert` 或其他问题。想象一下，如果有 `[](auto r) requires(r != 3) { return decltype(r)::value == n; })`：即使 `n != 3`，这也必须无法编译通过。

因此，至少需要实例化 100,000 个模板来调用该函数。你会预期编译时间与 `m` 的值成正比。经过一些轻微的测试：

$ time clang++ -std=c++17 -fsyntax-only test.cpp -DMMM=1000

real    0m0.075s
user    0m0.064s
sys     0m0.009s
$ time clang++ -std=c++17 -fsyntax-only test.cpp -DMMM=10000

real    0m0.586s
user    0m0.528s
sys     0m0.050s
$ time clang++ -std=c++17 -fsyntax-only test.cpp -DMMM=100000

real    0m5.771s
user    0m5.538s
sys     0m0.230s
$ time clang++ -std=c++17 -fsyntax-only test.cpp -DMMM=1000000

real    0m58.760s
user    0m56.831s
sys     0m1.920s

看起来似乎是这样。