整数についての考察 (2023)

この投稿では、整数型の私の見解と、 それに至った経緯を述べます。 最初は反対するかもしれませんが、最後には納得していただけることを願っています！

The status quo

まず、今日の人気のあるプログラミング言語における 現状を特徴づけてみましょう。 ただし、いくつかの注意点があります: この記事では、スクリプト言語については明らかな理由で触れません。 また、Javaはこのセクションから除外します。 なぜなら、Javaには整数に関する奇妙な点があるためです (int と Integer の違い、および明確な符号なし型がない点)。

まず、古典的なシステムプログラミング言語である C から始めましょう。 伝統的な C の整数型 int、char、short、long、long long などに加えて、 C99 では int8_t、uint64_t などの名前を持つ固定サイズの型が追加されました。 現代の 64 ビットプラットフォームでは int は常に符号付きで 32 ビット幅です。 さらに、C には ptrdiff_t や size_t などの マシン依存の型の混乱を招く配列があります。 一般に、添字とサイズは size_t 型ですが、 C の暗黙の変換により、 しばしば int や他の型が代わりに使われることがあります。 C で符号付き整数がオーバーフローすると未定義動作が発生し、 コンパイラはオーバーフローが発生しないと仮定します。 一方、符号なし整数のオーバーフローはラップすると定義されています。

次に、C# です。C# は低レベルの制御が必要ない場合に使われる 典型的な「アプリケーション・プログラミング」言語として位置づけられます。 C# の型名は C のものと似ています: int、short、long、byte。 int は 32 ビット幅です。 符号なし版は型の前に u を付けることで得られます。 添字とサイズには通常の int が使われ、 デフォルトではオーバーフロー時にラップします。

Go は C# と同じ領域の言語に対する現代的な代替です。 ここでトレンドの始まりが見られます: 直感に反する C スタイルの整数型名を使うのではなく、 Go は各型のビット幅を単に追加します: int8、uint64 など。 もう一つの興味深い違いは int と uint のサイズに現れます: これらはターゲットプラットフォーム上のアドレスのサイズに一致し、 特定の幅にハードコードされていません。 やはり、サイズと添字には int が使われます。 Go では整数のオーバーフローはラップすると定義されています。

Swift はこの「コンパイル済みで静的型付けされた非低レベル商用ソフトウェア」ニッチにおけるもう一つの最近の言語で、 その整数型は Go と複数の点で似ています。 型名は大文字が違うことを除いて Go と同一です: Int8、UInt64 など。 Int と UInt は Go と同じサイズ動作を持ち、 添字とサイズの両方に Int が使われます。 興味深いことに、Swift はリリースビルドでもデフォルトで整数オーバーフロー時にパニックします。

Rust: より良いアプローチ

上で挙げたすべての例に共通点があることに気づきましたか? これらの言語はすべて何らかのデフォルトの int 型を持っています。 符号なし型を符号付き型ではなく使うには追加の入力が必要で、 明示的にサイズ指定された型をデフォルトサイズの int の代わりに使う必要があります。 私はこれが int の使用を他の型より促していると言えます。 結局のところ、画面いっぱいの int と uint32_t のどちらを見る方がいいでしょうか? これは見た目を超えた問題でもあります。 状況に最適な型を慎重に検討するよりも、 何も考えずに int と入力する安易な方法を選ぶのは非常に簡単です。

Rust はこれらの各点を排除します: すべての整数型は明示的なサイズを持ち、 すべての型は符号付きと符号なしをそれぞれ示すために i または u のいずれかが前置されます。 特定のサイズや符号付き/なしへのバイアスはありません。 状況を考慮し、その状況に最も適した型を判断せざるを得ません。 整数を狭くすることでメモリが節約されるかもしれませんし、 Rust コミュニティがよく引用する教義を呼び出せば、 無効な値（負の数）が表現不可能になることでバグが防がれるかもしれません。

この表について気づくかもしれないことの一つは、 usize と isize の存在です。 usize は C の size_t と同様に添字とサイズに使われます。 C とは異なり、Rust には暗黙の整数キャストがないため、 配列のインデックスには実際に usize を使わなければなりません (as キャストの洪水を望まない限り)。 32 ビットの int ではなく usize を使うことは、 配列が 20 億を超える要素を持てることを意味し、 符号なし型を使うことは負の配列インデックスが発生し得ないことを意味します。

