c++ - 在 C++ 中调整动态堆栈分配的大小

Question

我正在编写一个小型光线追踪器，使用边界体积层次结构来加速光线追踪。长话短说，我有一个二叉树，我可能需要访问多个叶子。

当前我有一个左右两个子节点的节点，然后在 travel() 期间，如果某些条件，在这个例子中是 intersect()，子节点被访问:

class BoundingBoxNode{
    BoundingBoxNode* left, *right;
    void travel(param &p);
    inline bool intersect(param &p){...};
};

void BoundingBoxNode::travel(param &p){
    if(this->intersect(p)){
        if(left)
            left->travel(p);
        if(right)
            right->travel(p);
    }
}

这种方法使用递归方法调用，但是，我需要尽可能地优化这段代码......根据 IA-32 优化引用手册，深度超过 16 的函数调用可能非常昂贵，所以我想使用 while 循环而不是递归调用来执行此操作。但我不希望进行动态堆分配，因为它们很昂贵。所以我在想，也许我可以利用这个事实，即每次 while 循环开始时，堆栈都会处于相同的位置。在以下非常丑陋的 hack 中，我依靠 alloca() 始终分配相同的地址:

class BoundingBoxNode{
    BoundingBoxNode* left, right;
    inline void travel(param &p){
        int stack_size = 0;
        BoundingBoxNode* current = this;
        while(stack_size >= 0){
            BoundingBoxNode* stack = alloca(stack_size * 4 + 2*4);
            if(current->intersect(p)){
                if(current->left){
                    stack[stack_size] = current->left;
                    stack_size++;
                }
                if(current->right){
                    stack[stack_size] = current->right;
                    stack_size++;
                }
            }
            stack_size--;
            current = stack[stack_size];
        }
    };
    inline bool intersect(param &p){...};
};

然而令人惊讶的是，这种方法似乎确实失败了 :)但只要堆栈小于 4 或 5，它就可以工作...我也非常有信心这种方法是可行的，我只是真的认为我需要一些帮助才能正确实现它。

那么我如何从 C++ 手动操作堆栈，我是否可以使用一些编译器扩展......或者我必须这样做是汇编程序，如果是这样，我如何编写汇编程序而不是用两者编译GCC 和 ICC。

我希望有人能帮助我...我不需要一个完美的解决方案，只需要一个 hack，如果它有效就足够了:)

问候乔纳斯·芬尼曼·詹森

Answer 1

因此，您有一个要转换为循环的递归函数。您正确地计算出您的函数不是尾调用，因此您必须使用堆栈来实现它。

现在，您为什么担心分配“暂存空间”堆栈的次数？这不是每次遍历都完成一次吗？ -- 如果没有，则将暂存区域传递给遍历函数本身，这样它就可以分配一次，然后在每次遍历时重新使用。

如果堆栈小到足以放入缓存，它将保持热状态，并且它不在真正的 C++ 堆栈上这一事实也无关紧要。

一旦你完成了所有的配置文件，就可以双向查看它是否有任何不同——保持更快的版本。