.NET Performance: Deep Recursion vs Queue

Question

I'm writing a component that needs to walk large object graphs, sometimes 20-30 levels deep.

What is the most performant way of walking the graph?

A. Enqueueing "steps" so as to avoid deep recursion

or

B. A DFS (depth first search) which may step many levels deep and have a "deep" stack trace at times.

I guess the question I'm asking is: Is there a performance hit in .NET for doing a DFS that causes a "deep" stack trace? If so, what is the hit? And would I better better off with some BFS by means of queueing up steps that would have been handled recursively in a DFS?

Sorry if I'm being unclear. Thanks.

Answer 1

There's nothing in the runtime that would cause code execution in a deep stack to be slower than in a shallow call stack. There's no reason for that, because usually code execution doesn't trigger a stack walk.

When I say usually, this means there are a couple of exceptions:

• Security/Evidence checks do usually walk the call stack to determine the current security context
• Throwing and catching exceptions of course (you don't want to do that in a tree traversal anyway, except for aborting it)

Whether you should implement an iterative or recursive tree traversal isn't dependent on whether the .NET runtime will give you better perfomance in one scenario vs. the other, but you should make your decision based on Big-O (time and memory), especially if its for large trees. I don't think I need to remind you of the chance of a stack overflow with a recursive solution, given where we are... Tailcall optimization is possible though.

After you've chosen the fastest traversal for your tree and traversal purpose Big-O wise, you can start worrying about optimizing your implementation.