Go 部落格

新的 unique 包

Michael Knyszek
2024 年 8 月 27 日

Go 1.23 的標準庫現在包含了 新的 unique 包。這個包的目的是實現可比較值的規範化（canonicalization）。換句話說，這個包允許您去除重複值，使它們指向一個唯一的規範副本，同時在內部高效地管理這些規範副本。您可能已經熟悉這個概念，它被稱為“interning”。讓我們深入瞭解它是如何工作的以及為何有用。

interning 的簡單實現

從高層面看，interning 非常簡單。請看下面的程式碼示例，它僅使用一個普通的 map 來去除字串重複。

var internPool map[string]string

// Intern returns a string that is equal to s but that may share storage with
// a string previously passed to Intern.
func Intern(s string) string {
    pooled, ok := internPool[s]
    if !ok {
        // Clone the string in case it's part of some much bigger string.
        // This should be rare, if interning is being used well.
        pooled = strings.Clone(s)
        internPool[pooled] = pooled
    }
    return pooled
}

這對於構建大量可能重複的字串時很有用，例如解析文字格式時。

這個實現超級簡單，對於某些情況來說效果不錯，但它有一些問題

• 它從不從池中移除字串。
• 它不能被多個 goroutines 併發安全地使用。
• 它只適用於字串，儘管這個想法非常普遍。

這個實現還有一個被忽略的機會，而且很微妙。在底層，字串是不可變結構，由一個指標和長度組成。當比較兩個字串時，如果指標不相等，那麼我們必須比較它們的內容來確定是否相等。但是如果我們知道兩個字串已經規範化（canonicalized），那麼只檢查它們的指標就足夠了。

引入 unique 包

新的 unique 包引入了一個與 Intern 類似名為 Make 的函式。

它的工作方式與 Intern 大致相同。內部也有一個全域性 map (一個快速的泛型併發 map)，並且 Make 在該 map 中查詢提供的值。但它與 Intern 在兩個重要方面有所不同。首先，它接受任何可比較型別的值。其次，它返回一個包裝值，一個 Handle[T]，從中可以檢索規範值。

這個 Handle[T] 是設計的關鍵。一個 Handle[T] 具有這樣的特性：當且僅當用於建立它們的原始值相等時，兩個 Handle[T] 值才相等。更重要的是，比較兩個 Handle[T] 值非常廉價：它歸結為指標比較。與比較兩個長字串相比，這要便宜一個數量級！

到目前為止，這些都是您可以在普通 Go 程式碼中完成的事情。

但 Handle[T] 還有第二個作用：只要某個值存在一個 Handle[T] 引用，map 就會保留該值的規範副本。一旦所有指向特定值的 Handle[T] 值都不再存在，該包會將該內部 map 條目標記為可刪除，以便在不久的將來被回收。這為何時從 map 中移除條目設定了明確的策略：當規範條目不再被使用時，垃圾收集器就可以自由地將其清理掉。

如果您以前使用過 Lisp，這可能聽起來非常熟悉。Lisp 符號 (symbols) 是 interned 字串，但它們本身不是字串，並且所有符號的字串值都保證在同一個池中。符號和字串之間的這種關係，類似於 Handle[string] 和 string 之間的關係。

一個真實的例子

那麼，如何使用 unique.Make 呢？標準庫中的 net/netip 包就是一個很好的例子，它對型別為 addrDetail 的值進行了 interning，addrDetail 是 netip.Addr 結構體的一部分。

下面是 net/netip 中使用 unique 的實際程式碼的節選版本。

// Addr represents an IPv4 or IPv6 address (with or without a scoped
// addressing zone), similar to net.IP or net.IPAddr.
type Addr struct {
    // Other irrelevant unexported fields...

    // Details about the address, wrapped up together and canonicalized.
    z unique.Handle[addrDetail]
}

// addrDetail indicates whether the address is IPv4 or IPv6, and if IPv6,
// specifies the zone name for the address.
type addrDetail struct {
    isV6   bool   // IPv4 is false, IPv6 is true.
    zoneV6 string // May be != "" if IsV6 is true.
}

var z6noz = unique.Make(addrDetail{isV6: true})

// WithZone returns an IP that's the same as ip but with the provided
// zone. If zone is empty, the zone is removed. If ip is an IPv4
// address, WithZone is a no-op and returns ip unchanged.
func (ip Addr) WithZone(zone string) Addr {
    if !ip.Is6() {
        return ip
    }
    if zone == "" {
        ip.z = z6noz
        return ip
    }
    ip.z = unique.Make(addrDetail{isV6: true, zoneV6: zone})
    return ip
}

由於許多 IP 地址很可能使用相同的區域（zone），並且這個區域是它們標識的一部分，因此對其進行規範化非常有意義。對區域進行去重減少了每個 netip.Addr 的平均記憶體佔用，而它們被規範化這一事實意味著 netip.Addr 值比較起來更高效，因為比較區域名稱變成了簡單的指標比較。

關於 interning 字串的附註

雖然 unique 包很有用，但必須承認，對於字串來說，Make 與 Intern 不完全相同，因為需要 Handle[T] 來防止字串從內部 map 中刪除。這意味著您需要修改程式碼來同時保留 handles 和字串。

但字串是特殊的，儘管它們表現得像值，但如我們之前提到的，它們在底層實際上包含指標。這意味著我們有可能只對字串的底層儲存進行規範化，將 Handle[T] 的細節隱藏在字串本身內部。因此，未來仍然有我稱之為透明字串 interning 的空間，在這種機制下，字串可以在沒有 Handle[T] 型別的情況下進行 interning，類似於 Intern 函式，但語義更接近 Make。

同時，unique.Make("my string").Value() 是一個可能的臨時解決方案。儘管未能保留 handle 會導致字串可以從 unique 的內部 map 中刪除，但 map 條目不會立即被刪除。實際上，條目至少要等到下一次垃圾回收完成才會刪除，因此這個臨時解決方案在垃圾回收之間的時間段內仍然可以在一定程度上實現去重。

一些歷史，以及展望未來

事實是，net/netip 包從最初引入時就對區域字串進行了 interning。它使用的 interning 包是 go4.org/intern 包的內部副本。與 unique 包一樣，它有一個 Value 型別（看起來很像泛型之前的 Handle[T]），其顯著特點是：一旦其 handles 不再被引用，內部 map 中的條目就會被移除。

但為了實現這種行為，它必須做一些不安全的事情。特別是，它對垃圾收集器的行為做了一些假設，以便在執行時外部實現 弱引用 (weak pointers)。弱引用是一種不會阻止垃圾收集器回收變數的指標；當回收發生時，該指標會自動變成 nil。巧合的是，弱引用也是 unique 包的核心抽象。

沒錯：在實現 unique 包的同時，我們在垃圾收集器中添加了適當的弱引用支援。在經歷了一系列與弱引用相關的令人遺憾的設計決策雷區之後（比如，弱引用是否應該跟蹤物件復活？不！），我們驚訝地發現這一切竟然如此簡單明瞭。這種驚訝程度足以讓弱引用現在成為一個公開提案。

這項工作還促使我們重新審視 finalizers，從而提出了另一個更容易使用且更高效的finalizers 替代方案的提案。隨著可比較值的雜湊函式也即將推出，Go 中構建記憶體高效快取的未來一片光明！