Оптимизация индексов: fast append и first+rest

Недавно @dmedovich добавил в движок flat inverted index под данные с высокой кардинальностью и даже написал отдельную статью про его устройство и оптимизации. Мое дело, конечно, найти, что из этого имеет смысл перенести в мои существующие индексаторы HAMT/radix. Потому что заинтересовала меня не столько хешмапа, на которой строится индекс, сколько обвязка вокруг нее. Начала с простого: fast append для списка документов. У каждого слова есть список доков, где оно содержится (postings). Эти postings отсортированы по внутреннему числовому индексу документа (ordinal). При обычной индексации ordinal почти всегда инкрементится по возврастанию: 1, 2, 4, 7, 8... Ранее для вставки, например, документа с ordinal 6, требовалось проходится бинарным поиском по всему срезу ordinals для поиска индекса между 4 и 7. Но в типичном случае новый ordinal просто больше последнего, поэтому сначала можно проверить хвост (подробнее):

 last := len(d) - 1

 // Если last документ совпадает с добавляемым - просто увеличиваем частоту.
 if last >= 0 && d[last].Ord == ord {
  d[last].Count++
  return d
 }

 // Новый документ
 if last < 0 || ord > d[last].Ord {
  return append(d, fts.DocRef{
   Ord:   ord,
   Count: 1,
  })
 }

 // Док с индексом в середине, ищем нужное место по бин поиску
 i := sort.Search(len(d), func(i int) bool {
  return d[i].Ord >= ord
 })
}

Получился быстрый путь для вставки доков с фоллбеком на бинпоиск. Добавила это оптимизацию в итоге и в HAMT, и в radix. Вторая идея: fast + rest для списка postings Допустим,`rare-word` терм встретился только в одном документе:

rare-word -> [doc 42]

В обычном HAMT список документов хранится в cлайсе []Posting. Даже ради одного дока 42 создаётся слайc и все ему сопутствующее, в котором лежит этот единственный posting. Таких редких термов в высококардинальных данных может быть очень много. Идея first + rest в том, чтобы первый posting хранить прямо внутри entry:

type postings struct {
    first Posting
    rest  []Posting
}

Тогда для term, который встретился только в одном документе (`df=1`), first содержит этот документ, а rest остаётся ниловым. Если term встретился ещё раз, следующие документы уже складываются в rest:

df=1:  first=[42]  rest=nil
df=3:  first=[42]  rest=[57, 81]

Для данных, где df=1 термов очень много, можно скосить по аллокации. Но мой HAMT - скорее индекс общего назначения, поэтому мне было интересно, что будет по бенчам на обычном тексте. Для начала прогнала тест на 4096 синтетических термов.

HAMT        22433 allocs/op
HAMT-first  18337 allocs/op

Ожидаемо, разница ровно 4096 - исчезло по одной аллокации на каждый терм. Но B/op почти не изменился: массивы мы убрали, зато увеличили структуру entry за счет поля first. Дальше был Zipf тест, где одновременно есть редкие, среднечастотные и частые слова. Там HAMT-first уже стабильно проигрывал по build. Получилось примерно следующее:

build          +0.6% у HAMT-first
heap           610.3 -> 611.5 MB
heap objects   -4.6%

term search    -2.4%
boolean        ≈ одинаково
phrase         +0.9%

То есть first + rest делает свое дела за счет уменьшения количества маленьких heap-объектов. Но на обычных запросах это не дало ни меньшего retained heap, ни ускорения поиска. Получается, цена фичи - это оптимизация df=1, но поле first появляется у каждого терма - в том числе у тех, у которых есть появления в куче других документов. Плюс надо будет работать с разделением first/rest, что как-никак влияет на читаемость. Поэтому HAMT индекс с first+rest я решила не оставлять. Но сама идея вполне рабочая. Просто, кажется, ей действительно подходит отдельный хешмап индекс, где df=1 - основное свойство данных (например, логи), а не частный случай внутри универсального текстового индекса по обычным докам (например статьям). Ну и я поняла, что недостаточно смотреть только на`allocs/op` - можно убрать кучу аллокаций и в итоге вообще не уменьшить размер хипа.