Resizing dynamic stack allocations in C++

Question

Hi,

I'm writing a small ray tracer using bounding volume hierarchies to accelerate ray tracing. Long story short, I have a binary tree and I might need to visit multiple leafs.

Current I have a node with two children left and right, then during travel() if some condition, in this example intersect(), the children are visited:

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);
    }
}

This approach uses recursive methods calls, however, I need to optimized this code as much as possible... And according to Optimization Reference Manual for IA-32, function calls deeper than 16 can be very expensive, so I would like to do this using a while loop instead of recursive calls. But I do NOT wish to do dynamic heap allocations as these are expensive. So I was thinking that maybe I could use that fact that every time a while loop starts over the stack will be in the same position. In the following very ugly hack I rely on alloca() to always allocate the same address:

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){...};
};

However surprising it may seem this approach does fail :) But it does work as long as the stack is smaller than 4 or 5... I'm also quite confident that this approach is possible, I just really think I need some help implementing it correctly.

So how can I manipulate the stack manually from C++, is it possible that I can use some compiler extension... Or must I do this is assembler, and if so, how do I write assembler than can be compiled with both GCC and ICC.

I hope somebody can help me... I don't need a perfect solution, just a hack, if it works it's good enough for this purpose :)

Regards Jonas Finnemann Jensen

Answer 1

The C++ Standard provides no means of manipulating the stack - it doesn't even require that there be a stack. Have you actually measured the performance of your code using dynamic allocation?

Answer 2

Stack allocations cannot be resized.

In your example, it isn't immediately obvious which data you need to allocate - besides the call stack itself. You could basically hold the current path in a vector preallocated to the maximum depth. The loop gets ugly, but that's life...

If you need many small allocations that can be released as a whole (after the algorithm completes), use a continuous pool for your allocations.

If you know an upper boundary for the required memory, the allocation is just a pointer increment:

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 ;)
};

If you don't have an upper boundary for the total size, use "pool on a rope" - i.e. when the big chunk of memory runs out, get a new one, and put these chunks in a list.

Answer 3

Hi Jonas,

Since alloca allocations are cummulative, I suggest you do a first alloca to store the "this" pointer, thus becoming the "base" of the stack, keep track of how many elements your stack can hold and allocate only the size needed:

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)
};

Answer 4

The fact that it works with small stack sizes is probably a coincidence. You'd have to maintain multiple stacks and copy between them. You're never guaranteed that successive calls to alloca will return the same address.

Best approach is probably a fixed size for the stack, with an assert to catch overflows. Or you could determine the max stack size from the tree depth on construction and dynamically allocate a stack that will be used for every traversal... assuming you're not traversing on multiple threads, at least.

Answer 5

So, you've got a recursive function that you want to convert to a loop. You correctly work out that your function is not tail call so you have to implement it with a stack.

Now, why are you worried about the number of times that you allocate your "scratch space" stack? Is this not done once per traversal? -- if not then pass the scratch area in to the traverse function itself so it can be allocated once and then re-used for each traversal.

If the stack is small enough to fit in the cache it will stay hot and the fact that it isn't on the real C++ stack won't matter.

Once you've done all of that profile it both ways and see if it made any difference -- keep the faster version.

Answer 6

You don't need the stack, you just need a stack. You can probably use a std::stack<BoundingBoxNode* >, if I look at your code.

Answer 7

From your question, it appears there is a lot that still needs to be learned.

The most important thing to learn is: don't assume anything about performance without first measuring your runtime execution and analysing the results to determine exactly where the bottlenecks to performance are.

The function 'alloca' allocates a chunk of memory from the stack, the stack size is increased (by moving the stack pointer). Each call to 'alloca' creates a new chunk of memory until you run out of stack space, it does not re-use previously allocated memory, the data that was pointed to by 'stack' is lost when you allocate another chunk of memory and assign it to 'stack'. This is a memory leak. In this case, the memory is automatically freed when the function exits so it's not a serious leak, but, you've lost the data.

I would leave the "Optimization Reference Manual for IA-32" well alone. It assumes you know exactly how the CPU works. Let the compiler worry about optimisations it will do a good enough job for what you're doing - the compiler writers hopefully know that reference inside out. With modern PC's, the common bottleneck to performance is usually memory bandwidth.

I believe the '16 deep' function calls being expensive is to do with how the CPU is managing its stack and is a guideline only. The CPU keeps the top of the stack in onboard cache, when the cache is full, the bottom of the stack is paged to RAM which is where the performance starts to decrease. Functions with lots of arguments won't nest as deeply as functions with no arguments. And it's not just function calls, it's also local variables and memory allocated using alloca. In fact, using alloca is probably a performance hit since the CPU will be designed to optimise its stack for common use cases - a few parameters and a few local variables. Stray from the common case and performance drops off.

Try using std::stack as MSalters has suggested above. Get that working.

Answer 8

Use a C++ data structure. You are using C++ after all. A std::vector<> can be pre-allocated in chunks for an amortized cost of pretty much nil. And it's safe too (as you have noticed that using the normal stack is not. Especially when you're using threads)

And no, it's not expensive. It's as fast as a stack allocation.

std::list<> yes, that will be expensive. But that's because you can't pre-allocate that. std::vector<> is chunk-allocated by default.