Начала с простого: 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 реализация стабильно проигрывала.
В конце сравнила оба варианта на 50k документов Simple Wikipedia:
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` - можно убрать кучу аллокаций и в итоге вообще не уменьшить размер хипа.#fts #projects #perf