The Computer Language Benchmarks Game - отличный синтетический тест для компиляторов. Существуют разные виды алгоритмических задач, реализуемых с использованием популярных языков программирования.

Go language - один из моих любимых языков, который я использую для своих любимых проектов и проектов, готовых к производству.

Я был удивлен, что Go медленнее нескольких родных языков (родных для VM / JIT) на нескольких тестах, например. Бинарные деревья.

Двоичные деревья - это задача, требующая интенсивного использования памяти. Подтверждено профилированием. Я профилировал лучшую реализацию Go - Go # 8. Результат - узкое место - это выделение памяти.

Буферизованное распределение

Исходная реализация однажды имеет точку с интенсивным распределением:

func bottomUpTree(depth uint32) *Tree {
    tree := &Tree{}
    // .....
}

Небольшой рефакторинг переместит этот фрагмент кода в «распределитель», чтобы упростить использование в проекте другого типа распределителей:

func (o *AllocatorNaive) NewTree() *Tree {
	return &Tree{}
}
func NewTree(depth uint32, allocator Allocator) (tree *Tree) {
	tree = allocator.NewTree()
    // .....
}

Эта функция вызывала около 600 000 000 раз «наивный» распределитель для глубины 21, и это было место для 97,9% распределения памяти.

Улучшение основано на прогнозировании количества выделений для конкретной задачи. Бинарное дерево имеет узел 2 ^ (глубина + 1), включая корневой узел. Буферизованный распределитель выделяет это количество узлов один раз для дерева:

func NewAllocatorBuffered(depth uint32) Allocator {
	return &AllocatorBuffered{
		buffer: make([]Tree, 1<<(depth+1)),
	}
}

В результате - наиболее вызывающее распределение памяти - это та функция в 5 580 000 раз, что в ~ 107 раз меньше, чем наивный распределитель.

Сборка и запуск

Https://github.com/7phs/binary-trees

Вам понадобится Go 1.12+ с поддержкой модуля (GO111MODULE = on) для сборки или запуска проекта:

# build
go build
# run
./binary-trees -allocator 0 21
# run skipping build 
go run . -allocator 1 21

Команда поддерживает параметры для выбора распределителя и глубины двоичных деревьев. Поддерживаемые распределители:

  • 0 - наивный (по умолчанию)
  • 1 - буферизованный

Оцените производительность ЦП распределителей

Окружающая среда:

  • Go 1.13 (подсказка)
  • MacBook Pro 15 2012 г., Intel Core i7–3615QM (4 ядра), 16 Гбайт
  • Выполнить 5 раз для каждого распределителя
  • Оцените, используя команду времени:
  • время ./binary-trees -allocator 1 21

Результат:

  • Наивный: 15.5796 сек.
  • Буферизовано: 4,8432 сек.
  • Разница: 3,196x

Заключение

  • Профилируйте свой проект, чтобы понять узкое место в производительности.
  • Использование стратегии выделения памяти для конкретных задач может помочь повысить производительность задач обработки данных, реализованных в программе Golang.

P.S.

В стандартную библиотеку Go входит sync.Pool. По словам автора fasthttp, это в общих случаях ваш лучший друг.