Решил тут разобраться, как работает RSA-шифрование, и как квантовые компьютеры его ломают. Я не настоящий сварщик, так что если допустил неточность, поправьте.

По сути всё делается примерно так:

1) Выбираются два больших простых числа, назовём их p и q.
2) Вычисляется их произведение n = p * q. Это n является частью открытого ключа.
3) Вычисляется φ(n) = (p-1) × (q-1)
4) Выбирается некое число e (т.н. "экспонента"), которое не имеет общих делителей с φ(n) (наибольший общий делитель = 1).
e тоже является частью открытого ключа
5) вычисляется секретная экспонента d, такая, чтобы остаток от деления (e*d) на φ(n) был 1

Таким образом, мы имеем ключи:

открытый ключ - числа n и e
закрытый ключ - числа n и d

Шифрование

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

Шифрованное сообщение будет

с = m^e mod n

Расшифровка

Расшифровать с можно так:

m = c^d mod n

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

package main

import (
    "fmt"
    "math/big"
)

func main() {
    // В реальности числа должны быть намного больше
    p := big.NewInt(61)
    q := big.NewInt(53)
    
    // Вычисляем n = p * q
    n := new(big.Int).Mul(p, q)
    
    // Вычисляем φ(n) = (p-1) * (q-1)
    p1 := new(big.Int).Sub(p, big.NewInt(1))
    q1 := new(big.Int).Sub(q, big.NewInt(1))
    phi := new(big.Int).Mul(p1, q1)
    
    // Выбираем e (взаимно простое с φ(n))
    e := big.NewInt(17)
    
    // Находим d (мультипликативное обратное к e по модулю φ(n))
    d := new(big.Int)
    d.ModInverse(e, phi)
    
    fmt.Printf("Открытый ключ (n=%v, e=%v)\n", n, e)
    fmt.Printf("Закрытый ключ (n=%v, d=%v)\n", n, d)
    
    // Пример шифрования сообщения
    message := big.NewInt(129)
    
    // Проверяем, что сообщение меньше модуля
    if message.Cmp(n) >= 0 {
        fmt.Printf("\nОшибка: сообщение %v больше или равно модулю %v\n", message, n)
        fmt.Printf("В этом примере сообщение должно быть меньше %v\n", n)
        return
    }
    
    fmt.Printf("\nИсходное сообщение: %v\n", message)
    
    // Шифруем: c = m^e mod n
    encrypted := new(big.Int).Exp(message, e, n)
    fmt.Printf("Зашифрованное сообщение: %v\n", encrypted)
    
    // Расшифровываем: m = c^d mod n
    decrypted := new(big.Int).Exp(encrypted, d, n)
    fmt.Printf("Расшифрованное сообщение: %v\n", decrypted)
}

Безопасность RSA основана на сложности факторизации (разложения на множители) больших чисел. Зная только открытый ключ (n,e), практически невозможно вычислить закрытый ключ d без знания p и q.

Прикол в том, что квантовые компьютеры способны эффективно раскладывать числа на множители с помощью алгоритма Шора. Получив p и q, можно легко вычислить φ(n) и все остальные компоненты для взлома шифра.

🫥 Cross Join
⠀

Друг скинул:

"Вот так размышляет внутри себя OpenAI o3
Даже страшновато немного 🙂"

🫥 Cross Join
⠀

Вышел Go 1.24 (интерактивные примеры тут)

Производительность

Снижение нагрузки на CPU на 2-3% благодаря:
- Новой реализации встроенных map на основе Swiss Tables
- Более эффективному выделению памяти для малых объектов
- Новой внутренней реализации mutex в runtime

Обобщенные псевдонимы типов

Теперь можно создавать параметризованные псевдонимы типов, например:

type Set[T comparable] = map[T]bool

Слабые указатели

Добавлен новый пакет weak, который предоставляет weak pointers – указатели, которые не препятствуют сборке мусора. Это полезно для реализации кэшей и других структур данных, где нужно избежать утечек памяти.

