Thoughts On Integers (2023)

在這篇文章中，我將闡述我對整數型別的看法，以及我如何形成這些看法。 希望你一開始會不同意，但到最後能被說服！

The status quo

讓我們從我認為是當今流行程式語言中現狀的東西開始。 但首先，有些注意事項： 基於顯而易見的原因，我在整篇文章中不會提及腳本語言。 此外，我在本節中排除了 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）， 這意味著編譯器會假設溢位從未發生。 另一方面，無號數整數的溢位則被定義為回繞（wrap）。

接下來是 C#，我認為這是一種典型的「應用程式程式設計」語言， 用於不需要低階控制的場合。 C# 的型別命名與 C 類似：int、short、long 和 byte。 int 的寬度為 32 位元。 無號數版本則透過在型別前加上 u 來取得。 下標和大小使用普通的 int， 且預設情況下整數會在溢位時回繞。

Go 是 C# 同領域的一種現代替代語言。 在這裡我們看到一個趨勢的開始： Go 並非使用 C 風格的非直觀整數型別名稱， 而是直接在每個型別後附加位元寬度：int8、uint64 等。 另一個有趣的差異出現在 int 和 uint 的大小上： 它們與目標平台上的位址大小相符， 而非硬編碼為特定寬度。 同樣地，大小和下標使用 int。 Go 將整數溢位定義為回繞。

Swift 是這個「編譯式、靜態型別、非低階商業軟體」領域的另一種近期語言， 其整數型別在多方面與 Go 相似。 型別名稱與 Go 相同，只是大小寫不同：Int8、UInt64 等。 Int 和 UInt 的大小行為與 Go 相同， 且下標與大小都使用 Int。 有趣的是，Swift 預設即使在 release 建置中也會在整數溢位時 panic。

Rust: a better approach

你有注意到我上面列出的所有範例有一個共通點嗎？ 所有這些語言都有某種預設的 int 型別。 它們需要額外的輸入才能使用無號數型別而非有號數型別， 以及使用明確大小的型別而非預設大小的 int。 我認為這會鼓勵使用 int 而非其他型別。 畢竟：你會比較想盯著滿滿的 int，還是 uint32_t？ 這不僅僅是美觀問題。 輕鬆偷懶地輸入 int 而不加思考， 遠比仔細檢視使用情境以找出最適合該工作的型別要容易。

Rust 消除了上述所有問題： 所有整數型別都有明確的大小， 且所有型別都以前綴 i 或 u 來表示有號數或無號數。 沒有對特定大小或有無號數的偏好。 你被迫考慮情境，並判斷哪種型別最適合該情境。 也許可以透過縮小整數寬度來節省記憶體， 並透過讓無效值（負數）無法表示來防止錯誤—— 這是 Rust 社群經常引用的 dogma。

你可能會注意到這個表格中出現了 usize 和 isize。 usize 用於下標和大小，就像 C 中的 size_t 一樣。 與 C 不同的是，Rust 沒有隱式整數轉換， 因此你真的必須使用 usize 作為陣列索引 （除非你想淹沒在 as 轉換中）。 使用 usize 而非 32 位元的 int， 意味著陣列可以擁有超過二十億個元素， 而使用無號數型別則意味著永遠不會出現負的陣列索引。

Rust 在 debug 建置中會在溢位時 panic 以捕捉錯誤， 但在 release 建置中為了效能而使用回繞。 請注意，溢位時並不會產生 UB。

關於 Rust 不偏好特定整數型別的說法，有一個例外：

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

當 Rust 對整數字面值沒有型別資訊時，預設會使用 i32， 因此對有號數 32 位元整數有（雖然微小）的偏好。 不過根據我使用 Rust 的經驗，我發現自己很少使用有號數整數， 以至於我幾乎會提倡將無號數整數設為預設值。 如果 Rust 沒有將無號數和有號數整數放在平等的地位， 我可能永遠不會得出這個結論。

對我來說，所有這些改變似乎都是顯而易見的改進。

A Rust programmer tries other languages

當我開始嘗試 C#、Swift 和 Go 時， 我很快變得沮喪。 抱持著為任務挑選正確整數型別的態度， 我試圖在這些語言預設使用的有號數 int 之外， 到處使用 uint 作為陣列索引。 由於需要大量的轉換，這是不切實際的， 所以我沮喪地放棄了。 這讓我更加確信： 為什麼不是每種語言都有像 Rust 一樣的整數型別？

