How to input millions of integers quite fast in C++?

Question

I'm doing a data structure programming assignment about stack in C++.

In this assignment, I should read lots of integers(in the worst case I should read 1,600,000 integers) and finally output some strings.

As a student, I submit my cpp source file and the website judges and scores my source code. I got 100% but I want to do better. The time restriction of this assignment is 2 seconds and the execution time of my source code is 128 milliseconds. However, the top student only used 52 milliseconds to complete the task. So I want to know how to make my code faster.

My source code mainly contains three parts:

1. use cin to read lots of integers from the OnlineJudge system(up to 1,600,000 integers).
2. try to find the solution and store it in a char array.
3. use cout to output the char array.

OnlineJudge tells me the execution time of my code. The 1st part takes 100 milliseconds, the 2nd part takes 20 milliseconds, and the 3rd part takes 12 milliseconds. So if I want to make my code faster, I should improve input speed.

Input of OnlineJudge is like this:

5 2
1 2 3 5 4

The 1st line is two integers n and m, the 2nd line is n integers separated by spaces. Restrictions are: 1<=n<=1,600,000 and 0<=m<=1,600,000. In order to read more than 1 million integers, my code is like this:

#include <iostream>
using namespace std;
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    int *exit = new int[1600000];
    cin>>n>>m;
    for (int i=0;i<n;++i)
        cin>>exit[i];
    return 0;
}

If n is small, OnlineJudge says execution time is 0 milliseconds. if n is very large,e.g. 1,600,000. OnlineJudge says this code takes 100 milliseconds. If I delete

std::ios::sync_with_stdio(false);
cin.tie(NULL);

Then the code takes 424 milliseconds. However, reading integers is necessary in this assignment, so I'm really curious about how the top student can finish "cin,find the solution,cout" within only 52 milliseconds.

Do you have any ideas on improving input speed?

2019.4.17：Someone suggests using vector or std::from_chars, but in this assignment these are banned. If I write

#include <vector>

or

#include <charconv>

or

#include <array>

then OnlineJudge says "Compilation error".

Someone suggests using scanf, my code is like this:

for (int i=0;i<n;++i)
    scanf("%d", &exit[i]);

But the execution time is 120 milliseconds.By the way, I don't think scanf is faster than cin, Using scanf() in C++ programs is faster than using cin?

Someone suggests using getline.I seldom uses this fuction,my code is like this:

stringstream ss;
string temp;
getline(cin, temp);
ss<<temp;ss>>n;ss>>m;
ss.clear();temp.clear();
getline(cin, temp);ss<<temp;
for (int i=0;i<n;++i)
    ss>>exit[i];

Execution time is also 120 milliseconds.

Someone suggests using mmap. I've never heard this function before. It seems this function is only available in Unix? But I'm using Visual Studio 2010. My code is like this:

#include <unistd.h>
#include <sys/mman.h>
    //to load 1,600,000 integers
    int *exit = static_cast<int*>(mmap(NULL,1600*getpagesize(),PROT_READ,MAP_ANON|MAP_SHARED,0,0));
    for (int i=0;i<n;++i)
        cin>>*(exit+i);

OnlineJudge says "Runtime error (signal 11)" instead of "Compilation error", signal 11 means "Invalid memory reference", this signalis is sent to a process when it makes an invalid virtual memory reference, or segmentation fault, i.e. when it performs a segmentation violation. I don't know if there's anything wrong with my mmap.Hope you can tell me.

2019.4.22：Thanks for all your help.Now I solve this problem successfully.The key function is mmap.The code is like this:

#include <sys/mman.h>
    cin.tie(NULL);
    std::ios::sync_with_stdio(false);
    string temp;

    int n,m;
    int *exit = new int[1600000];

    const int input_size = 13000000;
    void *mmap_void = mmap(0,input_size,PROT_READ,MAP_PRIVATE,0,0);
    char *mmap_input = (char *)mmap_void;
    int r=0,s=0;
    while (mmap_input[s]<'0' || mmap_input[s]>'9') ++s;
    while (mmap_input[s]>='0' && mmap_input[s]<='9')
    { r=r*10+(mmap_input[s]-'0');++s; }
    n=r;r=0;
    while (mmap_input[s]<'0' || mmap_input[s]>'9') ++s;
    while (mmap_input[s]>='0' && mmap_input[s]<='9')
    { r=r*10+(mmap_input[s]-'0');++s; }
    m=r;r=0;
    while (mmap_input[s]<'0' || mmap_input[s]>'9') ++s;
    for (int i=0;i<n;++i)
    {
        while (mmap_input[s]>='0' && mmap_input[s]<='9')
        { r=r*10+(mmap_input[s]-'0');++s; }
        ++s;
        exit[i]=r;r=0;
    }

Execution time of mmap and convert chars to integers take 8 milliseconds. Now the total execution time of this homework take 40 milliseconds, faster than 52 milliseconds.

Answer 1

