У Алексея Кладова есть пост про реализацию интернирования строк (советую прочитать перед моим постом). Как он замечает, простейший способ интернировать строки — через такой тип:
struct Interner {
map: HashMap<String, u32>,
vec: Vec<String>,
}Новые строки добавляются через вставку в
map, а идентификатор строк создаётся от длины vec на момент добавления. map позволяет быстро проверить, была ли строка записана, а vec позволяет быстро получить строку по её идентификатору.Недостаток такого решения очевиден: каждая строка выделяется в куче дважды. Особенно это печально в связи с тем, что строки часто интернируют именно для того, чтобы сэкономить память, выделяя её только единожды на каждое значение. Алексей решает это тем, что выделяет память по возможности одним куском в одной
String и хранит в мапе &str на эту память с принудительно приведённым к 'static временем жизни. Инвалидацию ссылок он обходит остроумным приёмом: при нехватке ёмкости он выделяет новый буфер, вдвое больше предыдущего, и записывает новые строки туда, а старый буфер переносит в отдельный вектор. Он эксплуатирует тот факт, что адреса выделенной в куче памяти стабильны и не меняются при перемещении String. С таким дизайном определение структуры данных выглядит так:struct Interner {
map: HashMap<&'static str, u32>,
vec: Vec<&'static str>,
// новые строки записывают сюда
buf: String,
// буферы с недостаточной памятью переносят сюда
full: Vec<String>,
}К сожалению, у этого дизайна есть несколько недостатков.
* Выдаваемые
Interner идентификаторы не самодостаточны: всё ещё нужно обращаться к пулу, если нам потребуется содержимое строки. Пул при этом можно перепутать* Из-за индексации каждый лукап — потенциальная паника.
* Идентификаторы никак не привязаны к пулу временами жизни: если мы создадим пул, выделим строку, дропнем пул, создадим заново и снова выделим строку, то возвращённые значения будут считаться равными — что технически верно, но не вполне корректно.
* Можно сравнивать идентификаторы, полученные от двух разных пулов, и получить как и ложно-положительные, так и ложно-отрицательные результаты, и компилятор вообще никак от этого не защищает.
* Очень нишевый недостаток:
u32 не имеет ниши и потому не получает null pointer optimization при оборачивании в Option. Это, в принципе, решаемо оборачиванием в NonNull<u32>, но не очень удобно из-за инкремента при генерации и декремента при индексации.* Количество потребляемой таки пулом памяти может только расти, явное переиспользование памяти невозможно. Это может быть важно, если нам требуется многократно использовать пул в ограниченной области действия.
От всех этих недостатков можно избавиться, используя два решения.
Первый из них заключается в трюке, используемом в thin_vec: вместо того, чтобы хранить длину аллокации отдельно, выделять дополнительную память в куче и хранить в начале длину строки. Сами интернированные строки будут хранить указатель на начало аллокации и создавать толстый указатель на строку по требованию. Это даёт несколько преимуществ:
* Выдаваемые идентификаторы могут быть переведены в строки без обращения к пулу — его не надо держать под рукой и получение строки не может паниковать.
* К создаваемой строке можно (на самом деле нужно, для корректности) привязать время жизни. Это позволяет избежать ошибок со случайным переиспользованием строк и до какой-то степени защищает от сравнения строк из разных пулов.
* Указатель имеет естественную нишу в виде null и потому получает оптимизацию раскладки
Option.Второе решение заключается в том, чтобы использовать bump-аллокатор — в данном случае bumpalo. Он даёт гарантии стабильности адресов, а внутри использует тот же трюк с удваиваемыми буферами, который нам не надо повторять самостоятельно. Дополнительно он позволяет скопом освобождать память, сохраняя при этом аллокацию последнего буфера, что позволяет уменьшить потребление памяти и обращение к аллокатору и закрыть таким образом последний недостаток решения Кладова.
Что ж, приступим к реализации!