Speed comparison between recursive and nonrecursive implementation

Question

I have an complex algorithm which uses really deep recursion. Because there is stack overflow with some specific data I have tried to rewrite it without recursion (using external stack on the heap). So I have two modifications of the same algorithm. Then I have performed some tests and I have found out that recursive implementation is much time faster than another one.

Can someone explain it to me, please? It is part of my final university project to discuss these results (why is one implementation highly faster than another one). I think that it is because of different caching of stack and heap but I am not sure.

Thanks a lot!

EDIT

OK, there is a code. The algorithm is written in C++ and solves tree isomorphism problem. Both implementations are same except one method which compares two nodes. The comparison is defined recursively - one node is lesser than another if one of it's children is lesser than corresponding child of another node.

Recursive version

char compareTo( const IMisraNode * nodeA, const IMisraNode * nodeB ) const {
    // comparison of same number of children
    int min = std::min( nodeA->getDegree( ), nodeB->getDegree( ) );
    for ( int i = 0; i < min; ++i ) {
        char res = compareTo( nodeA->getChild( i ), nodeB->getChild( i ) );
        if ( res < 0 ) return -1;
        if ( res > 0 ) return 1;
    }
    if ( nodeA->getDegree( ) == nodeB->getDegree( ) ) return 0; // same number of children
    else if ( nodeA->getDegree( ) == min ) return -1;
    else return 1;
}

Nonrecursive implementation

struct Comparison {
    const IMisraNode * nodeA;
    const IMisraNode * nodeB;
    int i;
    int min; // minimum of count of children

    Comparison( const IMisraNode * nodeA, const IMisraNode * nodeB ) :
    nodeA( nodeA ), nodeB( nodeB ),
    i( 0 ), min( std::min( nodeA->getDegree( ), nodeB->getDegree( ) ) ) { }
} ;

char compareTo( const IMisraNode * nodeA, const IMisraNode * nodeB ) const {
    Comparison * cmp = new Comparison( nodeA, nodeB );
    // stack on the heap
    std::stack<Comparison * > stack;
    stack.push( cmp );

    char result = 0; // result, the equality is assumed

    while ( !result && !stack.empty( ) ) { // while they are not same and there are nodes left
        cmp = stack.top( );

        // comparison of same children
        if ( cmp->i < cmp->min ) {
            // compare these children
            stack.push( new Comparison( cmp->nodeA->getChild( cmp->i ), cmp->nodeB->getChild( cmp->i ) ) );
            ++cmp->i; // next node
            continue; // continue in comparing on next level
        }
        if ( cmp->nodeA->getDegree( ) != cmp->nodeB->getDegree( ) ) { // count of children is not same
            if ( cmp->nodeA->getDegree( ) == cmp->min ) result = -1; // node A has lesser count of children
            else result = 1; 
        }
        delete cmp;
        stack.pop( );
    }

    while ( !stack.empty( ) ) { // clean stack
        delete stack.top( );
        stack.pop( );
    }

    return result;
}

What language, what implementation? That makes a huge difference. — zoul, May 18 '11 at 11:15
@Zoul C++ both. The difference is only in one method ( recursive and nonrecursive implementation ) — Gaim, May 18 '11 at 11:17
Without details of the algorithm you're trying to implement, your recursive code and your non-recursive code, it's difficult to give any kind of meaningful answer. Most textbooks I've read state that recursion is usually slower than iteration, though, so it seems odd that your iterative version is slower. — GordonM, May 18 '11 at 11:19
Tail recursion optimisation support is a language feature that can significantly influence the performance of the recursive version. Especially since you are experiencing stack overflow problems. — Ruben, May 18 '11 at 11:31

score 2 · Accepted Answer · 2011-05-18T11:59:25.750

2

Your non-recursive code does dynamic memory allocation (explicitly with new, and implicitly by your use of std::stack), while the recursive one does not. Dynamic memory allocation is an extremely expensive operation.

To speed things up, try storing values, not pointers:

stack <Comparison> astack;

then code like:

astack.push( Comparison( cmp->nodeA->getChild( cmp->i ), cmp->nodeB->getChild( cmp->i ) ) );

Comparison cp = astack.top();

edited May 18 '11 at 11:59

answered May 18 '11 at 11:46

Ok, it confirms my presumption. But is that all or eg. cache has a significant influence? By the way is there any different solution of rewriting this type of recursion without using dynamic memory to keep original performance? Because that nonrecursive version is 4-5 times slower – Gaim May 18 '11 at 11:52
Compared with dynamic allocation, everything else fades into insignificance. To speed things up, you could implement your own stack as a fixed-sized array which you allocate once, and store comparison objects in it, not comparison pointers. – May 18 '11 at 11:55
I agree with Neil. I'm not a C programmer by trade but it always holds for pretty much all programming that if you have an expensive operation inside a loop then moving it outside the loop will always yield the biggest performance win. In this case it would involve allocating one big block of memory at the start of the loop instead of multiple allocations inside. Of course you need to work out approximately how big the memory block should be before you start or you'll be wasting memory, or running out (like how you're overflowing the stack in your recursive version) – GordonM May 18 '11 at 12:02
1

@GordonM: Or you could simply double the storage at every overflow. That has the same complexity class -- O(n) -- as pre-allocating the correct size. – jmg May 18 '11 at 12:07

score 0 · Answer 2 · edited May 23 '17 at 12:12

0

This doesn't answer your speed-comparison question, but rather suggests ways to increase stack size for your recursive solution.

You can increase the stack size (default: 1MB) under VC++: search "stacksize" in Visual Studio help.

And you can do the same under gcc. There's an SO discussion on that very question.

edited May 23 '17 at 12:12

Community

1
1

answered May 18 '11 at 11:58

Pete Wilson

8,610
6
39
51

Speed comparison between recursive and nonrecursive implementation

2 Answers2