Blog Dice

fastcat - A Faster `cat` Implementation Using Splice

Matthias Endler

fastcat — spliceを使った高速なcat実装

有名なUnixコマンドの内部実装について記事を書いてほしいと、たくさんの人に頼まれました。いや、実際には誰にも頼まれていませんが、導入としてはなかなか良いですよね。前回のyesやlsについての記事は読んでいただけたと思いますが、あれは傑作です。

さて、今回はcatについてお話しします。catはファイルを連結するためのコマンドですが、より一般的にはファイルの中身を画面に出力するために（乱用）されています。

# Concatenate files, the intended purpose
cat input1.txt input2.txt input3.txt > output.txt

# Print file to screen, the most common use-case
cat myfile

catを実装する

まずは、Rubyで書いた素朴なcatです。

#!/usr/bin/env ruby

def cat(args)
  args.each do |arg|
    IO.foreach(arg) do |line|
      puts line
    end
  end
end

cat(ARGV)

このプログラムは各ファイルを順に読み込み、1行ずつ内容を出力します。簡単ですね！しかし、このツールはどれくらい速いのでしょうか。

ベンチマーク用に、2GBのランダムなファイルをさっと用意しました。

素晴らしいpv（Pipe Viewer）ツールを使って、素朴な実装とシステム標準のものの速度を比較してみましょう。すべてのテストはウォームキャッシュ（ファイルがメモリ上にある状態）で5回実行した平均です。

# Ruby 2.5.1
> ./rubycat myfile | pv -r > /dev/null
[196MiB/s]

悪くない、といったところでしょうか。では、システム標準のcatと比べるとどうでしょう。

cat myfile | pv -r > /dev/null
[1.90GiB/s]

おや、GNU catは私たちの小さなRuby製catの10倍も速いようです。💎🐈🐌

Ruby製catを少し速くしてみる

素朴なRubyコードは少し工夫ができます。どうやら行単位のバッファリングが最終的にパフォーマンスを落としているようです1。

#!/usr/bin/env ruby

def cat(args)
  args.each do |arg|
    IO.copy_stream(arg, STDOUT)
  end
end

cat(ARGV)
rubycat myfile | pv -r > /dev/null
[1.81GiB/s]

おお…それほど頑張ったわけでもないのに、1971年から最適化が続けられているツールに迫る速さになりました。🎉

ただ、喜ぶのはまだ早いです。さらに速くできるかどうか見てみましょう。

Splice

そもそもcatについて書こうと思ったきっかけは、Hacker Newsでのユーザーwahernさんのこちらのコメントでした。

GNU yesもGNU catもsplice(2)を使っていないのは驚きだ。

このspliceというものを使えば、ファイルの出力はさらに速くなるのだろうか。——興味をそそられました。

Spliceは2006年に初めてLinuxカーネルに導入されました。Linus Torvalds自身による分かりやすい要約もありますが、ここではmanページの説明を引用します。

splice()は、カーネルアドレス空間とユーザアドレス空間の間でコピーを行うことなく、2つのファイルディスクリプタ間でデータを移動します。最大lenバイトのデータをファイルディスクリプタfd_inからファイルディスクリプタfd_outへ転送しますが、どちらか一方はパイプを指している必要があります。

さらに深く掘り下げたい方のために、Linuxカーネルの該当するソースコードへのリンクを貼っておきますが、今は細かい詳細まで知る必要はありません。代わりに、C言語でのヘッダ定義を見てみましょう。

#include <fcntl.h>

ssize_t splice (int fd_in, loff_t *off_in, int fd_out,
                loff_t *off_out, size_t len,
                unsigned int flags);

さらに分かりやすくすると、srcファイル全体をdstにコピーする場合は次のように書けます。

const ssize_t r = splice (src, NULL, dst, NULL, size, 0);

面白いのは、これらすべてがLinuxカーネル内部で完結する点です。つまり、ユーザ空間（私たちのプログラムが動いている場所）には1バイトもコピーされません。理想的には、spliceはページの再マッピングによって動作し、実際にはデータをコピーしないため、I/O性能が向上する可能性があります（参考）。

Noun ProjectのAleksandr Vector氏によるファイルアイコン。Noun Projectのuseiconic.comによるターミナルアイコン。
出典： Noun ProjectのAleksandr Vector氏によるファイルアイコン。Noun Projectのuseiconic.comによるターミナルアイコン。

Rustからspliceを使う

白状すると、私はCプログラマではなく、より安全なインターフェースを提供してくれるRustの方が好みです。同じものをRustで書くと次のようになります。

