HN 日本語サマリー

← 一覧へ戻る
プログラミング

ほぼ常に符号なし

Almost Always Unsigned (graphitemaster.github.io)

25 pointsby gavide26 コメント

要約

この記事は、プログラム内で負の値を示すことがほとんどないにもかかわらず、多くのコードが符号付き整数をほぼ排他的に使用している現状を指摘しています。符号なし整数の使用には多くの誤解や反対意見がありますが、筆者は、適切なイディオムを用いれば、符号なし整数の方が安全で、より広範な値域を扱えるため、積極的に使用すべきだと主張しています。特に、ループの逆順処理やインデックス計算における安全な実装方法について解説しています。

全文翻訳

ほとんど常に符号なし整数を使う

Dale Weiler 著

最終更新: 2022年1月1日(土)

プログラム内で負の値を持つことがほとんどないにもかかわらず、符号付き整数演算の必要性はしばしば誤解されています。配列のインデックスやループの反復回数もこの概念を反映しています。符号付き整数よりも符号なし整数をより頻繁に使用する傾向があるべきですが、それにもかかわらず、ほとんどのコードは誤ってほぼ排他的に符号付き整数を選択しています。

この記事の動機の大部分はCおよびC++に適用されますが、Go、Rust、Odinなどの他の言語の例も提示し、この概念が言語の選択(例えばCとC++は符号付き整数のラップを未定義とする)に関係なく、算術自体に固有のものであることを確立しようと試みます。

符号なし整数に対する議論 #

符号なし整数型を使用することには多くの議論があります。それらがほとんど間違っている理由を説明しましょう。

安全性の議論 #

符号なし整数型を使用することに対する最も典型的な議論は、オーバーフローよりもアンダーフローの方がはるかに起こりやすいため、よりエラーを起こしやすいということです。このアドバイスは非常に一般的であるため、公式のGoogle C++ Style Guideは符号なし型の使用を明確に推奨していません。

次の議論で、これらの安全上の問題がどこから来るのか、そしてそれらを理解しやすい簡単なイディオムでどのように簡単に回避できるかを見ていきます。また、これらの議論はほとんどの場合間違っていることもわかります。なぜなら、それらは安全でないコードを書き続け、使用することを奨励しているからです。

逆順ループの議論 #

forループのカウンターが逆順にカウントする必要があり、ループ本体がカウンターがゼロの場合にも実行される必要がある場合、ほとんどのプログラマーは符号なし整数が使いにくいと感じるでしょう。なぜなら i >= 0 は常に true と評価されるからです。

符号なし値を符号付き値にキャストしたくなる誘惑に駆られます。例:

for (int64_t i = int64_t(size) - 1; i >= 0; i--) {
    // ...
}

もちろん、これは幅の狭い変換であり、正当な警告をサイレンスさせるキャストを伴うため危険です。CおよびC++では、特定の大きな値が与えられると未定義の動作を呼び出し、確実に悪用可能です。ほとんどのアプリケーションは、>= 0x7ffffffffffffffff の入力でクラッシュするでしょう。典型的な議論は、そのような値は「病理学的」であるということです。この議論は間違っているだけでなく、後述するようにさらに危険です。

この危険性は、常に符号付き整数演算を使用することの支持論拠の1つです。しかし、この議論は間違っています。なぜなら int64_t は 0x7ffffffffffffffff 以上の値を決して許可しないからです。それは単に問題を回避しているだけで、その上限を超える特定の病理的な数値範囲がもはや許可されなくなります。その値が必要だった場合は運が悪く、Googleの賢明なアドバイスに従って常に符号付きを使用し、その大きな値を持っていた場合、今度はさらに深刻な問題が発生します。なぜなら、それは無条件に符号付きオーバーフローを呼び出したことになるからです。CやC++のような言語では未定義の動作を呼び出します。一方、GoやOdinのような言語ではラップし、そのラップ動作の結果としてループで間違った数値範囲になります。

正しいアプローチは、符号なしアンダーフローはCおよびC++で明確に定義されており、ラップ算術の動作を教えるべきだということです。なぜならそれは一般的に有用であり、逆順のイテレーションを順方向と同じくらい簡単にできるからです。

for (size_t i = size - 1; i < size; i--) {
    // ...
}

ここでのアプローチは size - 1 から開始し、各イテレーションでカウントダウンすることです。カウンターがゼロに達すると、デクリメントによりカウンターはアンダーフローし、符号なし型の最大可能値にラップアラウンドします。この値は size よりもはるかに大きいため、条件 i < size は偽と評価され、ループは停止します。

