Хочу поделится своими наблюдениями по поводу производительности при реализации домашних заданий из курса MADE по алгоритмам, но это применимо к любому спортивному и не очень программированию где важна скорость выполнения когда. И сделать небольшое введение в Go.
Императивное программирование для бедных
Go специально создан простым и примитивным, чтобы любой вчерашний школьник попавший в на работу в Гугл не отстрелил себе ноги. Go — это некий общий знаменатель всех императивных языков, и своей простотой и скоростью (как компиляции так и выполнения) он подкупает. Сначала мне надоело думать как написать на Питоне чтобы задача зашла в лимит времени (TL), а потом всё равно переписывать на C++, так как всё таки не влез в тайм-лимит, потом ещё быстрее мне надоело смотреть на очередной сегфолт вместо полноценного стектрейса и я решил подойти к вопросу радикально.
Базовые элементы синтаксиса:
package main
// Используемые модули
import (
"fmt"
)
const (
ADD = "+"
MUL = "*"
)
// Структуры (типа классов но без наследования)
type TreeNode struct {
Value int
Left *TreeNode // * = ссылка
Right *TreeNode
}
// Функции
func insert(node *TreeNode, value int) *TreeNode {
if node == nil {
return &TreeNode{Value: value} // создание экземпляра TreeNode и & = взятие ссылки
} else if value < node.Value {
node.Left = insert(node.Left, value)
} else if value > node.Value {
node.Right = insert(node.Right, value)
}
return node
}
// Основная функция будет выполнена при запуске программы
func main() {
var command string
var value1 int // объявление переменной по-умолчанию всегда 0
value2 := 0 // объявление переменной с выведением типа
fmt.Scan(&command, &value1, &value2) // Чтение из stdin, fmt.Scanf - C-style чтение
var result int
if command == ADD {
result = value1 + value2
} else if command == MUL {
result = value1 * value2
} else {
panic("Unknown operator: " + command)
// panic - типа исключения, но отловить его нельзя, программа завершится
}
var arr = make([]int, 10) // Массивы
for i := 0; i < 10; i++ {
arr[i] = result
}
fmt.Println(arr)
}
Также язык имеет крайне opinionated подход к форматированию кода, а именно как дядька Роб Пайк (создатель языка) сказал, так и будет. go fmt форматирует ваш код согласно стандартам языка. Всё, точка и никаких споров о пробелах и запятых, и ИМХО в этом есть определённые плюсы.
Часто Go конечно поражает чем-нибудь типа отсутствия в stdlib функций min, max или abs для целых чисел (они есть только для float чисел), их любезно предлагается реализовать самостоятельно.
Скорость выполнения программы = Алгоритм + IO
Чем отличается O(n^2) от O(n*log(n)) и какие бывают алгоритмы нам рассказывал Григорий Филиппович на прекрасном курсе по алгоритмам в MADE, здесь всё очевидно (за исключением констант перед O конечно) выбираем самый быстрый алгоритм.
Но если алгоритм работает с большим объёмом данных (примерно от 10^5 элементов и больше) то ввод/вывод начинает играть существенную роль.
Обычно самый простой способ fmt.Scan прочитать данные из стандартных потоков ввода/вывода самый медленный т.к. там используются небуферизированные операции, если мы просим прочитать число, то буквально читается число, потом следующее, хотя данные можно прочитать зараз большим куском. При записи после каждого вызова fmt.Println происходит flush, т.е. программа выталкивает данные из буфера в поток вывода операционной системы, и ждёт от ОС подтверждения что данные получены.
На помощь приходит буферизированный ввод/вывод, при вводе сразу читается большой кусок данных, и разбирается уже в памяти программы, при выводе мы пишем в буфер программы, а выталкивание в поток вывода делаем один раз вручную в самом конце.
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
var n int64
fmt.Fscanf(in, "%d\n", &n)
var sum int64
for i := int64(0); i < n; i++ {
var value int64
fmt.Fscanf(in, "%d", &value)
sum += value
}
fmt.Fprintf(out, "%d\n", sum)
out.Flush()
}
Это значительно ускоряет ввод/вывод
Оказалось что в Go есть классный встроенный инструмент для не только для unit-тестирования, но и для бенчмарков.
Для этого достаточно добавить вот такой файл с тестом:
a_test.go
package main
import (
"os"
"testing"
)
func BenchmarkSolveA(t *testing.B) {
fin, _ := os.Open("a.in")
fout, _ := os.Create("a.out")
for i := 0; i < t.N; i++ {
fin.Seek(0, 0)
fout.Seek(0, 0)
solve(fin, fout)
}
fin.Close()
fout.Close()
}
Здесь открывается файл с входными данными и в цикле вызывается реализацию алгоритма из функции solve. testing.B — это нечто вроде фикстуры (как в Python) бенчмарка, количество итераций он подбирает автоматически, в зависимости от того как быстро выполняется код. Решение будет выглядеть вот так:
a.go
package main
import (
"os"
)
func solve(fin *os.File, fout *os.File) {
// Код решения
}
func main() {
solve(os.Stdin, os.Stdout)
}
Функция solve принимает ссылки на файлы с входными данными и файл куда будет выведен ответ и вызывается из main() со стандартными потоками ввода/вывода
Попробуем оптимизировать решение задачи #HW10A на вход подаётся граф размером в 200_000 рёбер.
Начнём с решения с небуферизированным вводом:
$ go test -bench=. -cpuprofile cpu.prof cpu.svg goos: darwin goarch: amd64 BenchmarkSolveA-8 1 3202774957 ns/op PASS ok 0_unbuffered 3.402s
3.2 секунды, в таймлимит явно не влезем )
В Go очень крутой toolset (встроенный в язык!), сгенерированный профайлером файл можно визуализировать в виде графа go tool pprof -svg cpu.prof > cpu.svg, посмотрим что там:
89% процентов времени занимает чтение данных и почти 9% вывод, есть над чем поработать. В сумме почти 98% времени на IO.
Меняем ввод на буферизированный, запускаем тест
$ go test -bench=. -cpuprofile cpu.prof goos: darwin goarch: amd64 BenchmarkSolveA-8 4 285979620 ns/op PASS ok 1_buffered 2.456s
286 мс, теперь решение должно зайти, буферизированные операции ускорили работу с IO на порядок.
Здесь 76% времени выполнения программы тратится на IO
Вывод уже кажется быстрее не сделать. Ввод… Хм, а что если прочитать все данные разом и уже в памяти парсить, используем ioutil.ReadAll, потом превращаем в строку, сплитим и парсим.
$ go test -bench=. -cpuprofile cpu.prof goos: darwin goarch: amd64 BenchmarkSolveA-8 13 87102857 ns/op PASS ok 2_read_all_strings 2.346s
87 мс
Сработало, само чтение данных теперь занимает 1.3% но много времени уходит на преобразование строк и сплиты. Как можно сделать быстрее? А что если ничего не конвертировать в строки, а просто читать данные по одному байту из буффера и по ходу разбираться что с ними делать, парсинг на лету, это даст минимально возможное количество лишних операций.
$ go test -bench=. -cpuprofile cpu.prof goos: darwin goarch: amd64 BenchmarkSolveA-8 22 51912710 ns/op PASS ok 3_read_all_bytes 2.245s
52 мс! Сработало!
Теперь самый большой кусок CPU в 24% отжирает динамическое расширение массивов (слайсов в терминах Go) в которых мы храним списки смежности, но здесь никаких очевидных оптимизаций на ум не приходит, хеш-таблицы в качестве списков смежности работают на порядок медленнее, матрицу мы не можем использовать т.к. нужно выделить память под 10^10 элементов.
Думаю достаточно уже извращаться с вводом. Репозиторий с примерами
Другие наблюдения
- Выделять массив быстрее сразу правильного размера, а не наращивать постепенно
- Обход большого массива по порядку быстрее чем случайный доступ к его элементам
- Маленькие структуры типа 8 байт быстрее копировать, а не передавать по ссылке
- В Go есть возможность отключить сборщик мусора, иногда это давало небольшой прирост, а иногда взрывало потребление памяти
- Похоже что 64-битный компилятор С++ имеет преимущество на 32 битными С++ и Go только когда программа использует 64-битные типы данных
- Порядок полей в структуре может ускорять и замедлять программу (оффсеты)
Прикосновение к Rust
Благодаря небольшой задержке последнего домашнего задания выпавшей на выходные, я смог посвятить один день и наконец-то прочитать несколько глав из документации к Rust, я был наслышан о сложности этого языка, но также и о его красоте и продуманности. Оказалось не так страшен чёрт, как его малюют, я был приятно удивлён, а меня уже достаточно сложно удивить (как в плохом так и в хорошем смысле). 5 глав было достаточно чтобы решиться написать последнее ДЗ на Rust, в запасе куча времени, почему бы и нет.
Одна из самых крутых фич Rust — это концепция владения, которая позволяет избежать как ручного управления памятью, так и необходимости в отдельном сборщике мусора. А также позволяет писать потоко-безопасный код который проверяется на этапе компиляции, т.е. если компилятор просто не позволяет скомпилировать код который может одновременно читать и писать в одну и ту же переменную.
И на удивление с пятью задачами я справился быстро, компилятор очень дружелюбный и в случае проблем он выдаёт максимально понятное и подробное сообщение об ошибке, часто с описанием того что нужно исправить, чуть ли не сам за тебя исправляет. Концепция владения оказалось не такой уж и сложной и компилятор опять же подсказывал что делать. Потом я по фану переписал одно из моих топовых решений предыдущих задач с Go на Rust и смог добиться небольшого ускорения! Круто, да он ещё и быстрый!
Также, как и у всех современных языков, в комплекте идут разные тулзы, менеджер пакетов, форматтер rustfmt он кстати имеет настройки в отличие от go fmt. При использовании было ощущение очень близкое к «компилируется значит работает» (прям как Haskell обещает). Мощный патерн-матчинг который следит все ли ты варианты учёл (это прям супер). Структуры + traits которые форсят composition over inheritance. Очень приятное послевкусие, обязательно буду стараться использовать ещё, если понадобиться что-то быстрое, компилируемое написать.
В общем я конечно понимаю, что у нас впереди ещё огромный объём учёбы и работы, но просто помните, что однажды Rust надо попробовать.
Первый семестр позади
Спасибо всем кто находил время пооптимизировать свой код, чтобы подняться повыше в топе решений по времени работы, ребята вы крутые!
Особый респект тем кто осилил весь курс на Питоне, вы виртуозы!
Спасибо Григорию огромное! Нам удалось прикоснуться к культуре олимпиадного программирования выращенной в топовом ВУЗе страны, это так классно, чувствуешь себя как будто ты сам в ИТМО поучился, хоть маленько поучился, но всё равно приятно.