Оптимизация 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