Rustのような言語は、デバッグビルドでは符号なしアンダーフローさえもトラップ表現にすることを選択しましたが、Range のような特定の機能は、よりクリーンな構文でアンダーフロー時の効率的なラップ動作を安全に達成できます。

for i in (0..size).rev() {
    // ...
}

このアプローチでは、キャストは不要で、サイレントなバグも導入されず、「病理学的」な入力も正しく機能します。実際、この形式は [0, 0xffffffffffffffff) のすべての可能な値を許可し、範囲全体をカバーします。

size == 0 の場合、これらのループは依然として機能します。なぜなら 0 - 1 は符号なし型の最大値を生成し、それは size (依然として 0) より大きいため、ループは決して実行されないからです。

2つの数値の差が負になることがある #

差(またはデルタ)を計算したい場合、それを次のように表現することがよくあります。

delta = x - y;

ほとんどの場合、符号は必要ないため、次のように記述・表示する傾向があります。

delta = abs(x - y);

符号なし整数は y > x の場合にアンダーフローするため、ここで危険であるという議論があります。この議論の問題点は、x と y の符号に関係なく、コード自体が単に間違っているため、有効ではないということです。符号付き整数アンダーフローを引き起こす x と y の値は両方存在します。したがって、以前と同様に、CやC++のような言語では、符号付き整数アンダーフローは未定義であるため、単に未定義の動作を無条件に呼び出しています。ラップ動作をサポートする言語であっても、符号付き整数で安全に差を計算することは実際には非常に困難です。例えば INT_MAX - INT_MIN でさえ間違った結果になります。これを安全に行う簡単な方法はありません。これが現在知っている最善のテクニックです。

if ((y > 0 && x < INT_MIN + y) || (y < 0 && x > INT_MAX + y)) {
    // error
} else {
    delta = abs(x - y);
}

しかし、符号なし整数では、次のように記述する方がはるかに簡単です。

delta = max(x, y) - min(x, y);

これは常に絶対差を安全に与えます。個人の好みかもしれませんが、私はこれも読みやすいと思います。delta という名前は、式が自己説明的であるため、もはや必要ありません。

符号付き演算でのインデックス計算はより安全 #

上記の議論の拡張として、インデックスを計算するためのより複雑な式がある場合、それを符号付きで表現する方が安全だというものがあります。この議論は主にアンダーフローとオーバーフローの誤った直感から来ていると思いますが、符号付きの場合はさらに悪い形で現れます。

例として、インデックスを計算するための最も単純な「わずかに複雑な」式、つまり区間の中間点を取り上げましょう。

int mid = (low + high) / 2;

これは現実世界で、非人工的な例として選びました。二分探索、マージソート、その他ほとんどの分割統治アルゴリズムで見つけることができます。

ほとんどの人はこのように書くでしょう。低と高の平均を整数に切り捨てたものです。low と high の合計が 2^31-1 を超えると、合計は負の値にオーバーフローし、その負の値は除算されても負のままです。より大きな符号付き整数型を使用しても、合計が 2^63-1 を超えることも容易であるため、救われません。

前の例と同様に、このコードは理想的ではありません。

実際、2つの変数の中心点を安全に計算することは、ラップ動作の有無にかかわらず、特定の入力が失敗するため、ライブラリ関数の助けなしにどの言語でも pretty much 不可能です。

符号付きの一般的な解決策は、このイディオムに書き直すことですが、high = INT_MAX および low = INT_MIN の場合は依然として失敗します。

int mid = low + (high - low) / 2;

符号なし整数にとどまると、最初に意図したように明らかに記述できると思うかもしれませんが、これも問題があることがわかります。

size_t mid = (low + high) / 2;

これは実際には機能しません。例えば low = 0x80000000 および high = 0x80000002 の場合、アンダーフローして 2 を生成し、それを 2 で割ると 1 になりますが、正しい値は実際には 0x80000001 です。

符号なしがここで利益を得るのは、これらが配列へのインデックスとして使用される場合です。符号付きの動作はほぼ確実に無効なインデックスを生成し、メモリの安全性に関する問題につながります。符号なしの方法は決してそうならず、生成されるインデックスが実際には間違っていても、常に範囲内に収まります。これははるかに軽微な論理バグですが、文脈によっては悪用される可能性があります。

符号の有無にかかわらず、これを安全に行う正しい方法は、すべてを符号なしに変換し、マスクされた加算でラップを考慮することです。

