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, это в общих случаях ваш лучший друг.