计算的编译时性能
我有一些非平凡的C++17函数标记为constexpr。他们正在进行与图相关的计算(深度优先遍历)和一般算法(例如，查找、排序、唯一.)。
如果我试图通过将结果放入constexpr全局变量在编译时强制进行评估，可能会发生以下三种情况：
- 对于小规模的计算(为了给出一个想法，假设图是大约100个节点，节点或多或少是整数)，编译是很好的(需要~2s)。
- 对于大约500个节点，编译要花费1分钟，占用30 of的内存(!)。
- 对于~1000个节点，编译需要太多的内存才能让它完成。
如果我移除constexpr限定符并要求运行时计算，编译和执行非常快(小于5s)。
我使用了g++ 8.2和-O3 -std=c++17。
为什么要花这么长时间？g++因constexpr的编译时优化问题而闻名吗？在编译过程中，我应该期望constexpr函数的性能如何？据我所知，编译器将自己转换为用于constexpr计算的解释器。但我毫不怀疑，考虑到数据的非常小，用Python评估相同的程序会非常快。
编辑：这些问题被提到这里 ( GCC开发人员的博客)
回答 1
Stack Overflow用户
发布于 2019-03-04 21:00:40
g++回忆录编译时结构。更重要的是，编译时结构可以沿着您想要的分支和不想要的分支进行创建和检查，除非您非常小心。
指数爆破是很有可能的，并且可能是你所看到的。
有一些策略可以降低编译时的复杂性。避免深度递归。注意累积的符号长度。确保只检查您想要的分支。
我是说，检查一个非常简单的：
std::conditional_t< (A<B), make_type_A<Ts...>, make_type_B<Ts...> >此代码的编写者可能只打算创建一种类型，但这段代码要求创建这两种类型。
这不太可能是您的问题，但是在运行constexpr代码时可能会出现类似的问题。
对于每个调用，计算所需状态的大小。将所需的总状态相加。加10倍的开销。
你也可以分析你的问题的O-表示法是什么，让更多的样本，而不是2个完成。查看100,200,300,400,500大小的图表。尝试线性图，平凡图，完全图，具有常数或百分比连通性的随机图。
编译时增长的O-表示法可能有助于缩小问题的范围。如果它是线性的，多项式的或者指数的，你将会看到不同类型的问题。
线性与尖锐的拐点意味着你正在碰到一个资源瓶颈。也许是记忆。开始绘制其他资源使用情况图，并查看是否可以找到瓶颈。
指数看起来很像线性与悬崖，如果你不记录它和放大“悬崖”。可能有一个很窄的部分，指数部分留下常数因子。
多项式变得有趣了。多项式的顺序(日志图可以帮助发现)可以告诉你是什么样的操作。就像知道你的传统算法是O(n^3)，意味着你在寻找一个三重循环。O(n^3)编译时间意味着您正在以某种方式实例化等效的三重循环。
https://stackoverflow.com/questions/54990407
复制相似问题
腾讯云开发者
