Роман Химов

Посмотрев на стандартную библиотеку C++, у меня появилась мысль попробовать решить ту же задачу средствами языка Го. У меня было время немного посмотреть на него, что-то понравилось, что-то так себе (это будет отдельной темой), было время прочитать ключевую работу тов. Хоара. Ну а чтобы лучше понять, как оно работает, неплохо бы попробовать что-нибудь сделать.

Итак, сетап тот же самый, необходимо максимально разумно распараллелить задачу поиска или подбора пароля. В Го для организации взаимодействия различных активных сущностей естественным образом предназначены каналы, именно их и будем использовать.

В общем плане, задача неплохо ложится на гошные потоки и каналы: создаём генерирующий задания поток и несколько рабочих, обмен данными между ними через канал. Проблемы (надо отметить, что и в плюсовой версии ключевые вопросы были те же) возникают в коммуникации состояния от рабочих потоков к генератору (после нахождения ответа генератор должен замолчать) и от рабочих потоков к вызывающему.

Вопрос остановки генератора можно решить с использованием глобального флага состояния, либо путём заворачивания состояния генератора в структуру, которая будет по поведению напоминать генераторный объект из плюсовой версии. Ни то, ни другое, не видится правильным решением для Го, поскольку глобальные состояния порочны изначально, а обёрточные структуры тоже не хочется городить без особой на то нужды.

Поэтому, для сигнализации от рабочих потоков к генераторному имеет смысл использовать всё те же каналы, просто добавив ещё один. Для генератора это уже будет читаемый канал, в отличие от основного его канала, в который генератор пишет. Со стороны может показаться, что это усложнит дело, так как надо проверять наличие данных в канале обратной связи, но фактически, благодаря наличию в Го выражения select, вопрос вилки между записью в один канал и чтением из другого канала решается тривиально.

Для коммуникации же от рабочих потоков к вызывающему можно использовать… ещё один канал! Здесь даже не видно разумных альтернатив, поскольку необходимо отдать найденное значение. В итоге по каналам получается такая схема:

Если предположить, что генератор выдаёт структуры типа chunk, то в коде это должно выглядеть как-то так:

func generator(chout chan<- chunk, chin <-chan bool, ...) {
        defer close(chout)
        for ; ; { // generator loop
                ...
                // do something to generate the next chunk
               select {
                       case _ = <- chin:
                                return
                        case chout <- newchunk:
                }
                ...
        }
}
 
func worker(chin <-chan chunk, finout chan<- string, genchan chan<- bool, ...) {
        for next := range chin {
                ...
                // proceed chunk
                if found {
                        genchan <- true
                        finout <- result
                        return
                }
        }
}
 
func main() {
        ...
        runtime.GOMAXPROCS(runtime.NumCPU())
        chunks := make(chan chunk)
        final := make(chan string)
        genchan := make(chan bool)
        go generator(chunks, genchan, ...)
        for i := 0; i < runtime.NumCPU(); i++ {
                go worker(chunks, final, genchan, ...)
        }
        result := <- final
        ...
}

Казалось бы, полная идиллия — синхронизация чётко по обмену данными. Но, увы, по факту не получается сразу с нескольких сторон.

Во-первых, у нас есть случай «ничего не найдено», и он, также как и в плюсовой версии, требует особого отношения. Изначально, мне казалось, что можно поиграться закрытием каналов на стороне рабочих потоков, но нет, гошные каналы в этом плане очень сильно отличаются от каких-нибудь файловых дескрипторов, если канал закрыть в одном из потоков, он закроется навсегда и везде.

Поэтому, увы, но получается, что основной поток не может просто ждать чего-нибудь из канала (если не использовать дополнительные обёртки, конечно), ему необходимо подождать завершения всех рабочих потоков. В общем-то, для синхронизации всех потоков многого не надо, есть модуль sync, а в нём есть sync.WaitGroup, являющийся, по сути, чем-то средним между семафором и условной переменной с очень простым функционалом:

func worker(wg *sync.WaitGroup, ...) {
        defer wg.Done()
        ...
}
 
func main() {
        ...
        var wg sync.WaitGroup
        for i := 0; i < runtime.NumCPU(); i++ {
                wg.Add(1)
                go worker(&wg, ...)
        }
        wg.Wait()
        ...
}

Нужное количество потоков добавляется через Add(), каждый из потоков делает Done(), в результате Wait() разблокируется с выходом последнего потока. Отлично? Отлично!

Но только возникает другая проблема, если всё-таки что-нибудь находится, то вся программа встаёт колом во взаимной блокировке. Казалось бы, как так? А очень просто — по умолчанию, каналы в Го жёстко синхронны и если наш рабочий поток что-то туда пишет (а он радостно пишет ответ), то покуда с обратной стороны канала никто не вычитает ответ, он встанет. Но это поправимо:

        final := make(chan string, 1)

