How to avoid if cond. for stack operation

I have created a stack class which holds std::vector. I have written stack operation like pop() and exch() like

int Stack::pop() 
{
  if (v.size() < 0)
    throw("Error : Stack Underflow");

  int tos = v.back();
  stack.erase(v.end()-1);
  return tos;
}

void Stack::exch()  // Exchange top 2 element
{
  if (v.size() < 2)
    throw("Error : Stack Underflow");

  size_t n = v.size();
  int tmp = v[n-1];
  v[n-1] = v[n-2];
  v[n-2] = tmp;
}

My application consist of lot of 'pop()' & 'exch()' operations. But due to 'if' condi开发者_开发知识库tions the performance is little bit slow. Can you tell me how to avoid 'if' conditions ? Is there any way Or work around to avoid 'if'.

Thanks in advance.

Thanks, Nilesh

No, not really. If you have to check, you have to check. You could replace the if with a ternary operator but that will almost certainly compile down to the same code.

Unless the size() method is particularly convoluted, I can't see it dragging down the performance that much. You may get some speed improvement by caching the value in the Stack class (I'm assuming v is a vector of some sort).

However, if it is a vector, it's perfectly capable of acting as a stack on its own so you can let it raise its own exceptions rather than imposing your exceptions on it.

The only thing you're missing is the exch method which you could do as:

a = v.back(); v.pop_back();
b = v.back(); v.pop_back();
v.push_back(a);
v.push_back(b);

You said that checking the conditions amounts to a big part of the cost of execution. The question is whether throwing the exceptions or the ifs themselves are the highest cost there. If the cost is associated with the situations where the exception is actually thrown, you might want to refactor the code to work without exceptions (return codes seem a good option here) as exceptions are expensive. Also, note that exceptions might have a small impact even when they are not thrown --i.e. the compiler must track the set of objects to destroy during stack unwinding in case an exception is thrown. Compilers are smart, so expect that cost to be small, but not zero.

If on the other hand, the exceptions are not thrown, but the cost is really associated with mispredictions then you might want to go back to your compiler vendor docs and look how to hint it. Many compilers allow for a two phase compilation, where after the first compilation you can run tests and profile, and you can hand that profiling information back to the compiler to optimize your code with knowledge of what the expected behavior of the application can be.

Manually you can also hint the compiler as to what the most expected result of a check might be. In particular, some compilers will assume that the most probable outcome of an if is a success (enter the if, skip the else) , and that the most probable code path will enter the if. There are also special keywords that you can use to hint the compiler, as an example, in gcc you can use if (__builtin_expect( (condition), 0 )) to tell the compiler that the most probable outcome is condition to be false.

Your if statements are not a performance issue. In analyzing an algorithm you can consider your decision statements as constant or in other words not effecting the performance. This is not to say that if you have some code if (SomeExpensiveFn() == AnotherExpensiveFn()) it wouldn't take some time just that the if part, ie the comparison of the results, is less then negligible.

This is only true if you are not reevaluating entire sets. While 1 to n if statements are not a performance issue. If you stack class causes N^2 if statements to be executed every then you will see performance degradation.

Also I assume this is homework but if its not there is std::stack

If you know you're about to do N pop()s with no pushes, you can do a single check of size() in your client code, then call a new unsafe_pop() member function that doesn't check. Similarly, you can have an unsafe_exch() for times when your client code can more efficiently guarantee sufficient elements.

But, the expense of other operations here will dwarf the if statements... even the pointer arithmetic for erase(end() - 1) probably takes 10 times longer. If your performance needs are that extreme, you should look much deeper, and also at alternative algorithms, threading/concurrency etc..

change the if/throw to assertions

That mix of STL containers and your own code makes me wonder why don't you use std::stack? Stick to one option. For example pop operation in your code could be as simple as:

int Stack::pop() 
{
  if (size == 0)
    throw("Error : Stack Underflow");

  int tos = v[size-1];
  --size;  
  return tos;
}

and

void Stack::exch()  // Exchange top 2 element
{
  if (size < 2)
    throw("Error : Stack Underflow");

  std::swap(v[size-1], v[size-2]);
}

No, you can't remove the if-statements..
But you could increase the performance a little, if you remove somehow the "throw". Throwing and catching an exception is a slow operation (refer to this, if you're interested in: http://www.codeproject.com/KB/cpp/exceptionhandler.aspx ).

So, in Stack::exch() you could just put return, instead of throw... If you want to know if the exchange is done successfully, you could make the function bool and check for true or false.

But there's nothing you can do for the pop operation.

Also, you could change the v.size() < 0 (by the way, this must be v.size() <**=**0, or you could try to pop from an empty stack ) to if( ! v.empty() ).

EDIT: You can write these functions like this:

int Stack::pop() 
{
    if ( v.empty() )
    {
        throw( "Error : Stack Underflow" );
    }

    int tos = v.back();
    stack.erase( v.end() - 1 );
    return tos;
 }

bool Stack::exch()  // Exchange top 2 element
{
    if( v.size() < 2 )
    {
        return false;
    }

    std::vector< int >::size_type n = v.size();

    int nTmp = v[ n - 1 ];
    v[ n - 1 ] = v [ n - 2 ];
    v[ n - 2 ] = nTmp;

    return true;
}