Thank Go!

Скорость алгоритмов: O(1)

O(1), так же известно как «константное время». Самый лучший вариант, скорость алгоритма не зависит от количества котиков входных данных.

🐾 Пример

Вы — счастливый обладатель N котиков. Каждый котик знает, как его зовут. Если позвать «Феликс!», то прибежит только он, а остальным N-1 жопкам пофиг.

🐈 🐈 🐈 🐈 🐈
🐈 🐈‍⬛ 🐈 🐈 🐈
    ↓
   мяу!

В жизни время выполнения O(1) обычно встречается при работе со срезами и картами.

Срезы

У среза известен адрес в памяти первого элемента и размер каждого элемента. Следовательно, адрес i-го элемента тоже известен (first + i*size) — а значит, доступ к i-му элементу выполняется за константное время. Изменение i-го элемента аналогично — тоже O(1).

s := make([]int, 1e6)
i := rand.IntN(1e6)
s[i] = 42 // O(1)
fmt.Println(s[i]) // O(1)

С добавлением и удалением элементов сложнее — они рано или поздно приводят к созданию нового массива под срезом — а это уже операция O(n). Но если аккуратно все посчитать, то получится, что в среднем добавление/удаление тоже константные.

Карты

Не вдаваясь в подробности скажу, что за картой тоже скрывается массив. Грубо говоря, когда вы пишете m["answer"] = 42, то Go превращает "answer" в целое число (хеш строки), после чего считает по нему нужный индекс в массиве. По этому индексу и находится значение 42.

d := map[string]int{}
d["answer"] = 42 // O(1)
fmt.Println(d["answer"]) // O(1)

Поэтому доступ к элементу карты по ключу — тоже O(1).

🐈

Скорость алгоритмов: O-нотация

Скорость работы алгоритмов принято оценивать в О-нотации: у медленного она «о», у более быстрого «ооо», у самого быстрого «ооооо ваще огонь».

Вру, конечно.

На самом деле, скорость оценивают в количестве действий, которое выполняет алгоритм. Например, если у вас дома 10 котов, и нужно определить самого увесистого, то придется взвесить каждого кота, то есть выполнить 10 операций.

Алгоритм, понятное дело, должен работать одинаковым образом что для 10 котиков, что для 100, что для 10000. Оценка же скорости нужна одна. Поэтому оценивают не конкретное количество операций, а количество операций относительно количества входных данных (котов в нашем случае).

Если у вас n котов, то чтобы определить самого жирненького, придется выполнить n взвешиваний. В таком случае говорят, что скорость работы алгоритма — O(n).

В реальности действий всегда будет не n, а несколько больше. Например, сначала нужно откалибровать весы, а в конце убрать их обратно в шкаф. Получается уже n+2 действия. Но поскольку дополнительных действий константное количество, их в оценке не учитывают: O(n+2) = O(n)

А что делать, если котики отказываются взвешиваться без рыбов? Тогда на каждого кота приходится 2 действия: выдать рыбку и взвесить, поэтому общее количество действий 2n. Но фактор 2× тоже константный, поэтому и его в оценке не учитывают: O(2n) = O(n)

Ровно так это работает и в коде:

var fattest Cat
for _, cat := range cats {
  if cat.weight > fattest.weight {
    fattest = cat
  }
}

Здесь на каждого кота выполняется до трех действий:

1. Выбрать очередного кота из среза
2. Сравнить вес кота с весом жирнейшего
3. (возможно) Обновить жирнейшего

То есть действий может быть до 3n+1 (+1 — инициализация переменной fattest). Но скорость работы алгоритма — O(n)

Таким образом, в O-нотации любые константные факторы игнорируются. Есть и другие нюансы, но с ними разберемся дальше по ходу дела.

P.S. Я пока не уверен, что реально нужна серия про скорость алгоритмов — может, для всех это совсем очевидная тема. Посмотрим, как пойдет.

🐈

Или

Допустим, ваше приложение по умолчанию слушает на порту 8080. Порт можно изменить, задав переменную окружения PORT. Как бы реализовать это в коде?

Можно так:

port := os.Getenv("PORT")
if port == "" {
  port = "8080"
}