И мы получаем буфер в один элемент, которого нам как раз хватит, рабочий поток сможет записать результат без блокировки. Всё? Ничуть. Оказывается, ещё и до добавления синхронизации у нас были точно такие же проблемы с каналом от потоков к генератору!

Всё по той же самой схеме — к тому моменту, когда поток обнаружит результат, генератор вполне себе может уже и завершиться, соответственно, никакого селекта не будет и рабочий поток точно так же повиснет на отправке в канал. Причём, повесить генератор на чтение из канала перед выходом мы тоже не можем, поскольку в случае неуспеха поиска результата, записи в канал не будет вообще и генераторный поток останется ждать до смерти программы. Решение здесь может быть то же самое, добавление буфера, но вот так потихоньку то, что изначально казалось простым и изящным, обрастает разного рода неочевидными подпорками.

Тем не менее, после этого результат становится уже вполне себе рабочим. И тут интересно сказать о других аспектах. Поскольку, в целом, несмотря на подпорки, задача ложится на Го гораздо лучше, мне было интересно опробовать чуть разные подходы в плане построения генераторного потока, плюс поиграться с буфером канала от генератора к рабочим потокам (а его ведь тоже можно очень легко сделать ненулевым).

Первый вопрос состоял в том, что должен выдавать на выходе генератор. В коде на Си-плюс-плюсе такого вопроса как-то не возникало, поскольку генератор там являлся пассивным объектом, дёргаемым из рабочих потоков, очевидно, что он должен был выдавать некоторые диапазоны рабочей области, но не единичный базовый элемент, поскольку этот вызов должен быть жёстко синхронизирован, и если потоки будут ходить к генератору за каждым штучным элементом, они устанут друг друга ждать.

Но в Го у нас генератор изначально активен (понятно, что так можно сделать и в плюсовом коде, но заметно дороже с точки зрения сложности реализации), плюс к его выходному каналу можно бесплатно прикрутить буфер, и, хотя чтение потоками из каналов тоже жёстко синхронизировано, накладные расходы должны бы быть поменьше и, возможно, такой подход будет вполне оправдан, при том, что он очень сильно упрощает весь код.

Если быть точным, то именно с такого подхода я и начал реализацию, в моём случае рабочая область это пространство слов заданной длины и мощности алфавита, один элемент это одно слово, а вот диапазоны, как они были реализованы в плюсовом коде, это несколько букв слова. Поэтому, если передавать диапазоны, то и генератору, и рабочему потоку, необходимо уметь перебирать буквы внутри слова, знать алфавит и длину. В случае же с выдачей из генератора не диапазона, а слова, всё это остаётся только в нём, а рабочие потоки получают одно слово, обрабатывают его и либо выдают результат, либо идут за следующим словом. С точки зрения реализации получилась разница в 25 % объёма кода!

Что касается буферов, то, очевидно, что при общении через канал имеет смысл поиграться с буферами, попробовать оценить, насколько синхронность отправки и приёма замедляет дело.

Ещё же один вопрос, который возник почти случайно, касается инструментальной стороны. У Го есть своя «родная» реализация от Гугла и независимая реализация в ДжиСиСи. Изначально я, конечно, использовал реализацию не от Гугла (ДжиСиСи 5.3.1), но потом попробовал и её (1.6.1).

И особенно важно было сравнить цифры с плюсовой реализацией. Для всех сравнений использовались два набора входных данных. Получились вот такие увлекательные цифры (всё в секундах):

Получается довольно наглядно, причём, очень хорошо видно, насколько огромное влияние оказывает реализация рантайма Го, родная гугловая реализация правильнее в разы, что можно видеть даже по загрузке процессора при работе программы, с джисисишной версией загрузка процессора (четырёхядерного) на диапазонном варианте не превышает 270–280 %, а вот гугловая стабильно кушает около 380 %, где-то так же, как и реализация на плюсах.

Также видно, что простая реализация всё-таки очень далека от оптимума, что ожидаемо, но так нагляднее. Правильная реализация с правильным рантаймом, получилось, даже смогла опередить плюсовый код по скорости, но это я бы связывал скорее не с чудесами компиляторов Го, а с разницей в реализации используемой программой криптофункции, если к плюсам подключить какой-нибудь ОпенССЛ, они будут однозначно бодрее.

Разница в буферизации укладывается в ожидания, для простой реализации это важный параметр, а вот для диапазонной влияние укладывается в погрешность измерений.

Если же сравнить с Си-плюс-плюсом объём кода, то получается, что симпатичная реализация на плюсах съела 350 строк кода, простая реализация на Го обошлась в 167 строк, а диапазонная в 208 строк. Плюсовую реализацию можно было бы поуменьшить, если не использовать объектность, но всё равно достаточного запаса в ней нет, Го явно дешевле при его знании, что и было ожидаемо.