Blog Dice

fastcat - A Faster `cat` Implementation Using Splice

Matthias Endler

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

原文は Matthias Endler により に公開されました。 このブログを購読する

有名な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の実装

まずは単純なcatをRubyで書いてみます。

#!/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つのファイルディスクリプタ間でデータを移動する。ファイルディスクリプタfd_inからファイルディスクリプタfd_outへ最大lenバイトのデータを転送し、その際、どちらか一方のファイルディスクリプタはパイプを指していなければならない。

もっと深く掘り下げたい方のために、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 APIへのRustフレンドリーなバインディングを提供するnixというライブラリを使いました。

ただし、1つ注意点があります。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氏に感謝します。↩

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

コメント