А с функцией cmp.Or можно компактнее:

port := cmp.Or(os.Getenv("PORT"), "8080")

Or принимает любое количество аргументов и возвращает первый ненулевой. Работает в 1.22+

Мелочь, но приятная.

Курсы на Степике

На степике сегодня скидка 20% на все курсы по промо-коду STEPIKSALE20. Так что если давно хотели что-нибудь подучить, сейчас хороший момент, чтобы начать.

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

README для начинающих разработчиков

Нашел тут отличную книжку. Я бы ее выдавал всем начинающим разработчикам, а то и изучал отдельным предметом на старших курсах универа:

The Missing README

Это по сути такой очень подробный чеклист на 250 страниц по всяким хорошим практикам в разных областях разработки:

— Работа с кодом
— Проектирование и архитектура
— Управление зависимостями
— Тестирование
— Ревью кода
— Сборка, интеграция и деплой
— Решение инцидентов с прода
— Планирование и оценка
— Общение с менеджером
— Дальнейшая карьера

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

Есть перевод на русский, но он местами с потерей исходного смысла.

🗒 Узнаем больше о Go разработке 2024

Второй год подряд ребята из DevCrowd проводят большое исследование Go-разработчиков:

- Что входит в обязанности и каких навыков не хватает
- Сколько в среднем зарабатывают в профессии в зависимости от грейда
- Какие инструменты, сервисы наиболее популярны
- Что читают, слушают и смотрят для профессионального развития.

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

Результаты опроса помогут вам сравнить свои ожидания с рыночными, построить план своего развития, и просто понять, что происходит с индустрией!

👉 Пройти опрос

👀 Посмотреть результаты прошлого года

Проверки в коде

Разберем функцию, которая проверяет разрешения пользователя:

// CanEdit returns true if the user can edit objects.
func CanEdit(user *User) bool {
  if user.IsActive() {
    perms := user.Permissions()
    for _, perm := range perms {
      if perm == PermWrite {
        return true
      }
    }
    return false
  } else {
    return false
  }
}

Оставим за скобками вопросики к типу User — например, почему CanEdit не сделан методом. Для простоты будем считать, что тип User менять нельзя.

Первая проблема — нет проверки на nil. Вторая — отсутствие early return (он же guard clause). С nil, думаю, и так понятно, а вот на раннем возврате остановимся подробнее.

В реальной жизни проверки в функциях часто бывают более сложными, вроде таких:

func Do() {
    if cond_1 {
        // do stuff
        if cond_2 {
            // do more stuff
            if cond_3 {
                // do even more stuff
            }
        }
    }
}

Читать такое больно из-за лесенки ифов. Лучше переделать на ранний возврат, а «основной сценарий» сделать без отступов:

func Do() {
    if !cond_1 {
        return
    }
    // do stuff

    if !cond_2 {
        return
    }
    // do more stuff

    if !cond_3 {
        return
    }
    // do even more stuff
}

Теперь явно видно, что делает функция, и что в ней может пойти не так.

Применим к CanEdit:

func CanEdit(user *User) bool {
  if user == nil || !user.IsActive() {
    return false
  }
  for _, perm := range user.Permissions() {
    if perm == PermRead {
      return true
    }
  }
  return false
}

Можно еще заменить цикл на slices.Contains (хотя это уже частности):

func CanEdit(user *User) bool {
  if user == nil || !user.IsActive() {
    return false
  }
  perms := user.Permissions()
  return slices.Contains(perms, PermRead)
}

Главное — не забывайте проверять на nil и использовать ранний возврат.

Проверки в коде

Есть вот такая функция, которая проверяет разрешения пользователя.

// CanEdit returns true if the user can edit objects.
func CanEdit(user *User) bool {
  if user.IsActive() {
    perms := user.Permissions()
    for _, perm := range perms {
      if perm == PermWrite {
        return true
      }
    }
    return false
  } else {
    return false
  }
}

Что думаете о ней? (опрос следует)

Go 1.23

Тут вышел Go 1.23, ну а мы с вами успели разобрать основные изменения заранее:

— Итераторы
— Таймеры
— Уникальные значения
— Скопировать каталог
— Куки