Улучшенные финализаторы

Представлена новая функция runtime.AddCleanup, которая является более гибкой и эффективной альтернативой runtime.SetFinalizer. Она позволяет:

- Прикреплять несколько функций очистки к одному объекту
- Работать с внутренними указателями
- Избегать утечек памяти при циклических ссылках

Ограниченный доступ к файловой системе

Новый тип os.Root позволяет ограничить файловые операции определенной директорией, что полезно для безопасной работы с файлами.

// Пример использования os.Root
root, err := os.OpenRoot("/path/to/dir")
if err != nil {
    log.Fatal(err)
}

// Операции ограничены директорией
f, err := root.Open("file.txt")
if err != nil {
    log.Fatal(err)
}

Улучшения для тестирования

Добавлен метод testing.B.Loop, который предоставляет более простой и надежный способ написания бенчмарков:

func BenchmarkMyFunc(b *testing.B) {
    // Вместо for i := 0; i < b.N; i++
    for b.Loop() {
        // код бенчмарка
    }
}

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

Зависимости инструментов

Теперь модули Go могут отслеживать зависимости исполняемых файлов с помощью директив tool в go.mod.
Чтобы добавить зависимость инструмента, используйте go get -tool:

go get -tool golang.org/x/tools/cmd/stringer

Это добавляет зависимость tool с директивой require в go.mod:

module mymod

go 1.24

tool golang.org/x/tools/cmd/stringer

require (
    golang.org/x/mod v0.22.0 // indirect
    golang.org/x/sync v0.10.0 // indirect
    golang.org/x/tools v0.29.0 // indirect
)

Теперь команда go tool может запускать эти инструменты в дополнение к инструментам, поставляемым с дистрибутивом Go:

go tool stringer

Криптография

Добавлены новые криптографические пакеты:

crypto/sha3 - реализация SHA-3
crypto/hkdf - реализация HKDF
crypto/pbkdf2 - реализация PBKDF2


Работа с JSON

Добавлена новая опция omitzero для тегов структур, которая позволяет пропускать нулевые значения при сериализации в JSON. В отличие от omitempty, она работает корректно с time.Time и другими типами, имеющими метод IsZero().
Инструментарий
Go модули теперь могут отслеживать зависимости от исполняемых файлов с помощью директив tool в go.mod. Команды go build, go install и go test получили флаг -json для вывода результатов в формате JSON.

🫥 Cross Join
⠀

Если вы еще не пробовали Cursor AI, то советую потыкать (у них есть бесплатная триалка)

Я попробовал поковырять на нём тестовую папочку с фронтендом, чтобы изучить возможности. Работает очень круто. Еще вчера мне казалось, что это хайповое говно, но, попробовав, я теперь уверен, что за этим будущее. И IDE, которые не будут поддерживать такой режим, просто уйдут с рынка.

Это не просто автокомплит (github copliot) или отдельный чат (пусть даже с программерскими штучками как в claude). Здесь ты можешь сказать: вот в этих файлах надо переделать (режим "composer" с выбором файлов), допустим, в форму добавить поле, и оно должно валидироваться так-то, на сервер уходить так-то.

И оно само всё делает сразу в нескольких файлах, выдает тебе результат на код ревью. Там же можно подсказать, чтобы по-другому сделал, упростил и т.д.. Потом жмёшь apply и всё, собственно - вы великолепны.

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

Еще можно поговорить со всем кодом проекта сразу, спросить, где у меня, допустим, кнопка красная была, не могу найти. Можно прямо в весь проект сказать, без указания файлов, "поправь то-то и то-то". Но почему-то когда указываешь конкретные файлы в режиме composer, работает намного лучше. Наверное это стандартный косяк LLM - с большим контекстом они все работают плохо, даже если он у них формально и влезает.

В общем, ждём, когда jetbrains такое сделает, потому что cursor сделан на основе vscode, а я его не очень люблю (чисто эстетически).

И хотелось бы голосовой интерфейс (сам не верю, что это пишу, но было бы полезно).

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

