编译时拓扑排序超过 C++ 中的递归深度

Compile-Time Topological Sort Exceeds Recursion Depth in C++

提问人：bibanac 提问时间：8/5/2023 最后编辑：bibanac 更新时间：8/5/2023 访问量：93

问：

你好:)

我正在使用 C++ 模板元编程实现编译时拓扑排序算法。该算法旨在对游戏引擎中不同系统之间的依赖关系图进行排序，但它可用于对任何有向无环图 （DAG） 进行排序。

该图表示为 SystemNode 对象的元组，每个对象都表示一个系统及其依赖项。该算法对这些节点进行排序，使每个节点出现在排序列表中的依赖项之前。

故障

  1. GraphWithDegrees_t：这是算法的起点。它采用对象的元组并将每个节点转换为一个对象，该对象还包括其度数（依赖于它的节点数）。每个节点的度数由结构计算。SystemNodeNodeWithDegreeCountDependencies

  2. TopologicalSort：这是算法的主要部分。它是一个递归结构，用于执行拓扑排序。其工作原理如下：

    • 提取度数为零的所有节点（即没有其他节点依赖的节点）。这些节点将添加到元组中，该元组保存排序的节点。ExtractedSystems

    • 收集零度节点的依赖关系。这样做是为了知道在下一步中需要递减哪些节点的度数。

    • 从原始元组中删除零度节点。

    • 递减依赖于已删除节点的任何节点的程度。这是通过检查节点是否在上一步中收集的依赖项来完成的。

    • 使用更新的元组和元组递归调用。TopologicalSortExtractedSystems

    • 当元组为空时（即，所有节点都已排序），递归结束，元组作为结果返回。ExtractedSystems

  3. ExtractZeroDegree_t和RemoveZeroDegree_t：这些结构用于从元组中提取和删除零度节点。它们的工作原理是递归地遍历元组，并根据节点的程度在新元组中添加/删除节点。

  4. DecrementDegrees_t：此结构用于递减依赖于给定节点集的节点程度。它的工作原理是递归迭代元组并递减元组中任何节点的度数。Dependencies

  5. AddSystemsToTuple_t：此结构用于将零度节点添加到元组中。它的工作原理是递归迭代零度节点的元组，并将每个节点添加到元组中。ExtractedSystemsExtractedSystems

问题

我面临的问题是，该算法适用于多达 15 种类型，但对于 16 种类型，它超过了最大递归深度。我相信递归深度应该是 O（M），其中 M 是最大度数，所以我不确定为什么它在 16 种类型中失败。

我的问题是：

  1. 为什么这个算法超过最大递归深度 16 类型？
  2. 如何修改它以处理更多类型？
  3. 鉴于这种方法的复杂性，是否可取 采用更简单的方法来达到相同的结果？如果是这样，什么 可以推荐替代方案吗？

请放轻松，我是新来的:)

源代码

您也可以在此处重现该问题：https://godbolt.org/z/T8cohdasr。

#include <tuple>
#include <iostream>
#include <type_traits>
#include <string_view>

template<typename SystemType, typename... DependencyTypes>
class SystemNode;

template<typename SystemType, typename... DependencyTypes>
class SystemNode<SystemType, std::tuple<DependencyTypes...>>
{
public:
    using system = SystemType;
    using dependencies = std::tuple<DependencyTypes...>;
};

template <typename System, typename Dependencies, size_t Degree>
struct NodeWithDegree 
{
    using system = System;
    using dependencies = Dependencies;
    static constexpr size_t degree = Degree;
};

template <typename Node, size_t Degree>
struct ToNodeWithDegree
{
    using type = NodeWithDegree<typename Node::system, typename Node::dependencies, Degree>;
};

template <typename Node, size_t Degree>
using ToNodeWithDegree_t = typename ToNodeWithDegree<Node, Degree>::type;

template <typename T, typename Tuple>
struct Contains;

template <typename T, typename... Us>
struct Contains<T, std::tuple<Us...>> : std::disjunction<std::is_same<T, Us>...> {};

template <typename T, typename... Us>
constexpr size_t Contains_v = Contains<T, Us...>::value;

template <typename Node, typename Nodes>
struct CountDependencies;

template <typename Node, typename First, typename... Rest>
struct CountDependencies<Node, std::tuple<First, Rest...>>
{
    static constexpr size_t value = 
        Contains_v<typename Node::system, typename First::dependencies> 
        + CountDependencies<Node, std::tuple<Rest...>>::value;
};

template <typename Node>
struct CountDependencies<Node, std::tuple<>>
{
    static constexpr size_t value = 0;
};

