C文字列：50年続いた過ち

 (longtran2904.substack.com)
1 ポイント 投稿者 GN⁺ 4 시간 전 | 1件のコメント | WhatsAppで共有
  • CのNUL終端文字列は長さ情報を保持しないため、反復的な探索や境界エラーを生む。現代では、ポインタとサイズを一緒に保存する長さベースの文字列のほうが、基本設計としてより適している
  • 明示的な長さがないと、strlen呼び出しとバイト走査が繰り返されるうえ、snprintf、sizeof、strlenごとに終端バイトを含むかどうかが異なり、コードの作成とレビューが難しくなる
  • 長さベースの文字列は、空文字列をsize == 0として一貫して扱い、NULバイトを含む任意のバイナリデータにも探索・分割・スライス操作をそのまま適用できる
  • 元のメモリの一部を指す部分文字列を返せるため、切り出し・検索・トークン化や、CSV・Markdown・JSON・Cのパースで、中間的な割り当てとコピーを避けられる
  • センチネルは不変条件の維持や一部のトークン探索では今も有用で、既存のC・OS APIとの変換も必要だが、多くのコードでは長さベースの文字列にAPI境界での不変性を組み合わせるほうが単純で柔軟である

NUL終端の代わりにポインタと長さを保存する

  • C文字列は文字ストリームを指すポインタと末尾のNULバイトで境界を表す
    • 1970年代のメモリ・性能制約の下では合理的だったかもしれないが、現代ではこの方式を維持する理由はほとんどない
  • 現代の言語や主要フレームワークが採用している代替案は、データポインタとサイズを一緒に保存する構造体である
struct String
{
    u8* data;
    u64 size;
};
  • 文字列リテラルはsizeof(s) - 1で長さを計算してStringにでき、比較・出力のような操作は保存されたサイズを直接利用する
  • 配列もポインタに変換されると長さなどの情報を失い、文字列と似た安全性・使い勝手の問題を抱える

長さ情報を捨てることで生じるコスト

  • 長さを保存しないと、利用側のコードが毎回strlenを繰り返し呼ぶか、バイトを1つずつ走査しなければならず、不要な作業と複雑さが増える
  • ランタイムで長さを検査して強制するのも遅く面倒になり、デバッガや解析ツールはchar*、char[N]、char*[N]を一貫して扱いにくい
  • Cのメモリ問題やオーバーフローバグのかなりの部分はこの設計に由来するという見方がある一方、センチネルだけで十分だという反論もある
  • 長さが分からない文字列は、配列のランダムアクセスよりも連結リストのような逐次アクセスパターンに近くなる
  • NUL終端方式を擁護する側は、逐次処理がマルチパスよりもシングルパスアルゴリズムを促し、効率的だと見る
    • 初心者を含む多くのプログラマーは、文字列長を安価に取得できると仮定してコードを書く
    • 一般的な文字列ルーチンも、長さが与えられる形のほうが自然に書ける。また、繰り返しのstrlen呼び出しによって、実際のコードでは同じ文字列を何度も走査することになる
    • パス数が少なければ常に速いという前提は、現代CPUの動作方式を誤解した結果である

snprintf、sizeof、strlenが意味する異なる長さ

  • snprintfの2つの整数は同じ「長さ」のように見えるが、NULを含むかどうかの規則が互いに逆である
int snprintf(char *str, size_t size, const char *format, ...);
  • 入力のsizeは出力バッファのNUL終端用領域まで含める必要があるが、返り値はNULバイトを除いて生成されるはずだった文字列長を表す
  • 文字列関連の関数やAPIを使うたびに、次の条件を個別に確認しなければならない
    • 関数がNULバイトを直接書き込むか
    • 割り当てサイズにNULバイト分の領域を追加する必要があるか
    • サイズ引数と返り値がNULバイトを含むか
  • sizeof("some string")はNULバイトを含むが、strlen("some string")は含まない
  • リテラルベースのコードをランタイムのポインタベースのコードに変える際に同じ- 1を維持すると、長さが1つ短くなるバグが生じる
#define TEST_STRING "some string"
size_t size = sizeof(TEST_STRING) - 1;

const char *str = "some string";
size_t size = strlen(str) - 1;

