Thursday, November 25, 2010

Parallel stacks and Common Stacks Algorithm

For SharpDevelop I have created a version Parallel stacks. In this post I will present a algorithm that creates this Parallel stacks controls using "Common Stacks Algorithm".

Prerequisites: a debugger that gets you for every thread of the application it's call-stack;

SharpDevelop has a debugger that gives you for every thread of the debugged application it's call stack.
The Common Stacks Algorithms is like this:
1. For every thread, get it's call stack in ThreadStacks structure - just a class that contains the actual call-stack - and save them in some kind of list- List.
2. Get & Split common stacks
2.1. For all ThreadStacks, check if they have stack frames. If not, remove them from the list.
2.2 Get all call-stacks that start with the same stack-frame. This can be a Dictionary>.
2.3. For every group of ThreadStacks, find the place of split.
3. Create the common parent ThreadStack and clear the group of common stack-frames.
4. Link the parent to the children and children to parent.
5. Update the collection of ThreadStacks
6. Repeat from 1, until no split is possible - all are parents or simple leaves = the list of common stacks contains only 1 ThreadStack.

What do you think? Pretty nice!

For an implementation, see my Parallel branch in my github.

Happy coding!

No comments: