4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Changing to std::vector increased user and sys, and real remained about the same. 8.76 real 7.29 user 1.44 sys \$\endgroup\$ – Jackson Jan 3 '16 at 19:06
  • \$\begingroup\$ 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. \$\endgroup\$ – Juho Jan 3 '16 at 19:08
  • \$\begingroup\$ The full test code is 2 million lines... it goes PUSH 1\nPUSH 2\n...PUSH 1000000\nPOP\nPOP...POP \$\endgroup\$ – Jackson Jan 3 '16 at 19:10
  • \$\begingroup\$ 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). \$\endgroup\$ – Mat Jan 3 '16 at 20:20
  • \$\begingroup\$ Can you put the test data file somewhere we can download? \$\endgroup\$ – Martin York Jan 4 '16 at 2:14
4
\$\begingroup\$
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));
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – David Hammen Jan 3 '16 at 21:05
  • \$\begingroup\$ They are not default-initialized they are zero-initialized. For int this means they are zero. \$\endgroup\$ – Martin York Jan 4 '16 at 1:34
  • \$\begingroup\$ 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 \$\endgroup\$ – Martin York Jan 4 '16 at 1:59
  • \$\begingroup\$ Would you recommend reading using gets/gets_s then? \$\endgroup\$ – Jackson Jan 4 '16 at 2:04
  • \$\begingroup\$ Whoa! I'd recommend you not use clang combined with libc++. I'll update my answer. \$\endgroup\$ – David Hammen Jan 4 '16 at 4:17
5
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.