Rust はデバッグビルドではオーバーフロー時にパニックしてバグを捕捉しますが、 リリースビルドではパフォーマンスのためにラップを使用します。 オーバーフロー時の UB がないことに注意してください。

Rust が特定の整数型にバイアスを持たないと言ったことには注意点があります:

fn demo() {
	let x = 1; // x: i32
}

Rust は整数リテラルに型情報がない場合、デフォルトで i32 を使います。 したがって、符号付き 32 ビット整数への（些細ではありますが）バイアスがあります。 しかし、Rust の経験から、私は符号付き整数を非常に稀にしか使わないことに気づき、 符号なし整数をデフォルトにすることをほぼ支持するほどでした。 Rust が符号なし整数と符号付き整数を同等に扱わなかったなら、 私はこの結論に到達しなかったでしょう。

私にとって、これらの変更はすべて明らかな改善のように思えます。

Rust プログラマが他の言語を試す

C#、Swift、Go で実験を始めたとき、私はすぐに苛立ちました。 タスクに適した整数型を選ぶという姿勢で、 これらの言語がデフォルトで使う符号付きの int の代わりに、 配列のインデックスに uint をどこでも使おうとしました。 必要なキャストの量のため非現実的だったため、私は苛立ちながら諦めました。 これは私をますます確信させました: なぜすべての言語が Rust のような整数型を持てないのでしょうか?

なぜ C は符号付き整数のオーバーフローを UB にするのか?

元々はハードウェアの動作の違いが理由でしたが、 今日最もよく聞く議論はパフォーマンスです。 しかし、ほとんどの CPU は算術演算がオーバーフローしたときにラップを実行するのではないでしょうか? なぜ単にオーバーフローをラップと定義して （CPU が「無料」で提供してくれるので、追加コストなしで） 済ませないのでしょうか?

私は UB のトピックに関する Chandler Carruth の講演を見ました。 その中で彼は啓発的な例を含めています。 （64 ビットアドレスのアーキテクチャで実行していると仮定します。1）

bool mainGtU(int32_t i1, int32_t i2, uint8_t *block)
{
	uint8_t c1, c2;

	c1 = block[i1]; c2 = block[i2];
	if (c1 != c2) return c1 > c2;
	i1++; i2++;

	c1 = block[i1]; c2 = block[i2];
	if (c1 != c2) return c1 > c2;
	i1++; i2++;

	// repeats several more times
}

コンパイラは i1 と i2 の変更を排除するのに十分賢いです。 バイトは block + i1 と block + i2 から直接ロードされ、 次に block + i1 + 1 と block + i2 + 1、 次に block + i1 + 2 と block + i2 + 2、 という具合にロードされます。 これらのアドレス計算はロード命令の一部として行われるため、 64 ビット整数の範囲内で発生します。

オーバーフロー時にラップを強制したとしましょう。 i1++; と i2++; は 32 ビット整数の限界に達するとラップします。 ランタイムの動作がこのラップに忠実であることを保証するため、 コンパイラは i1 + n が 32 ビットをオーバーフローしたときに block + i1 + n が block + 0 にラップバックするようにする 追加の命令を生成します。 言い換えれば、「CPU はオーバーフロー時に無料でラップする」という主張は このケースでは成り立たず、その結果コードが肥大化します。

これは仮定の話ではありません; i1 と i2 を符号なしにすると、 これらの追加命令も生成されます。 彼の講演で、Chandler はこのコードを、 符号なし整数から符号付き整数に切り替えることでパフォーマンスが向上する例として使っています。 なぜなら、コンパイラがオーバーフロー時の UB を利用できるからです。 彼はさらにこう言っています:

算術的に扱いたい整数がある場合、 ある種のモジュラ空間（2 のべき乗）ではなく、 符号付きにしてください。 より多くのビットが必要なら、ビット数を増やしてください。 符号付きにしておいてください。

これは私にとって魅力的でした。 型システムを使ってバグを防ぐはずではないでしょうか? 数値が負になることがないなら、なぜ符号付きにするのでしょうか? Chandler のこの問題に対する見方は私を不快にさせました。

