整数型に関する考察 (2023年)
Thoughts on Integers (2023) (blog.xoria.org)
要約
この記事は、プログラミング言語における整数型の扱いについて、C、C#、Go、Swift、Rustなどの例を比較しながら論じています。特にRustの明示的で偏りのない整数型設計を高く評価し、C言語における符号付き整数オーバーフローの未定義動作(UB)がパフォーマンスに与える影響についても考察しています。
全文翻訳
整数型に関する考察
この記事では、整数型に関する私の見解と、その見解に至った経緯を説明します。読者の皆さんが最初は同意せず、最後には納得してくれることを願っています!
現状
まずは、今日の一般的なプログラミング言語における現状と私が考える「ステータス・クオ」から始めましょう。ただし、いくつか注意点があります。この記事では、明白な理由からスクリプト言語には触れません。また、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言語で符号付き整数がオーバーフローした場合、それは未定義動作(undefined behavior)を招きます。つまり、コンパイラはオーバーフローが決して発生しないと仮定します。一方、符号なし整数のオーバーフローは、ラップアラウンド(循環)するように定義されています。
次に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コミュニティでしばしば引用されるドグマに従えば、無効な値(負の数)は表現不可能になることでバグが防止されます。
| 名前 | 符号付き? | ビット単位のサイズ |
|---|---|---|
u8 | いいえ | 8 |
u16 | いいえ | 16 |
u32 | いいえ | 32 |
u64 | いいえ | 64 |
usize | いいえ | アドレスサイズ |
i8 | はい | 8 |
i16 | はい | 16 |
i32 | はい | 32 |
i64 | はい | 64 |
isize | はい | アドレスサイズ |
この表で気づくかもしれないことの一つは、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が「無料」で提供してくれるので)ラップするように定義して、それで済ませてはいけないのでしょうか?
Chandler Carruth氏のUBに関する講演を視聴したのですが、その中で示唆に富む例が含まれています。(ここでは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++;
// さらに数回繰り返す
}
コンパイラは 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が巨大なオブジェクトを扱うのは筋違いです!我々は短い文字列と小さなファイルを扱っています。もしそれが大きなオブジェクトにつながるなら、それはそれ自身かシステムかのどこかに欠陥があり、 abort(終了)されるべきです。したがって、サイズと添え字は自然な
intです!
引用段落のリンクをご覧ください。そこには、サイズと添え字は符号付きであるべきだと述べているBjarne Stroustrup氏自身が書いた短い文書へのリンクがあります。懐疑的な態度とRustに基づいた先入観から、私は彼の議論をあまり説得力があるとは思いませんでした。それでも、これらの人々が何か一理あるに違いないという、心の奥底でかすかな感覚がありました。
C言語の代替案を見る
Odinは、シンプルさと「プログラミングの喜び」に焦点を当てた、新興のC言語代替案の1つです。別の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%のオーバーヘッドのオーバーフローチェックを考慮すると、デバッグビルドに限定するのは妥当なトレードオフだと思います。一貫性と単純さのために、デバッグビルドであってもオーバーフロー時のラップを使用するという議論も理解できます。
符号なし整数は直感的ではない
例えば、ある数値からゼロまでループしたいとします。符号付き整数を使えば簡単です。
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 がゼロに達すると、それをデクリメントすると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が常に飽和することはめったにないため、最初のチェックを削除しても、境界チェックの実行時間に変化はないでしょう。
符号なし整数はよりバグを起こしやすい
2つの配列インデックス i と j があると仮定しましょう。また、オーバーフロー時のパニックのオーバーヘッドがユースケースにとって許容できないため、ラップオーバーフローを使用していると仮定します。私たちは i と j の間の要素数を求めて、それらを新しい配列にコピーしたいと考えています。簡単ですよね?要素数を決定するには j - i だけでよく、そのサイズの新しい配列を作成してコピーを実行できます。
テストデータでは j が常に i 以上であると想像してください。しかし、本番環境では何らかの理由で j が i より小さくなってしまいました。もし i と j が符号なしの場合、j - i はラップアラウンドして、おそらく非常に大きな数になります。私たちはその非常に大きなサイズの配列を作成します。運が良ければ、コピーに境界チェックがあり、パニックが発生します。
要点は、符号なしアンダーフローは検出が難しいということです。大きな数がラップによって誤って発生したのか、それとも意図的なものなのかを区別する方法はありません。ここで符号付き整数を使用すると、無効な j - i の減算はすぐに「汚染された」(負の)結果を生成します。この結果は、巨大な数の予測不能な連鎖効果を通じて後で検出されるのではなく、配列を作成する際にすぐに検出できます。
符号付き整数はより多くのassertを必要としないか?
確かに、その負の配列サイズを検出するためには、配列割り当てコードに assert(count > 0) が必要だったでしょう。しかし、符号なし整数を使用していた場合にそれを検出するには、assert 以上のものが必要でした。プログラム全体で包括的なオーバーフローチェックを有効にする必要があったでしょう。
符号付き整数を使用する場合に追加する必要があるアサートは、軽量なオーバーフローチェックの形式と見なすことができます。すべての算術演算の後にオーバーフローをテストする代わりに、API境界で同等のチェックを1つ置くだけで済みます。言い換えれば、多数のオーバーフローチェックが、単一のチェックに集約されています。
もちろん、単一の assert(count > 0) は、すべての場所でのオーバーフローを徹底的にチェックすることと同等ではありません。例えば、create_array(1000 + j - i) のようなものをキャッチすることはできません。ここにはパフォーマンスと安全性のトレードオフがあり、アサートを多用し、オーバーフロー時にラップする符号付き整数が、幸せな中間地点であると私は言えます。
符号付き整数は最大値が低いため、より多くのビットを使用する必要があるのではないか?
これには同意しません。64ビットプラットフォーム上では、配列の要素数が63ビットに制限されていても、実際には問題にならず、むしろ良いことかもしれません。例えば、Rustはすべての割り当てのサイズを制限しています(ptr::offset(isize) のようなAPIが機能するように、符号付きアドレスサイズの整数の最大値まで)。
32ビットインデックスをコンパクトさのために使用する場合のような、より小さいビット幅では、1ビット失っても大した違いはありません。40億ではなく20億個の要素の最大値で十分でないアプリケーションについては、私は知りません。
-
ほとんどの「64ビット」CPUは実際には48ビットまたは52ビットのアドレスを持っていることを認識しています。簡潔にするために、「64ビットアドレス」で進めましょう。↩︎
-
オーバーフローチェックは例外です。オーバーフローをUBにすることは、コンパイラがオーバーフローチェックを削除できることを意味し、パフォーマンスが向上する可能性があります。しかし、これはCがパフォーマンスを正しさよりも優先するもう一つのケースであり、それらのチェックはそもそも削除されるべきではないと私は主張します。↩︎
Luna Razzaghipour
2023年9月14日