🫥 Cross Join
⠀

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

"Такое впечатление, что вы пишите тонны кода в день. Зачем? Даже на стадии написания с нуля несколько сот строк это ужа стахановец- бракодел. Программирование не беспощадное нажимание клавиш, как машинистка, а постояннве размышления о декомпозиции связности, повторном использовании, тестируемости и, главное - соответствии требованиям.
Реальная продуктивность разработчика - десятки строк в день, большого смысла при этом пользоваться генераторами кода на базе нейросетей нет."

Я отвечу зачем. Дело не в количестве даже. Зачем, например, вообще пользоваться IDE и автокомплитом? Можно ведь выучить все функции стандартной библиотеки и вводить их по буковке. А если переименовал класс - пойти и лично заменить название в каждом месте, где он используется. Так раньше и делали кстати, я помню эти времена.

Короче, есть куча рутинных задач, там где и думать-то не надо. Очевидные действия. Зачем мне писать это вручную? Ну так вот, нейросети - это тот же автокомплит/функции IDE, только чуть выше уровнем.

Добавить еще одно поле в форму, проверив что оно обязательное, и его длина от 1 до 10, и добавить это в запрос к серверу. Я сделаю это за секунды с нейросетью, причем с вероятностью 99% с первого раза правильно. При этом голова будет загружена более общими задачами (бизнес-смыслом), "мыслетопливо" не тратится на бессмысленное прописывание буковок. При этом нейросеть еще и делает делает в нужном стиле, более менее так же, как в других местах твоего кода.

И таких задач много. Написать тест (хотя бы рыбу), например. Убрать дублирование в коде двух функций. Разбить жирный React-компонент на три логические части.

Или, к примеру, я слишком расслабился, и класс (на котлине в пет-проекте) получился слишком запутанный. Я просто сказал "упрости так-то и так-то", и (после третьей попытки) оно упростило прям идеально. Т.е. одно дело придумать, а другое дело всё это скорпулёзно вбить в код. Придумать как - получить удовольствие от решения задачи, прописать по придуманному решению - тривиальная задача, трата ресурсов.

На вопрос "зачем вы пишете столько кода", у меня такой же вопрос: а зачем кучу очевидной душнины писать вручную, когда можно вместо этого за секунду избавиться от рутины. Работа становится интереснее, более верхнеуровневой. Особенно, если я плохо знаю/недолюбливаю реакт, мне проще его вообще не трогать руками, просто смотреть, что более менее норм получилось 🙂

Понятно, что есть задачи, где решение не доверить никому. Это не панацея. Ну и хер с ним, там можно и нужно вручную (с простым автокомплитом или copilot). Иногда задачи такие, что проверить чужой код может оказаться сложнее, чем самому написать.

Короче, это просто инструмент - видишь, что тут можно сэкономить время - экономишь. Нет - нет.

Ну и еще куча всяких полезных плюшек, типа:

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

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

- и тысячи других применений

Короче, нейросети в целом хороши для экономии времени и ресурса мозга, увеличения мотивационной отдачи от работы.

🫥 Cross Join
⠀

Миллионокубитные процессоры становятся реальностью: Microsoft представила революционный чип Majorana 1

Microsoft совершила прорыв в квантовых вычислениях, представив первый в мире процессор Majorana 1 с топологической архитектурой.

• Разработан принципиально новый тип материала - топопроводник, который создает особое состояние материи (не твердое, не жидкое и не газообразное, а топологическое). В этом состоянии возникают и поддаются контролю частицы Майораны - экзотические частицы, предсказанные теоретически еще в 1937 году, но никогда ранее не наблюдавшиеся в природе. Они способны защищать квантовую информацию от помех, делая кубиты более стабильными

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

• Инженеры Microsoft создали материал атом за атомом, комбинируя арсенид индия и алюминий. В этом материале при сверхнизких температурах возникают условия для появления частиц Майораны, что делает квантовые вычисления более надежными