template <typename... Nodes>
struct GraphWithDegrees
{
    template<typename Node>
    static constexpr size_t CountDependencies_v = CountDependencies<Node, std::tuple<Nodes...>>::value;

    using type = std::tuple<ToNodeWithDegree_t<Nodes, CountDependencies_v<Nodes>>...>;
};

template <typename... Nodes>
using GraphWithDegrees_t = typename GraphWithDegrees<Nodes...>::type;

template <typename NodesWithDegrees, typename ZeroDegreeNodes = std::tuple<>>
struct ExtractZeroDegree;

template <typename FirstNode, typename... RestNodes, typename... ZeroDegreeNodes>
struct ExtractZeroDegree<std::tuple<FirstNode, RestNodes...>, std::tuple<ZeroDegreeNodes...>>
{
    using type = std::conditional_t<
        FirstNode::degree == 0,
        typename ExtractZeroDegree<std::tuple<RestNodes...>, std::tuple<ZeroDegreeNodes..., FirstNode>>::type,
        typename ExtractZeroDegree<std::tuple<RestNodes...>, std::tuple<ZeroDegreeNodes...>>::type
    >;
};

template <typename... ZeroDegreeNodes>
struct ExtractZeroDegree<std::tuple<>, std::tuple<ZeroDegreeNodes...>>
{
    using type = std::tuple<ZeroDegreeNodes...>; 
};

template <typename NodesWithDegrees, typename ZeroDegreeNodes = std::tuple<>>
using ExtractZeroDegree_t = typename ExtractZeroDegree<NodesWithDegrees, ZeroDegreeNodes>::type;

template <typename NodesWithDegrees, typename NonZeroDegreeNodes = std::tuple<>>
struct RemoveZeroDegree;

template <typename FirstNode, typename... RestNodes, typename... NonZeroDegreeNodes>
struct RemoveZeroDegree<std::tuple<FirstNode, RestNodes...>, std::tuple<NonZeroDegreeNodes...>>
{
    using type = std::conditional_t<
        FirstNode::degree == 0,
        typename RemoveZeroDegree<std::tuple<RestNodes...>, std::tuple<NonZeroDegreeNodes...>>::type,
        typename RemoveZeroDegree<std::tuple<RestNodes...>, std::tuple<NonZeroDegreeNodes..., FirstNode>>::type
    >;
};

template <typename... NonZeroDegreeNodes>
struct RemoveZeroDegree<std::tuple<>, std::tuple<NonZeroDegreeNodes...>>
{
    using type = std::tuple<NonZeroDegreeNodes...>; 
};

template <typename NodesWithDegrees, typename NonZeroDegreeNodes = std::tuple<>>
using RemoveZeroDegree_t = typename RemoveZeroDegree<NodesWithDegrees, NonZeroDegreeNodes>::type;

template <typename T, typename Tuple>
struct Prepend;

template <typename T, typename... Ts>
struct Prepend<T, std::tuple<Ts...>>
{
    using type = std::tuple<T, Ts...>;
};

template <typename T, typename Tuple>
using Prepend_t = typename Prepend<T, Tuple>::type;

template <typename T, typename Tuple>
struct AddUnique;

template <typename T>
struct AddUnique<T, std::tuple<>>
{
    using type = std::tuple<T>;
};

template <typename T, typename First, typename... Rest>
struct AddUnique<T, std::tuple<First, Rest...>>
{
    using type = std::conditional_t<
        std::is_same_v<T, First>,
        std::tuple<First, Rest...>,
        Prepend_t<First, typename AddUnique<T, std::tuple<Rest...>>::type>
    >;
};

template <typename T, typename Tuple>
using AddUnique_t = typename AddUnique<T, Tuple>::type;

template <typename Tuple1, typename Tuple2>
struct AddUniqueElements;

template <typename First, typename... Rest, typename Tuple2>
struct AddUniqueElements<std::tuple<First, Rest...>, Tuple2>
{
    using type = typename AddUniqueElements<std::tuple<Rest...>, AddUnique_t<First, Tuple2>>::type;
};

template <typename Tuple2>
struct AddUniqueElements<std::tuple<>, Tuple2>
{
    using type = Tuple2;
};

template <typename Tuple1, typename Tuple2>
using AddUniqueElements_t = typename AddUniqueElements<Tuple1, Tuple2>::type;

template <typename Nodes>
struct CollectDependencies;

template <typename FirstNode, typename... RestNodes>
struct CollectDependencies<std::tuple<FirstNode, RestNodes...>>
{
    using type = AddUniqueElements_t<
        typename FirstNode::dependencies,
        typename CollectDependencies<std::tuple<RestNodes...>>::type
    >;
};