T midpoint(T x, T y) {
    // U は T の符号なしバージョン、または T が既に符号なしの場合は T と同じです。
    // digits は T の数値桁数(符号を除く)です。
    // C++ では std::numeric_limits<T>::digits が役立ちます。
    U shift = digits - 1;
    U difference = (U)x - (U)y;
    U sign = y < x;
    U half = (difference / 2) + (sign << shift) + (sign & difference);
    T mid = (T)(x + half);
    return mid;
}

C++ には実際、これとまったく同じことを行う std::midpoint があります。

符号なし乗算はオーバーフローする可能性がある #

符号なし変数を乗算する際に、そのような式が簡単にオーバーフローして正しい値よりもはるかに小さい値を生成するという懸念があります。これは、配列の割り当てで符号なし乗算が最もよく見られるため、メモリの安全性に関する非常に一般的な苦情です。Cで次のように書きたくなる誘惑に駆られます。

malloc(sizeof(Object) * n)

そのような式がオーバーフローした場合、malloc は n 個の Object 全てに対して十分な大きさではないメモリを割り当てて返します。ここでも、符号付きは私たちを救いません。実際には、int を使用した場合、約4GiBのメモリを過剰に割り当てることで、サイレントにメモリ安全性の問題を回避します。ランダムなリソース枯渇は、より良い状況ではありません。

これを記述するためのより良い方法がいくつかあります。最初の明らかな方法は calloc を使用することです。ただし、これにはゼロ化のコストがかかり、realloc が必要な場合には役立ちません。

C++やGoのような言語はこの問題を認識し、よりクリーンな方法で解決し、危険な乗算の必要性を排除しました。

  • C++

    new Object[n];
    
  • Go

    make([]Object, n);
    
    // しかし、明示的な n * m の形式もあります。
    make([]Object, n, m);
    

これらは一般的に適用されません。しかし、x * y がオーバーフローするかどうかをチェックするのは非常に簡単であり、非常にシンプルで明白なテストを学ぶべきです。

if (y && x > (T)-1/y)

ここで (T)-1 は符号なし型であり、-1 をキャストすると最大値、つまりすべてのビットがセットされた値が得られます。C++ では ~((T)0)、UINT{8,16,32,64}?_MAX、または numeric_limits<T>::max() を使用することもできます。この値を計算する方法はたくさんあります。

センチネル値 #

符号付き整数型の非常に一般的な使用法は、負の範囲を使用してエラーコードやセンチネル値をエンコードすることです。これは悪いプログラミング習慣であり、文字通りのカテゴリエラーです。それを中心に設計された既存のまたはレガシーなコードを扱う際には pretty much 回避不可能ですが、この習慣を続けるための符号付き整数型の強力な議論ではありません。符号なし整数でもセンチネルを持つことは可能ですが、そうすべきではありません。

私たちはこれを奨励すべきではなく、符号付き整数を支持する議論として使用すべきではありません。

int result = connect();
if (result >= 0) // ...

ここで、正の値以外はすべてエラーです。

これは初期のCでは典型的です。

これを表現するための、より良く、より安全な方法がいくつかあります。例えば:

  • 結果のためのアウトパラメータ。見た目はあまりきれいではありません。

    if (uint result; connect(&result)) {
        // ...
    }
    
  • タプルまたはペアの返却。見た目は少し良いです。

    tuple<bool, uint> result = connect();
    pair<bool, uint> result = connect();
    if (get<0>(result)) {
        // ...
    }
    
  • オプション型を使用できます。Rustではかなり一般的です。

    // connect は Option<u32> を返します
    match connect() {
    Some(u32) => // ...
    None      => // error
    }
    
  • ただし、数値範囲が最初から明確に定義されている場合は、単にドメイン全体を定義し、全範囲整数を使用して可能な値のサブセットを表すことを避けてください。

    enum class ConnectionStatus : unsigned {
        Connected,
        NoRouteToHost,
        Disconnected,
        TimedOut,
    };
    
    ConnectionStatus status = connect();
    if (status == ConnectionStatus::Connected) {
        // ...
    }
    
  • OdinやGoのような一部の言語では複数の戻り値があり、慣用的な方法は次のとおりです。

        status, err := connect();
        if err != nil {
            // ...
        }
    

これらはすべて、符号付き整数の負の部分にエラー状態をエンコードする必要性を排除する優れた方法であり、ほぼすべての言語で表現可能です。

デフォルトである #