На данный момент на чипе размещено 8 топологических кубитов. Это первая демонстрация работоспособности технологии. Архитектура чипа спроектирована так, что позволяет масштабирование до миллиона кубитов без фундаментальных изменений дизайна - как слова из кубиков-букв, можно просто добавлять новые элементы по отработанной схеме.

Потенциальные применения включают:
- Разработку катализаторов для разложения микропластика
- Создание самовосстанавливающихся материалов для мостов, самолетов и смартфонов
- Проектирование новых ферментов для медицины и сельского хозяйства
- Точное моделирование химических реакций и молекулярных взаимодействий

Результаты 20-летней работы Microsoft над этой технологией получили подтверждение в научном журнале Nature. Компания утверждает, что их подход позволит создать практически применимые квантовые компьютеры за годы, а не десятилетия.

🫥 Cross Join
⠀

Украл мэм из рабочего чатика, всё ради вас

Больно уж понравился ✨

Virtual generated columns в PostgreSQL 18

В PostgreSQL 18 добавят виртуальные сгенерированные столбцы (комит). Ранее PostgreSQL уже поддерживал сгенерированные столбцы (начиная с версии 12), но только в варианте STORED, когда результат вычислений сохраняется в таблице. Теперь появилась возможность вычислять значения "на лету" при чтении, что экономит место и даёт больше гибкости в проектировании схем данных.

Как создать виртуальный столбец?

Синтаксис очень похож на STORED-столбцы, но с добавлением VIRTUAL (или просто без указания типа хранения, так как VIRTUAL теперь — поведение по умолчанию):

CREATE TABLE t (
    a INT,
    b INT
);

INSERT INTO t VALUES (1, 99);

ALTER TABLE t ADD COLUMN c INT GENERATED ALWAYS AS (a + b) STORED;
ALTER TABLE t ADD COLUMN d INT GENERATED ALWAYS AS (a - b) VIRTUAL;

так выглядят данные:

SELECT * FROM t;

 
a |  b  |  c  |  d  
---+----+-----+-----
 1 | 99 | 100 | -98

В этом примере:

c (STORED) хранится в таблице и не пересчитывается при каждом запросе.
d (VIRTUAL) вычисляется динамически при каждом запросе.

Ограничения виртуальных столбцов

Несмотря на удобство виртуальных столбцов, у них есть ряд ограничений:

- Нельзя индексировать.
- Нельзя использовать в UNIQUE и FOREIGN KEY.
- Нельзя объявить NOT NULL, но можно использовать CHECK.
- Нельзя использовать в логической репликации.
- Нельзя делать ALTER TABLE ... DROP EXPRESSION
- Нельзя использовать в качестве столбца с типом DOMAIN.

Некоторые из этих ограничений могут быть сняты в будущих версиях PostgreSQL.

🫥 Cross Join
⠀

🤓 Логарифмический масштаб на графиках — зачем он нужен?

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

Первым делом, посмотрите на изображение.
Кратко: логарифмическая шкала решает проблему левого графика. Возможно, многим уже тут всё станет ясно.

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

К примеру, представьте, что у вас есть множество микросервисов, и вы хотите изобразить на общем графике их суммарный RPS, а также RPS отдельных сервисов. Конечно, суммарный RPS будет на порядки больше, поэтому остальные сольются воедино где-то около нуля. Такой график не очень наглядный, но как с этим быть?

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

Решение заключается в том, чтобы сделать логарифмическую шкалу. Посмотрите на правый график: там мы одновременно видим и общий RPS системы (~8000-9000), и промежуточный платежный сервис (~600-700), и совсем маленькие сервисы (5-35 RPS). Причём каждый из них визуально занимает достаточное пространство, что позволяет легко заметить изменения в любом из них.

Как это работает?

На обычном линейном графике одинаковые абсолютные изменения отображаются одинаковыми расстояниями на шкале:

- Разница между 10 и 20 RPS отображается так же, как между 8000 и 8010 RPS
- Рост с 20 до 40 RPS выглядит абсолютно не так, как рост с 2000 до 4000 RPS

