C++20或更高版本中具有常量参数的递归函数

mm5n2pyu 于 2023-10-21 发布在其他

关注(0)|答案(1)|浏览(110)

我想知道在C++20或更高版本中处理递归函数中常量参数的首选（和最高性能）方法是什么-例如，考虑以下形式的递归函数

void f(int p, int x) {
    if (someCondition(p, x)) {
        sideEffect;
    } else {
        f(p, g(x));
        f(p, h(x));
    }
}

其中p在所有函数调用中保持不变。
这个问题was asked already，但在2016年被问到**。最受欢迎的答案使用struct，但对该答案的评论说：
C11支持闭包。所以你不需要再创建一个专用的结构体（用一个愚蠢的名字）。- Frank Puffer Mar 21，2016 at 8：17
这表明现代C可能会以不同的方式处理这种情况。因此，这个问题特别是要问在现代C中实现这一点的最佳方法是什么（在撰写本文时），例如。C20或C23。
这个问题也是从一个C新手的Angular 写的！例如，我真的不明白这位评论者所说的是如何应用于递归函数的--他们是在谈论this question中演示的递归函数吗？在编译递归lambda时，你是否受益于与编译“普通”递归函数相同的编译器优化？或者，对于这种形式的递归函数，有没有一种不同的、未提及的策略更好？
我主要关心的是性能，因为我进入C++的动机首先是需要有效地搜索大空间。
任何建议（即使与问题无关）都很感激。我很乐意提供更多的细节，如果这个问题是欠确定的，但不想让这个问题太长，如果我可以帮助它。

**关于算法的更多细节：**实际的算法是从Combinatorial Object Server上的源代码中创建Lyndon单词（k = 2），然后从this paper实现算法。但是，我想使用N和我计划在sideEffect中调用的函数作为常量参数。

下面是算法的具体形式：

// a is a long global array of bools. Maybe there's a better way?
// g will be some kind of side-effectful function that e.g. puts work items in a queue;
// might be more intensive than this algorithm, not sure.
// g and N are constant parameters; t and p vary from call to call.
void Gen(auto g, int N, int t, int p) {
    if(t>N && N == p) {
        // Call `g` and read from `a`, somehow, perhaps via adding to a queue
        sideEffect(g, N, t, p);
    }
    else {
        a[t] = a[t-p]; 
        Gen(g, N, t+1, p);
        if (!(a[t-p])) {
            a[t] = true;
            Gen(g, N, t+1, t);
        }
    };
};

我从原始算法中继承了一些设计选择，但我可以自由地改变它们;例如，我对a使用全局数组有点不舒服，但它可能是最快的。
编辑：g(x)和h(x)以前只是x-1和x+1，正如评论中指出的那样，这使事情变得琐碎。

c++

来源：https://stackoverflow.com/questions/77276405/recursive-functions-with-constant-parameters-in-c20-or-later

1条答案

按热度按时间

umuewwlo1#

答案是相当微妙的，需要对ABI的理解。可以假设int、引用和传递给函数的隐式this指针（如果有的话）需要一个寄存器来传递信息。

简单解决方案

在你过于简单的例子中：

void f(int p, int x) {

即使p是常量，使用lambda或struct也不会更好，因为p占用一个寄存器，成员函数的隐式this指针也是如此。如果p是一个类的数据成员，那么就不会保存任何性能方面的内容。实际上，如果使用成员函数来解决这个问题，您将通过this指针添加间接性。
在实际示例中：

void Gen(auto g, int N, int t, int p) {

g是一个任意的函数对象，可以是任意大的，并且复制起来可能很昂贵。N适合寄存器。为了避免复制g，您可以创建Gen的第二个版本：

// hide this in a detail namespace or a source file
void GemImpl(auto& g, int N, int t, int p); // does what your old Gen did

void Gen(auto g, int N, int t, int p) {
    return GenImpl(g, N, t, p);
}

N没有间接寻址，g不会被复制（只有对它的引用被复制），g始终是一个间接寻址级别。这可能是性能的最佳选择，尽管您仍然应该对其进行基准测试以确定。

使用递归递归函数的解决方案

另一种解决方案是使用递归函数：

void Gen(auto g, int N, int t_, int p_) {
    [&g, N](this auto& self, int t, int p) -> void {
        // ...
        self(t + 1, p); // recursive call
        // ...
    }(t_, p_);
}

这稍微不太理想，因为g有两个间接层，因为它是通过lambda的this指针获得的，lambda有一个引用成员。N也有一个额外的间接级别。然而，优化编译器可以消除其中的一些。
请注意，在C++23之前，您可以使用struct获得与lambda相同的行为，具有相同的ABI和性能属性。

总结

常量参数可能不是最糟糕的东西。您应该避免潜在的昂贵副本，只要您这样做，您就不需要递归lambda或struct。
递归并不一定会提高ABI或性能（事实上，它们可能会使情况变得更糟，尽管您应该对此进行基准测试以确保这一点）。然而，它们摆脱了函数参数，从而提高了代码质量。也就是说，如果您不认为代码质量会受到使用更模糊的语言特性的影响。

赞(0）回复(0）举报 2023-10-21

我来回答

C++20或更高版本中具有常量参数的递归函数

1条答案

简单解决方案

使用递归递归函数的解决方案

总结

相关问题

热门标签

最新问答