競技プログラミングにおける C++ の入出力を高速化する (入力編)

私は普段 AtCoder では GCC を使っているのですが、たまには Clang も試してみるか～と軽い気持ちで Clang で提出してみました。すると、実行時間が GCC の場合の 3倍 になってしまいました。どうやら、その原因は入出力のようでした。

Clang (libc++) の cin, cout は遅い！！

一方で Clang は再帰関数をループに展開する能力が GCC より高かったりするので、Clang を一切使わないというのもちょっと悲しい感じもします。どうにかして Clang の入出力を高速化できないでしょうか？

ということで色々高速化を試してみました。その結果、Clang だけでなく GCC でも大幅に入力を高速化できることがわかりました。

実験

標準入力から1000万個の整数を読み込んでその和を出力する時間を計測します。計測対象として以下の5通りのプログラムを用意しました。(各プログラムのソースコードは Appendix にあります)

• naive_cin_cout
  • 普通に iostream の cin と cout を使います。
• faster_cin_cout
  • 最初に cin.tie(nullptr) と ios::sync_with_stdio(false) を行います。それ以外は naive_cin_cout と同じです。
  • libstdc++ を使っている場合はこれでかなり速くなることが知られています。libc++ では残念ながらほとんど効果がありません。
• scanf_printf
  • scanf() と printf() を使って入出力を行います。
• getc_unlocked
  • getchar_unlocked() を使って入力を読みます。getchar_unlocked() は C の標準関数である getchar() とほぼ同じ動作をしますが、ロックを行わないため getchar() よりもさらに高速です。競技プログラミングで入力関数を自作している人は getchar_unlocked() を使っている場合が多いような気がします。
• read_syscall
  • stdio すら使わず、read() システムコールを直接呼びます。バッファリングを自前でやらないといけないためコードは長くなりますが、試した中では最速でした。

それぞれのプログラムについて、以下の2通りの処理系でコンパイルしました。どうしてこの組み合わせなのかというと、AtCoder がこの組み合わせだからです。コンパイルオプションなどの詳細は Appendix の build を参照してください。

• clang 10 + libc++
• gcc 9 + libstdc++

これら 5×2 の組み合わせについてそれぞれ10回ずつ実行時間を計測しました。以下の図がその結果です。

まず、Clang の iostream が飛び抜けて遅い ということがわかります。また、naive_cin_cout / clang と faster_cin_cout / clang の差がほとんどないことから、cin の高速化テクニックも効果がありません。Clang で大量の入力を扱う場合は cin を避けたほうが無難でしょう。

ところで、Clang が遅いと書きましたが、遅いのはコンパイラのせいではなく libc++ のせいです。Clang でコンパイルしたとしても libstdc++ を使っていれば GCC でコンパイルした場合とほぼ同じ速度になります。というわけで AtCoder様におかれましては、Clang + libstdc++ という組み合わせを使わせていただきたく。

一方、GCC (というか libstdc++)の iostream は優秀で、高速化テクニックにより stdio と遜色ない速度まで高速化されます。これだけ速ければ競技プログラミングでも困ることはほぼないでしょう。

それでは残りのプログラムの性能も見ていきましょう。左の３つが遅すぎてグラフが見づらいので、それらを取り除いたグラフを以下に用意しました。

stdio を使った場合、0.9秒前後と、GCC でも Clang でも同じぐらいの速度になりました。Clang で巨大な入力を扱いたいなら stdio を使うのが無難な感じがします。(個人的には scanf() はフォーマットの指定をミスったときのわかりにくいバグが怖いのであんまり使いたくないです。まあ最近のコンパイラなら警告を出してくれるはずなので杞憂だとは思いますが…)

getchar_unlocked() を使ったプログラムは 0.4秒前後と、scanf() を使ったプログラムの半分以下の時間です。Clang でも GCC でも性能はほぼ同じです。AtCoderでたまに getchar_unlocked() を使っている人を見かけるんですが、こんなに速かったんですね。

最後は read システムコール直呼びプログラムです。これが 0.25～0.3秒で最速でした。GCC のナイーブcinと比べると10倍弱、Clang のナイーブcinと比べると20倍以上高速です。速い！

ただ、stdio を使ってないので、バッファリングを自前で実装しないといけない上に int のパースももちろん自前実装なのでなかなか面倒です。正直ここまで高速化しないといけないような場面は競技プログラミングには存在しないと思うので、提出結果ラインキングの実行時間の上位を目指すなどの特殊な用途以外には使い所はなさそうな気がします。

その他

streambuf::pubsetbuf() を使って大きなバッファを指定すれば高速化できるという情報がありましたが、実際にやってみたところ、Clang でも GCC でも効果はありませんでした。strace で実際に実行される read のサイズを見てみると、pubsetbuf() を使わないときと全く同じだったので、cin に対して pubsetbuf() は効かないっぽいです。

また、istreambuf_iterator を使って入力を string として全部読み込み、それを stringstream に変換して >> で読んでいくという方法も考えられます。しかし、試してみると全く速くなりませんでした。ここで istreambuf_iterator の代わりに read() を使うともともとの半分ぐらいの実行時間になりました。しかし、半分でも十分遅いので嬉しくありません。

