高性能化のための改善が続けられているyesコマンド 68
ストーリー by headless
高速 部門より
高速 部門より
insiderman 曰く、
「y」という文字を出力するだけのUNIXコマンド「yes」は改良が続けられており、性能が強化されているそうだ(POSTDの記事)。
yesコマンドは、単純にループを使って標準出力に「y」を出力するプログラムよりも数十倍速いという。もちろんコードも複雑になっているのだが、なかなかその手法は興味深い。ただ、本当にそのスループットが必要かはちょっと疑問ではあるが……。
元記事はGNU版yesコマンドのスループットが10.2GiB/sというReddit記事に触発され、この速度にRustで挑戦したという話のようだ。日本語訳には何か所か細かい間違いもあるので、英文を読むのが苦にならない方は原文もあわせて参照するといいだろう。
対照的なのが (スコア:5, 興味深い)
GNUのyesコマンドと対照的なのがOpenBSDのyesコマンドのソース [openbsd.org]。
ご覧のとおり見たまんまで、まったく捻りなし。
特徴的なのが、実行開始時にpledgeというシステムコールを発効しているところ。
これを行うことで、それ以降のシステムコールの実行を標準入出力関連のものだけに制限している。
もしyesに脆弱性があっても、それを利用した悪さができにくいようになっている。
改善というのは高性能化だけではない、ってことですな。
Re: (スコア:0)
楽しいね。
この単純なプログラムでさえ、システムコールを制限しようとする姿勢が。
FreeBSDはどうなんだろう、と思ってみたらちょっと長くて [openbsd.org]読んでない。
Re: (スコア:0)
リンクミスった。
FreeBSDのは こっち。 [github.com]
ちなみにやってることはOpenBSD + バッファ使った性能向上かなあ。
斜め読みというか、斜め見した感じ。
ちなみにminix 2.0.4のyesは以下。
yes[n++]= '\n';ってなんでやってるんだろう。
argv[1]って最後に終端はいるよね？
/* yes 1.4 - print 'y' or argv[1] continuously. Author: Kees J. Bot
* 15 Apr 1989
*/
#include
#include
#include
#include
int main(int argc, char **argv)
{
char *yes;
static char y
Re:対照的なのが (スコア:2)
|yes[n++]= '\n';ってなんでやってるんだろう。
|argv[1]って最後に終端はいるよね？
その終端がヌルターミネータだから改行を追加しているのでは。
ヌルターミネータを上書きして大丈夫なのかと一瞬思ったが、writeで長さ指定してた。
Re:対照的なのが (スコア:2)
これがないと出力が改行なし ("yyyyy...") になっちゃいますね。
Re: (スコア:0)
なるほど。
意味がわかったでござる。
tmiura氏のNULL Terminatorの話も、説明されてわかった。
\0 を \nで上書きしていると。
writeだから\0はいらないわけね。
Re: (スコア:0)
plegdeは良いと思うけれど、同じ意味のfor(;;) puts()が繰り返されるのが嫌だな。
私はV7の三項演算子使ったやつの方が好き。
Re:対照的なのが (スコア:2)
Re: (スコア:0)
最適化されない気がする。引数が処理中に書き換わる可能性がゼロじゃないと。
Re: (スコア:0)
argc>1の評価はmain()の呼出毎に不変だから現代のコンパイラなら最適化されるよ。
main(argc, argv)
char **argv;
{
char *p = argc>1? argv[1]: "y";
for (;;)
printf("%s\n", p);
}
みたいな感じに解釈されると思う。
Re:対照的なのが (スコア:1)
上のコードをgcc -O3でコンパイルするとこんな風に最適化される
main(argc, argv)
char **argv;
{
if (argc>1) {
for (;;)
puts(argv[1]);
} else {
for (;;) {
puts("y");
puts("y");
}
}
}
printf自体が無駄だと判断してputsに置き換えてるみたい
Re: (スコア:0)
OpenBSD って if や for の後が単文なら {} つけない流儀?
Re:対照的なのが (スコア:2)
Kernel source file style guide (KNF) [openbsd.org]
No braces are used for control statements with zero or only a single statement unless that statement is more than a single line, in which case they are permitted.
OpenBSDカーネルのコーディングスタイルではそのように決まっているので、ユーザランドもそれに倣っていると思われます。
ありがたやありがたや (スコア:1)
一番手軽なので/dev/nullにリダイレクトしてCPU負荷張り付きとか高温時の制限機能のデバッグとかで使わせてもらってます。
なるほど、どうりで高効率で食い潰せるわけだ。
Re: (スコア:0)
り、りょうほーですかあああ〜と聞かれた時にも使えるしね
10.2GiB/s (スコア:0)
ギガyes毎秒のほうが良くないかな？
Re:10.2GiB/s (スコア:2)
おそらく半分になって、イマイチな気分になるから、よろしくないかもしらないみたいな。
Re: (スコア:0)
yes コマンドの引数で繰り返す文字（や文字列）を指定できる。
長い文字列ならば、当然遅くなるので（線形ではないだろうが）、Bytesでいい気もする。
結構スリリング。
#yes no | rm -ir *
yes! (スコア:0)
yesコマンドなんて最初は「何だこれ？」と思ったけど
最近はPC起動するたびに使ってる気がする
何かと手間が省けるんだよね
地味ｲーーにものぐさができる
Re:yes! (スコア:1)
横棒グラフを端末でちゃちゃっと出したかったんだけど、perlを持ち出すほどじゃないよなってとき
yes '*' | head -n 10 | tr -d '\n'
とか
yes '*' | head -n 10 | paste -s -d ''
でなんとかやりくりした思い出…
yes -d '' -n 10 '*'
とかでぱぱっと ********** が出てくれないかなー。だめかな？UNIX原理に反するもんね
Re:yes! (スコア:1)
俺なら/dev/zeroからNUL読みだしてきて*に置換するかなー。
$ dd if=/dev/zero bs=10 count=1 status=none | tr '\0' '*'
Re:yes! (スコア:1)
なるほど、個数が有限だと確かにこっちのがエレガントですね。
printfは%10sじゃなくて
$ printf '%*s' 10 ' '
でもいけるはずです。昔C言語の本で読んだ。
yes!高須クリニック! (スコア:0)
つい
Re:yes!高須クリニック! (スコア:1)
ゲデヒトニス「レッスン２、質問にハイかYesで答えよ」
Re:yes!高須クリニック! (スコア:1)
yesの前と後ろにはsirを忘れずに。
Re: (スコア:0)
「もしかしてオラオラですかーッ!? 」 [youtube.com]
Re: (スコア:0)
初期のUNIXのシンプルさ、柔軟さを今に伝える貴重なプログラム。
...なのだが、GNU 版のソースとかを見るとロブ・パイクがUNIXは腐臭を放っていると発言したのも最もだと思わせる。
Re: (スコア:0)
でも例えばprintfを改良してどうにかなる問題じゃないからな。ループで問答する時のバッファをどうするかって話なんだから、まさにアルゴリズムの優劣が結果にダイレクトに反映されてるわけだ。
Re:yes! (スコア:2)
アルゴリズムとは言い難い感じ。
一行ずつチマチマ投げるよりも、ページ境界に合うのを期待した大きい領域に何行も詰め込んで投げる方が早いよねっていう。
Re: (スコア:0)
> 一行ずつチマチマ投げるよりも、ページ境界に合うのを期待した大きい領域に何行も詰め込んで投げる方が早いよねっていう。
なんで後者の方が早いんですか？
Re: (スコア:0)
境界またがったら2ページ分の操作が要るとか
というか、パディング分の領域が無駄になるとか
再構成の時間がかかるとか
いろいろ
Re:yes! (スコア:3, 参考になる)
一番の理由はシステムコールのオーバヘッドですよ
一行ずつチマチマ投げるとその都度システムコールが発行されます
これが結構重たい処理になります．システムコールが発行されると，その都度，ユーザ空間とカーネル空間の切り替え，
CPUのレジスタの保存と復帰，メモリキャッシュのフラッシュが必要になります
またCPUのパイプラインもストールします．
ですからこの手の高速化では
システムコールの発行回数を最低限に抑える工夫が必須となります
その工夫の一つが，大きなバッファを用意して，複数回のシステムコールを，一つにまとめる方法です
Re:yes! (スコア:2)
printf(3)はシステムコールじゃないってのは余計な突込み？
stdioライブラリ中のバッファ処理より高速なんだろう
♯改行くるとwrite(2)してるとか
ページサイズかける文字数分の境界整列したバッファを用意しといて
埋めた後グルグル回すとか
#writeに渡した後の中身って保全されてると期待しちゃいかんのじゃなかったかな
Re: (スコア:0)
まさにアルゴリズムだと思うのだが…
単純というだけでアルゴリズムに変わりはないでしょ。
Re:yes! (スコア:1)
自分の理解ではこういうのはI/Oの効率化で、アルゴリズムというよりストラテジ
アルゴリズムはもっとロジック寄りの処理を指すと思ってる
うじゃうじゃ
Re: (スコア:0)
ストラテジーよりはタクティクスかな…
Re: (スコア:0)
「アルゴリズム上の工夫とは言いがたい」と言いたいのでは
Re: (スコア:0)
unixのというよりオープンソースの話だろう。いやプロプラでも見えないだけで実はくだらないところで最適化を頑張っているのかもしれないが。
Re: (スコア:0)
> We didn't beat GNU's yes, and there probably is no way. Even with the function overheads and additional bounds checks of GNU's yes, the limit isn't the processor, it's how fast memory is. With DDR3-1600, it should be 11.97 GiB/s (12.8 GB/s), where is the missing 1.5? Can we get it back with assembly?
yyyyyyyを毎回メインメモリから読み出していると考えているようだが、3次キャッシュには乗ってんじゃねーの？
L3のバンド幅は俺は知らんが、とりあえずこいつの認識は間違ってるかもしれんぞ
Re: (スコア:0)
つか、yesのwriteでユーザー空間からyyyyyyを読んでシステム空間のパイプのバッファに書く、pvはパイプのバッファからyyyyyを読む、で都合3回メモリアクセスするよな
Re: (スコア:0)
in/outがハッキリしてるなら極端なパフォーマンスの問題がなければどう実装してもいいと思うけどな。
Re: (スコア:0)
「最もだ」
Re: (スコア:0)
ただ、本当にそのスループットが必要かはちょっと疑問 (スコア:0)
>ただ、本当にそのスループットが必要かはちょっと疑問
いやいや、パイプで自動処理とかする際にも使えるし、
ベンチマークとしてもつかえるんですよ
部屋中がホットケーキミックスの匂いが充満してたので
おっ！今日はホットケーキか！とおもったけど違ってた
たいしたことしてなくないか（クソリプ） (スコア:0)
POSTDの記事を読んだが、やってることはバッファリングとmutexの除去くらいで、こんなん基本中の基本じゃないかね。
こんな内容で感心されるほど、（伝統的な意味での）システムプログラミングをやってる人が減ったってことか。
#Goが「システムプログラミング言語」を名乗ってることにイラっとしてる人。おめーはPHPやVB6の立ち位置の言語だろ。
Re: (スコア:0)
デバイスドライバなど低レイヤの実装を業務としている開発者なら、そう(であるべき)かもしれない。
多くの分野で求められている実装は、高能率より短納期、という状況が、背景にあるような気がする。
本当にそのスループットが必要かはぼくも疑問 (スコア:0)
そのスループット向上によって節約される時間より、 yes が含まれるパッケージを最初のインストールのためにダウンロードしたり、アップデートの時にダウンロードするのにかかる時間の方が大きいのではないでしょうか。
( 特に長期で考えると CPU やメモリも性能の向上より常にネットワークのバンド幅の向上の方が遅いし、Docker のようなコンテナにもベースシステムとして yes が含まれる事も考えるとサイズが 1byte でも小さいほうがよいのではないでしょうか )
Re:本当にそのスループットが必要かはぼくも疑問 (スコア:2)
一方で、どうでもいいことに [y/N] を聞いてくる何かがいると yes のスループットによる節約効果がありますね。
Re:本当にそのスループットが必要かはぼくも疑問 (スコア:2)
Docker 知ってるけど Dockerfile 書かんし apt upgrade もしないというのは一種の自慢なのでは?
Re: (スコア:0)
「そこにコードがあるから」という月並みな常套句はおいといても。
計算機が使えるリソースが、UNIX系OSの登場時とは比べ物にならないこと、
その一方で、計算機のこなさねばならない演算量も膨大になっていること、
それに比して、アップデートに費やすリソースは、さほど過大でもなさそうなこと。
といった前提条件で考えると、高速処理のために比較的大きなリソースを有効活用するアプローチが、一般論として有効と思える。
「大きなリソースを活かせるよう、OSの設計を根本から見直すべきだ」という議論は当然あるが。