Оптимизация Go map{-}{-}

Введение

Хеш-таблица(мапа) — одна из самых популярных структур данных, потому что поиск по ключу происходит за O(1). Причем ключ может быть любым любым типом, элементы которого можно сравнивать (Comparable Trait).

Я столкнулся с тем, что мапа не такая быстрая по бенчмаркам на языке GO, хотя теоретическая сложность алгоритма О(1).

Давайте рассмотрим следующую задачу и способы ее решения.

Задача

У людей есть какие-то национальности, и национальностей может быть несколько у одного человека. Определить все национальности группы людей, при условии того, что нас интересуют только конкретные национальности(не все).

Дано:

1. Национальности людей. Пример: u1:{n1,n2,n3}, u2:{n1}, u4:{n3}, u5:{n2}, u6:{n1}

2. Национальности, которые нам нужны. Пример: cfgNs:{n1,n2,n5}

Найти:
Национальности группы людей nationalities(group{u1,u2,u3,u4,u5}).
Ответ на пример: {n1,n2}.

Решения будут представлены на языке Go.

Решения

1. Стандартное решение задачи

Для каждого человека из группы по всем национальностям поверяем вхождение человека в данную национальность. Сложность O(n*m).

type ( NationID uint64 PersonID uint64 )  type Calc struct { cfgNs    []NationID                         // интересующие национальности n2people map[NationID]map[PersonID]struct{} // связь национальность -> люди }  func (c *Calc) Nationalities(group []PersonID) map[NationID]struct{} { res := make(map[NationID]struct{})  for _, n := range c.cfgNs { // для интересующих национальностей nPeople, ok := c.n2people[n] // люди, имеющие данную национальность if !ok { continue }  // для каждого человека из компании for _, person := range group { // добавляем в результат, если человек есть в этой группе if _, ok := nPeople[person]; ok { res[n] = struct{}{} break } } }  return res } 

Результат бенчмарка(Apple M1 Pro):

1297513           918.9 ns/op     520 B/op       5 allocs/op

Попробуем оптимизировать.

2. Оптимизация_1

Можно заметить, что национальностей, которые нам нужны, не так много (около 30), и тогда набор групп можно заменить на битовую маску.

type ( bitmask   uint64 NationIDs bitmask )  type CalcOptimized1 struct { cfgNs NationIDs              // интересующие национальности p2ns  map[PersonID]NationIDs // человек -> национальности }  func (c *CalcOptimized1) Nationalities(group []PersonID) NationIDs { var res NationIDs  for _, person := range group { res |= c.p2ns[person] }  res &= c.cfgNs  return res } 

Результат бенчмарка(Apple M1 Pro):

13790236          86.22 ns/op       0 B/op       0 allocs/op

Результат весьма и весьма хорош (выигрыш в 10.65 раз). Но мы пойдем дальше.

3. Оптимизация_2

Можно заметить, что мапа у нас специализированная: int -> int. И тогда ее можно заменить на быструю имплементацию intmap.

import "github.com/kamstrup/intmap"  type CalcOptimized2 struct { cfgNs NationIDs                        // интересующие национальности p2ns  *intmap.Map[PersonID, NationIDs] // человек -> национальности }  func (c *CalcOptimized2) Nationalities(group []PersonID) NationIDs { var res NationIDs  for _, person := range group { res |= mapGet(c.p2ns, person) }  res &= c.cfgNs  return res } 

Результат следующий(Apple M1 Pro):

32768679          36.69 ns/op       0 B/op       0 allocs/op

Получили выйгрыш еще в 2.34 раза (в 25 раз от первоначального). Пойдем дальше?

4. Оптимизация_3′

Можно заменить мапу на массив, если пользователей не так много, но тогда память будет расти с количеством пользователей, что не очень хорошо, поэтому эту оптимизацию лучше применять с осторожностью.

type CalcOptimized3Risky struct { cfgNs       NationIDs   // интересующие национальности p2ns        []NationIDs // человек -> национальности maxPersonID PersonID }  func (c *CalcOptimized3Risky) Nationalities(group []PersonID) NationIDs { var res NationIDs  for _, person := range group { if person <= c.maxPersonID { res |= c.p2ns[person] } }  res &= c.cfgNs  return res } 

Результат (Apple M1 Pro):

100000000         10.51 ns/op       0 B/op       0 allocs/op

Получили выйгрыш еще в 3.4 раза (выигрыш в 87 раз от первоначального).

На этом все!

Benchmark Results

goos: darwin goarch: arm64 pkg: github.com/ilyadt/benchmap cpu: Apple M1 Pro BenchmarkCalculators/calculator-8                     918.9 ns/op BenchmarkCalculators/calculator_optimized1-8           86.2 ns/op BenchmarkCalculators/calculator_optimized2-8           36.6 ns/op BenchmarkCalculators/calculator_optimized3_risky-8     10.5 ns/op

P.S.

Пробовал так же заменять мапу на RoaringBitmap по пользователям (n → rb{people}), но по производительности она проигрывает для этой конкретной задачи.

Итог

1. Хоть мапа и быстрая (поиск по ключу O(1)), но по факту требуется время много больше, чем в поиске по массиву, где тоже O(1). Особенно это заметно в циклах.

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

3. Если мапа специализированная (например int->int), то можно использовать специализированные имлементации вместо стандартной мапы. В моем случае это увеличило скорость в 2.29 раза.

Ссылки

• Бенчмарки — https://github.com/ilyadt/benchmap

• Реализация эффективной intmap — https://github.com/kamstrup/intmap

• Дополнительно: RoaringBitmap — https://github.com/RoaringBitmap/roaring