C へのさらなる足を踏み入れる

C を使ったシステムプログラミングに没頭する中で、 負になることがないにもかかわらず、 インデックスには符号付き整数を使うべきだと言う人々に何度か出会いました。 特に、Chris Wellons のブログの 3つの 異なる 投稿を読みました。 これらはすべてこの見解を支持しています:

近年、私は符号なしのサイズは深刻な誤りだったと確信するようになりました。 おそらく初期のコンピューティングにおける大きな過ちの一つであり、 サイズと添字は符号付きであるべきです。 pkg-config が巨大なオブジェクトを扱う必要はありません! 私たちが扱っているのは短い文字列と小さなファイルです。 大きなオブジェクトに行き着くなら、どこかに欠陥があるはずです — 自身またはシステムに — そして中止すべきです。 したがって、サイズと添字は自然と int です!

引用された段落のリンクをご覧ください? それは Bjarne Stroustrop 本人が書いた短い文書にリンクしています。 彼もまたサイズと添字は符号付きであるべきと言っています。 懐疑的な態度と Rust に基づく先入観で、 私は彼の議論をあまり説得力があるとは思いませんでした。 それでも、頭の片隅で、これらの人々が何かポイントを持っているという くすぐったい感覚がありました。

いくつかの C の代替案を見る

Odin は、シンプルさと「プログラミングの喜び」に焦点を当てた、 台頭しつつある C の代替案の一つです。 別の C 代替案である Zig での実験が失敗した後、 私は Odin をより詳しく見ることにしました。

再び、馴染みのある「モダン言語」の整数システムが登場しますが、 低レベルプログラミング向けのいくつかのひねりが加えられています:

• int と uint はアドレスサイズです
• i8 から i128 は符号付きです
• u8 から u128 は符号なしです
• 明示的にサイズ指定された型には le または be を 接尾辞として付けて、メモリ内表現をリトルエンディアンまたはビッグエンディアンにできます
• サイズと添字には int が使われます
• オーバーフロー時にラップします

今回は、開かれた心を持ち、 このセットアップが持つかもしれない利点を詳しく見ることにしました。 以下の議論のいくつかは私のものではありませんが、 どこから得たものか、どれが私自身のものか覚えていません。

アドレスサイズは完璧なデフォルトサイズ

前述のように、 ポインタと 32 ビット整数を混在させると、 オーバーフローを UB にしない限りパフォーマンスの問題につながる可能性があります。 i1 と i2 を ptrdiff_t やそれに類する型にしていたなら、 オーバーフロー時のラップはうまく機能したでしょう。 さらに、A64 のような ISA は 32 ビットと 64 ビットの算術命令しか持たないため、 8 ビットと 16 ビットの整数を操作するには追加の and 命令が必要です。 アドレスサイズの整数ですべての算術を行うのが、 一般的に最善の選択肢です。

これに対する反論として、現代の CPU は通常メモリ境界であるため、 データ構造をできるだけ小さくパックするのが良いというものがあります。 デフォルトを 32 ビットではなくアドレスサイズの整数にすることは、 この目標に反します。 それでも、配列のインデックス、サイズ、算術、 およびデフォルトの整数型としてプレーンな int を使える シンプルさは、適切な場所で int32 を使うことを覚えておくコストを上回ると言えます。

リリースビルドでは、オーバーフロー時のラップは妥当なトレードオフ

操作されるすべての整数がアドレスサイズの場合、 オーバーフローを未定義動作にすることには利点がありません2。 関数の先頭で数回のキャストをする方が、 UB の時限爆弾を増やすよりも良いと思います。

約 30% のオーバーヘッドを考慮すると、 オーバーフローチェックをデバッグビルドに限定するのは妥当なトレードオフだと思います。 デバッグビルドでも一貫性とシンプルさのためにオーバーフロー時にラップを使うという議論も成り立つでしょう。

符号なし整数は直感的でない

ある数値から 0 までループしたいとしましょう。 符号付き整数なら自明です:

void demo(int32_t top)
{
	for (int32_t i = top; i >= 0; i--) {
		printf("%d\n", i);
	}
}

予想通り、demo(3) を実行すると

3
2
1
0

と出力されます。 しかし、ここで i と top が負になることはありません。 したがって、このような状況では符号なし整数の方が良いのではないでしょうか?