Why does C make signed integer overflow UB, anyway?

最初的原因是硬體行為的差異， 但今天你最常聽到的論點是效能。 但難道大多數 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++;

	// repeats several more times
}

編譯器足夠聰明，能夠消除 i1 和 i2 的變動。 位元組會直接從 block + i1 和 block + i2 載入， 然後是 block + i1 + 1 和 block + i2 + 1， 然後是 block + i1 + 2 和 block + i2 + 2， 依此類推。 這些位址計算是作為 load 指令的一部分完成的， 因此它們發生在 64 位元整數的空間內。

假設我們強制編譯器在溢位時回繞。 當 i1++; 和 i2++; 達到 32 位元整數的極限時會回繞。 為了確保執行時的行為與此回繞一致， 編譯器會產生額外的指令，使 block + i1 + n 在 i1 + n 溢位 32 位元時回繞到 block + 0。 換句話說，「CPU 免費提供溢位回繞」在這個情況下並不成立， 我們因此得到膨脹的程式碼。

這一切都不是假設的；將 i1 和 i2 設為無號數 也會導致這些額外指令的產生。 在演講中，Chandler 使用這段程式碼作為範例，說明 從無號數轉為有號數整數可以改善效能， 因為它讓編譯器能夠利用溢位時的 UB。 他甚至說：

if you have an integer which you want to treat arithmetically as opposed to in some modular space (on some power of two), Make. It. Signed. If you need more bits, get more bits. Keep it signed.

這讓我感到著迷。 你不是應該使用型別系統來防止錯誤嗎？ 如果一個數字永遠不可能是負數，為什麼還要讓它成為有號數？ Chandler 對這個問題的看法讓我感到不安。

A foray further into C

當我沉浸在使用 C 進行系統程式設計時， 我遇到好幾個人一直說， 即使索引不可能是負數，也應該使用有號數整數。 特別是，我讀了 三篇 不同的 文章， 都來自 Chris Wellons 的部落格， 它們都支持這個觀點：

In recent years I’ve been convinced that unsigned sizes were a serious error, probably even one of the great early computing mistakes, and that sizes and subscripts should be signed. Not only that, pkg-config has no business dealing with gigantic objects! We’re talking about short strings and tiny files. If it ends up with a large object, then there’s a defect somewhere — either in itself or the system — and it should abort. Therefore sizes and subscripts are a natural int!

看到引文中的連結嗎？ 它指向一份由 Bjarne Stroustrup 撰寫的簡短文件， 他也說大小和下標應該是有號數。 抱持著懷疑的態度和我基於 Rust 的先入為主觀念， 我並不覺得他的論點很有說服力。 儘管如此，我腦海中仍有一絲揮之不去的感覺： 這些人一定都有道理。

Looking at some C alternatives

Odin 是新興的 C 替代語言之一， 注重簡單性和「程式設計的樂趣」。 在對另一個 C 替代語言 Zig 進行了一些失敗的實驗後， 我決定更仔細地看看 Odin。

再次出現了熟悉的「現代語言」整數系統， 但有一些針對低階程式設計的調整：

• int 和 uint 是位址大小
• i8 到 i128 是有號數
• u8 到 u128 是無號數
• 明確大小的型別可以加上 le 或 be 後綴， 以使其記憶體中的表示為 little-endian 或 big-endian
• 大小和下標使用 int
• 溢位時回繞

這一次，我決定抱持開放的心態， 仔細看看這種設定可能帶來的好處。 以下的一些論點並非我原創， 但我不記得哪些是我從哪裡學來的，哪些是我自己的想法。

Address-sized is the perfect default size

如我們之前所見， 如果我們不願意讓溢位成為 UB， 混合使用指標和 32 位元整數可能會導致效能問題。 如果我們讓 i1 和 i2 的型別是 ptrdiff_t 或類似的型別， 則溢位時回繞就會運作得很好。 此外，像 A64 這樣的 ISA 只有 32 位元和 64 位元的算術指令， 因此對 8 位元和 16 位元整數進行運算需要額外的 and 指令。 在位址大小的整數上執行所有運算是通常的最佳選擇。