template <>
struct CollectDependencies<std::tuple<>>
{
    using type = std::tuple<>;
};

template <typename... Nodes>
using CollectDependencies_t = typename CollectDependencies<Nodes...>::type;

template <typename NodesWithDegrees, typename Dependencies>
struct DecrementDegrees;

template <typename FirstNode, typename... RestNodes, typename... Dependencies>
struct DecrementDegrees<std::tuple<FirstNode, RestNodes...>, std::tuple<Dependencies...>>
{
    using type = std::conditional_t<
        Contains_v<typename FirstNode::system, std::tuple<Dependencies...>>,
        Prepend_t<
            NodeWithDegree<
                typename FirstNode::system, 
                typename FirstNode::dependencies, 
                FirstNode::degree - 1
            >, 
            typename DecrementDegrees<std::tuple<RestNodes...>, std::tuple<Dependencies...>>::type
        >,
        Prepend_t<
            FirstNode, 
            typename DecrementDegrees<std::tuple<RestNodes...>, std::tuple<Dependencies...>>::type
        >
    >;
};

template <typename... Dependencies>
struct DecrementDegrees<std::tuple<>, std::tuple<Dependencies...>>
{
    using type = std::tuple<>; 
};

template <typename NodesWithDegrees, typename Dependencies>
using DecrementDegrees_t = typename DecrementDegrees<NodesWithDegrees, Dependencies>::type;

template <typename NodesWithDegrees, typename ExtractedSystems>
struct AddSystemsToTuple;

template <typename FirstNode, typename... RestNodes, typename... ExtractedSystems>
struct AddSystemsToTuple<std::tuple<FirstNode, RestNodes...>, std::tuple<ExtractedSystems...>>
{
    using nextTuple = std::tuple<RestNodes...>;
    using newExtractedSystems = std::tuple<typename FirstNode::system, ExtractedSystems...>;
    using type = typename AddSystemsToTuple<nextTuple, newExtractedSystems>::type;
};

template <typename... ExtractedSystems>
struct AddSystemsToTuple<std::tuple<>, std::tuple<ExtractedSystems...>>
{
    using type = std::tuple<ExtractedSystems...>;
};

template <typename NodesWithDegrees, typename ExtractedSystems>
using AddSystemsToTuple_t = typename AddSystemsToTuple<NodesWithDegrees, ExtractedSystems>::type;

template <typename SystemsWithDegrees, typename ExtractedSystems = std::tuple<>>
struct TopologicalSort
{
    using ZeroDegreeSystems = ExtractZeroDegree_t<SystemsWithDegrees>;
    using NewExtractedSystems = AddSystemsToTuple_t<ZeroDegreeSystems, ExtractedSystems>;
    using Dependencies = CollectDependencies_t<ZeroDegreeSystems>;
    using RemainingSystems = RemoveZeroDegree_t<SystemsWithDegrees>;
    using DecrementRemainingSystems = DecrementDegrees_t<RemainingSystems, Dependencies>;
    using type = typename TopologicalSort<DecrementRemainingSystems, NewExtractedSystems>::type;
};

template <typename ExtractedSystems>
struct TopologicalSort<std::tuple<>, ExtractedSystems>
{
    using type = ExtractedSystems;
};

template <typename SystemsWithDegrees, typename ExtractedSystems = std::tuple<>>
using TopologicalSort_t = typename TopologicalSort<SystemsWithDegrees, ExtractedSystems>::type;

template <typename T>
constexpr auto type_name() noexcept {
    std::string_view name = "Error: unsupported compiler", prefix, suffix;
#ifdef __clang__
    name = __PRETTY_FUNCTION__;
    prefix = "auto type_name() [T = ";
    suffix = "]";
#elif defined(__GNUC__)
    name = __PRETTY_FUNCTION__;
    prefix = "constexpr auto type_name() [with T = ";
    suffix = "]";
#elif defined(_MSC_VER)
    name = __FUNCSIG__;
    prefix = "auto __cdecl type_name<";
    suffix = ">(void) noexcept";
#else
    static_assert(false, "Unsupported compiler!");
#endif
    name.remove_prefix(prefix.size());
    name.remove_suffix(suffix.size());
    return name;
}

template <typename T>
void printSystem()
{
    std::cout << type_name<T>() << '\n';
}

struct System1 {};
struct System2 {};
struct System3 {};
struct System4 {};
struct System5 {};
struct System6 {};
struct System7 {};
struct System8 {};
struct System9 {};
struct System10 {};
struct System11 {};
struct System12 {};
struct System13 {};
struct System14 {};
struct System15 {};
struct System16 {};
struct System17 {};
struct System18 {};
struct System19 {};
struct System20 {};

