# C++ Stack implementation using std::list

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.

• Changing to std::vector increased user and sys, and real remained about the same. 8.76 real 7.29 user 1.44 sys – Jackson Jan 3 '16 at 19:06
• The way you parse input can also be a big factor. Maybe you could get rid of the Python code, and post full code that you use for benchmarking? It should be easier to answer the question then. – Juho Jan 3 '16 at 19:08
• The full test code is 2 million lines... it goes PUSH 1\nPUSH 2\n...PUSH 1000000\nPOP\nPOP...POP – Jackson Jan 3 '16 at 19:10
• That 0.00 user in your question is not really believable, are you sure that your test or copy/paste was accurate (and repeatable)? Also make sure you're timing only the C++ part, not the python generator (store the output of the generator in a file, and time only the C++ part). – Mat Jan 3 '16 at 20:20
• Can you put the test data file somewhere we can download? – Martin York Jan 4 '16 at 2:14

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));
}
}
}

• After converting to vectors and C-style I/O, the exact same input file yields timing results of 0.28 real 0.27 user 0.01 sys on my computer. I'm going to leave those conversions as an exercise for the questioner. – David Hammen Jan 3 '16 at 21:05
• They are not default-initialized they are zero-initialized. For int this means they are zero. – Martin York Jan 4 '16 at 1:34
• C++ I/O is notoriously slow: This is actually false and has been shown to be false on SO several times. Now; It is hard to compete with C I/O but it is close (The problem us usually caused by user failure. Especially excessive flushing and syncing the C++ IO streams with the C IOstream. Turn off the sync with ios_base::sync_with_stdio(false); and don't use std::endl as much) See: Performance Difference Between C and C++ Style File IO especially the answer by Konrad Rudolph – Martin York Jan 4 '16 at 1:59
• Would you recommend reading using gets/gets_s then? – Jackson Jan 4 '16 at 2:04
• Whoa! I'd recommend you not use clang combined with libc++. I'll update my answer. – David Hammen Jan 4 '16 at 4:17

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