golang

За последние пару месяцев я полюбил Go по разным субъективным причинам. Чтобы продемонстрировать всю красоту и простоту языка Go, рассмотрим классическую небольшую программу, которая поприветствует нас с помощью фразы Hello World.

Здороваемся

Есть несколько способов того, как можно отобразить на экране приветствие «Hello world!». В идеале нужно использовать блокчейн и нейронную сеть на серверной архитектуре (хайпа ради), но делать это всё ради простейшего вывода строчки на экран — это слишком трудозатратно и дорого.

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

Блок-схема типичной программы Hello, world!

Реализация такой схемы на языке Go довольно проста: мы выделим части из целевой строки, превратим их в руны и будем перетасовать с помощью функции rand.Shuffle до тех пор, пока она не будет соответствовать целевой строке.

// hello.go
package main
import (
  "fmt"
  "math/rand"
)
func main() {
  t := "Hello World!"
  s := []rune(t)
  
  for {
    rand.Shuffle(len(s), func(i int, j int) {
      s[i], s[j] = s[j], s[i]
    })
    if string(s) == t {
      break
    }
  }
fmt.Println(string(s))
}

Запустим этот скрипт с помощью команды go run hello.go

Потрясающе! Теперь у нас есть минимальная высокоэффективная рабочая версия программы «Hello World»!

Отслеживание прогресса

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

// hello.go
package main
import (
  "fmt"
  "math/rand"
)
func main() {
  t := "Hello World!"
  s := []rune(t)
  for {
    rand.Shuffle(len(s), func(i int, j int) {
      s[i], s[j] = s[j], s[i]
    })
    fmt.Println(string(s))
    if string(s) == t {
      break
    }
  }
}

Запустим программу с помощью go build hello.go

Круто! Она отработала!

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

$ hello | cat -n

При использовании такого набора по умолчанию нам потребуется сделать тридцать восемь миллионов пятьсот двадцать восемь тысяч девятьсот шестьдесят семь итераций, чтобы на выходе получить «Hello world».

Примечание. Если вы пытаетесь запустить этот код в операционной системе Microsoft Windows, а не на UNIX, сейчас самое время переоценить свой жизненный выбор.

Много — это больше, чем один

Наша программа на самом деле уже довольно быстро отрабатывает, учитывая то, сколько всего она должна делать. Сборщик мусора не сильно тормозит выполнение скрипта, даже несмотря на то, что мы постоянно создаем новые строки.

Тем не менее, мы можем ускорить исполнение кода, распараллелив создание строк, что, в свою очередь, позволит Go спланировать вычисления так, чтобы они по мере возможности выполнялись параллельно в нескольких аппаратных потоках.

Модель параллелизма Go основана на автономных совместных подпрограммах, которые обмениваются сообщениями по каналам, которые часто метафорично называют Gophers (суслики).

Итак, каков наш план? Заставим кучку маленьких сусликов делать всю работу: они будут пытаться угадать и выкрикнуть правильный вариант перестановки, пока мы просто будем сидеть в кабинете босса и решать, правильный он или нет.

Блок-схема сортировки с помощью сусликов

БОльшая часть нашей реализации останется прежней. Мы вынесем код перестановки в отдельную функцию, которая будет отправлять сообщения на наш канал. А в нашей основной функции будем перебирать сообщения и проверять их на эквивалентность нашей целевой строке.

// hello.main
package main
import (
  "fmt"
  "math/rand"
)
func main() {
  t := "Hello world!"
  c := make(chan string)
  for i := 0; i < 32; i++ {
    go gopher(t, c)
  }
  for s := range c {
    fmt.Println(s)
  if s == t {
      break
    }
  }
}
func gopher(t string, c chan string) {
  s := []rune(t)
  for {
    rand.Shuffle(len(s), func(i, j int) {
      s[i], s[j] = s[j], s[i]
    })
  c <- string(s)
  }
}

Успех! Теперь у нас есть кучка одновременно работающих сусликов!

Толпа — это сколько?

Какой прирост производительности нам удалось выиграть таким образом? На самом-то деле мы, наоборот, снизили производительность.

Больше не всегда лучше и оказывается, что для проведения этого урока не будет выделен бюджета на покупку процессора AMD Ryzen Threadripper(суперпроизводительный процессор с 32 потоками одновременной многозадачной мощности — прим.пер.). По крайней мере так изначально планировалось. Так что распределить 32 суслика в 4 рабочих потока означает, что им, возможно, придется ждать в своих назначенных очередях, прежде чем они смогут приступить к своим обязанностям.

И всё-таки, слишком много — это сколько? Здравый смысл подскажет нам, что это один экземпляр за поток выполнения, но единственный способ узнать точное значение — измерить его.

Мы будем измерять время, которое требуется для отработки программы (1).

График эффективности сусликов при выполнении сусличной сортировки

Отлично! У нас есть данные, шесть — это оптимальное количество сусликов … упс, подождите-ка минуту, тут возникла небольшая проблема!

Поскольку наша программа основана на псевдо-рандомности, она становится недетерминированной и довольно неустойчивой, как только мы начинаем использовать гоурутины ( go routines — легковесные потоки).

По сути, горутины сами по себе вносят в код неопределенность, потому что мы не делаем никаких блокировок, и нет гарантии того, в каком порядке будут поступать сообщения. Это означает, что мы в конечном итоге получаем гонку данных, но в данном случае это не проблема.

Причина, по которой нас ждет веселый сценарий состоит в том, что мы по умолчанию используем стандартный псевдо-случайный источник. Хотя сам источник детерминирован по умолчанию и технически подходит для параллельных вычислений, мы сталкиваемся с проблемой, лежащей в самой сути задачи.

Поскольку каждый суслик использует один и тот же источник, вероятность того, что суслик получит правильное предположение, резко сокращается, потому что «подсказка», которая могла бы дать суслику правильный ответ, дана другому суслику, который делает другое неправильное предположение.

Хорошо! Мы разобрались в данных, анализ эффективности тупой сортировки оказался… интересным?

Вывод

Наши суслики не могут работать одновременно качественно и самостоятельно, так как они не уверены, правильную ли верисю они называют. Поэтому в данном случае добавление большего количества кричащих сусликов не сильно помогло нам.

Мы узнали, что суслики могут выполнять обезьянью сортировку, то есть алгоритм обеспечивает межвидовую совместимость!

Перевод статьи Casper Beyer: “Hello Go