0

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

当前我有一个左右两个孩子的节点，然后在 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 循环从堆栈开始时都会处于相同的位置。在以下非常丑陋的黑客攻击中，我依靠 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 编译.

我希望有人可以帮助我......我不需要一个完美的解决方案，只是一个黑客，如果它有效，它就足以达到这个目的:)

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

4

8 回答 8

4

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

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

如果堆栈足够小以适合缓存，它将保持热状态，并且它不在真正的 C++ 堆栈上的事实并不重要。

一旦你完成了所有这些配置文件，它会以两种方式完成，看看它是否有任何不同——保留更快的版本。

于 2009-06-02T09:39:06.063 回答
2

堆栈分配无法调整大小。

在您的示例中，除了调用堆栈本身之外，您需要分配哪些数据并不是很明显。您基本上可以将当前路径保存在预先分配给最大深度的向量中。循环变得丑陋，但这就是生活......

如果您需要许多可以作为一个整体释放的小分配（在算法完成后），请为您的分配使用连续池。

如果您知道所需内存的上限，则分配只是一个指针增量：

class CPool
{
    std::vector<char> m_data;
    size_t m_head;
  public:
    CPool(size_t size) : m_data(size()), m_head(0) {}
    void * Alloc(size_t size)
    {
      if (m_data.size() - head < size)
        throw bad_alloc();
      void * result = &(m_data[m_head]);
      m_head += size;      
      return result;
    }
    void Free(void * p) {} // free is free ;)
};

如果您没有总大小的上限，请使用“绳索上的池” - 即当大块内存用完时，获取一个新的，并将这些块放入列表中。

于 2009-06-02T09:29:28.067 回答
1

你不需要堆栈，你只需要一个堆栈。std::stack<BoundingBoxNode* >如果我查看您的代码，您可能可以使用 a 。

于 2009-06-02T10:01:20.653 回答
0

使用 C++ 数据结构。毕竟，您使用的是 C++。std::vector<> 可以分块预先分配，摊销成本几乎为零。而且它也是安全的（因为您已经注意到使用普通堆栈不是。尤其是当您使用线程时）

不，它并不昂贵。它与堆栈分配一样快。

std::list<> 是的，那会很贵。但那是因为你不能预先分配它。std::vector<> 默认是块分配的。

于 2009-06-02T12:55:19.693 回答
0

由于 alloca 分配是累积的，我建议您执行第一个 alloca 来存储“this”指针，从而成为堆栈的“基础”，跟踪堆栈可以容纳多少元素并仅分配所需的大小：

inline void travel(param &p){

    BoundingBoxNode* stack = alloca(sizeof(BoundingBoxNode*)*3);
    int stack_size = 3, stack_idx = 0;
    stack[stk_idx] = this;

    do {
            BoundingBoxNode* current = stack[stk_idx];
            if( current->intersect(p)){
                    int need = current->left ? ( current->right ? 2 : 1 ) : 0;
                    if ( stack-size - stk_idx < need ) {
                         // Let us simplify and always allocate enough for two
                         alloca(sizeof(BoundingBoxNode*)*2);
                         stack_size += 2;
                    }
                    if(current->left){
                            stack[stack_idx++] = current->left;
                    }
                    if(current->right){
                            stack[stack_idx++] = current->right;
                    }
            }
            stack_idx--;
    } while(stack_idx > 0)
};
于 2009-06-02T09:34:01.083 回答
0

它适用于小堆栈大小的事实可能是巧合。您必须维护多个堆栈并在它们之间进行复制。您永远无法保证对 alloca 的连续调用将返回相同的地址。

最好的方法可能是堆栈的固定大小，并带有一个断言来捕获溢出。或者，您可以在构造时从树深度确定最大堆栈大小，并动态分配将用于每次遍历的堆栈......至少假设您没有在多个线程上遍历。

于 2009-06-02T09:35:54.450 回答
0

C++ 标准没有提供操作堆栈的方法——它甚至不要求有堆栈。您是否使用动态分配实际测量过代码的性能？

于 2009-06-02T09:11:37.463 回答
0

从你的问题看来，还有很多东西需要学习。

要学习的最重要的事情是：在没有首先测量您的运行时执行并分析结果以确定性能瓶颈的确切位置之前，不要假设任何关于性能的事情。

函数“alloca”从堆栈中分配一块内存，堆栈大小增加（通过移动堆栈指针）。每次调用'alloca'都会创建一个新的内存块，直到你用完堆栈空间，它不会重新使用以前分配的内存，当你分配另一块内存时，'stack'指向的数据会丢失，并且将其分配给“堆栈”。这是内存泄漏。在这种情况下，当函数退出时，内存会自动释放，所以这不是严重的泄漏，但是，你已经丢失了数据。

我会单独留下“IA-32 的优化参考手册”。它假定您确切知道 CPU 的工作原理。让编译器担心优化它会为你正在做的事情做得足够好 - 编译器编写者希望从里到外知道这个引用。对于现代 PC，性能的常见瓶颈通常是内存带宽。

我相信“16 深度”函数调用成本高昂与 CPU 如何管理其堆栈有关，并且只是一个指导方针。CPU 将堆栈顶部保留在板载缓存中，当缓存已满时，堆栈底部将被分页到 RAM，这是性能开始下降的地方。有很多参数的函数不会像没有参数的函数那样嵌套那么深。而且它不仅仅是函数调用，它也是局部变量和使用 alloca 分配的内存。事实上，使用 alloca 可能会影响性能，因为 CPU 将被设计为针对常见用例优化其堆栈 - 一些参数和一些局部变量。偏离常见情况，性能下降。

尝试使用上面 MSalters 建议的 std::stack 。让它工作。

于 2009-06-02T10:23:29.407 回答