Unixコマンド”yes”についてのちょっとした話

知っているUnixのコマンドで一番シンプルなものは何ですか?
例えばechoという、stdoutに文字列を出力しtrueを返す – すなわち常に0の終了コードで終了するシンプルなコマンドがあります。

シンプルな、と言えばyesもそうでしょう。引数なしで実行すると、改行されたyが無限に出力され続けます。

y
y
y
y
(...you get the idea)

最初は無意味に見えたものが、最終的に有益になることもあります。

yes | sh boring_installation.sh

続行するために”y”を入力し、Enterキーを押す必要があるようなプログラムをインストールしたことはありますか? そんな時、yesは救いの神です。あなたに代わってその作業を丹念にこなしてくれるので、その間にあなたは『Pootie Tang』を観て楽しめますね。

yesを書く

以下は、BASICでベーシックに書いた場合の例です。

10 PRINT "y"
20 GOTO 10

次はPythonで同じことをやるとこうなります。

while True:
    print("y")

シンプルでしょう。え、ちょっと遅いですって?
ご名答。このプログラムはかなり遅いですね。

python yes.py | pv -r > /dev/null
[4.17MiB/s]

私のMacにビルトインされていたものと比較してみましょう。

yes | pv -r > /dev/null
[34.2MiB/s]

そんなわけで、Rustを使って速いバージョンを書いてみようと思いました。以下は最初の試作です。

use std::env;

fn main() {
  let expletive = env::args().nth(1).unwrap_or("y".into());
  loop {
    println!("{}", expletive);
  }
}

説明です。

  • ループで印刷したい文字列が最初のコマンドラインパラメータであり、expletiveという名前です。yesのmanページで、この言葉を知りました。
  • unwrap_orを使ってパラメータからexpletiveを取得します。パラメータが設定されていない場合、デフォルトで”y”が使用されます。
  • デフォルトのパラメータは、into()を使用して、文字列スライス(&str)からヒープ(String)上のowned文字列に変換されます。

では、テストしてみましょう。

cargo run --release | pv -r > /dev/null
   Compiling yes v0.1.0
    Finished release [optimized] target(s) in 1.0 secs
     Running `target/release/yes`
[2.35MiB/s] 

いや、全然よくなってないですね。それどころか、Pythonのバージョンよりも遅くなりました。そんなわけで、私はC実装のソースコードを調べてみました。

こちらが、1979年1月10日にKen Thompsonによって書かれ、Unixバージョン7でリリースされたプログラムの最初のバージョンです。

main(argc, argv)
char **argv;
{
  for (;;)
    printf("%s\n", argc>1? argv[1]: "y");
}

魔法のようなものは何もありません。

Githubに反映されているGNU coreutilsの128行のバージョンと比較してみてください。最初のバージョンから25年が経ちますが、いまだ活発に開発が続けられています!。最新の変更は1年前で、これはかなりの速さです。

# brew install coreutils
gyes | pv -r > /dev/null 
[854MiB/s]

重要なのは、最後の部分です。

/* Repeatedly output the buffer until there is a write error; then fail.  */
while (full_write (STDOUT_FILENO, buf, bufused) == bufused)
  continue;

なるほど!バッファを使用して書き込み操作を高速化していたというわけですね。バッファサイズはBUFSIZという名前の定数で定義され、I/Oを効率的にするために各システムで選択されます(ここを参照)。私のシステムでは、1024バイトと定義されていましたが、実際には8192バイトの方がパフォーマンスはよかったです。

これを受けて、Rustのプログラムを拡張しました。

use std::io::{self, Write};

const BUFSIZE: usize = 8192;

fn main() {
  let expletive = env::args().nth(1).unwrap_or("y".into());
  let mut writer = BufWriter::with_capacity(BUFSIZE, io::stdout());
  loop {
    writeln!(writer, "{}", expletive).unwrap();
  }
}

重要なのは、メモリのアラインメントを確実にするために、バッファサイズが4の倍数であることです。

実行の結果は51.3MiB/sでした。私のシステムにビルトインされていたバージョンよりも速いですが、10.2GiB/sという速度が議論されているこのRedditの記事の結果に比べると、まだ足元にも及びません。

アップデート

しかし、Rustコミュニティは私を裏切りませんでした。
この投稿がRustのサブレディットに掲載されてすぐに、ユーザのnwydoが、同じトピックに関する以前のディスカッションを教えてくれたのです。こちらが最適化されたそのコードで、私のマシンで3GB/sを突破しました。

use std::env;
use std::io::{self, Write};
use std::process;
use std::borrow::Cow;

use std::ffi::OsString;
pub const BUFFER_CAPACITY: usize = 64 * 1024;

pub fn to_bytes(os_str: OsString) -> Vec<u8> {
  use std::os::unix::ffi::OsStringExt;
  os_str.into_vec()
}

fn fill_up_buffer<'a>(buffer: &'a mut [u8], output: &'a [u8]) -> &'a [u8] {
  if output.len() > buffer.len() / 2 {
    return output;
  }

  let mut buffer_size = output.len();
  buffer[..buffer_size].clone_from_slice(output);

  while buffer_size < buffer.len() / 2 {
    let (left, right) = buffer.split_at_mut(buffer_size);
    right[..buffer_size].clone_from_slice(left);
    buffer_size *= 2;
  }

  &buffer[..buffer_size]
}

fn write(output: &[u8]) {
  let stdout = io::stdout();
  let mut locked = stdout.lock();
  let mut buffer = [0u8; BUFFER_CAPACITY];

  let filled = fill_up_buffer(&mut buffer, output);
  while locked.write_all(filled).is_ok() {}
}

fn main() {
  write(&env::args_os().nth(1).map(to_bytes).map_or(
    Cow::Borrowed(
      &b"y\n"[..],
    ),
    |mut arg| {
      arg.push(b'\n');
      Cow::Owned(arg)
    },
  ));
  process::exit(1);
}

もはや、完全に別物と言っていいでしょう。

  • いっぱいになった文字列バッファを準備します。このバッファは各ループで再利用されます。
  • Stdoutはロックによって保護されます。そのため、取得とリリースを定期的に行うのではなく、常にそれを保持します。
  • 不要な割り当てを避けるために、プラットフォーム固有のstd::ffi::OsStringstd::borrow::Cowを使用します。

私が貢献できる唯一のものは、不要なmutを取り除くことだけでした。

学んだこと

些細なプログラムyesが、結果的には全く些細とは言えないものになりました。パフォーマンスの向上には、出力バッファとメモリ配列を使用しています。Unixのツールは楽しいですね。それとコンピュータを高速化させるこうした効果的なテクニックは、本当に頼りになります。