Hacker News Digest

Статья разбирает, как структуры данных влияют на производительность Go-программ под современными CPU. Автор подчеркивает, что чтение из оперативной памяти в 60 раз медленнее, чем из кэша L1, и что ложный обмен (false sharing) между ядрами может убить производительность. Показано, как добавление 56-байтовой прокладки между полями структуры устраняет проблему и ускоряет код в 6-10 раз. Другой совет — разделять «горячие» и «холодные» данные и использовать структуры, оптимизированные под кэш-линии. Показано, как профилировать кэш-промахи через perf и как тестировать эффективность структур данных.

• False sharing и cache-line padding в Go приводят к 10-кратному ускорению при использовании структур, разделённых на разные ядра, но требуют ручного управления выравниванием и размером кэш-линии.
• Компилятор Go не переупорядочивает поля структур и не вставляет паддинг, что делает невозможным автоматическое устранение false sharing без кода, что ограничивает оптимизации только ручными методами.
• Пользователи отмечают, что большинство описанных приёмов применимы к другим языкам и что современные компиляторы должны бы справляться с большинством этих проблем автоматически, но в то же время признают, что для низкоуровневой оптимизации лучше подойдут другие языки и инструменты.

• Сортировка с хешем быстрее хеш-таблиц: на больших данных 1,5–4×, несмотря на «O(n log n)».
• Память: хеш-таблица тянет 128 Б на 8-Б ключ (64 чтение + 64 запись), радикс-сорт 3 прохода — 48 Б (вся линия кэша используется).
• Плохие распределения (мало заполненных корзин) замедляют радикс-сорт; решаем хешем hash(key) перед сортировкой. Берём обратимую функцию (Murmur3, MulSwapMul), хешируем «на лету» в первом проходе.
• Результат: 2 ГиБ уникальных uint64 за 1,9 с против 2,6 с у оптимизированной хеш-таблицы.
• Подходит, когда порядок не важен, а нужны только уникальные значения; иначе остаёмся на хеш-таблицах.

• Улучшенная нестабильная сортировка Rust почти догнала по скорости специально настроенный radix-sort, несмотря на разницу в O(n log n) vs O(n).
• Хэш-таблица «побеждает» лишь при ограниченном размере ключа и хорошем кэше; при росте данных снова проигрывает из-за промахов и O(n log n) внутри.
• Radix можно ускорить, выделяя buckets через MMU, а не вручную управляя памятью.
• На очень больших объёмах (≥120 ГБ) константы radix снова могут перевесить, но пока доминирует кэш-эффективность сортировки.
• Всё обсуждение подчёркивает: конкретные константы и архитектура CPU важнее «чистой» Big-O.