Все вместе с интерактивными примерами:
https://antonz.org/go-1-23

Большая крыса Go

Прежде чем вы решите, что я сошел с ума — речь на самом деле о типе big.Rat.

В отличие от float64, он позволяет работать с обыкновенными дробями (a/b) без потери точности.

Например, из школьного курса математики мы знаем, что 1/10 + 2/10 = 3/10. Однако, float64 другого мнения:

x := 0.1
y := 0.2
fmt.Println(x + y)
// 0.30000000000000004

А вот big.Rat справляется с такими вычислениями без проблем:

x := big.NewRat(1, 10)
y := big.NewRat(2, 10)
z := new(big.Rat)
z.Add(x, y)
fmt.Println(z)
// 3/10

Если вдруг придется работать с обыкновенными дробями — имейте «крысу» в виду.

Статический HTTP-сервер

Вы, наверно, слышали про встроенный в Python статический сервер:

python -m http.server 8080

На Go его можно реализовать в десять строчек кода (плюс импорты):

func main() {
  port := "8000"
  if len(os.Args) > 1 {
    port = os.Args[1]
  }

  fs := http.FileServer(http.Dir("."))
  http.Handle("/", fs)

  log.Printf("Serving HTTP on port %s...\n", port)
  log.Fatal(http.ListenAndServe(":"+port, nil))
}

И запускать вот так:

go run http.go 8080

Кто канал создал, тот и закрывает

В Go есть одна эвристика, которую лучше не нарушать без веских причин: кто канал создал, тот и закрывает.

Поэтому мне больше по душе такая реализация канала завершения:

func work() <-chan struct{} {
  done := make(chan struct{})
  go func() {
    // do work
    time.Sleep(10 * time.Millisecond)
    close(done)
  }()
  return done
}

done := work()
<-done

Если нужно не просто сигнализировать о завершении, а возвращать значение — заменяем chan struct{} на нужный тип вроде chan int, и готово.

А если хотим возвращать еще и ошибку, то так:

type Result[T any] struct {
  Value T
  Err   error
}

func work() <-chan Result[int] {
  out := make(chan Result[int], 1)
  go func() {
    // do work
    time.Sleep(10 * time.Millisecond)
    out <- Result[int]{Value: 42}
    close(out)
  }()
  return out
}

out := work()
result := <-out
fmt.Println(result)
// {42 <nil>}

песочница

Удобно!

Канал завершения

Как вы знаете, с помощью done-канала горутина сигнализирует вызывающему, что закончила работать.

Есть пара вариантов реализации:

➊ Принимаем done-канал на входе

func worker1(done chan struct{}) {
  // do work
  time.Sleep(10 * time.Millisecond)
  close(done)
}

done := make(chan struct{})
go worker1(done)
<-done

➋ Возвращаем done-канал из функции

func worker2() chan struct{} {
  done := make(chan struct{})
  go func() {
    // do work
    time.Sleep(10 * time.Millisecond)
    close(done)
  }()
  return done
}

done := worker2()
<-done

песочница

Какой вариант вам больше по душе и почему?

Про печеньки

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

За годы развития веба куки обзавелись дополнительной атрибутикой. Вот как выглядит структура Cookie в Go 1.23:

— Name и Value — ключ и значение.
— Quoted — true, если значение передано в кавычках.
— Path — разрешает куку на страницах, которые начинаются с указанного пути.
— Domain — разрешает куку на указанном домене и всех его поддоменах.
— Expires — дата окончания годности куки.
— MaxAge — срок жизни куки в секундах.
— Secure — разрешает куку только по HTTPS.
— HttpOnly — закрывает доступ к куке из JavaScript.
— SameSite — разрешает или запрещает куку при кросс-доменных запросах.
— Partitioned — ограничивает доступ к third-party кукам.

Неслабо, да?

Начиная с версии Go 1.23, серверную куку можно распарсить из строки с помощью http.ParseSetCookie:

line := "session_id=abc123; SameSite=None; Secure; Partitioned; Path=/; Domain=example.com"
cookie, err := http.ParseSetCookie(line)

Браузерные куки тоже можно распарсить из строки, с помощью http.ParseCookie:

