Goブログ

新しいユニークパッケージ

Michael Knyszek
2024年8月27日

Go 1.23の標準ライブラリには、新しいuniqueパッケージが含まれるようになりました。このパッケージの目的は、比較可能な値の正規化を可能にすることです。言い換えれば、このパッケージを使用すると、値を重複排除して、単一の正規のユニークなコピーを指すようにし、同時に、内部で正規のコピーを効率的に管理できます。この概念は、「インターン」と呼ばれ、既に馴染みがあるかもしれません。どのように動作し、なぜ便利なのかを見ていきましょう。

インターンの簡単な実装

上位レベルでは、インターンは非常にシンプルです。通常のマップのみを使用して文字列の重複を排除する以下のコードサンプルをご覧ください。

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
}

これは、テキスト形式を解析する場合のように、重複する可能性の高い文字列を多数構築する場合に役立ちます。

この実装は非常にシンプルで、いくつかのケースでは十分に機能しますが、いくつかの問題があります。

• プールから文字列を削除することはありません。
• 複数のゴルーチンで同時に安全に使用することはできません。
• アイデアは非常に一般的ですが、文字列でのみ機能します。

この実装には、微妙ですが、見逃されている機会もあります。内部的には、文字列はポインタと長さで構成される不変の構造体です。2つの文字列を比較する場合、ポインタが等しくない場合、それらの内容を比較して等価性を判断する必要があります。ただし、2つの文字列が正規化されていることがわかっている場合は、ポインタを確認するだけで十分です。

uniqueパッケージを入力してください

新しいuniqueパッケージでは、Internに似たMakeと呼ばれる関数が導入されています。

これはInternとほぼ同じように機能します。内部にもグローバルマップ（高速な汎用コンカレントマップ）があり、Makeはそのマップで指定された値を検索します。ただし、2つの重要な点でInternとは異なります。第一に、任意の比較可能な型の値を受け入れます。第二に、正規の値を取得できるラッパー値であるHandle[T]を返します。

このHandle[T]が設計の鍵となります。 Handle[T]には、それらを作成するために使用された値が等しい場合にのみ、2つのHandle[T]値が等しいという特性があります。さらに、2つのHandle[T]値の比較は安価です。ポインタ比較に帰着します。2つの長い文字列を比較するのに比べて、桁違いに安価です！

これまでのところ、これは通常のGoコードではできないことではありません。

しかし、Handle[T]には第二の目的もあります。値のHandle[T]が存在する限り、マップはその値の正規のコピーを保持します。特定の値にマップするすべてのHandle[T]値がなくなると、パッケージはその内部マップエントリを削除可能としてマークし、近い将来に再利用できるようにします。これにより、マップからエントリをいつ削除するかについての明確なポリシーが設定されます。正規エントリが使用されなくなると、ガベージコレクターはそれらを自由にクリーンアップできます。

以前にLispを使用したことがある場合、これはすべて非常に馴染みがあるかもしれません。Lispのシンボルはインターンされた文字列ですが、文字列自体ではなく、すべてのシンボルの文字列値は同じプールにあることが保証されています。シンボルと文字列の関係は、Handle[string]とstringの関係と似ています。

実際の例

では、どのようにunique.Makeを使用するのでしょうか？標準ライブラリのnet/netipパッケージ以外に目を向ける必要はありません。このパッケージは、netip.Addr構造体の一部であるaddrDetail型の値をインターンします。

以下は、uniqueを使用するnet/netipの実際のコードの省略バージョンです。

// 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アドレスが同じゾーンを使用する可能性が高く、このゾーンはそれらのIDの一部であるため、それらを正規化することは非常に理にかなっています。ゾーンの重複排除により、各netip.Addrの平均メモリフットプリントが削減されます。また、ゾーン名が正規化されているため、ゾーン名の比較が単純なポインタ比較になるため、netip.Addr値の比較がより効率的になります。

文字列のインターンに関する脚注

uniqueパッケージは便利ですが、Handle[T]は文字列を内部マップから削除されないようにするために必要であるため、Makeは文字列のInternとは少し異なります。つまり、文字列だけでなくハンドルも保持するようにコードを変更する必要があります。

しかし、文字列は、値のように動作しますが、前述したように、実際には内部にポインタが含まれているという点で特別です。これは、文字列自体の内部にHandle[T]の詳細を隠蔽することで、文字列の基盤となるストレージのみを正規化できる可能性があることを意味します。そのため、将来においても、私が*透過的な文字列インターン*と呼ぶものの場所があります。このインターンでは、Intern関数と似ていますが、セマンティクスはMakeに似ており、Handle[T]型なしで文字列をインターンできます。

その間、unique.Make("my string").Value()は1つの可能な回避策です。ハンドルを保持しないことで文字列がuniqueの内部マップから削除される可能性がありますが、マップエントリはすぐに削除されません。実際には、少なくとも次のガベージコレクションが完了するまでエントリは削除されないため、この回避策では、コレクション間の期間に程度の重複排除が可能です。

いくつかの歴史、そして未来に向けて

実際には、net/netipパッケージは、最初に導入されて以来、ゾーン文字列をインターンしていました。使用していたインターンパッケージは、go4.org/internパッケージの内部コピーでした。 uniqueパッケージと同様に、Value型（Handle[T]によく似ていますが、ジェネリクスより前）があり、ハンドルが参照されなくなると内部マップのエントリが削除されるという注目すべき特性があります。

しかし、この動作を実現するには、安全でないことを行う必要があります。特に、 *弱ポインタ*をランタイム外に実装するために、ガベージコレクターの動作についていくつかの仮定を立てています。弱ポインタとは、ガベージコレクターが変数を再利用するのを妨げないポインタです。これが発生すると、ポインタは自動的にnilになります。偶然にも、弱ポインタはuniqueパッケージの基盤となるコア抽象化でもあります。

そうです。uniqueパッケージを実装しているときに、ガベージコレクターに適切な弱ポインタサポートを追加しました。そして、弱ポインタに伴う残念な設計上の決定（弱ポインタはオブジェクトの復活を追跡する必要がありますか？いいえ！）の地雷原を通り抜けた後、すべてがどれほどシンプルで簡単になったかに驚かされました。弱ポインタが公開提案になったほど驚きました。

この作業により、ファイナライザーを再検討することになり、使いやすく、より効率的なファイナライザーの代替案の別の提案が生まれました。比較可能な値のハッシュ関数も登場し、Goでメモリ効率の高いキャッシュを構築する未来は明るいです！