對此的一個反論點是，現代 CPU 通常受記憶體限制， 因此將資料結構打包得盡可能小是個好主意。 讓整數成為位址大小而非預設為 32 位元， 與這個目標背道而馳。 儘管如此，我認為能夠對陣列索引、大小、算術以及作為預設整數型別使用普通的 int 的簡單性， 勝過了必須記得在適當處使用 int32 的成本。

In release builds, wrapping on overflow is a fine tradeoff

如果所有被運算的整數都是位址大小， 讓溢位成為未定義行為並沒有好處2。 我寧願在函式開頭放幾個轉換， 也不願看到更多UB 定時炸彈等待爆炸。

鑑於溢位檢查有大約 30% 的額外開銷， 我認為將它們限制在 debug 建置中是合理的權衡。 我也能理解即使在 debug 建置中也使用回繞以求一致性和簡單性的論點。

Unsigned integers are unintuitive

假設你想從一個數字向下循環到零。 使用有號數整數這很簡單：

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， 並因此跳出迴圈。 真是糟糕。

Won't signed integers make bounds checks slower?

當使用有號數索引時執行邊界檢查， 需要同時檢查 0 <= i 和 i < count。 這兩個檢查彼此獨立， 因此現代 CPU 可以並行執行它們。 CPU 的 ALU 很少會飽和， 因此移除第一個檢查不太可能改變 邊界檢查所需的執行時間。

Unsigned integers are more bug-prone

假設我們有兩個陣列索引 i 和 j。 也假設對我們的使用情境而言， 在溢位時 panic 的開銷是無法接受的， 因此我們選擇在溢位時回繞。 我們想找出 i 和 j 之間有多少個元素， 並將它們複製到新陣列中。 很簡單，對吧？ 只需要 j - i 就能決定元素數量， 然後我們可以建立一個該大小的新陣列並執行複製。

想像一下，在我們的測試資料中 j 總是大於或等於 i， 但在正式環境中 j 卻小於 i。 如果 i 和 j 是無號數， j - i 會回繞成一個可能非常大的數字。 我們最終會建立一個那麼大的陣列； 如果我們幸運的話，複製操作有邊界檢查並會導致 panic。

重點是，無號數的 underflow 很難被捕捉： 你無法判斷一個大數字是因為回繞而錯誤產生， 還是其存在是有意的。 在這裡使用有號數整數意味著無效的 j - i 減法 會立即產生一個「中毒的」（負數）結果。 這個結果可以在用來建立陣列時立即被捕捉到， 而不是透過巨大數字不可預測的連鎖效應在稍後才被發現。

Won't signed integers require more asserts?

確實，為了捕捉到那個負的陣列大小， 我們的陣列配置程式碼需要有一個 assert(count > 0)。 然而，如果我們使用的是無號數整數， 要捕捉到它需要的遠不止一個 assert—— 我們需要為整個程式啟用全面的溢位檢查。

你可將使用有號數整數時需要加入的 assert 視為一種輕量級的溢位檢查形式。 與其在每一個算術運算之後檢查溢位， 我們只需在每個函式的開頭放置一個等效的檢查。 換句話說，大量的溢位檢查 已被合併為在 API 邊界處的單一檢查。

當然，單一個 assert(count > 0) 並不等同於徹底檢查各處的溢位。 例如，它不會捕捉到像 create_array(1000 + j - i) 之類的情況。 效能與安全性之間存在權衡， 我認為有號數整數搭配大量使用 assert 並在溢位時回繞， 是一個愉快的折衷方案。

Don't signed integers have a lower maximum value, so you'll need to use more bits?

我不同意這個說法。 假設我們在 64 位元平台上， 陣列中元素的數量被限制在 63 位元， 其實並不重要， 而且可能反而是件好事。 例如，Rust 將所有配置的大小限制 在有號數位址大小整數的最大值， 以便 ptr::offset(isize) 這類 API 可以運作。

對於較小的位元寬度， 例如我們為了精簡而使用 32 位元索引進入陣列， 失去一個位元並不會造成太大差別。 我不知道有任何應用程式會出現 最多二十億個元素不夠用，但四十億個就夠用的情況。

Luna Razzaghipour
14 September 2023