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

Question

查看 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使用二分搜索算法，因此具有对数时间复杂度，因此我预计最多需要 18 个步骤才能实现 5 位整数值的映射。为什么编译器似乎需要做更多的工作而不仅仅是几个模板实例化和整数值比较？

实例

Answer 1

无论如何完成，boost::mp11::mp_with_index<m>(f, n)都需要实例化f(mp_size_t<K>{})不同m的值K。

评估期间实际上最多采用 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

情况似乎确实如此。