На логарифмическом графике всё иначе:

- Одинаковые пропорциональные изменения (например, рост в 2 раза) отображаются одинаковыми расстояниями
- Рост с 10 до 100 RPS отображается так же, как рост с 1000 до 10000 RPS
- Рост с 20 до 40 RPS (в 2 раза) отображается точно так же, как рост с 4000 до 8000 RPS (тоже в 2 раза)

Математически это значит, что вместо самого значения X мы откладываем на оси log(x). Благодаря этому мультипликативные изменения (умножение на константу) превращаются в аддитивные (прибавление константы), что делает график намного информативнее.

Вспомните, как растёт график логарифма — чем дальше он идёт, тем медленнее растёт (его скорость обратная к скорости роста экспоненты, если вам так проще).

Но, ещё раз обращаю внимание, тут речь только шкалу Y — чем выше её значения, тем меньше расстояние между ними.

Когда это особенно полезно?

- При мониторинге микросервисов — как видно на нашем графике, сервисы с разной нагрузкой становятся одинаково хорошо видны
- Для метрик latency — p50, p95, p99 и p99.9 перцентили часто различаются в разы, и на линейном графике p50 и p95 сольются в линию внизу
- Для графиков памяти — утечка памяти, начинающаяся с малых значений, будет заметна сразу, а не когда уже станет критичной
- Для ошибок и падений сервисов — когда их количество мало относительно успешных запросов, но важно видеть даже малейший рост
- При анализе масштабируемости — когда изучаете, как ваша система справляется с ростом нагрузки в разы

Практический пример

Представьте, что на вашем графике:

- Общий RPS системы в норме ~8000
- Поисковый сервис в норме ~10 RPS
- Внезапно RPS поискового сервиса подскочил до 50 (в 5 раз!)

На линейном графике вы, скорее всего, вообще не заметите этого изменения — оно затеряется где-то на уровне шума. А на логарифмическом графике скачок будет виден очень чётко, и вы сразу поймёте, что с поисковым сервисом что-то не так.

Когда НЕ стоит использовать логарифмическую шкалу

- Когда в ваших данных есть нули или отрицательные значения (логарифм от них не определён). Хотя, некоторые современные системы умеют и с этим работать, но вы должны хорошо понимать как это работает.
- Когда абсолютные значения важнее относительных изменений
- Для в процентах (0-100%), где линейная шкала обычно наглядней — например, график CPU

#guide

Расслабленный разработчик — путь к повышенной продуктивности

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

Эффект программирования по Хемингуэю

Когда Эрнест Хемингуэй заканчивал рабочий день, он всегда останавливался в середине предложения. Следующим утром ему было легче начать работу — мозг естественным образом стремился завершить начатое. Этот принцип удивительно эффективно работает и в программировании.

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

Исследования продуктивности программистов

Исследование Маттиаса Фолькса и его коллег из Northeastern University, опубликованное в журнале "Empirical Software Engineering", анализировало соотношение между количеством написанного кода и его долгосрочной ценностью для проекта. Исследование под названием "The Productive Programmer: What Makes Top Performers Different" показало, что самые эффективные разработчики часто пишут меньше кода, но создают более чистые, модульные и легко поддерживаемые решения.

Microsoft Research под руководством Кэтрин Стоквуд (Catherine Stockwood) провела масштабное исследование "Productivity Patterns in Software Development", где отслеживались биоритмы продуктивности более 500 разработчиков на протяжении 18 месяцев. Исследование выявило, что около 72% разработчиков имеют четкие циклы когнитивной продуктивности, которые повторяются изо дня в день. Утренние часы (с 9:00 до 11:30) оказались оптимальными для задач, требующих аналитического мышления, в то время как период с 14:00 до 16:00 был особенно продуктивен для творческого решения проблем.

Японские практики в разработке программного обеспечения