void demo(uint32_t top)
{
	for (uint32_t i = top; i >= 0; i--) {
		printf("%u\n", i);
	}
}

これは無限ループです。 符号なし整数 n では、n >= 0 は常に真です。 符号なし整数はオーバーフロー時にラップするため、 i が 0 に達するとデクリメントされて 4,294,967,295 になります。 これを修正するには、条件を i <= top に変更できます:

void demo(uint32_t top)
{
	for (uint32_t i = top; i <= top; i--) {
		printf("%u\n", i);
	}
}

i がラップアラウンドすると、top より大きくなり、 ループから抜け出します。 なんてひどいのでしょう。

符号付き整数は境界チェックを遅くしないか?

符号付きインデックスを使う場合の境界チェックでは、 0 <= i と i < count の両方をチェックする必要があります。 これら 2 つのチェックは互いに独立しており、 現代の CPU は並列に実行できます。 CPU のすべての ALU が飽和することは稀なので、 これらのチェックの 1 つ目を削除しても、 境界チェックの実行時間は変わらないでしょう。

符号なし整数はバグを起こしやすい

2 つの配列インデックス i と j があるとしましょう。 また、オーバーフロー時にパニックするオーバーヘッドが 私たちのユースケースでは許容できないため、 オーバーフロー時にラップしているとしましょう。 i と j の間にいくつの要素があるかを求め、 それらを新しい配列にコピーしたいとします。 簡単ですよね? 要素数を決定するには j - i だけで十分で、 そのサイズの新しい配列を作成してコピーできます。

テストデータでは j が常に i 以上であると想像してください。 しかし、本番環境では j が i より小さくなることがあります。 i と j が符号なしの場合、 j - i はおそらく非常に大きな数にラップします。 その非常に大きなサイズの配列を作成することになります; 運が良ければ、コピーには境界チェックがあり、パニックを引き起こします。

重要なのは、符号なしのアンダーフローは捕捉しにくいということです: 大きな数がラッピングによって誤って引き起こされたのか、 意図的なのかを判断する方法はありません。 ここで符号付き整数を使うと、無効な j - i の減算は 即座に「毒された」（負の）結果を生成します。 この結果は、巨大な数の予測不能な波及効果を通じて後で捕捉されるのではなく、 配列を作成するために使われた時点で即座に捕捉できます。

符号付き整数はより多くのアサートを必要としないか?

その負の配列サイズを捕捉するには、 配列割り当てコードに assert(count > 0) が必要だったのは事実です。 しかし、符号なし整数を使っていた場合にそれを捕捉するには、 単なる assert よりもはるかに多くのものが必要です — プログラム全体に対して包括的なオーバーフローチェックを有効にする必要があります。

符号付き整数を使う場合に追加する必要があるアサートを、 軽量な形式のオーバーフローチェックと見なすことができます。 すべての算術演算の後にオーバーフローをテストするのではなく、 API の境界で同等のチェックを関数の先頭に置くだけで済みます。 言い換えれば、大量のオーバーフローチェックが 単一のチェックに集約されています。

もちろん、単一の assert(count > 0) は、 どこでもオーバーフローを徹底的にチェックすることと同等ではありません。 たとえば、create_array(1000 + j - i) のようなものは捕捉しません。 ここにはパフォーマンスと安全性のトレードオフがあり、 アサートを寛大に使い、オーバーフロー時にラップする符号付き整数は 幸せな中間地点だと私は言えます。

符号付き整数は最大値が低いので、より多くのビットが必要になるのではないか?

私はこれに同意しません。 64 ビットプラットフォーム上では、 配列内の要素数が 63 ビットに制限されることは、 実際には問題にならず、むしろ良いことかもしれません。 たとえば、Rust は すべての割り当てのサイズを 符号付きアドレスサイズ整数の最大値に制限しているため、 ptr::offset(isize) のような API が機能します。

より小さなビット幅の場合、 コンパクトさのために 32 ビットのインデックスを配列に使っている場合でも、 1 ビットを失うことは大した違いではありません。 20 億要素の最大値では不十分だが、40 億要素なら十分というアプリケーションは知りません。

Luna Razzaghipour
2023年9月14日