line := "session_id=abc123; dnt=1; lang=en; lang=de"
cookies, err := http.ParseCookie(line)

песочница

Скопировать каталог

Раньше, чтобы рекурсивно скопировать каталог со всем содержимым, вам пришлось бы написать 50 строк кода.

Теперь, благодаря os.CopyFS в Go 1.23, будет достаточно одной:

src := os.DirFS("/home/src")
dst := "/home/dst"
err := os.CopyFS(dst, src)

Вроде и мелочь, но весьма уместная.

Уникальные значения

Продолжаем разбирать нововведения в Go 1.23.

Новый пакет unique помогает сэкономить память, если обрабатываются неуникальные значения.

Рассмотрим пример. У нас есть генератор слов:

const nDistinct = 100
const wordLen = 40
generate := wordGen(nDistinct, wordLen)

fmt.Println(generate())
// nlfgseuif...
fmt.Println(generate())
// anixapidn...
fmt.Println(generate())
// czedtcbxa...

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

Сгенерим 10000 слов и запишем их в срез строк:

words = make([]string, nWords)
for i := range nWords {
    words[i] = generate()
}

Memory used: 622 KB

10К слов заняли 600 Кб в куче.

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

words = make([]unique.Handle[string], nWords)
for i := range nWords {
    words[i] = unique.Make(generate())
}

Memory used: 95 KB

100 Кб вместо 600 Кб — в 6 раз меньше памяти.

Функция Make создает уникальный дескриптор для значения любого comparable-типа. Она возвращает ссылку на «каноническую» копию значения в виде объекта Handle.

Два Handle равны только в том случае, если равны исходные значения. Сравнение двух Handle эффективно, потому что сводится к сравнению указателей.

Под капотом пакет unique ведет глобальный конкурентно-безопасный кеш всех добавленных значений, гарантируя их уникальность и повторное использование.

песочница

Пустышки

Вряд ли вы об этом задумывались, но все эти конструкции в Go разрешены:

// ничего не делает
{}

// ничего не делает
switch {}

// бесконечный цикл
for {}

// блокирует горутину
select {}

Полезным может быть разве что select{} для быстрых демок — это самый короткий способ заблокировать горутину.

Например:

func main() {
  // тикающая горутина
  go func() {
    ticker := time.NewTicker(1 * time.Second)
    for range ticker.C {
      fmt.Print(".")
    }
  }()

  // блокирует горутину main
  select {}
}

Ча-ча-ча

(несерьезное) В чате спросили, разбирается ли на курсе тема канала каналов (chan chan). Пользуясь случаем, хочу вам его представить.

Встречайте: ча, чача, и ча-ча-ча:

cha := make(chan int, 1)
chacha := make(chan chan int, 1)
chachacha := make(chan chan chan int, 1)

cha <- 1
chacha <- cha
chachacha <- chacha

fmt.Printf("%#v\n", chachacha)
// (chan chan chan int)(0x14000102180)

Если серьезно, то канал — это всего лишь указатель на структуру. Ничего особенного в нем нет.

Поэтому канал может содержать другие каналы точно так же, как указатели на строки или числа или любые другие значения. Нет принципиальной разницы.

✓ Курс «Многозадачность в Go»

Закончил курс по многозадачности! Вот какие темы в нем разобраны:

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

Если вы совсем не знакомы с многозадачностью, курс поможет освоить ее с нуля. А если уже прошли модуль «Многозадачность» на курсе «Go на практике» — детально разберетесь в гонках, синхронизации и пакетах sync и atomic.

Как обычно, все концепции разобраны на практических примерах и закреплены задачками с автоматической проверкой.

Курс непростой. Подойдет практикующим разработчикам с уверенным знанием основ Go.

https://stepik.org/a/133280

Цена скоро вырастет.

Всем go 💪

Таймеры в Go 1.23

Тут прям детективная история приключилась. В Go есть таймер (тип Timer), а в нем — поле с каналом (Timer.C), в который таймер тикает спустя указанное время.

В коде стдлибы таймер создается так:

func NewTimer(d Duration) *Timer {
  c := make(chan Time, 1)
  t := &Timer{
    C: c,
    // ...
  }
  startTimer(&t.r)
  return t
}