A few ideas:

1. Read integers using std::scanf, not std::istream. The latter is known to be slower for multiple reasons, even with std::ios::sync_with_stdio(false) call.
2. Read the file by mapping it into memory.
3. Parse integers faster than scanf and strtol.

Example:

#include <cstdio>

int main() {
    int n, m, a[1600000];
    if(2 != std::scanf("%d %d", &n, &m))
        throw;
    for(int i = 0; i < n; ++i)
        if(1 != std::scanf("%d", a + i))
            throw;
}

You can also unroll that scanf loop to read multiple integers in one call. E.g.:

#include <cstdio>

constexpr int step = 64;
char const fmt[step * 3] =
    "%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d "
    "%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d "
    "%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d "
    "%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d"
    ;
void main() {
    int a[1600000];
    int n, m;
    if(2 != std::scanf("%d %d", &n, &m))
        throw;

    for(int i = 0; i < n; i += step) {
        int expected = step < n - i ? step : n - i;
        int* b = a + i;
        int read = scanf(fmt + 3 * (step - expected),
                         b + 0x00, b + 0x01, b + 0x02, b + 0x03, b + 0x04, b + 0x05, b + 0x06, b + 0x07,
                         b + 0x08, b + 0x09, b + 0x0a, b + 0x0b, b + 0x0c, b + 0x0d, b + 0x0e, b + 0x0f,
                         b + 0x10, b + 0x11, b + 0x12, b + 0x13, b + 0x14, b + 0x15, b + 0x16, b + 0x17,
                         b + 0x18, b + 0x19, b + 0x1a, b + 0x1b, b + 0x1c, b + 0x1d, b + 0x1e, b + 0x1f,
                         b + 0x20, b + 0x21, b + 0x22, b + 0x23, b + 0x24, b + 0x25, b + 0x26, b + 0x27,
                         b + 0x28, b + 0x29, b + 0x2a, b + 0x2b, b + 0x2c, b + 0x2d, b + 0x2e, b + 0x2f,
                         b + 0x30, b + 0x31, b + 0x32, b + 0x33, b + 0x34, b + 0x35, b + 0x36, b + 0x37,
                         b + 0x38, b + 0x39, b + 0x3a, b + 0x3b, b + 0x3c, b + 0x3d, b + 0x3e, b + 0x3f);
        if(read != expected)
            throw;
    }
}

---

Another option is to parse integers manually (mapping file into memory would help here and there are much faster algorithms for parsing integers than this and standard atoi/strtol, see Fastware - Andrei Alexandrescu):

int main() {
    int n, m, a[1600000];
    if(2 != std::scanf("%d %d", &n, &m))
        throw;

    for(int i = 0; i < n; ++i) {
        int r = std::getchar();
        while(std::isspace(r))
            r = std::getchar();
        bool neg = false;
        if('-' == r) {
            neg = true;
            r = std::getchar();
        }
        r -= '0';
        for(;;) {
            int s = std::getchar();
            if(!std::isdigit(s))
                break;
            r = r * 10 + (s - '0');
        }
        a[i] = neg ? -r : r;
    }
}

---

Yet another is to map the file into memory and parse it faster:

#include <boost/iostreams/device/mapped_file.hpp>

inline int find_and_parse_int(char const*& begin, char const* end) {
    while(begin != end && std::isspace(*begin))
        ++begin;
    if(begin == end)
        throw;
    bool neg = *begin == '-';
    begin += neg;
    int r = 0;
    do {
        unsigned c = *begin - '0';
        if(c >= 10)
            break;
        r = r * 10 + static_cast<int>(c);
    } while(++begin != end);
    return neg ? -r : r;
}

void main() {
    boost::iostreams::mapped_file f("random-1600000.txt", boost::iostreams::mapped_file::readonly);
    char const* begin = f.const_data();
    char const* end = begin + f.size();
    int n = find_and_parse_int(begin, end);
    int m = find_and_parse_int(begin, end);

    int a[1600000];
    for(int i = 0; i < n; ++i)
        a[i] = find_and_parse_int(begin, end);
}

---

Benchmark source code.

Note that the results may differ considerably across different versions of compilers and standard libraries:

• CentOS release 6.10, g++-6.3.0, Intel Core i7-4790 CPU @ 3.60GHz

---- Best times ----
seconds,    percent, method
0.167985515,  100.0, getchar
0.147258495,   87.7, scanf
0.137161991,   81.7, iostream
0.118859546,   70.8, scanf-multi
0.034033769,   20.3, mmap-parse-faster

• Ubuntu 18.04.2 LTS, g++-8.2.0, Intel Core i7-7700K CPU @ 4.20GHz

---- Best times ----
seconds,    percent, method
0.133155952,  100.0, iostream
0.102128208,   76.7, scanf
0.082469185,   61.9, scanf-multi
0.048661004,   36.5, getchar
0.025320109,   19.0, mmap-parse-faster