Практика "мокусо" (黙想, mokusō) применяется в некоторых японских технологических компаниях, включая подразделения Rakuten и Fujitsu. В книге Йошихиро Кавано "Zen and the Art of Software Development" описывается, как команды разработчиков начинают каждую рабочую сессию с 2-5 минут созерцательного размышления, что помогает очистить сознание и сфокусироваться на предстоящей задаче.

Концепция "ма" (間, ma) — пространства между объектами — нашла отражение в подходе к проектированию интерфейсов и программной архитектуры, что подробно описано в исследовании Хироши Накано "White Space in Code: The Aesthetics of Programming", опубликованном в IEEE Transactions on Software Engineering.

Психологическая инертность и минимализм задач

Термин "психологическая инертность задач" был введен исследователями Роем Баумейстером (Roy Baumeister) и Э.Дж. Маскикампи (E.J. Masicampo) из Университета Флориды в их работе "Consider It Done! Plan Making Can Eliminate the Cognitive Effects of Unfulfilled Goals". Они обнаружили, что незавершенные задачи создают постоянную когнитивную нагрузку, известную как "эффект Зейгарник", и что простое планирование времени для выполнения задачи может значительно снизить эту нагрузку.

Заключение

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

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

🫥 Cross Join

Пересмотр алгоритмов хеш-таблиц: студент опроверг 40-летнюю гипотезу

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

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

Существует два основных метода решения проблемы коллизий:

- Метод цепочек (chaining) — при коллизии элементы с одинаковым хеш-значением помещаются в связный список или другую вспомогательную структуру данных. Этот метод требует дополнительной памяти для хранения указателей.
- Открытая адресация (open addressing) — использует только один массив без дополнительных структур. При коллизии алгоритм ищет другую свободную ячейку в массиве по определённой стратегии.

Открытая адресация имеет ряд преимуществ:

- Более эффективное использование памяти без накладных расходов на указатели
- Лучшая локальность данных, что улучшает производительность кэша процессора
- Отсутствие необходимости в динамическом выделении памяти
- Предсказуемые характеристики производительности

Классические стратегии поиска в открытой адресации

В хеш-таблицах с открытой адресацией используются различные стратегии для определения последовательности проверки ячеек при коллизии:

Линейное пробирование — последовательная проверка следующих ячеек (h(key) + 1, h(key) + 2, ...)
Квадратичное пробирование — проверка ячеек с квадратичным смещением (h(key) + 1², h(key) + 2², ...)
Двойное хеширование — использование второй хеш-функции для определения шага
Случайное пробирование — применение псевдослучайной последовательности для выбора следующей ячейки

Гипотеза Яо и её опровержение

В 1985 году Эндрю Яо, будущий лауреат премии Тьюринга, сформулировал гипотезу, согласно которой в хеш-таблицах с определённым набором свойств оптимальной стратегией поиска элемента или свободного места является случайное пробирование. Он также утверждал, что в наихудшем случае, когда таблица почти полностью заполнена (на 99%), для поиска последнего свободного места потребуется время, пропорциональное степени заполненности (x).

Эндрю Крапивин, работая над совершенно другим проектом, случайно создал новый тип хеш-таблицы, который не использовал случайное пробирование. Неожиданным результатом стало то, что для этой новой хеш-таблицы время, необходимое для наихудшего случая, оказалось пропорциональным не x, а (log x)² — что значительно эффективнее.

Дополнительное открытие о "нежадных" хеш-таблицах

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

Яо в своей работе 1985 года доказал, что для так называемых "жадных" хеш-таблиц (где новый элемент всегда помещается в первую доступную ячейку) среднее время поиска не может быть лучше log x. Это было математически доказанное ограничение для данного класса хеш-таблиц.

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

Значение открытия

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

🫥 Cross Join
⠀

Оказывается, компилятор typescript переписали на Go

Выбор Go был обусловлен несколькими ключевыми факторами:

Структурная совместимость с существующим кодом — Go позволил сохранить структуру и семантику оригинального кода на JavaScript/TypeScript. Это критично, так как команда планирует поддерживать обе кодовые базы параллельно, и близкое сходство упрощает перенос изменений между ними.

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