using Node1 = SystemNode<System1, std::tuple<>>;
using Node2 = SystemNode<System2, std::tuple<System1>>;
using Node3 = SystemNode<System3, std::tuple<System2>>;
using Node4 = SystemNode<System4, std::tuple<System3>>;
using Node5 = SystemNode<System5, std::tuple<System4>>;
using Node6 = SystemNode<System6, std::tuple<System5>>;
using Node7 = SystemNode<System7, std::tuple<System6>>;
using Node8 = SystemNode<System8, std::tuple<System7>>;
using Node9 = SystemNode<System9, std::tuple<System8>>;
using Node10 = SystemNode<System10, std::tuple<System9>>;
using Node11 = SystemNode<System11, std::tuple<System10>>;
using Node12 = SystemNode<System12, std::tuple<System11>>;
using Node13 = SystemNode<System13, std::tuple<System12>>;
using Node14 = SystemNode<System14, std::tuple<System13>>;
using Node15 = SystemNode<System15, std::tuple<System14>>;
using Node16 = SystemNode<System16, std::tuple<System15>>;
using Node17 = SystemNode<System17, std::tuple<System16>>;
using Node18 = SystemNode<System18, std::tuple<System17>>;
using Node19 = SystemNode<System19, std::tuple<System18>>;
using Node20 = SystemNode<System20, std::tuple<System19>>;

int main()
{
    using tuple = GraphWithDegrees_t<
        Node10, Node9, Node8, Node7, Node6, Node5, Node4, Node3, Node2, Node1, 
        Node11, Node12, Node13, Node14, Node15, Node16, Node17, Node18, Node19, Node20
    >;
    using SortedTuple = TopologicalSort_t<tuple>;
    printSystem<SortedTuple>();
    return 0;
}

输出：

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc```
C++ 算法 排序 模板 template-元编程

评论

2赞 Pepijn Kramer 8/5/2023
我知道 constexpr 有 500 个深度（在 MSVC 上）。我想模板递归也有类似的限制。
1赞 n. m. could be an AI 8/5/2023
无法重现。请不要发布工作代码。仅发布非工作代码。
0赞 bibanac 8/5/2023
@n.m.couldbeanAI，如果替换：using tuple = GraphWithDegrees_t< node10， node9， node8， node7， node6， node5， node4， node3， node2， node1， node11， node12， node13， node14， node15， node16， node17， node18， node19， node20 >;它对我不起作用：在抛出“std：：bad_alloc”的实例后终止调用 what（）： std：：bad_alloc
1赞 n. m. could be an AI 8/5/2023
请不要发布需要修改的代码以重现问题。按原样重现问题的邮政编码，无需任何修改。
2赞 n. m. could be an AI 8/5/2023
无论如何，您的编译器只是内存不足。它没有达到任何类型的模板实例化深度限制。它刚刚崩溃了。我在本地验证了其他编译器可以编译它，但它花费的时间太长了，所以 godbolt 会因为超过时间限制而杀死它们。

答：

4赞 n. m. could be an AI 8/5/2023 #1

编译器存在内部错误/内存不足情况。它不是某种任意嵌套的模板实例化限制。

我能够在本地在我的机器上编译一个有 20 个节点的版本。gcc 大约需要 20 秒，clang 大约需要 30 秒。

然后，我将节点数增加到 50 个。编译使我的计算机（诚然，以今天的标准来看不是很强大）爬行，我在 20 分钟左右后杀死了它。

因此，在实践中，将模板元编程推到那么远可能不是一个好主意。

评论

0赞 bibanac 8/5/2023
那么，您是建议运行时方法更适合吗？你认为有优化的空间吗 - 使用这种方法，也许在几秒钟内达到 100 个节点？
1赞 pts 8/5/2023
如果运行时版本经过优化，则相同的算法在运行时的运行速度通常比在编译时快得多（例如 或 ）。它还使用更少的内存。gcc -O2gcc -O3
1赞 pts 8/5/2023
在编译时计算某些东西的优点是，每次运行程序时，最终结果都很容易获得。如果程序只编译了几次，但运行了很多次，这是一个净收益。
1赞 n. m. could be an AI 8/5/2023
@bibanac 我认为走TMP路线是没有意义的。模板从来都不是为做这些事情而设计的。consteval 函数可能是一个可行的替代方案。

上一个：C++ 模板类型和该类型的可变参数数据

下一个：如何在任何嵌套级别替换模板中的类型？