1

I want to implement a LIFO stack object. The C++ standard lib provides a convenient stack structure (std::stack) with a very simple interface. By default, it uses std::deque as its underlying container.

Is there any performance penalty to using std::stack rather than using std::deque directly?

My use case would involve many pops and pushes per second.

cutcrew
  • 17
  • 3
  • Using stack, or using a deque and doing stack operation manually to it should have the same performance. If you really want to know, code it both ways and benchmark. – NathanOliver May 18 '21 at 14:59
  • profile it, experiments are far better than opinion based answers – Alessandro Teruzzi May 18 '21 at 14:59
  • 1
    @AlessandroTeruzzi actually, random profiling might do more bad than good. One have to know what they are expecting and why before engaging in profiling. – SergeyA May 18 '21 at 15:01
  • @SergeyA you have a point, my comment was rushed, I don't believe that there is any significant difference between stacks and deque implementation. Clarity in the code is always very important. However, I cannot be certain without an experiment and "many" is not enough to dismiss the question. Saying that, benchmark is a better term than profiling. – Alessandro Teruzzi May 18 '21 at 15:28

2 Answers2

2

No, there will be no performance profile changes by using std::stack (as compared to using std::deque directly).

SergeyA
  • 61,605
  • 5
  • 78
  • 137
2

As commenters pointed out, you should always benchmark first in such cases. As an example I used a tool called Quick Bench, as it is online and can be embedded in here. You should always pick the tool that fits the particular need the best.

In this case the answer depends on whether you have optimizations turned on. Please note that you should always benchmark optimized builds, but I included the unoptimized version to show how results differ. If we run a benchmark (link) with optimizations off (-O0 on g++), we see that stack is slightly slower:

enter image description here

However when we run the benchmark (link) with optimizations (-O3 on g++), the story is different:

enter image description here

The performance is nearly identical. This is due to inlining. This means that in release builds you won't suffer any performance loss from using stack. In C++ this is called zero cost abstractions.

Its worth pointing out that in reality even "zero cost" abstractions still carry a cost - increased compile times.

janekb04
  • 4,304
  • 2
  • 20
  • 51
  • @cutcrew Glad I could help! If the answer solved your issue you may upvote it and mark as accepted, so other users in the future can find it easier. – janekb04 May 18 '21 at 17:49