Одной из проблем, которую авторы языка Go пытались решить, создавая его, было облегчение программирования надежных приложений под многоядерные системы. Для этого язык использует легковесные потоки, называемые горутины (goroutines), и каналы в качестве средства взаимодействия между ними. Помимо каналов в пакете sync содержатся такие примитивы синхронизации, как мьютексы или условные переменные, однако их рекомендуется применять только для низкоуровневых библиотек или там, где каналы будут явным оверхедом.
Каналы в Go типизированы и являются объектами первого класса. Их можно посылать в функции, возвращать из функций, присваивать переменным и полям структур, а также пересылать по каналам. Они могут работать только в одну сторону или в обе. Причем, если обычный двунаправленный канал передать в функцию, где он используется, например, только на прием, его можно промаркировать соответствующим образом в списке параметров функции и компилятор проверит правильность его использования. Обычные каналы блокируют горутину, которая пытается получить из или послать что-то в канал, пока с другой стороны не будет произведено соответсвующее обратное действие. Но канал может иметь буфер, который может накапливать и отдавать накопленное определенное количество значений без блокировки. Канал может быть закрыт встроенной функцией close, после этого посылка в него значений приведет к панике. Если закрытый канал имеет непустой буфер, эти значения все еще могут быть получены. Но когда буфер уже пуст или его нет, закрытый канал при попытке чтения будет выдавать нулевые значения того типа, для пересылки которых он создан. То есть, закрытый строковый канал будет выдавать пустые строки, целочисленный — нули, канал указателей — nil. А теперь от теории к практике.
Продолжая традицию , напишем две версии (с одним и с несколькими нативными потоками) программы для брутфорса хэша пятизначного пароля, состоящего из цифр и латинских букв нижнего регистра. Следующий код является общим для обоих вариантов, за исключением закомментированного импорта пакета runtime, который нужен только в многопоточном варианте.
import (
«crypto/md5»
«encoding/hex»
// «runtime»
«fmt»
«log»
«time»
)
var hash [ 16 ] byte
// nextByte возвращает следующий после данного
// символ алфавита
func nextByte ( b byte ) byte {
switch b {
case ‘z’ :
return ‘0’
case ‘9’ :
return ‘a’
default :
return b + 1
}
}
// nextPass изменяет текущий пароль(на месте)
// на следующий в лексикографическом порядке
func nextPass ( b [] byte ) {
for i := len ( b ) — 1 ; i > = 0 ; i — {
b [ i ] = nextByte ( b [ i ])
if b [ i ] != ‘0’ {
return
}
}
}
Продолжение однопоточной версии выглядит следующим образом:
func worker ( b [] byte ) string {
for md5 . Sum ( b ) != hash {
nextPass ( b )
}
return string ( b )
}
Чтобы не делать лишних преобразований во время выполнения программы, заданный строкой хэш приводим к тому же типу, что выдает md5.Sum , то есть, шестнадцатибайтному массиву.
t := time . Now ()
const hashString = «95ebc3c7b3b9f1d2c40fec14415d3cb8» // «zzzzz»
//приведение к строки хэша к типу [16]byte
h , err := hex . DecodeString ( hashString )
if err != nil {
log . Fatal ( err )
}
copy ( hash [:], h )
fmt . Println ( «Пароль: » , worker ([] byte ( «00000» )))
fmt . Println ( «Время поиска: » , time . Since ( t ))
}
В функцию main добавлен счетчик времени, который для этой версии на моем стареньком двухъядернике выдает около 52 секунд на полный перебор. Здесь или здесь можно найти код целиком.
Теперь рассмотрим многопоточный вариант. Прежде всего, нужно будет разбить множество возможных паролей на небольшие части, которые последовательно будут посылаться горутинам-воркерам. Для этого используется структура part, где start — первое значение интервала паролей, а end — следующее значение первого символа пароля, которое будет сигнализировать о завершении интервала. Таким образом, первый интервал для пятизначных паролей будет таким: 00000-10000, второй: 10000-20000 и так далее. Для генерации этих интервалов напишем функцию с говорящим названием generator:
start string
end byte
}
func generator ( in chan< — part ) {
start := [] byte ( «00000» )
var b byte
for {
b = nextByte ( start [ 0 ])
in < — part { string ( start ), b }
start [ 0 ] = b
}
}
Функция worker заметно усложнилась и на вход уже принимает не первое значение пароля, а пару каналов, in — для приема границ проверяемого интервала и out — для отсылки результата в случае совпадения хэшей.
var p part
var b [] byte
for {
p = < — in
b = [] byte ( p . start )
for b [ 0 ] != p . end {
if md5 . Sum ( b ) == hash {
out < — string ( b )
return
}
nextPass ( b )
}
}
}
В main добавим вызов runtime.NumCPU() , чтобы получить количество логических процессоров, а посредством runtime.GOMAXPROCS(num) попробуем использовать их одновременно.
t := time . Now ()
num := runtime . NumCPU ()
runtime . GOMAXPROCS ( num )
const hashString = «95ebc3c7b3b9f1d2c40fec14415d3cb8» // «zzzzz»
h , err := hex . DecodeString ( hashString )
if err != nil {
log . Fatal ( err )
}
copy ( hash [:], h )
in := make ( chan part )
out := make ( chan string )
for i := 0 ; i < num ; i ++ {
go worker ( in , out )
}
go generator ( in )
fmt . Println ( «Пароль: » , <- out )
fmt . Println ( «Время поиска: » , time . Since ( t ))
}
Далее мы создаем каналы и запускаем по одной горутине-воркеру на каждое ядро. Воркеры блокируются каналами до получения первых заданий, посылаемых генератором, который тоже запускается в отдельной горутине. Примечательно, что мы можем поменять местами вызов этой функции и цикл, запускающий горутины-воркеры. При этом все будет работать, как задумано. Тем временем главная горутина, раздав всем ценные указания, останавливается в ожидании результата вычислений, а получив, печатает его и время работы программы, после чего сразу завершается, попутно убив все, возможно еще работающие, горутины. Код целиком можно скачать здесь или здесь . Эта версия отработала у меня примерно за 27 секунд, что в 1.9 раза быстрей однопоточной.
Эксперимента ради, я написал и третью версию программы (код не привожу). В ней пароли генерируются не в воркерах, а в специально для этого созданной функции, в отдельной горутине, из которой через канал по одному (!) пароли передаются воркерам. Это значительно упрощало код всей программы. И все бы хорошо, да не тут-то было — время полного перебора увеличилось в 4 раза до рекордных 118 секунд, при том, что вычислений стало даже немного меньше. Многократно возросшая нагрузка на канал перевесила по ресурсоемкости даже вычисления самих хэшей.
Вывод: писать параллельные и многопоточные приложения на Go можно и довольно легко, главное не перебарщивать с коммуникациями, они все же не бесплатны. Еще у меня сложилось впечатление, не знаю, насколько оно оправдано, что начинать писать программу на языке Go лучше всего на основе небуферизованных каналов, а уже после добавлять буфер там, где это дает прирост производительности. Такой подход позволяет сразу найти дедлоки, которые иначе могут «спрятаться» за буфером и всплыть в самый неподходящий момент.
От себя я хочу сказать спасибо Владимиру за уже второй замечательный гостевой пост и подтвердить, что приведенная в заметке программа почти линейно ускоряется с ростом числа ядер в процессоре. Также мне хотелось бы призвать читателей не стесняться задавать вопросы Владимиру касательно горутин и предлагать темы, связанные с Go, для будущих постов.
Дополнение: Коллеги-блогеры решили зарядить своего рода флешмоб. Здесь можно найти решение задачи перебора паролей на C++, здесь — на языке D, здесь — на Scala+Akka, здесь — на Clojure, а вот тут — на Rust. Напоминаю, что ранее в этом блоге публиковались варианты на Haskell и даже на Erlang . Предлагайте решения на своем любимом языке! 🙂
Дополнение: Также читаем заметку Давайте напишем акторы на языке Go .