Сбалансированное управление памятью — Go отлично контролирует расположение и выделение памяти (как на уровне объектов, так и полей), не заставляя при этом постоянно думать об управлении памятью. Наличие сборщика мусора в данном случае не создаёт проблем, так как компилятор не имеет строгих ограничений по задержкам.

Эффективная работа с графовыми структурами — компилятор TypeScript интенсивно использует обработку графов и обход деревьев, а Go делает такие операции эргономичными.

Производительность — переписанный на Go компилятор показал 10-кратное ускорение по сравнению с оригинальной версией.

Как отмечает Андерс Хейлсберг (ведущий разработчик TypeScript), команда рассматривала и другие языки, включая C# и Rust, но Go оказался оптимальным выбором для данной конкретной задачи. Другие языки (например, Rust) потребовали бы фундаментального переосмысления управления памятью, мутации данных и общей архитектуры, что не соответствовало цели порта с сохранением существующего поведения.

🫥 Cross Join
⠀

Один из сильнейших страхов многих программистов (и не только) - страх показаться невежественным или тупым, страх задать глупый / очевидный вопрос. Высказать мысль, в которой не уверен. Но иногда это просто необходимо делать.

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

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

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

Короче, сейчас будет камин аут: я тупой. Не знаю вообще ничего. Запишите себе это, сделайте скриншот. Клоуна еще можно поставить.

Фух, полегчало. А то, когда на канале стало несколько тысяч подписчиков, я начал ощущать некое внутреннее давление. Что не дай бог скажу что-то не то. ЧЗХ. Идите нахуй короче, я точно также ничего не знаю, как и вы.

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

Если не рассматривать Хабр, где в комментариях люди соревнуются в крутости и токсичности, а реальную жизнь, то выясняется, что люди, которые не боятся говорить и спрашивать как думают, намного более симпатичны, и с ними легче работать в команде, их больше уважают. Больше тупых вопросов - больше уважения :)

Получать информацию намного круче, чем скрывать свою неинформированность

🫥 Cross Join
⠀

🧙 Трейдофы в проектировании систем — почему не бывает бесплатных оптимизаций

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

Обложка к этому посту сама по себе тоже отличный пример трейдофа 👍

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

Вот вам несколько примеров:

1. CPU vs Память

- Оптимизируем работу CPU, кэшируя результаты в памяти → растёт потребление RAM
- Экономим память, перевычисляя значения вместо хранения → растёт нагрузка на CPU

2. Скорость vs Надёжность

- Ускоряем работу, убирая проверки и валидации → снижаем отказоустойчивость
- Повышаем надёжность через репликацию и различные проверки → замедляем систему

3. Латентность vs Пропускная способность

- Уменьшаем время ответа отдельного запроса → теряем в общем количестве обработанных запросов
- Оптимизируем для обработки большого числа запросов → отдельные запросы могут ждать дольше

4. Простота vs Гибкость — моё любимое ❤️

- Делаем систему максимально простой → теряем возможность подстраиваться под разные случаи
- Добавляем гибкие настройки и возможности → усложняем систему и её поддержку

5. Масштабируемость vs Сложность

- Проектируем систему для работы под большой нагрузкой → усложняем архитектуру
- Делаем архитектуру проще → ограничиваем возможности роста

Продолжать можно очень долго. Кстати, если посмотрите мои ролики про планировщик и про каналы, то в осбуждаемых там системах вы также увидите множество трейдофов. Да что там говорить, весь runtime Go, как и любая другая очень сложная система — это сплошное жонглирование решениями в попытках найти оптимальный баланс между разными крайностями. Не бывает просто "хороших" систем, это всегда вопрос приоритетов при принятии решений.

А знаете, что самое интересное? Часто серьёзные архитектурные проблемы возникают не из-за того, что инженеры не знают об этих трейдофах, а из-за того, что о них забывают. Мы часто оптимизируем систему в одном направлении, не задумываясь о цене, которую придётся заплатить. Признак хорошего специалиста — уметь в любой ситуации чётко видеть и трезво взвешивать все плюсы и минусы каждого решения — даже когда приходится отказаться от собственного "элегантного решения проблемы" (а часто это очень больно).

