Ни для кого не секрет, что некоторые программисты в свободное от работы время программируют. Но у каждого такого программиста свой интерес. Кто-то пишет петпроект, на который возлагает большие надежды. Кто-то помогает знакомым поднять проект мобильного приложения (да, тот товарищ из анекдота). А кто-то занимается ерундой.
Я конечно из тех, кто бесцельно пишет код, когда находит свободное время. Во-первых, это помогает отвлечься от тех проблем, которые я решаю на работе. Во-вторых, это помогает мне развивать мою способность писать код, который отличается от того кода, который я пишу на работе.
И сегодня я расскажу вам об одной такой ерунде, которая написана на языке golang и, возможно, кому-то покажется абсолютно бесполезной, а кому-то подскажет интересные мысли и идеи.
Каты
Для начала я объяснюсь. Конечно, никакой такой бесполезной ерундой я не занимаюсь, а занимаюсь самыми обыкновенными катами (кто не знает погуглите). Я отрабатываю базовые навыки печатания программного кода – постепенно перевожу способность писать понятный код (я хочу подчеркнуть это – именно понятный) на более низкий уровень мышления. Не в мышечную память, конечно, но тем не менее. Чем больше вы пишете простой и понятный код, тем проще вам его писать.
Порой я делаю это один, а иногда в компании друга (парное программирование). Иногда мы играем в игру, когда один должен писать модульные тесты, а второй должен писать код, который эти тесты проходит. Подобные вещи Роберт Мартин описывал в своей книге “Идеальный программист”, они помогают улучшить свои навыки.
Что же я такое пишу? Да самые обыкновенные задачи, с которыми программист сталкивается каждый день. Например, алгоритм поиска элемента в массиве пятью разными способами или функцию подсчета очков для боулинга. Иногда я возвращаюсь к уже выполненным когда-то работам и пытаюсь сделать их заново, а потом смотрю, как за это время изменился мой подход. Порой добавляю новые условия в задачу. Например, сделать так, чтобы код был thread-safe или с нулевым количеством аллокаций в heap.
Где я их достаю? Да в самых разных местах. На собеседованиях в Яндексе. У Дяди Боба в блоге. Просто гуглю или сам выдумываю иногда.
С чего началась сегодняшняя история
Сегодняшняя история началась с того, что в нашем чате разработчиков один наш работник запостил следующую цитату из go 1.20 release notes:
The math/rand package now automatically seeds the global random number generator (used by top-level functions like Float64 and Int) with a random value, and the top-level Seed function has been deprecated.
На что я попытался ответить следующей шуткой:
Никто:
некоторые разработчики так и не научились пользоваться math/rand
Пользователи crypto/rand:
[попивают сок].
Да, я согласен, совсем не смешно. И я понимаю, что, если ваш алгоритм не должен быть сколь-нибудь криптостойким, то целесообразнее использовать math/rand. Это связано не столько даже с быстродействием, сколько с удобством интерфейса. Ведь math/rand сразу предоставляет нам такие функции, как rand.Intn(int) или rand.Int63(), а в случае с crypto/rand мы имеем Reader, который предоставляет нам возможность прочитать случайную последовательность байт. Ну скажите, разве не прелесть?
И вот тут то мне в голову начали приходить мысли. А на сколько падает производительность, если мы реализуем чтение int64 из crypto, а не из math? А что там с thread-safe? А можно ли…
Тестирование
Для начала, я хотел убедиться, что функция выполняет свое дело. Что каждое следующее число, которое она генерирует, можно назвать случайным. Ну а вдруг, я написал код, который не работает, а я замеряю его производительность?
Как убедиться в случайности генерируемых чисел?
Ну, допустим, что мне тут не нужна точность, как в аптеке, я всего лишь хочу убедиться, что есть какая то энтропия, что функция-генератор не выдает мне одни и те же числа по порядку. Эта задача уже проще. И я подумал, предположим, я генерирую 1 миллион единиц и раскладываю их в ячейки памяти случайным образом, тогда после того, как я посчитаю, сколько в каждую ячейку упало, у меня получится примерно одинаковое количество. Примерно, да все-таки не одинаковое.
Оттолкнувшись от этой задумки, я написал следующий тест:
Тест сомнительный, границы разброса взяты методом проб, но для меня пойдет - все реализации генератора случайных чисел уложились в предложенный мною диапазон, а значит, они работают примерно одинаково. Или нет.
Обратите внимание, как я раскладываю значения по ячейкам. Я использую lock-free функцию atomic.AddInt64. Это позволяет протестировать реализации сразу в режиме многопоточной работы. Т.к. я хочу сразу concurrency-ready код.
Бенчмарки
Для того, чтобы протестировать производительность разных реализаций генератора случайных чисел в одинаковых условиях, я написал простую функцию, которая принимает в качестве аргумента интерфейс генератора:
И теперь могу подкладывать нужные реализации в тест просто передав нужный struct. А вот так выглядят реализации:
Реализацию crypto я спер из интернета. Да, сейчас использование big не считается криптостойким, но меня больше интересует сам факт использования crypto, чем какие то мелочи вроде безопасности =)
Так что я просто запустил тесты, чтобы посмотреть, что получится. К слову сказать, у меня достаточно мощный компьютер с восемью ядрами i7 и 32 ГБ оперативной памяти. Так что я увидел вот такие результаты:
MathRand_Generate-8 100000000 11.75 ns/op 0 B/op 0 allocs/op
CryptoRand_Generate-8 3288141 364.9 ns/op 56 B/op 4 allocs/op
Ух-ты! Ежкин кот! Тут есть где разгуляться. Так что я заварил кофейку и начал свои изыскания.
Изыскания
Теперь я переделаю функцию так, чтобы она просто читала восемь случайных байт, а потом мы просто сделаем из них int64. Вот такой код:
И вот какими были результаты тестирования в сравнении с предыдущей реализацией, построенной с использованием big.Int:
CryptoRand: 364.2 ns/op 56 B/op 4 allocs/op
LightRand: 46.19 ns/op 8 B/op 1 allocs/op
Неплохо. Мы потеряли возможность указывать диапазон генерации, но выиграли в производительности. Для тех, кто не понял – в предыдущей реализации вот эта строчка “bint.SetInt64(math.MaxInt64)” позволяла задать максимум для сгенерированного числа. Это очень интересно, но я вот о чем подумал, а можно ли избавиться от аллокаций вообще? И чего мне это будет стоить?
Конечно, аллокация происходит вот на этой строчке: “var b [8]byte”. Эта переменная не может быть выделена на стеке, потому, что ее данные утекают вот тут: “crand.Reader.Read(b[:])”. Reader – это интерфейс и эскейп-анализ не может гарантировать, что его реализация не выполнит небезопасных операций со ссылками. Давайте я немного расскажу, как можно избавиться от аллокаций в случаях, когда мы работаем с маленькими слайсами.
Аллокации
Дело в том, что все объекты go старается расположить в стеке. Таким образом, когда функция вернет результат, ее стек-фрейм будет просто отброшен и сборщику мусора не придется анализировать объекты, которые можно освободить - их просто не будет в куче. Для того, чтобы решить, можно или нельзя расположить объект на стеке, эскейп-анализ определяет, смогут ли ссылки на объект убежать далеко от фрейма нашей функции.
Давайте рассмотрим пример. Функция возвращает слайс байтов (возможно где-то берет данные или генерирует на лету) вызывающая функция этот слайс будет использовать.
Эскейп-анализатор видит, что объект рождается в нижележащей функции, а используется в вышележащей. Т.е. объект будет использоваться в то время, как фрейм вызывающей функции будет уже отброшен. И, если данные были расположены в этом фрейме, то все ссылки на них будут испорчены. Таким образом принимается решение о расположении данных в куче.
Обойти эту проблему очень легко – нужно создать объект выше, чтобы все использующие его функции были ниже по вызову. например, вот так:
Мы передаем в функцию готовый слайс байтов, как подготовленное буферное пространство. И, если буфера достаточно, то никаких аллокаций не произойдет, а сама переменная не утечет в кучу, а останется на стеке.
Но ни в коем случае не подумайте, что это непреложное правило. У эскейп-анализатора есть свои пределы, иначе, если заставить анализатор обходить и отрабатывать все возможные варианты, время компиляции может увеличиться во много раз. Давайте посмотрим, как мы можем сломать код примера и заставить go выделять данные в куче:
Если мы просто вызовем функцию “sumABC”, чтобы получить значение, анализатор определит, что переменная не утекает. Но я применил вот такой финт – функциональный подход. Теперь анализатор видит, что в функции “foldFunc” может произойти что угодно, никто не защитит от многопоточной реализации или сохранения ссылки на объект в куче. Не смотря на то, что единственный вариант использования этой функции предполагает безопасное использование объекта, анализатор не будет полагаться на варианты использования, т.к. их обнаружение дорого стоит.
Если применить вот такую команду “go tool compile -m -m ./check_buff.go”, то можем увидеть, как к этому выводу пришел анализатор. Эта строчка “check_buff.go:28:11” – это как раз “return fn(bytes)”
./check_buff.go:27:15: parameter bytes leaks to {heap} with derefs=0:
./check_buff.go:27:15: flow: {heap} = bytes:
./check_buff.go:27:15: from fn(bytes) (call parameter) at ./check_buff.go:28:11
Ну хорошо, а в нашем то случае что? А в нашем случае интерфейс io.Reader. И анализатор не может гарантировать, что все варианты реализации этого интерфейса будут безопасно обращаться с объектом. А это означает, что абсолютно бесполезно рассчитывать на то, что буфер останется на стеке.
Буферы
Что делать? Ну так давайте сделаем этот буфер еще выше – на уровне структуры. Тогда всякий следующий вызов будет использовать тот же самый буфер, что и предыдущий. Т.е. аллокация будет не на каждый вызов, а один раз и навсегда. Но, это конечно полностью ломает concurrency нашего кода. Т.к. все потоки выполнения будут использовать один буфер. Но все равно, давайте попробуем, как это будет выглядеть. Кроме того, что я вынес переменную на уровень описания структуры, вот так:
Я еще решил сделать Reader буферизованным. Т.е. чтение случайных данных сразу будет происходить блоками, которые затем будут читаться в поле структуры “b [8]byte” по мере необходимости. Вот как стал выглядеть код:
Ну и в такой конфигурации бенчмарки (однопоточные) дают вот такие результаты:
21.51 ns/op 0 B/op 0 allocs/op
А вот это уже существенная разница, не правда ли? Но, к сожалению, такой вариант не работает в многопоточном режиме. Конечно, я могу создать для каждого потока свой объект “LightRand” и тогда все будет безопасно. Но сегодня моя цель не в практичности, а в интересе. Так что, я продолжаю с многопоточными реализациями.
Lock-Free
Наиболее производительными многопоточными алгоритмами считаются так называемые lock-free алгоритмы. Для того, чтобы определить, что наш алгоритм можно считать lock-free воспользуемся следующим маркером:
– Могут ли потоки блокировать друг друга на неопределенное время?
Если ответ на этот вопрос “НЕТ”, значит это lock-free. Подход довольно смешной, но я не буду тут описывать все проблемы многопоточного программирования, блокировок доступа к разделяемой памяти и проблем, которые должны решать алгоритмы lock-free.
И еще одно допущение: если потоки блокируются на время для того, чтобы можно было заполнить буфер из которого они читают - это все равно lock-free.
Довольно просто организовать конкурентное чтение из разделяемой памяти – я просто создаю атомарный указатель на вершину буфера, каждый поток сначала сдвигает указатель, а потом читает свой кусок данных. Если указатель сдвинут до нуля, то все потоки ожидают, пока буфер наполнится новыми данными.
Звучит довольно просто и атомарные операции позволяют легко реализовать этот алгоритм, но вот в чем проблема. Кто должен наполнять буфер? И как наполнить буфер так, чтобы не помешать тем потокам, которые уже начали чтение, но еще не закончили.
Я не буду описывать, какие глупые идеи мне приходили в голову, и, как одна за другой они терпели поражение. Скажу, что при большом количестве потоков я не мог подобрать нужный механизм постановки всех потоков на паузу в тот момент, когда один поток обновлял буфер. Я пробовал и не ставить их на паузу, а просто уводить в цикл, пока буфер не будет заполнен – это еще хуже. Основная проблема была в том, чтобы одновременно всем потокам дать сигнал о том, что можно продолжить работу. А если я использовал мьютекс, то все потоки по очереди должны были захватить и затем отпустить блокировку, а это довольно накладная операция.
Решение
Решение показалось мне довольно очевидным, когда я его нашел. Я использую RWMutex и каждый поток, когда получил свой указатель, блокируем мьютекс для чтения. Допускаются одновременные RLock, поэтому потоки не мешают друг-другу, а когда указатель уходит за пределы буфера, один поток захватывает блокировку для записи и заполняет буфер.
Хорошо, а что по поводу сигнала всем одновременно? Я использовал канал. Поток, который наполняет буфер, закрывает канал, что дает сигнал ожидающим потокам о том, что можно продолжить работу. А затем пишущий поток создает новый канал. Вернее, он делает это в другой последовательности - сначала порождает новый канал, для следующего цикла наполнения буфера,а затем закрывает текущий канал. Чтобы ожидающие потоки не перепутали канал, я считаю итерации наполнения буфера и ассоциирую (логически) их с каналом.
Чтобы потоки, которые должны встать на ожидание, по ошибке не захватили новый канал (который создается для нового цикла), они должны заранее захватить номер цикла, а затем (после того, как захватили сам канал в ветке ожидания) сверить сохраненный номер цикла и текущий, если они идентичны, поток встает на ожидание буфера, если нет – начинает свою логику заново с захвата номера цикла и канала. Прошу прощение за непонятное объяснение, надеюсь код поможет понять, что творится:
Тут есть пара моментов, которым стоит уделить внимание.
Указатель на вершину буфера случайных данных монотонно убывает, и в конкретный момент времени все потоки исполнения имеют свое собственное значение указателя. Отсюда вывод: -8 – число, которое является первым отрицательным числом в монотонном убывании с шагом -8 – обязательно будет захвачено в тот момент, когда буфер иссякнет, и только одним потоком. Именно этот поток мы и заставим обновлять буфер.
Функция, заполняющая буфер чтения, выполняется монопольно и только тогда, когда все читающие потоки завершили чтение. Все это гарантируется мьютексом. Перед тем, как создать новый канал, счетчик каналов “refSeq” инкрементируется, это будет сигналом для ожидающих потоков, что нужный канал уже не существует. А так как “refSeq” потоки читают еще до того, как попали в ветку с пустым буфером, а затем сверяют этот счетчик сразу после того, как прочитали указатель на канал, работа с правильным каналом будет гарантирована. Есть только один способ изменить канал без изменения счетчика – это, если все будет происходить после того, как наполняющая буфер функция обновит указатель на вершину буфера, но тогда читающие потоки не попадут в ту ветку, где этот канал используют, потому что значение не будет отрицательным.
Да, реализация получилась не из простых, но тесты проходят, а бенчмарк показывает неплохой результат:
54.09 ns/op 0 B/op 0 allocs/op
Обратите внимание на отсутствие аллокаций и довольно быструю обработку. К слову сказать, реализация основанная на math/rand в многопоточном бенчмарке показала себя не на много эффективнее:
39.34 ns/op 0 B/op 0 allocs/op
Т.е. ценой 14 наносекунд я решил следующую проблему: использование crypto/rand вместо math/rand. Ну а если серьезно, я ничего не решил, но просто интересно провел время. Кому нравятся такие челленджи, те меня поймут.
Под конец предоставлю бенчмарки всех реализаций:
Однопоточные тесты
math/rand: 11.84 ns/op 0 B/op 0 allocs/op
big.Int: 364.2 ns/op 56 B/op 4 allocs/op
lock-free: 32.25 ns/op 0 B/op 0 allocs/op
Многопоточные тесты
math/rand: 39.34 ns/op 0 B/op 0 allocs/op
big.Int: 59.26 ns/op 56 B/op 4 allocs/op
lock-free: 54.09 ns/op 0 B/op 0 allocs/op
Потоконебезопасная реализация
buffered: 21.51 ns/op 0 B/op 0 allocs/op
А полный исходный код вы можете найти тут.