• Create Account

[c++] non-recursive way to iterate tree

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

14 replies to this topic

#1Alundra  Members

Posted 16 May 2013 - 08:04 PM

Hi all,

Imagine a scene manager who has a root node with children, so it's a tree.

One way is to iterate the tree using recursivity, but perf is not the best.

An alternative is to use a similare code to a showed code in the wxWidgets documentation :

wxTreeItemId FindItemNamed(wxTreeCtrl &tree, const std::wstring &name)
{
std::stack<wxTreeItemId> items;
if (tree->GetRootItem().IsOk())
items.push(tree->GetRootItem());

while (!items.empty())
{
wxTreeItemId next = items.top();
items.pop();

if (next != tree->GetRootItem() && tree->GetItemText(next) == name)
return next;

while (nextChild.IsOk())
{
items.push(nextChild);
nextChild = tree->GetNextSibling(nextChild);
}
}

return wxTreeItemId();
} 

Is this method a good way to handle a tree ?

Thanks

Edited by Alundra, 16 May 2013 - 08:06 PM.

#2iMalc  Members

Posted 17 May 2013 - 12:37 AM

This is simply a breadth-first search. It may be breadth-first for multiple reasons.

1. It avoids recursion that leads to stack overflow.

2. It finds the closest node to the root matching the supplied name, which seems to be what would be most useful.

"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

#3swiftcoder  Senior Moderators

Posted 17 May 2013 - 05:17 AM

That method is functionally identical to recursion, the only difference being that you have to manually manage your own stack, rather than using the machine stack.

At best, any speedup will be minimal - the time complexity is still linear in relation to the number of nodes in the tree.

What makes you think that recursion is too slow?

Tristam MacDonald - Software Engineer @ Amazon - [swiftcoding] [GitHub]

#4Alundra  Members

Posted 17 May 2013 - 06:36 AM

I have always listen that recursion is slow because of the cache miss.

For a QuickSort algorithm the solution is to have a MaxLevel variables en switch to InsertionSort if MaxLevel is reached.

For a a scene tree the best solution is to use recursion ?

#5Álvaro  Members

Posted 17 May 2013 - 06:53 AM

I have always listen that recursion is slow because of the cache miss.

No, "recursion is slow" is a false statement. There are situations where recursion might be slow, and then it has nothing to do with cache misses.

For a QuickSort algorithm the solution is to have a MaxLevel variables en switch to InsertionSort if MaxLevel is reached.

That's a solution to a specific problem of QuickSort, and not to a general problem with recursion.

For a a scene tree the best solution is to use recursion ?

Best solution to what?

#6Alundra  Members

Posted 17 May 2013 - 07:23 AM

Best solution to what?

To traverse the tree for saving the scene, find an object by name or pointer, update each object and render the scene.

Edited by Alundra, 17 May 2013 - 07:23 AM.

#7Álvaro  Members

Posted 17 May 2013 - 07:29 AM

Write your code to be clear. If performance is a problem, use a profiler to see where the time is going. After that, if you find that traversing the tree is actually a performance bottleneck, then you can worry about this.

#8EVIL_ENT  Members

Posted 17 May 2013 - 07:44 AM

That method is functionally identical to recursion, the only difference being that you have to manually manage your own stack, rather than using the machine stack.

At best, any speedup will be minimal - the time complexity is still linear in relation to the number of nodes in the tree.

What makes you think that recursion is too slow?

It might be worthwhile to mention that the heap usually is a lot bigger than the stack which alows for deeper traversal so both solutions are not exactly identical.

It is very likely that this won't be a limiting factor though.

Always profile and benchmark.

If it's not too slow you don't have to care.

Otherwise it might be possible that std::stack is implemented as some kind of list with nodes allocated one by one which might lead to more cache misses than a contiguous block of stack memory which the recursive version would use.

#9Hodgman  Moderators

Posted 17 May 2013 - 08:06 AM

To traverse the tree for saving the scene, find an object by name or pointer, update each object and render the scene.

If you want to avoid cache misses when traversing a tree, then make sure that the tree's elements are stored contiguously in memory, in the order that they will be traversed. That way, it's the same as iterating through a linear array.

If the operation that you need to perform is "for each object", then you shouldn't even be using a tree in the first place, you should just have an array.

If the operation is "find object by name", then you want a hash map from names to object-pointers.

#10Álvaro  Members

Posted 17 May 2013 - 08:51 AM

Otherwise it might be possible that std::stack is implemented as some kind of list with nodes allocated one by one which might lead to more cache misses than a contiguous block of stack memory which the recursive version would use.

I don't think that can happen: By default std::stack uses std::deque as its underlying container (std::stack is not a container, but a container adaptor). There are multiple possible implementations of std::deque, but they won't be one-node-per-item implementations because of the performance guarantees (O(1) random access iterators).

#11SiCrane  Moderators

Posted 17 May 2013 - 09:49 AM

It's possible to get a one node per item deque implementation with a dynamic array containing pointers to the individual nodes, which gives you the constant time random access. Some standard library implementations have an N item per node implementation where N shrinks as sizeof(T) increases, which degenerates to N equals one after a point. IIRC, at least some versions of MSVC's standard library implementation work this way.

#12iMalc  Members

Posted 17 May 2013 - 02:58 PM

Oh sorry, it would be a breadth-first search, if the items were going in one end of the data structure and out the other end.

On second examination, this does not appear to be the case.

"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

#13frob  Moderators

Posted 17 May 2013 - 04:22 PM

For a a scene tree the best solution is to use recursion ?

Usually a world has multiple data structures involved.

A scene or level or world is usually going to be used for many frequent searches and lookups.  Queries are both for existence and also for position. There will be frequent changes to objects in the world.

Generally there is a hash table containing all the objects.  The hash should be a guid assigned to each object.  This is generally the master list.

There is also generally a spatial tree, such as a loose quadtree, that indicates where the guid lives in the world.  When an object's position is updated this spatial tree needs to also get updated.

There may be yet another graph, called the scene graph, used for display.  Quite likely this graph is not part of the game world since it is part of the renderer's responsibility, not world management's responsibility.

Edited by frob, 17 May 2013 - 04:22 PM.

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I occasionally write about assorted stuff.

#14Alundra  Members

Posted 18 May 2013 - 06:20 AM

Do you mean to have a root node and have children in it and have with that an array of SceneObject who is just all objects ?

Use the recursion to save/load and the array for other operations ?

#15Hodgman  Moderators

Posted 18 May 2013 - 07:45 AM

Do you mean to have a root node and have children in it and have with that an array of SceneObject who is just all objects ?

The idea is that you don't use a single data structure for everything. Many old engines tried to put absolutely everything into a "scene graph" (one graph to rule them all), which was a massive tree with a root node like you're describing, but that's a really bad idea. Data that's used for different purposes should be stored in different ways.

struct TransformNode
{
Mat44 local;
Mat44 global;
vector<TransformNode*> children;
};

struct BoundingSphere
{
Vec3 position;
};

struct Actor
{
TransformNode* transform;
BoundingSphere* sphere;
Mesh* mesh;
Material* material;
};

struct Scene
{
TransformNode* rootTransform;//tree of data
vector<BoundingSphere> spheres;//array of data
list<Actor> actors;//linked list of data, pointers into the above array and tree
};

Edited by Hodgman, 18 May 2013 - 07:46 AM.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.