Такая реализация привела к проблемам с time.After и Reset, от которых многие страдали.

И вот в Go 1.23 решили это исправить, для чего сделали канал в таймере небуферизованным:

// As of Go 1.23, the channel is synchronous (unbuffered, capacity 0),
// eliminating the possibility of those stale values.
func NewTimer(d Duration) *Timer {
  c := make(chan Time, 1)
  t := (*Timer)(newTimer(when(d), 0, sendTime, c, syncTimer(c)))
  t.C = c
  return t
}

Вот только если вы посмотрите на фактический код, то канал-то остался буферизованным 😁

c := make(chan Time, 1)

Из комментариев к коммиту выясняется, что канал действительно остался буферизованным, но притворяется, что никакого буфера у него нет:

Specifically, the timer channel has a 1-element buffer like it always has, but len(t.C) and cap(t.C) are special-cased to return 0 anyway, so user code cannot see what's in the buffer except with a receive.

Эту логику вкорячили прямо в реализацию канала (тип chan).

Что тут скажешь. Ну и дичь.

Git в примерах

Зашел я на Степик в новые курсы, а там «Основы Git». В связи этим вспомнил, что у меня тоже есть интерактивная книга / сборник рецептов по гиту, называется Git by example.

Удобный краткий формат с конкретными примерами, я сам туда постоянно подглядываю (особенно в раздел undo).

Загляните и вы, если не обзавелись еще черным поясом по гиту.

https://antonz.org/git-by-example

P.S. А вы же знаете, что по Go тоже такая есть?

Безопасные ворота

Вот три способа безопасно закрыть ворота, один другого краше.

➊ sync.Mutex

Дубовый, но надежный способ. Защищаем изменение логического поля closed мьютексом:

type Gates struct {
  // признак закрытия ворот
  closed bool
  // мьютекс для защиты closed
  mu sync.Mutex
}

func (g *Gates) Close() {
  g.mu.Lock()
  defer g.mu.Unlock()
  if g.closed {
    // игнорируем повторное закрытие
    return
  }
  // закрыть ворота
  g.closed = true
  // освободить ресурсы
}

➋ atomic.Bool

Compare-and-set на атомарном bool гарантирует, что только одна горутина сможет поменять значение с false на true:

type Gates struct {
  // признак закрытия ворот
  closed atomic.Bool
}

func (g *Gates) Close() {
  if !g.closed.CompareAndSwap(false, true) {
    // игнорируем повторное закрытие
    return
  }
  // закрыли ворота,
  // можно освободить ресурсы
}

➌ sync.Once

Once.Do гарантирует однократное выполнение в конкурентной среде, поэтому не приходится даже явно хранить состояние:

type Gates struct {
  // гарантирует однократное выполнение
  once sync.Once
}

func (g *Gates) Close() {
  g.once.Do(func() {
    // освободить ресурсы
  })
}

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

Кто ваш любимчик? Поделитесь в комментариях.

Опасные ворота

Вот наши ворота:

type Gates struct {
  // признак закрытия ворот
  closed chan struct{}
}

func (g *Gates) Close() {
  select {
  case <-g.closed:
    // игнорируем повторное закрытие
    return
  default:
    // закрыть ворота
    close(g.closed)
    // освободить ресурсы
  }
}

Метод Close — небезопасный. Если две горутины одновременно вызовут Close, обе могут провалиться в default-ветку селекта, обе попытаются закрыть канал, и второе закрытие приведет к панике.

Другими словами, здесь гонки на закрытии канала. Селект сам по себе не защищает от гонок. Sad but true.

Что с этим делать — традиционно в следующей заметке.

Помоги Маше закрыть ворота

Друзья, тут такое дело. Маша закрывает ворота вот так:

type Gates struct {
  // признак закрытия ворот
  closed chan struct{}
}

func (g *Gates) Close() {
  select {
  case <-g.closed:
    // игнорируем повторное закрытие
    return
  default:
    // закрыть ворота
    close(g.closed)
  }
}

Безопасно ли одновременно вызывать Close() из нескольких горутин? Опрос следует.

P.S. Чур в комментариях ответ не спойлерить!