これは弱い議論ですが、反論するのが難しい唯一の議論です。CとC++では int がデフォルトで符号付きであり、これはCの後継言語の多くに引き継がれたレガシーな選択です。Cの多くのデフォルトが悪かったことは一般的に合意されています。これも検討すべきでしょうか?

もし符号付きがラップするように定義されていたら? #

GoやOdinのような一部の言語は、符号付き整数演算がアンダーフローおよびオーバーフロー時にラップするように定義されているため、これらの問題を回避すると主張しています。そこでの安全性の議論もまた間違っています。前の例のすべてにおいて、符号付き整数がラップした場合、ほとんどの場合負の値が生成され、サイレントな論理バグ、あるいはさらに悪いことに、配列へのインデックスとして使用された場合のメモリ安全性の問題が発生します。

このような方法で符号付き整数を安全に使用できる唯一の方法は、すべての配列アクセスを境界チェックすることですが、これにはかなりの、無視できない実行時コストがかかります。境界チェックは自動化されていない場合、チェックを忘れることが容易であり、コードのリファクタリング中にしばしばメンテナンスされないため、非常にエラーを起こしやすいです。

残念ながら、LLVMベースの言語では、いくら手でこねくり回しても、符号付きラップが定義されることを望んでも、どんなに頑張っても機能しません。したがって、安全性に関するそのような声明は事実上不正確です。以下は、LLVMを使用するすべての言語に適用される、符号付き整数演算の未定義の動作の(完全ではない)リストです。

  • x / 0
  • INT_MIN / -1
  • INT_MAX % -1
  • INT_MAX - INT_MIN

これらは、Go、Rust、Odinのような言語で無効な結果を生成することが確実です。

トラップについてはどうですか? #

Rustのような一部の言語は異なるアプローチを採用しており、デバッグビルドでの整数アンダーフローまたはオーバーフローはプログラムがパニックするトラップ表現につながります。CおよびC++のサニタイザーもこれらの問題を検出するのに役立ちます。そして、CおよびC++は符号なしアンダーフローをラップと定義しているため、符号付き整数を使用する方が実際には優れています。なぜなら、それは整数に対してトラップ動作を得る唯一の方法だからです。なぜなら、それらを符号なしに使用すると、その動作に依存する有効なコードに対してトラップ表現がトリガーされるからです。

トラップ表現は実際には非常に不十分です。なぜなら、それらは正しいトラップ生成入力でパスが正常に実行された場合にのみ実行時にトリガーできるからです。このカバレッジは、網羅的な単体テストがあっても、非自明なプログラムでは期待できません。また、ライブラリコードのように、ライブラリがパニックすることをほとんど望まず、すべてのエラーは呼び出し元のアプリケーションコードで回復可能であるべき場合、またはパニックが pretty much 受け入れられないサービス可用性に敏感なコードでは、このアイデアは多くのコンテキストと互換性がありません。

あなたの反論は病理学的入力に関するものだ #

私の経験では、何が病理学的または悪意のある入力であるかについての私たちの直感は、時間見積もりと同じくらい正確です。要件は変更され、あらゆる攻撃ベクトルが見つけられ、悪用されます。病理学的または悪意のある入力をすべてのケースで正しくチェックするための仮定を覚えておき、リファクタリング中にそれらを更新し続けるという精神的な負担は、成功裏に維持するには大きすぎます。

この頑固な態度の最も有名なケースの1つは、Daniel J. Bernstein がバウンティを拒否した悪名高いqmail 64ビットリモートコード実行エクスプロイトであり、2020年現在でも悪用可能です。

これらは次のとおりです。

エクスプロイト作成者は次のように書いています。「古典的な符号付き整数オーバーフロー、符号付きインデックスを持つポインタ、および符号性の問題」

符号なし整数演算の使用は、これらのバグを防ぐだけでなく、それらがより明白になるため、病理学的および悪意のある入力についてより直接的に考えることを強制します。

符号なし整数を支持する議論 #

プログラム内のほとんどの整数は負の値を持たない #

符号なし整数の使用は、サイズ付き整数型と同様に、整数の数値範囲の型指示として優れています。負の数量を無視できる即時の能力は、実際に符号なし変数を使用する最大の利点の1つです。プログラム内のほとんどの値が実際には負ではなく、決して負になることがないというのは単純な観察ですが、私たちはその意図と動作を型システム内にエンコードして、追加の安全性と利点を提供すべきです。

