「ケーキを食べながら、それも早く味わう」：高速化されたバッファ付き出力の仕組み

1. バッファモードと従来の課題

基本動作の違い

• フルバッファ (Full Buffer):
  • バッファが満杯になるか、明示的なフラッシュが発生するまでデータを保持。
  • ファイルやパイプへの書き込みで一般的。
• ラインバッファ (Line Buffer):
  • ターミナル出力時に自動選択されることが多い。
  • 改行 (

    \n

    ) が出現すると即座に画面に表示（フラッシュ）。
  • 対話型アプリケーションでは必須だが、大量の出力時にはボトルネックになる。

現実的なジレンマ

• 従来の解決策は「ターミナルをリダイレクト」することだったが、使い勝手が悪い。
• **「ケーキを食べながら、それも早く味わう」**状況：
  • ユーザーにはリアルタイムで表示させつつ（ケーキを食べる）。
  • 内部処理は高速化し、遅延を回避したい（早く味わう）。

2.

unzip

コマンドのボトルネック事例

問題の実例

• Info-ZIP の

  unzip

  ：

  $ unzip example.zip
  Archive:  example.zip
    inflating: example.bmp
    inflating: example.svg
    inflating: example.txt
  

  • ファイル名を逐次表示する動作が抽出時間を支配する。
  • 多数の小ファイルを扱う場合、ターミナル出力が最大の原因になる。

回避策の限界

• 通常は

  -q

  （静粛モード）オプションで再実行することで回避される。
• しかし、これは UI を変更する必要があるため望ましくない。

• tugz unzip

  は UI を保ちつつ、同様の問題を解決した。

3. ラインバッファの実装と非効率さ

C プログラムでの動作確認

以下のプログラムは 3 行を出力するが、実装上の違いが見て取れる。

#include <stdio.h>

int main()
{
    puts("a\nb");
    puts("c");
}

glibc（ラインバッファ厳密実装）

strace

$ strace -o log -e write ./a.out
write(1, "a\n", 2)                      = 2
write(1, "b\n", 2)                      = 2
write(1, "c\n", 2)                      = 2

その他の実装（洗練された動作）

一部の環境では、行全体を一度に書き込む。

write(1, "a\nb\n", 4)                   = 4
write(1, "c\n", 2)                      = 2

CPython の挙動

CPython も同様に「改行ありならフラッシュ」というルールに従い、部分的な書き込みが発生する。

import sys

sys.stdout.write("a\nb\n")
sys.stdout.write("c\n")

非効率な実装の構造（C）

従来のラインバッファは、「バッファに改行が含まれていればフラッシュ」というロジックを持つ。

enum {
    BUF_ERR  = 1 << 0,
    BUF_LINE = 1 << 1,
};

typedef struct {
    uint8_t  *buf;
    ptrdiff_t cap;
    ptrdiff_t len;
    int       fd;
    int       flags;
} Buf;

bool os_write(int fd, void *, ptrdiff_t);

void flush(Buf *b)
{
    if (!(b->flags & BUF_ERR) && b->len) {
        if (!os_write(b->fd, b->buf, b->len)) {
            b->flags |= BUF_ERR;
        }
        b->len = 0;
    }
}

bool has_newline(Buf *b)
{
    int r = 0;
    for (ptrdiff_t i = 0; i < b->len; i++) {
        r |= b->buf[i] == '\n';
    }
    return r;
}

void append(Buf *b, uint8_t *src, ptrdiff_t len)
{
    uint8_t *end = src + len;

    while (!(b->flags & BUF_ERR) && src < end) {
        ptrdiff_t left   = end - src;
        ptrdiff_t avail  = b->cap - b->len;
        ptrdiff_t amount = avail < left ? avail : left;

        memcpy(b->buf + b->len, src, amount);
        b->len += amount;
        src += amount;

        if (amount < left) {
            flush(b);  // バッファに空き容量を作るため
        }
    }

    // ラインバッファモードの場合、改行が含まれていればテストしてフラッシュ
    if ((b->flags & BUF_LINE) && has_newline(b)) {
        flush(b);
    }
}

問題点

• 多数の行を連続して追加しても、1 回の書き込みで済むはずのデータが、改行ごとに分割されて書き込まれてしまう。
• これがシステムコールの増加となり、パフォーマンス低下を招く。

4. 解決策：期限に基づくフラッシュ (Deadline Flush)

目標

• ターミナル出力でも無限に待たせる必要はない。
• しかし、「改行ごとに必ず書き込む」わけでもない。
• ネーグルのアルゴリズムのように、バッファがアイドル状態になったら自動的に送信する仕組みを採用。

デッドライン機能の実装

バッファに期限 (

deadline

typedef struct {
    int64_t   deadline;
    // ...
} Buf;

int64_t os_monotonic_clock();

void deadline_flush(Buf *b)
{
    if ((b->flags & BUF_LINE) && b->len) {
        int64_t now = os_monotonic_clock();
        if (b->deadline && now > b->deadline) {
            flush(b);
            b->deadline = 0;
        } else {
            b->deadline = now + DEADLINE; // 例：DEADLINE = 100ms
        }
    }
}

• DEADLINE

  は人間が知覚できない程度（例：100 ms）に設定する。
• スレッドを呼ぶのではなく、短い処理ブロックの間に期限を更新することで実装可能。

5. アプリケーション側の書き換え事例 (

tugz unzip

)

新しいアプローチ

処理ループ内で

deadline_flush

for (/* filename in filenames */) {
    Str pre = S("  inflating: ");
    Str suf = S("\n");
    append(&stdout, pre.data, pre.len);
    append(&stdout, filename.data, filename.len);
    append(&stdout, suf.data, suf.len);

    while (/* not done inflating */) {
        // 1. ブロックを膨張させる
        // 2. ブロックを書き込む
        deadline_flush(&stdout);
    }
}

利点

• 人間には感知できないレベルでの出力遅延。
• プログラムがより速く動作する。
• 古い C

  stdio

  の制限に依存しない（ライブラリ側で制御可能）。
• ユーザーインターフェースはそのまま保ちつつ、ボトルネックを解消した。