C++ Stack implementation using std::list

Question

I have the following 'interface' to the C++ std::list and I was wondering how I could make it go faster. In particular, it needs to be able to evaluate up to two million operations in a matter of a couple seconds. Right now it's at around 8 seconds.

#include <iostream>
#include <list>

int main()
{

    int n, m;
    std::cin >> n >> m;

    std::list<int> myList (n);

    for (int i = 0 ; i < m; i++) {
        std::string op;
        std::cin >> op;
        if (op[1] == 'O') {
            std::cout << myList.back() << '\n';
            myList.pop_back();
        } else {
            int val;
            std::cin >> val;
            myList.push_back(val);
        }
    }

    return 0;
}

It reads input in the form

3 4
PUSH 2
PUSH 3
POP
POP

With expected output

3
2

Where 3 corresponds to highest value, and 4 corresponds to number of operations.

The operations are guaranteed to be safe (no POPing empty stacks), and each value is used at most once (this part in particular I feel I could optimize, but I'm not sure how).

Right now I'm testing with the following Python script:

print "1000000 2000000"

for val in xrange(1,1000001):
    print "PUSH ", val

for _ in xrange(0,1000000):
    print "POP"

And getting this for time:

8.89 real         0.00 user         0.01 sys

I started out using std::stack, but tried switching to std::list in order to give a preset size, so as to not need to reallocate memory. This did not help the time any, but that's where it stands as of now.

Answer 1

std::list<int> myList (n);

This does not do what you think it does. It creates a list of n elements. If you're using C++11, they're all garbage because those n elements are default-initialized. Fortunately, you'll never run across those garbage values. Your calls to push_back allocate a new chunk of memory.

You don't want to use a list. Use a vector.

When I run your program on my computer, compiled with optimization level 3, I get timing results of

6.64 real         6.32 user         0.32 sys

So comparable results. Let's trim your function down a bit in size. Let's trim it down a lot!

#include <iostream>
int main()
{   
    int n, m;
    std::cin >> n >> m;
    for (int i = 0 ; i < m; i++) {
        std::string op; 
        std::cin >> op; 
        if (op[1] == 'O') {
        } else {
            int val;
            std::cin >> val;
        }   
    }   
    return 0;
}   

The only logic that's left is reading the input. When I run this on my computer, I get timing results of

 5.23 real         5.22 user         0.00 sys

Almost all of the wall clock time is reading the file. C++ I/O is notoriously slow. If you need to read, parse, and write millions of lines in a couple of seconds I suggest you revert back to C I/O. And don't use fscanf. It, too, is slow. Take advantage of the known format of the input file. Read a line. If the second character is 'O' you have a POP. Otherwise you have a PUSH val. Parse the integer that starts at the character after the H, or the fifth character (character position 4).

Update

It turns out the compiler and standard c++ library makes a big difference. Reporting only the real times (first item from /usr/bin/time),

Version     g++-5/libstdc++   clang++-3.7/libc++
Original    4.79 seconds      7.29 seconds
Untie       0.65              5.90
Vector      0.50              5.71
Getline     0.25              3.11
C I/O       0.28              0.28

The getline version is even faster than is the C-based I/O version in the case of using g++. Clang, in this case, bites. Or perhaps it's the standard C library.

Here's the getline version:

#include <cstdlib>
#include <iostream>
#include <vector>


int main()
{   
    std::ios_base::sync_with_stdio (false);
    std::cin.tie (nullptr);

    int n, m;
    std::cin >> n >> m;
    std::cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n');

    std::vector<int> stack;
    stack.reserve (n);

    char line[256];
    for (int i = 0 ; i < m; i++)
    {
        std::cin.getline (line, sizeof(line));
        if (line[1] == 'O')
        {
            std::cout << stack.back() << '\n';
            stack.pop_back (); 
        }
        else
        {
            stack.push_back (std::atoi(line+4));
        }
    }
}

Answer 2

C++ std::cin and std::cout are both tied together and and tied to C stdin and C stdout respectively. This causes a lot of performance problems when dealing with std::cin and std::cout.

You can help the situation by using:

std::ios_base::sync_with_stdio(false);   // Disconnect from C IO
std::cin.tie(NULL);                      // Disconnect in from out (otherwise they flush).

If you change the code to use std::fstream (rather than std::cin/std::cout) you can get even better performance.

I did some experiments and reading a line and parsing the line separately improves things even more.

 std::getline(std::cin, line);
 if (line[1] == 'O') {
     // STUFF
 }
 else {
     int  val;
     std::stringstream  linestream(&line[5]);
     linestream >> val;
     // STUFF;
 }

Also you should be using vector rather than list. It has two advantages: 1) You can allocate all the space you need in advance. 2) Spacial locality can make access faster.

Times:

 As written:  real  0m5.119s   user  0m4.751s   sys  0m0.362s
 Use vector:  real  0m4.906s   user  0m4.585s   sys  0m0.325s
 Un Tie:      real  0m4.247s   user  0m4.233s   sys  0m0.017s
 std::getline real  0m1.559s   user  0m1.546s   sys  0m0.017s
 std::fstream real  0m0.804s   user  0m0.766s   sys  0m0.022s


 C Version    real  0m0.434s   user  0m0.422s   sys  0m0.016s