新しいuniqueパッケージ

New unique package by Michael Knyszek

Go 1.23の標準ライブラリには、新しいuniqueパッケージが追加されました。このパッケージの目的は、比較可能な値の正規化（canonicalization）を可能にすることです。言い換えると、このパッケージを使うと、値を重複排除して単一の正規化された唯一のコピーを指すようにしつつ、その正規化されたコピーを裏側で効率的に管理できます。この概念にはすでに馴染みがあるかもしれません。それは「インターニング（interning）」と呼ばれるものです。それでは、実際にどのように動作するのか、そしてなぜ有用なのかを見ていきましょう。

インターニングの単純な実装

大まかに言うと、インターニングは非常に単純です。以下のコード例を見てください。これは普通のマップだけを使って文字列を重複排除しています。

var internPool map[string]string

// Intern はsと等しい文字列を返しますが、それは以前にInternに渡された文字列と
// ストレージを共有している場合があります。
func Intern(s string) string {
    pooled, ok := internPool[s]
    if !ok {
        // 巨大な文字列の一部である場合に備えて文字列をクローンする。
        // インターニングがうまく使われていれば、これは稀なはずです。
        pooled = strings.Clone(s)
        internPool[pooled] = pooled
    }
    return pooled
}

これは、テキスト形式をパースするときのように、重複する可能性が高い文字列を大量に構築する場合に便利です。

この実装はきわめて単純で、いくつかのケースでは十分に機能しますが、次のようないくつかの問題があります。

プールから文字列が削除されることは決してありません。
複数のゴルーチンから同時に安全に使用することはできません。
この発想自体はかなり汎用的であるにもかかわらず、文字列に対してしか機能しません。

またこの実装には、見落とされがちですが、活かしきれていない機会もあります。裏側では、文字列はポインタと長さからなる不変の構造体です。 2つの文字列を比較するとき、ポインタが等しくなければ、内容を比較して等価性を判定しなければなりません。しかし、2つの文字列が正規化されているとわかっていれば、ポインタを確認するだけで十分です。

uniqueパッケージの登場

新しいuniqueパッケージは、Internによく似たMakeという関数を導入しています。

動作はInternとほぼ同じです。内部にはグローバルなマップ（高速な汎用の並行マップ）があり、 Makeは渡された値をそのマップの中から検索します。しかし、Internとは2つの重要な点で異なります。 1つ目は、任意の比較可能な型の値を受け付けることです。 2つ目は、ラッパー値であるHandle[T]を返し、そこから正規化された値を取り出せることです。

このHandle[T]がこの設計の要です。 Handle[T]は、2つのHandle[T]の値が等しくなるのは、それらの生成に使われた値が等しい場合に限られるという性質を持ちます。さらに、2つのHandle[T]の値の比較は安価です。結局のところポインタ比較に帰着するからです。長い文字列同士を比較するのに比べれば、これは桁違いに安価です。

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

しかしHandle[T]にはもう1つの目的があります。ある値に対するHandle[T]が存在し続けている限り、マップはその値の正規化されたコピーを保持し続けます。特定の値にマップされるすべてのHandle[T]の値がなくなると、このパッケージは内部のマップのエントリを削除可能としてマークし、近い将来に回収します。これによって、マップからエントリをいつ削除するかについて明確な方針が定まります。正規化されたエントリが使われなくなったら、ガベージコレクタが自由にそれらを片付けられるということです。

もしLispを使ったことがあるなら、これはどれもかなり馴染み深く聞こえるかもしれません。 Lispのシンボルはインターニングされた文字列であって、文字列そのものではありません。そしてすべてのシンボルの文字列としての値は、同じプールに存在することが保証されています。このシンボルと文字列の関係は、Handle[string]とstringの関係に対応しています。

実例

では、unique.Makeはどのように使えばよいのでしょうか。それを知るには標準ライブラリのnet/netipパッケージを見るだけで十分です。このパッケージは、netip.Addr構造体の一部であるaddrDetail型の値をインターニングしています。

