tags:

views:

145

answers:

7

Hello All, 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' conditions 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

+2  A: 

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);
paxdiablo
A slightly better approach if performance is critical would be: `std::swap( *(v.end()-2), *(v.end()-1) )`, as that will perform 3 copies of the contents (instead of 4) and will avoid having to update the `end` pointer in the vector (or `size` depending on the implementation) 4 times. Then again the optimizer might be able to clean the code for you, but when the solution is simple to implement, more readable and maintainable... that is not early optimization :)
David Rodríguez - dribeas
A: 

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

rerun
Due to the way modern cpu's work (branch prediction and forward caching in particular), a poorly predicted if statement can cause massive slow downs as the cpu has to flush everything it had ready (and any operations it may have started in anticipation of the result) and then load new code from memory ready to be processed. This can end up taking out a fair amount of time from the cpu. I've actually found that it is sometimes faster to do several calculations then it is to use an if statement to skip them (usually when doing things like operations on large arrays of mesh matrices/vertices).
Grant Peters
A: 

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..

Tony
A: 

change the if/throw to assertions

Justin
An assertion has the same effect - to check the condition and throw an exception is that condition doesn't hold true. It is usually implemented with an if-statement.
sharptooth
a) assertions typically call abort. b) assertions should be disabled in release builds. a disabled assertion would be preprocessed out, removing the condition as well as any exception scaffolding.
Justin
a) That's perfect. Why will just killing the program make it run faster that if an exception is thrown?b) If you sacrifice exceptions the program will run into undefined behavior if the condition is violated. That can be done, but this is equivalent to not checking the condition in the first place.
sharptooth
@Justin: This is a harsh change in behavior... an exception is something the system can recover from, an assert is something the system will die by. When the assert is removed from release code, that amounts to not performing the check and undefined behavior. @sharptooth: besides exceptions disappearing in release code, when an assertion fails only global objects need to be destroyed. That means that the compiler does not need to track by any means what objects in the stack will need to be destroyed by stack unwinding.
David Rodríguez - dribeas
a) you've missed the point. assertions are enabled in debug builds and preprocessed out in release builds. b) no, it becomes the programmer's responsibility to use the `Stack' interface correctly (e.g., to check the size when it is unknown before making the call rather than writing a catch statement). it is definitely an improvement to not checking at all because the condition is evaluated every time in debug. i've worked on plenty of projects where exceptions were not allowed (but assertions were) -- they do work to verify a program's correctness.
Justin
@David it is a harsh change, but it verifies that the programmer has used the interface correctly. exceptions aren't necessary to write good (and safe) programs. c++ is flexible enough that a writer *could* mandate that all checks have been performed (if you don't trust your clients, or if you really want to dig deep into verifying a program's correctness).
Justin
@Justin: Wow, non-trivial C++ projects where **exceptions** are banned? Tell me where you worked, so I can avoid being hired by them...
DevSolar
@Justin: there is a huge semantic difference from exceptions to asserts: exceptions should be thrown in situations that are meant to happen but that are exceptional, while asserts are meant to check situations that can only be present due to programmer's errors. You can program without exceptions, and C++ allows that, but the usual change is moving to some other error reporting mechanism (return code, error arguments) rather than killing the application. Semantically you have change the code from *this should be rare* to *this is an error*. Those two are not equivalent.
David Rodríguez - dribeas
@DevSolar shooore: avoid low level and performance critical work
Justin
@DevSolar: In the project I am working, the core of the system is an *exceptions free zone*. Exceptions are used in all but the critical path. That is the result of extensive performance testing and profiling by some really smart people.
David Rodríguez - dribeas
@David yes, of course there is a change to use other means of error handling for exceptional cases, as well as higher level mechanisms for error reporting when exceptions are not available. the basis is simple: a client should know the object's state before making the calls - that responsibility is passed to the programmer. both cases presented by the op can be easily checked by the client (if they are unknown at the callsite). assertions are great - it forces the caller to correct the mistake in their program immediately.
Justin
@David Rodríguez: That, on the other hand, is a concept I am familiar with. Optimizing exceptions out of the critical path is one thing. But forbidding them altogether... not really. @Justin: Low-level and performance critical work? Like what I did those last ten years? OK then... ?:-/
DevSolar
A: 

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;
}
Kiril Kirov
Yes, throwing is relatively slow. But in normal operation the code will never throw, so it doesn't matter that much.
sharptooth
Why "will never throw" ? If he try to "exchange" when the stack is with just one element or empty? Or i have misunderstood the "normal operation"
Kiril Kirov
If an exception is thrown normal operation will be interrupted. That's what exceptions are for. You just execute statements one-by-one as if everything's fine. If something goes wrong an exception is thrown and control goes to the handler, but you can't continue from that point. This is what I'm talking about and this is how sane C++ code is written - targeting for no exceptions in normal operation.
sharptooth
@sharptooth: if the question is right in saying that the ifs amount to a big part of the performance impact, then exceptions might not be the way at all. Exception handling has a cost even when exceptions are not thrown --the compiler must add code to track the objects that need deletion for the stack unwinding operation, it might not amount to much in general, but (if truly) when `if ( size() < 2 )` causes a performance issue... anything can.
David Rodríguez - dribeas
Automatic downvote for that hideous XOR trick, especially in the context of needed speed. It will _never_ outperform a simple three-step move and (not that I'm implying this is the case for _you_) it's almost always used by people trying to show how clever they are, and failing miserably. I'll be happy to reverse it if you give more sensible code.
paxdiablo
@David - Yes, I know that. That's why I said, that this would be useful **only** for `Stack::exch` .. There's no throw there. Also said, that there's nothing to be done for `Stack::pop`. Or you mean, that just using `std::vector` in `Stack::exch` is enough for the compiler to put this code for exceptions handling?
Kiril Kirov
@paxdiable - OK, I can bring back the standard way of exchanging, but I didn't get your point - what's wrong with this here, if we know, that we're working with `int`-s.
Kiril Kirov
(1) It's far less readable than a simple `int t = a; a = b; b = t;`. Readability is a big plus IMNSHO. (2) It will possibly be slower, it certainly won't be faster. Aarghh, I can't reverse in anticipation of the change due to the time limit. I'll have to wait for the edit (was hoping to go home early, oh well).
paxdiablo
@paxdiable - OK, noted, thanks
Kiril Kirov
No probs, and +1 for the good idea of not throwing on `exch` - if the caller really wants to catch that, they can check the return code. Code for the fast case, allow the safe case where desired.
paxdiablo
A: 

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]);
}
Grozz
+1  A: 

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.

David Rodríguez - dribeas