中間のNULバイトを繰り返し上書きする作業

  • 複数のsnprintfの返り値をオフセットに足して文字列を連結すると、各呼び出しが書き込んだNUL終端バイトを次の呼び出しが上書きする
int offset = 0;
offset += snprintf(ptr + offset, size - offset, "%d", my_int);
offset += snprintf(ptr + offset, size - offset, "%s", my_str);
offset += snprintf(ptr + offset, size - offset, "%f", my_flt);
  • 中間の終端バイトを書き込む作業は不要だが、性能への影響自体は大きくない可能性がある
  • より大きな問題は、この動作が直感的ではなく、snprintfはNUL終端しないという誤解を生む点である
  • その結果、最後にptr[offset] = 0;を追加するコードが生まれるが、この作業も不要であり、同じ誤解をさらに強める

空文字列とヌル文字列の二重状態

  • NUL終端モデルでは、空文字列とヌルポインタが互いに異なる無効な状態のように扱われ、文字列処理コードは両方を検査しなければならない
  • C#の文字列と配列も参照型なので、ヌル状態でLengthを読むか走査すると例外が発生し、別途処理が必要になる
  • よくある対応は、ヌルの代わりに常に空文字列や空配列を渡し、返すことだ
    • String.IsNullOrEmpty、「Don’t Return Null」、「Don’t Pass Null」といった規則も、この区別を扱うための方法である
  • ポインタと長さを持つ構造体では、空文字列かどうかをsize == 0だけで判断できる
    • ポインタはヌルの場合も、有効なアドレスの場合もある
    • 文字列の末尾まで移動した場合や、大きな文字列内部の空の部分文字列を指す場合は、長さが0でも有効なポインタを持ち得る
    • 長さを確認した後にのみ逆参照するなら、すでに解放されたメモリを指すポインタも、長さが0の状態ではアクセスされない

バイナリデータと同じ表現を使う

  • 長さベースの文字列はセンチネルに依存しないため、NULバイトを含む任意のバイナリデータも安全に保存できる
  • ASCII文字列関数がUTF-8でも動作するように、スキャン・分割・トリミング・スライスのような長さベースの操作をバイト配列にも適用できる
  • NUL終端のバイナリ形式では、終端バイトを保存するかどうかを別途決める必要がある
    • 保存すれば、読み書きのコードが一般的な文字列処理方式に近くなる
    • 保存しなければ、空間と処理オーバーヘッドを減らせる。これはバイナリ形式を使う主な理由の1つである
  • 長さと内容の両方を保存しつつNULバイトまで付ける形式は、保存された長さが終端バイトを含むかを再び確認しなければならず、同じ曖昧さを復活させる

割り当てとコピーのない部分文字列

  • NUL終端を強制すると、トリミング・スライス・分割・トークン化・検索結果の末尾にも終端バイトを配置しなければならないため、新しい文字列と中間バッファを割り当て・コピーすることになる
  • 長さベースの文字列は、元データの一部を指すポインタと長さだけを返せる
String StrPrefix(String str, u64 size);
String StrPostfix(String str, u64 size);
String StrChop(String str, u64 size);
String StrSkip(String str, u64 size);
String Substr(String a, u64 min, u64 max);

String StrFindNeedle(String str, String needle);
String StrTrim(String str);
  • CSV、Markdown、JSON、C用のレキサーとパーサーは、各トークンをコピーせず、入力バッファのスライスをパースツリーの名前や値として保持できる
  • パースツリーを使う後続コードも同じスライスを受け取り、追加のメモリ管理なしで処理できる

センチネルが今も有用な場合

  • センチネルはデータ構造の不変条件を維持し、一部の状況で性能上の利点をもたらし得る
  • 現代のハードウェアとコンパイラでは、性能上の利点は特殊なケースを除いてほとんど弱まっているが、プログラムが管理すべき不変条件の数を減らす効果は残っている
  • 手書きのトークン検査では、NULセンチネルのおかげでループが現在のバイトを安全に読める
    • s[i] == 'f' && s[i+1] == 'o' && s[i+2] == 'r'のような先読みは、バイト順と短絡評価を利用して早期に失敗できる
    • 長さベースの文字列では、空白でトークンが終わった場合と入力自体が終わった場合を区別する必要があり、先読みにもより体系的な境界検査が必要になる
  • 既存のCライブラリとOS APIの大半はNUL終端文字列を要求するため、変換コストが発生する
    • WindowsではUTF-8をUTF-16へすでに変換する必要があるため、NULバイトを追加するコストは相対的に小さい
    • OSとベンダーが課す制約は実際より過大評価され、長さベースの文字列の利点は過小評価されがちである

