Перевод/заметки New unique package


В стандартную библиотеку Go 1.23 добавили новых пакет unique. Цель этого пакета - позволить канонизировать сравниваемые(comparable) значения. Другими словами, этот пакет позволяет вам убрать дубли значений так, чтобы они указывали на единственную, каноническую, уникальную копию, при этом эффективно управляя каноническими копиями под капотом. Возможно, вы уже знакомы с этой концепцией, которая называется “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
}

Это полезно, когда вы создаете много строк, которые, скорее всего, будут дублироваться, например, при разборе текстового формата.

Эта реализация очень проста и работает достаточно хорошо в некоторых случаях, но у нее есть несколько проблем:

  • Она никогда не удаляет строки из пула.
  • Она не может безопасно использоваться несколькими горутинами одновременно.
  • Она работает только со строками, хотя идея довольно общая.

В этой реализации также есть упущенная возможность, и она очень тонкая. Под капотом строки представляют собой неизменяемые структуры, состоящие из указателя и длины. При сравнении двух строк, если указатели не равны, мы должны сравнить их содержимое, чтобы определить равенство. Но если мы знаем, что две строки канонизированы, то достаточно просто проверить их указатели.

Рассмотрим пакет unique

В новом пакете unique появилась функция, похожая на Intern, под названием Make.

Он работает примерно так же, как и Intern. Внутри также есть глобальная map (a fast generic concurrent map), а Make ищет в ней значения. Но он также отличается от Intern двумя важными особенностями. Во-первых, он принимает значения любого comparable типа. А во-вторых, он возвращает обертку значения, Handle[T], из которой можно получить каноническое значение.

Этот Handle[T] является ключевым для дизайна. Handle[T] обладает тем свойством, что два значения Handle[T] равны тогда и только тогда, когда равны значения, использованные для их создания. Более того, сравнение двух значений Handle[T] является недорогим: оно сводится к сравнению указателей. По сравнению со сравнением двух длинных строк это на порядок дешевле!

Пока что в этом нет ничего такого, что нельзя было бы сделать в обычном коде Go.

Но у Handle[T] есть и второе назначение: пока существует Handle[T], в map будет храниться каноническая копия его значения. Как только все переменные Handle[T], сопоставляемые с определенным значением, исчезают, пакет помечает эту внутреннюю запись map как удаляемую, которая будет освобождена в ближайшем будущем. Это задает четкую политику удаления записей из map: когда канонические записи больше не используются, сборщик мусора может их очистить.

Если вы уже использовали Lisp, все это может показаться вам довольно знакомым. symbols в Lisp являются interned строками, но не самими строками, и все строковые значения символов гарантированно находятся в одном и том же пуле. Эти отношения между символами и строками похожи на отношениям между Handle[string] и string.

Пример из реальной жизни

Как же можно использовать unique.Make? Посмотрите на пакет net/netip в стандартной библиотеке, в котором хранятся значения типа 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-адреса, скорее всего, используют одну и ту же зону, и эта зона является частью их идентификации, имеет смысл канонизировать их. Дедупликация зон уменьшает средний объем памяти каждого netip.Addr, а тот факт, что они канонизированы, означает, что значения netip.Addr более эффективны для сравнения, поскольку сравнение имен зон становится простым сравнением указателей.

Заметка о interning строках

Хотя пакет unique полезен, Make, по общему признанию, не совсем похож на Intern для строк, поскольку Handle[T] требуется для того, чтобы строка не была удалена из внутренней map. Вам нужно изменить свой код, чтобы он сохранял handles и строки.

Но строки особенны тем, что, хотя они ведут себя как значения, на самом деле они содержат указатели под капотом. Это означает, что потенциально мы можем канонизировать только базовое хранилище строки, скрывая детали Handle[T] внутри самой строки. Таким образом, в будущем все еще есть место тому, что я назову transparent string interning, когда строки могут быть interned без типа Handle[T], аналогично функции Intern, но с семантикой, более близкой к Make.

Тем временем unique.Make("my string").Value() является одним из возможных обходных путей. Даже если не удастся сохранить handle, строка будет удалена из внутренней map, записи map не удаляются немедленно. На практике записи не будут удалены, по крайней мере, до следующей сборки мусора, так что этот обходной путь все еще позволяет обеспечить некоторую степень дедупликации в периоды между сборками.

Немного истории и перспективы

Дело в том, что пакет net/netip на самом деле использует interned строки с момента своего появления. Пакет interned, который он использовал, был внутренней копией пакета go4.org/intern. Как и пакет unique, он имеет тип Value (который очень похож на Handle[T], до дженериков) и обладает тем примечательным свойством, что записи во внутренней map удаляются, когда на их handles больше нет ссылок.

Но чтобы добиться такого поведения, ему приходится делать некоторые небезопасные вещи. В частности, он делает некоторые предположения о поведении сборщика мусора, чтобы реализовать weak pointers вне runtime. weak pointer - это указатель, который не мешает сборщику мусора вернуть переменную; когда это происходит, указатель автоматически становится nil. Так получилось, что слабые указатели также являются основной абстракцией, лежащей в основе пакета unique.

Именно так: реализуя пакет unique, мы добавили в сборщик мусора поддержку слабых указателей. И пройдя через минное поле дизайнерских решений, сопровождающих слабые указатели (например, должны ли слабые указатели отслеживать object resurrection? Нет!), мы были поражены тем, насколько все это оказалось простым и понятным. Удивлены настолько, что слабые указатели теперь являются public proposal.

Эта работа также заставила нас задуматься о финализаторах. Нам пришла в голову идея, как их лучше заменить. Благодаря новой хэш-функции для comparable значений у Go большое будущее в создании memory-efficient caches!


Комментарии в Telegram-группе!