Databases
StackOverflow2013
Postsdbo
POResizing dynamic stack allocations in C++
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POResizing dynamic stack allocations in C++
    primarykey
    data
    text
    <p>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.</p> <p>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:</p> <pre><code>class BoundingBoxNode{ BoundingBoxNode* left, *right; void travel(param &amp;p); inline bool intersect(param &amp;p){...}; }; void BoundingBoxNode::travel(param &amp;p){ if(this-&gt;intersect(p)){ if(left) left-&gt;travel(p); if(right) right-&gt;travel(p); } } </code></pre> <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:</p> <pre><code>class BoundingBoxNode{ BoundingBoxNode* left, right; inline void travel(param &amp;p){ int stack_size = 0; BoundingBoxNode* current = this; while(stack_size &gt;= 0){ BoundingBoxNode* stack = alloca(stack_size * 4 + 2*4); if(current-&gt;intersect(p)){ if(current-&gt;left){ stack[stack_size] = current-&gt;left; stack_size++; } if(current-&gt;right){ stack[stack_size] = current-&gt;right; stack_size++; } } stack_size--; current = stack[stack_size]; } }; inline bool intersect(param &amp;p){...}; }; </code></pre> <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.</p> <p>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.</p> <p>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 :)</p> <p>Regards Jonas Finnemann Jensen</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USpeterchen
    1. USjonasfj
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POResizing dynamic stack allocations in C++
      1. USjonasfj
      1. VTFavorite
    1. COThe fact that you want a hack is disturbing, but if you want something "good enough", just use a fixed size array for the stack.
      singulars
      1. POResizing dynamic stack allocations in C++
      1. USDan Olson
    2. COhow does your algorithm terminate?
      singulars
      1. POResizing dynamic stack allocations in C++
      1. USTheFogger
    3. COAt some point intersect returns false thus it terminates... The code here only demonstrates my issue... It not complete in context...
      singulars
      1. POResizing dynamic stack allocations in C++
      1. USjonasfj
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload