为何Boost MP11的mp_with_index处理大值时编译耗时远超预期？

查看Boost MP11中mp_with_index的实现可知，它通过二分搜索将运行时值映射为编译时常量。这个实现在处理variant这类小值场景时表现正常，但测试99999这类5位大值时，编译器会出现超时（比如Compiler Explorer的默认超时）。按说二分搜索的复杂度是对数级，99999最多只需要18步映射，为什么编译器实际的工作量远远不止模板实例化和整数比较？

测试代码如下：

#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的二分搜索是通过递归模板实现的，每一层递归都会实例化mp_if、mp_less等多个元编程工具模板。这些模板本身又会展开更多的类型推导、常量计算逻辑，编译器需要为每个中间模板生成完整的类型信息、检查约束，这些操作的开销会随着递归层数累加，远不止表面上的18步。

• 编译器必须实例化所有可能的模板分支
  二分搜索的每一步都会生成两个逻辑分支（大于中间值/小于等于中间值），哪怕运行时只会走其中一条路径，编译器在编译期无法提前确定最终分支，因此必须实例化所有可能的模板分支。每一层递归都会产生新的子模板实例，这些实例的数量和嵌套深度会快速增加，带来远超预期的编译工作量。

• 常量表达式计算与约束检查的累积开销
  每一个模板实例都需要计算编译时常量（比如中间索引值、范围大小），还要检查模板参数的合法性（比如std::integral_constant的类型匹配、lambda的参数推导）。当数值规模较大时，这些计算和检查的次数会随着递归层数呈累积增长，而编译器对深层模板元编程的优化能力有限，容易触发性能瓶颈。

• 模板实例化缓存无法复用
  编译器会缓存已实例化的模板，但mp_with_index的每一次递归调用都对应不同的模板参数（比如不同的范围大小），这些都是全新的模板实例，无法复用缓存。这意味着编译器需要重复处理大量相似但不同的模板结构，进一步加剧了编译时间的消耗。

内容的提问来源于stack exchange，提问作者303