結論

• Clang の cin は 高速化できない。高速な入出力が必要ならば cin は使えない。
  • よって、このような場合は scanf() を使うか、getchar_unchecked() や read() などで入力関数を自作することになる。
• GCC の cin は cin.tie(nullptr) と ios::sync_with_stdio(false) を使えば十分に速い。
  • ただし、入力関数を自作すれば更に高速化できる。

Appendix

naive_cin_cout.cpp

#include <iostream>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    int64_t sum = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            int x;
            cin >> x;
            sum += x;
        }
    }
    cout << sum << endl;
}

faster_cin_cout.cpp

#include <iostream>
using namespace std;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    int64_t sum = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            int x; cin >> x;
            sum += x;
        }
    }
    cout << sum << '\n';
}

scanf_printf.cpp

#include <cstdio>
#include <cinttypes>
using namespace std;

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    int64_t sum = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            int x;
            scanf("%d", &x);
            sum += x;
        }
    }
    printf("%" PRId64 "\n", sum);
}

getc_unlocked.cpp

#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;

int64_t read_int() {
    int64_t ret = 0, sgn = 1;
    int ch = getchar_unlocked();
    while (isspace(ch)) { ch = getchar_unlocked(); }
    if (ch == '-') { sgn = -1; ch = getchar_unlocked(); }
    for (; isdigit(ch); ch = getchar_unlocked())
        ret = (ret * 10) + (ch - '0');
    ungetc(ch, stdin);
    return sgn * ret;
}

int main() {
    int N = read_int();
    int M = read_int();
    int64_t sum = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            int x = read_int();
            sum += x;
        }
    }
    cout << sum << '\n';
}

read_syscall.cpp

#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <stdexcept>
#include <vector>
#include <unistd.h>
using namespace std;

class Scanner {
    vector<char> buffer;
    ssize_t n_written;
    ssize_t n_read;

public:
    Scanner(): buffer(1024*1024) { do_read(); }

    int64_t read_int() {
        int64_t ret = 0, sgn = 1;
        int ch = current_char();
        while (isspace(ch)) { ch = next_char(); }
        if (ch == '-') { sgn = -1; ch = next_char(); }
        for (; isdigit(ch); ch = next_char())
            ret = (ret * 10) + (ch - '0');
        return sgn * ret;
    }

private:
    void do_read() {
        ssize_t r = read(0, &buffer[0], buffer.size());
        if (r < 0) {
            throw runtime_error(strerror(errno));
        }
        n_written = r;
        n_read = 0;
    }

    inline int next_char() {
        ++n_read;
        if (n_read == n_written) { do_read(); }
        return current_char();
    }

    inline int current_char() {
        return (n_read == n_written) ? EOF : buffer[n_read];
    }
};

int main() {
    Scanner scanner;
    int N = scanner.read_int();
    int M = scanner.read_int();
    int64_t sum = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            sum += scanner.read_int();
        }
    }
    cout << sum << '\n';
}

build

#!/bin/sh
set -eux

method=$1
compiler=$2

case $compiler in
    gcc)
        cxx="g++-9"
        flags=""
        ;;
    clang)
        cxx="clang++-10"
        flags="-stdlib=libc++"
        ;;
esac

$cxx -std=c++17 -O2 -Wall -Wextra ${flags} ${method}.cpp -o ${method}_${compiler}

計測プログラム

#include <iostream>
#include <string>
#include <chrono>
#include <vector>
using namespace std;
using namespace chrono;

int main() {
    vector<string> methods = {
        "naive_cin_cout",
        "faster_cin_cout",
        "scanf_printf",
        "getc_unlocked",
        "read_syscall",
    };
    vector<string> compilers = {
        "clang",
        "gcc",
    };

    // compile all
    for (const auto& method : methods) {
        for (const auto& compiler : compilers) {
            auto cmd = "./build "s + method + " " + compiler;
            system(cmd.c_str());
        }
    }

    // execute and measure performance
    for (const auto& method : methods) {
        for (const auto& compiler : compilers) {
            for (int k = 0; k < 10; ++k) {
                auto cmd = "./"s + method + "_"s + compiler + " < input.txt > /dev/null";
                cerr << cmd << endl;

                auto t1 = high_resolution_clock::now();
                system(cmd.c_str());
                auto t2 = high_resolution_clock::now();

                auto elapsed = duration_cast<microseconds>(t2 - t1).count();
                cout << method << "," << compiler << "," << k << "," << elapsed << endl;
            }
        }
    }
}

input.txt の生成プログラム

#include <iostream>
#include <random>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    random_device rng;

    cout << 10000 << ' ' << 1000 << '\n';
    for (int i = 0; i < 10000; ++i) {
        for (int j = 0; j < 1000; ++j) {
            int x = (int)(rng() % 2'000'000) - 1'000'000;
            if (j != 0) cout << ' ';
            cout << x;
        }
        cout << '\n';
    }
}

環境

WSL1
Ubuntu 18.04.5 LTS
Intel(R) Core(TM) i7-5820K CPU @ 3.30GHz
Memory 32GB