文字列APIに不変性を適用する方法

  • 完成度の高い文字列レイヤーの全体的なAPI設計と抽象化は範囲外だが、核となる構造原則として不変性を推奨する
  • 文字列は一度作成されたら内容を変更せず、定数のように扱う。文字列を受け取り文字列を返す関数も、この性質を維持すべきである
  • 不変性は関数シグネチャとAPI境界で保証すれば十分である
    • 関数内部では必要に応じてインプレース変更や別の手続き的処理を使える
    • 上位の情報フローでは関数型プログラミングの不変性の利点を得て、下位の実装では手続き型プログラミングの柔軟性を維持する
  • この規則は、言語やランタイムが強制しなくてもコーディング・API慣習として運用できる
  • 文字列型と操作を明確に区別すれば、規則を維持する負担は大きくなく、コードベースが適用範囲と緩和するタイミングを自ら決められる
  • 言語も1つのAPIなので、言語委員会が定めた制約だけに依存せず、必要な粒度で規則を設計できる

長さベース文字列の実装例

他の文字列表現が持つ制約

  • 柔軟な配列メンバー

    • RedisのSDSのように、構造体の先頭部分に現在の長さと最大容量を保存し、最後のフィールドを柔軟な配列メンバーとして宣言して文字データを配置する
    • strlenのO(n)スキャンや手動の連結・境界管理といったC文字列の問題を避けられる
    • 文字列リテラルと直接互換しにくく、長さベース文字列の核心的な利点である効率的な部分文字列をサポートできない

  • ストレッチバッファ

    • ストレッチバッファは動的配列に似ており、長さと容量のヘッダーを明示的な構造体ではなくポインタ直前の別領域に保存する
    • 柔軟な配列メンバー方式の欠点に加え、すべてのchar*にほとんど見えないメタデータ規則を課し、意味のある文字列操作ごとにこのヘッダーをAPIモデルの一部として使わなければならない
    • ポインタ表現は型安全性を提供し、.strまたは->strアクセスを避けられるが、この利点だけで隠れた規則を正当化するのは難しい
    • 別個のcapacityフィールドは動的配列には自然だが、文字列では異なる概念を1つの型に混ぜ、型間の区別を曖昧にする
    • 柔軟な配列メンバーにも同じ問題はあり得るが、初期の固定サイズを容量として使い、動的拡張を避けられるという違いがある

  • Pascalスタイル

    • Pascal式の短い文字列は通常、256バイトの固定サイズ文字配列を使い、長さ用の1バイトを予約するか、NUL終端を利用する
    • 過去の実際のメモリ・ハードウェア制約では有効だったが、現代では優れたアリーナメモリ割り当て戦略を使えるため、特殊な状況を除いて適していない

長さベースの文字列をデフォルトにすべき理由

  • 長さベース文字列の利点は一部のコミュニティや熟練プログラマーの間では知られているが、多くの開発者はいまだにこのような実装を検討したことがない
  • 関連資料が各所に散らばっており、長さの喪失、終端バイトの曖昧さ、バイナリ処理、部分文字列、センチネルの長所と短所、代替実装をまとめて比較するのは難しかった
  • 基本の文字列型をポインタと長さのスライス形式にすれば、境界情報の保持、状態の単純化、バイナリ互換、割り当て不要の部分文字列を1つの設計で解決できる

関連記事

