Iterative version of a recursive algorithm is slower

Question

I'm trying to implement an iterative version of Tarjan's strongly connected components (SCCs), reproduced here for your convenience (source: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm).

Input: Graph G = (V, E)

index = 0                         // DFS node number counter 
S = empty                         // An empty stack of nodes
forall v in V do
  if (v.index is undefined)       // Start a DFS at each node
    tarjan(v)                     // we haven't visited yet

procedure tarjan(v)
  v.index = index                 // Set the depth index for v
  v.lowlink = index
  index = index + 1
  S.push(v)                       // Push v on the stack
  forall (v, v') in E do          // Consider successors of v
    if (v'.index is undefined)    // Was successor v' visited?
        tarjan(v')                // Recurse
        v.lowlink = min(v.lowlink, v'.lowlink)
    else if (v' is in S)          // Was successor v' in stack S? 
        v.lowlink = min(v.lowlink, v'.lowlink )
  if (v.lowlink == v.index)       // Is v the root of an SCC?
    print "SCC:"
    repeat
      v' = S.pop
      print v'
    until (v' == v)

My iterative version uses the following Node struct.

struct Node {
    int id; //Signed int up to 2^31 - 1 = 2,147,483,647
    int index;
    int lowlink;        
    Node *caller;                    //If you were looking at the recursive version, this is the node before the recursive call
    unsigned int vindex;             //Equivalent to the iterator in the for-loop in tarjan
    vector<Node *> *nodeVector;      //Vector of adjacent Nodes 
};

Here's what I did for the iterative version:

 void Graph::runTarjan(int out[]) {  //You can ignore out. It's a 5-element array that keeps track of the largest 5 SCCs
        int index = 0;
tarStack = new stack<Node *>();
    onStack = new bool[numNodes];
  for (int n = 0; n < numNodes; n++) {
    if (nodes[n].index == unvisited) {
      tarjan_iter(&nodes[n], index);
    }
  }
}

void Graph::tarjan_iter(Node *u, int &index) {
    u->index = index;
    u->lowlink = index;
    index++;
    u->vindex = 0; 
    tarStack->push(u);
    u->caller = NULL;           //Equivalent to the node from which the recursive call would spawn.
    onStack[u->id - 1] = true;
    Node *last = u;
    while(true) {
        if(last->vindex < last->nodeVector->size()) {       //Equivalent to the check in the for-loop in the recursive version
            Node *w = (*(last->nodeVector))[last->vindex];
            last->vindex++;                                   //Equivalent to incrementing the iterator in the for-loop in the recursive version
            if(w->index == unvisited) {
                w->caller = last;                     
                w->vindex = 0;
                w->index = index;
                w->lowlink = index;
                index++;
                tarStack->push(w);
                onStack[w->id - 1] = true;
                last = w;
            } else if(onStack[w->id - 1] == true) {
                last->lowlink = min(last->lowlink, w->index);
            }
        } else {  //Equivalent to the nodeSet iterator pointing to end()
            if(last->lowlink == last->index) {
                numScc++;
                Node *top = tarStack->top();
                tarStack->pop();
                onStack[top->id - 1] = false;
                int size = 1;

                while(top->id != last->id) {
                    top = tarStack->top();
                    tarStack->pop();
                    onStack[top->id - 1] = false;
                    size++;
                }
                insertNewSCC(size);  //Ranks the size among array of 5 elements
            }

            Node *newLast = last->caller;   //Go up one recursive call
            if(newLast != NULL) {
                newLast->lowlink = min(newLast->lowlink, last->lowlink);
                last = newLast;
            } else {   //We've seen all the nodes
                break;
            }
        }
    }
}

My iterative version runs and gives me the same output as the recursive version. The problem is that the iterative version is slower, and I'm not sure why. Can anyone give me some insight on my implementation? Is there a better way to implement the recursive algorithm iteratively?

Sutler

Can you post actual code please instead of semi-pseudocode? It's probably an implementation issue. It looks like you might be doing a lot of unnecessary copies, but I can't tell because you've transformed your actual code into pseudocode. – Cavanagh

I've added the actual code per your request! :) – Sutler

On some of the larger graphs, it runs 20% slower. – Sutler

Answer 1

A recursive algorithm uses the stack as storage area. In the iterative version, you use some vectors, which themselves rely on heap allocation. Stack-based allocation is known to be very fast, since it is only a matter of moving an end-of-stack pointer, whereas heap allocation may be substantially slower. That the iterative version is slower is not fully surprising.

Generally speaking, if the problem at hand fits well within a stack-only recursive model, then, by all means, recurse.

Ellanellard

@mathee, If you want to support arbitrary data sizes, you will hit the limit eventually. Thus the comments a la "if it fits on the stack". – Morula

It looks like your iterative code uses an "artificial stack". As such it should have the same computational complexity and memory coherency as the recursive algorithm. To optimise it, I would use a conventional profiling approach to find out if there are any unexpected hotspots. – Barabarabarabas

This algo is supposed to be linear in terms of # of nodes and edges. I would call that fast. Are you doing something wrong perhaps? – Matthieu