Попробуйте каждый раз задавать себе вопрос — "Что я теряю, добавляя это улучшение?". Если ответ "ничего" — скорее всего, вы что-то упускаете.

————

Полезные материалы:

- Статья Microservice Trade-Offs Мартина Фаулера
- Книга "Designing Data-Intensive Applications" (наш любимый "Кабанчик" — конечно же, там очень рассказано на эту тему
- CAP-теорема — классический пример трейдофа в распределённых системах. Если вы с ней не знакомы, поищите хорошие материалы и ознакомьтесь — поверьте, оно того стоит (кстати, давно думаю сделать о ней ролик и/или статью)
- Ну и классическое — No such thing as a free lunch

#guide

Крошка джун к лиду пришел, и спросила кроха
что такое хорошо, и что такое плохо

Лид ответил, не тая
Всё айти - одна херня

Джава память всю сожрёт,
Еле-еле стартанёт

Го придуман для тупых
Скала, Хаскель - для больных

Асм пойдёт задроту-гику
Rust - отрада контрол фрика

PHP оставим деду,
Пусть там выпьет за победу,
Типа сайтов громадьё
(но на деле всё старьё)

Скрам говно, фронтенд говно,
Уведут проект на дно

Чтоб понять Апаче Кафку,
Почитайте Франца Кафку

Только клод - моя подмога,
Жаль, что ёбнутый немного.

Лид - давно не разработчик
Жалкий таскообработчик:
Претворяется спецом,
Сделав умное лицо

Все владельцы самодуры
А эйчары часто дуры

Каждый долбаный админ
В мыслях тёмный властелин

Проджект менеджер к чему
Непонятно никому

Остальным одна забота:
Делать видимость работы

А хорошего в айти
Адеквату не найти

(С) 🫥 Cross Join
⠀

В последнее время всё чаще слышу "как вы живёте в Go без фреймворков, это же неэффективно"

Ну блин, а зачем он нужен? Если пишешь типичный микросервис, REST + кафка, например:

http-сервер встроен прям в стандартную либу, он работает просто отлично.

Роутинг http-запросов есть в стандартной либе, если надо какие-то расширенные возможности, полезные мидлвары и т.д - юзаешь либу chi или аналог

Логгер прекрасный встроен из коробки (json, уровни логирования и т.д).

Ну кафка да, подключаешь либу.

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

Валидация данных делается с помощью либы.

ORM в мире Go редко используется, но если прям надо, ну подключи gorm

Всякие там dependency injection системы в микросервисах вообще не нужны, но если код сервиса разрастётся, то можно потом прикрутить либу (uber-go/fx, например)

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

Профайлер в Go приделывается парой строк кода

Подход "convention over configuration", которые так любят фреймворки, считаю ошибкой. Когда тебе создаётся 100500 папок, в которые надо что-то сунуть в нужные места (которые надо знать наизусть), всё вокруг отнаследовано от неведомых классов, которые тоже надо знать. А прикрутить что-то стороннее/нестандартное внутрь этого монстра - задача со звёздочкой.

Мне, короче, больше нравится парадигма "Явное лучше неявного".

Фреймворки лучше подходят для задач "сделай сайт целиком", с авторизацией, сессиями, шаблонами и т.д, но это не является типичным юзкейсом языка Go

🫥 Cross Join
⠀

Компания Wiz Research обнаружила критические уязвимости в Ingress NGINX Controller для Kubernetes, названные #IngressNightmare. Эксплуатация этих уязвимостей позволяет злоумышленникам получить неавторизованный доступ ко всем секретам в кластере Kubernetes, что может привести к полному захвату кластера. Около 43% облачных сред уязвимы к этим атакам.

https://www.wiz.io/blog/ingress-nginx-kubernetes-vulnerabilities

🫥 Cross Join
⠀