1件のコメント

 
GN⁺ 4 시간 전
Lobste.rsの意見

  • パディングバイトを避けるには、構造体メンバーの順序を次のように変えたほうがよいと思う

    struct String  
{  
    u8* data;  
    u64 size;  
};

    ではなく:

    struct String  
{  
    u64 size;  
    u8* data;  
};

    • 64ビットポインタ環境では2つのフィールドのサイズが同じなので、どちらの順序でもパディングはなく、32ビット環境ではポインタで表現できる範囲より大きい u64 自体が無駄になる
      CHERI のように 128ビットポインタを使う場合は、最初の配置では data と size の間に、2番目の配置では構造体の末尾にアラインメント用パディングが入るため、結局少し領域を無駄にする

    • 正しい定義は 可変長配列メンバーを使う形である

      typedef struct {  
  u64 len;  
  u8 buf[];  
} String;

  • C標準には u8 と u64 型は定義されておらず、これは Rust 風の表記である
    32ビット環境で長さを u64 で表すのも適切ではなく、C で配列サイズを表す慣用的な型は size_t なので、次のように書くほうが自然だ

    struct String  
{  
    char* data;  
    size_t size;  
};

    記事を書いた人か、これを生成した LLM は C をきちんと分かっていないように見える

    • 多くの C プロジェクトでは u8 と u64 を typedef で定義して使っており、これは非常によくある慣行である
      標準の uintN_t という名前を煩わしいと感じる場合も多く、大規模プロジェクトの中にはその標準より古いものもあり、Linuxカーネルもこうした別名を使っている
      むしろこの批判のほうが、C プロジェクトに慣れていないことを示している

  • C や C++ を数か月以上書いたことがあるなら、ポインタと長さを一緒に渡す方式はすでによく知られた話ではないかと思う
    現代的な C コードベースはほぼすべて、結局はデータポインタと長さを一緒に渡すか、独自の文字列ライブラリを持つようになる

    • 長さを保持するかどうかは C 文字列が抱える問題のひとつにすぎず、寿命管理にも厄介な点が多い
      現代 C++ の std::string_view は、「この文字列は参照できるが、変更したり保持したりしてはいけない」という意味を明示し、バグを大きく減らしてくれる
      C 文字列を受け取る API では、こうした制約は文書上の約束にすぎない

  • 本当の誤りは長さを保持するかヌル終端かではなく、任意の文脈で意味を持たせるには広すぎる String という概念そのものだと思う
    文字列は単なる文字配列を超えてさまざまな用途に使われ、その「文字」という言葉自体も、真空中の球形の牛を仮定する物理学ジョークのように、あまりに単純化されすぎている
    「長さ」が書記素クラスタ数なのか、コードポイント数なのか、全バイト数なのかすら曖昧である
    エンコーディングは何か、ユーザーに表示されローカライズが必要なのか、サニタイズ済みなのか、マップのキーのように変更する理由のない 不可分な値なのかも区別すべきだ
    この観点で見ると、一般的な実装の文字列型はもはや欲しくなくなる

    • Rust には文字列型が多すぎると不満を言うこともあるが、その一部はこうした情報を 型システムに載せるためのものだ
      どのライブラリも書記素クラスタ数を単に「長さ」と呼んではいないはずだ
      既定のエンコーディングを UTF-8 にし、他のエンコーディングやバイト配列には別の型を使う慣習で問題の一部は解決でき、多くは型システムで表現できる

  • 私の知る限り、C には大半の現代言語が提供する 言語レベルの文字列概念がない
    文字列操作は言語自体ではなく標準ライブラリで提供される
    K&R 第2版では、C は文字・数値・アドレスのようにコンピュータが直接扱う対象に近い、比較的低水準の言語であり、文字列・集合・リスト・配列のような複合オブジェクト全体を直接操作する演算は提供しないと説明している
    こうした機能の欠如は大きな欠陥に見えるかもしれないが、言語を小さく保ったおかげで短く記述でき、素早く学べ、プログラマが言語全体を理解して日常的に使えるという利点がある
    C がなぜこのように設計され、今では当然とされる現代的機能がなぜないのかを理解したいなら、K&R 第2版の序文と導入部を読むことを強く勧める

    • ただし、文字列リテラルの型とメモリ配置がライブラリの形を決めるという限定的な意味では、文字列も C 言語の一部である
      これは Rust のような低水準言語における言語とライブラリの区別とも、そこまで大きくは違わない

  • シリアライズ方式としては https://cr.yp.to/proto/netstrings.txt のような提案があり、https://web.archive.org/web/20230305073119/… のように 複雑な構造体まで扱う方式もある
    しかし、安全にパースするには単純すぎる見た目なのか、XML・JSON・YAML・Protocol Buffers などの熱心な支持者たちが引き続き忙しく働ける状態になっている