#[cfg(any(target_os = "linux", target_os = "android"))]
pub fn splice(
    fd_in: RawFd,
    off_in: Option<&mut libc::loff_t>,
    fd_out: RawFd,
    off_out: Option<&mut libc::loff_t>,
    len: usize,
    flags: SpliceFFlags,
) -> Result<usize>

なお、このLinuxバインディングを自分で実装したわけではありません。nixという、*nix APIへのRustフレンドリーなバインディングを提供するライブラリを使いました。

ただし、一つ注意点があります。spliceではどちらか一方のファイルディスクリプタがパイプである必要があるため、ファイルを直接標準出力にコピーすることはできません。回避策として、リーダーとライター（rdとwr）からなるパイプを作成します。ファイルをライター側にパイプで流し込み、そこから読み出して標準出力へ送り出します。

パフォーマンス向上のために、16384バイト（214）という比較的大きなバッファを使っているのが分かるかと思います。

extern crate nix;

use std::env;
use std::fs::File;
use std::io;
use std::os::unix::io::AsRawFd;

use nix::fcntl::{splice, SpliceFFlags};
use nix::unistd::pipe;

const BUF_SIZE: usize = 16384;

fn main() {
    for path in env::args().skip(1) {
        let input = File::open(&path).expect(&format!("fcat: {}: No such file or directory", path));
        let (rd, wr) = pipe().unwrap();
        let stdout = io::stdout();
        let _handle = stdout.lock();

        loop {
            let res = splice(
                input.as_raw_fd(),
                None,
                wr,
                None,
                BUF_SIZE,
                SpliceFFlags::empty(),
            ).unwrap();

            if res == 0 {
                // We read 0 bytes from the input,
                // which means we're done copying.
                break;
            }

            let _res = splice(
                rd,
                None,
                stdout.as_raw_fd(),
                None,
                BUF_SIZE,
                SpliceFFlags::empty(),
            ).unwrap();
        }
    }
}

では、速度はどうでしょう。

fcat myfile | pv -r > /dev/null
[5.90GiB/s]

なんと。システム標準のcatより3倍以上も速いのです。

OSの対応状況

  • LinuxとAndroidは完全にサポートされています。
  • OpenBSDにもsospliceというsplice実装があるようです。ただし、こちらは試していません。
  • macOSでspliceに最も近いのは、その上位互換ともいえるsendfileで、カーネル内でファイルをソケットに送信できます。残念ながら、ファイルからファイルへの送信には対応していません2。copyfileという似たインターフェースを持つものもありますが、こちらは残念ながらゼロコピーではありません。（当初はそうだと思っていましたが、間違っていました。）
  • Windowsはファイル間のゼロコピー転送を提供していません（TransmitFile APIを使ったファイルからソケットへの転送のみ可能です）。

とはいえ、プロダクションレベルの実装であれば、対応しているシステムではspliceを有効にしつつ、フォールバックとして汎用的な実装を用意するという形にできるでしょう。

なるほど、でも一体何のために？

正直、分かりません。おそらく必要ないでしょう。ボトルネックは別のところにあるはずですから。とはいえ、多くの人が次のようにcatを使って別のプロセスにデータをパイプで渡しています。

# Count all lines in C files
cat *.c | wc -l

あるいは

cat kittens.txt | grep "dog"

もしこのようなケースでcatがボトルネックになっていると感じたら、fcatを試してみてください（ただし、まずはcat自体を使わない方法を検討するのが先ですが）。

もう少し手を加えれば、fcatはnetcatのように、あるネットワークカードから別のネットワークカードへパケットを直接転送する用途にも使えるでしょう。

学んだこと

  • ベアメタルに近づけば近づくほど、苦労して築いた抽象化は崩れ、再び低水準なシステムプログラミングに戻ってきます。
  • 速いcatがある一方で、遅いcatにも使い道があります。古いコンピュータのためです。そのためにあるのが――ご想像のとおり――slowcatです。

とはいえ、なぜGNU catがLinuxでspliceを使っていないのかは、今でもよく分かりません。🤔 fcatのソースコードはGithubで公開しています。コントリビューションを歓迎します！

脚注

1. 読者のFreekyさん、よりイディオマティックなコードにしてくださりありがとうございます。↩
2. 読者のmasklinnさん、ヒントをありがとうございます。↩

原文は Matthias Endler により に公開されました。

この記事は「muse-spark-1.2-contributor」を使用して翻訳されました。