以下は、uniqueを使っているnet/netipの実際のコードを抜粋したものです。

// AddrはIPv4またはIPv6アドレス(スコープ付きアドレッシングゾーンの有無を問わず)を表します。
// net.IPやnet.IPAddrに似ています。
type Addr struct {
    // その他の無関係な非公開フィールド...

    // アドレスに関する詳細情報。まとめて正規化されている。
    z unique.Handle[addrDetail]
}

// addrDetailは、アドレスがIPv4かIPv6かを示し、IPv6の場合はそのアドレスの
// ゾーン名を指定します。
type addrDetail struct {
    isV6   bool   // IPv4の場合はfalse、IPv6の場合はtrue。
    zoneV6 string // IsV6がtrueの場合、""以外の値になることがある。
}

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

// WithZoneは、ipと同じだが指定されたzoneを持つIPを返します。zoneが空の場合、
// ゾーンは削除されます。ipがIPv4アドレスの場合、WithZoneは何もせずにipを
// そのまま返します。
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アドレスは同じゾーンを使う可能性が高く、しかもこのゾーンはそのアドレスのアイデンティティの一部であるため、それらを正規化するのは実に理にかなっています。ゾーンを重複排除することで、それぞれのnetip.Addrの平均的なメモリフットプリントが削減されます。また正規化されていることで、ゾーン名の比較が単純なポインタ比較になるため、netip.Addrの値をより効率的に比較できます。

文字列のインターニングについての補足

uniqueパッケージは便利ですが、正直なところMakeは文字列に対するInternとまったく同じというわけではありません。というのも、文字列を内部のマップから削除されないようにするには、Handle[T]を保持しておく必要があるからです。つまり、文字列だけでなくハンドルも保持するようにコードを変更する必要があるのです。

しかし文字列は特殊です。文字列は値のように振る舞いますが、先ほど触れたとおり、実際には裏側にポインタを持っています。これはつまり、文字列の背後にあるストレージだけを正規化し、Handle[T]の詳細を文字列そのものの中に隠してしまうことも潜在的には可能だということです。したがって、私が「透過的な文字列インターニング」と呼ぶものには、将来的にまだ活躍の場があります。これは、Intern関数に似ていながらもMakeに近いセマンティクスを持ち、Handle[T]型を使わずに文字列をインターニングできるというものです。

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

歴史の話と将来への展望

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

しかしこの振る舞いを実現するには、いくらか安全でないことをする必要がありました。具体的には、ランタイムの外側で弱いポインタ（weak pointer）を実装するために、ガベージコレクタの振る舞いについていくつかの前提を置いていたのです。弱いポインタとは、ガベージコレクタが変数を回収するのを妨げないポインタのことです。回収が起きると、そのポインタは自動的にnilになります。実のところ、弱いポインタはuniqueパッケージの根底にある中心的な抽象化でもあります。

そうなのです。uniqueパッケージを実装する過程で、私たちはガベージコレクタにきちんとした弱いポインタのサポートを追加しました。そして弱いポインタに付きまとう後悔しがちな設計判断という地雷原（たとえば、弱いポインタはオブジェクトの復活（object resurrection）を追跡すべきかといった問題です。答えは「いいえ」です）を一歩ずつ潜り抜けたあと、私たちはそのすべてが驚くほど単純で素直なものだったことに驚かされました。あまりに驚いたので、弱いポインタは今では公開プロポーザルにもなっています。

この作業はまた、ファイナライザを再検討するきっかけにもなり、その結果として、より使いやすく効率的なファイナライザの置き換えについてもう一つのプロポーザルが生まれました。比較可能な値に対するハッシュ関数も間もなく登場する予定であることを踏まえると、 Goでメモリ効率の良いキャッシュを構築する未来は明るいと言えるでしょう!

By Michael Knyszek