I made a realtime raytracer a while back and I had good luck with storing the nodes in an array in depth-first order with skip pointers. You get great cache coherency and the traversal code is most just incrementing a pointer. Here's a bit of a description of it: http://www.cse.chalmers.se/edu/course/_courses_2011/TDA361/EfficiencyIssuesForRayTracing.pdf On Jun 1, 2013 8:58 AM, "Dave Long" <dave.l...@bluewin.ch> wrote:
> Suppose you want to be able to execute the Visitor pattern as quickly >> as possible on some tree structure. You could compile your tree >> structure into executable code, each node a subroutine which invokes a >> method of the visitor object — traditionally each node type invokes a >> different method — and then passes the visitor object to each child >> node. >> > > My knee-jerk response is that waiting for i-cache misses is probably not > much faster than waiting for d-cache misses, and so it's probably better to > spend effort massaging your tree into a serialized form suitable for > traditional loops; I'd guess that the increased instruction count is easily > outweighed by the better prediction and streaming. What kinds of results > have you seen? > > -Dave > > (although if you squint at it properly, doing this kind of thing in > general is almost exactly what distinguishes compilers from interpreters) > > -- > To unsubscribe: http://lists.canonical.org/**mailman/listinfo/kragen-** > discuss <http://lists.canonical.org/mailman/listinfo/kragen-discuss> >
-- To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss
