3

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.

Jeff
  • 35,755
  • 15
  • 108
  • 220
  • 30 levels is not deep. You don't get it trouble until it goes tens of thousands levels deep. Avoid sweating the small stuff. – Hans Passant Jan 17 '11 at 21:22

3 Answers3

4

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.

Ruben Bartelink
  • 59,778
  • 26
  • 187
  • 249
Johannes Rudolph
  • 35,298
  • 14
  • 114
  • 172
1

See Why doesn't .NET/C# optimize for tail-call recursion?. Apparently, .NET performs tail recursion optimization on x86-64, so if that's your architecture, and your code is amenable to such an optimization, stick with recursion.

Community
  • 1
  • 1
EmeryBerger
  • 3,897
  • 18
  • 29
  • TRO won't help you with depth-first search. You need to keep a record of the current path and that is either going to go on the stack (which is very cheap to allocate) or in some other data structure, such as a FIFO, which will require some memory allocation (which is typically more costly). – Rafe Jan 16 '11 at 22:29
  • @Rafe: Are you using costly in the sense of number of bytes allocated, or efficiency of the allocator? – Ben Voigt Jan 17 '11 at 00:51
  • @Ben: mainly the cost of allocation. Stack overflows are often handled with a "red zone" where the page after the end of the stack is marked as inaccessible, which triggers an interrupt if the stack overflows, hence no end-of-stack testing code is needed for a stack allocation. Usually you can't do this for heap allocation. Moreover, heap objects have to be managed by the garbage collector, whereas stack objects don't. For all that, in any non-trivial search application whether you use heap or stack allocation is probably not going to make much difference in practice. – Rafe Jan 17 '11 at 22:50
1

You're mingling two concepts which ought to be separate to some degree:

  • Iteration of a data structure vs. using recursive functions where the call stack becomes your structure.

  • Breadth-first vs depth-first traversal.

They are connected, insofar as recursive functions tend to implement depth-first. However, when using a queue, there's nothing restricting you to breadth-first.

Use a FIFO queue if you want breadth-first, and a LIFO queue if you want depth first. Either way, you save the function call overhead (probably fairly minor, and calling methods on the queue may well be more expensive if they don't get inlined by the optimizer) and the stack space usage on the system call stack.

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720