私はかつて読んだIntelの調査論文を見つけることができませんでしたが、その観測によると、x86 Windowsデスクトップシステム全体の整数のわずか3%しか負の値を持っていなかったと主張していました。いずれにせよ、その3%という数字が正しい場合、上記の意見から、コードベース内の整数型の約97%が符号なしであると予想されます。

コンパイラ診断は符号なしの方が優れているが、全体としては悪い #

安全性が符号付き整数演算を使用する主な動機であるにもかかわらず、符号付き整数は実際には主張されているバグを回避していないように見える場合、なぜそもそもその考えが生まれたのか疑問に思うかもしれません。

コードベースで符号付きと符号なしを混合したことがあるなら、それらが生成する警告診断の量に精通しているでしょう。これらの診断は残念ながら役立つことを意図していますが、実際には安全でない型キャストの形でサイレンスを奨励するため、積極的に悪意があります。現実には、符号付きと符号なしの使用は、すべての整数をそれぞれ赤または青に塗るようなものです。What color is Your Function。一方の使用量が多いほど、それが適切かどうかに関わらず、すべてが同じ符号性を持つ可能性が高くなります。ほとんどの整数は負の値の表現を必要としないため、個人的には、この場合はすべてを青く塗る方が適切だと思います。例外は負の整数値です。ルールはほとんどが正の整数値です。プログラミング言語のデフォルトは、例外ではなく、ルールに合わせるべきです。

オーバーフローとアンダーフローのチェックがより簡単で安全 #

CおよびC++は符号付き整数オーバーフローとアンダーフローを未定義とするため、安全で正しい、明白なコードを書いてそれをチェックすることはほぼ不可能です。

したがって、次のようなシンプルで明白なテスト:

if (x + y < x) // 加算がオーバーフロー
if (x - y > x) // 減算がアンダーフロー

は、未定義の動作を呼び出すため、コンパイル時に削除されるか、誤ってコンパイルされます。

これは符号なし整数にとっては完全に問題なく安全です。

Odinのような定義された符号付きラップを持つ言語では、以前に言及したLLVMによる INT_MIN と INT_MAX を除いて、これも機能するはずです。

笑いのために、標準CまたはC++で符号付き整数オーバーフローとアンダーフローを検出する唯一の正しい方法(私が知る限り)は次のとおりです。

if ((b > 0 && a > INT_MAX - b) || (b < 0 && a < INT_MIN - b)) // 加算がオーバーフロー
if ((b > 0 && a < INT_MIN + b) || (b < 0 && a > INT_MAX + b)) // 減算がアンダーフロー

必要になったときに、これらの化け物を覚えてタイピングするのは大変でしょう。

コードがよりシンプルで高速になる #

すでに示した、符号なしが正しいことを行うほとんどすべての例に加えて、負にならない値を表すために符号付き整数を使用するほとんどすべてのコードは、範囲アサーションやその他のテストの不協和音を伴います。これらは、境界チェックと同じくらいエラーを起こしやすく、書くのを忘れる可能性があり、リファクタリング時にメンテナンスも必要です。型システム自体によって整数が実際に負にならない場合、これらのテストをどれだけ排除できるかは本当に過小評価されています。これは、nullポインタをチェックする必要がないという点で、生のポインタを持たないことに非常に似ています。多くの意味で、符号付き整数は整数のnullポインタです。コンパイラは、符号付き整数がアンダーフローまたはオーバーフローできないと仮定して、符号なしが参加できない最適化を行うことができます。あまり知られていないのは、値範囲解析は、最新の最適化コンパイラでは、任意の数値範囲の任意の数値型に適用できる最適化であるということです。前の例の enum は、これが適用されるものであり、符号なし型であってもそうです。単純なガイド分岐でコンパイラヒントとして数値範囲を定義できます。例えば、式 b = a + 2 は b > a を即座に確立し、コンパイラはこれを後で最適化に使用できます。

実際に機能する #

このタイトルが示唆するように、実際にほとんど常に符号なし整数を使用することがどのように可能か疑問に思うかもしれません。これは私個人の好みで5年間続いており、それに切り替えて以来、符号付き整数を実際に欠いたことはありません。一般的な知恵に反して、私のコードははるかに簡単、クリーン、そして堅牢になりました。ほとんどが符号付き整数で構成されている既存のコードベースでこれを使用しようとすることは推奨しません。そのような状況では、安全でない型キャストの結果としてサイレントなバグや問題が発生する可能性が高くなります。しかし、次回新しいプロジェクトを開始するときに試してみてください。きっと驚くほど良い結果が得られるでしょう。