Hacker News Digest

При оптимизации кастомной ограниченной приоритетной очереди автор столкнулся с парадоксальным случаем, когда уровень оптимизации O3 работал на 123% медленнее, чем O2. Этот результат был подтверждён на процессорах Intel Haswell и AMD Zen 3, что указывает на системную проблему, а не на специфичную для архитектуры. Бенчмарки проводились с использованием criterion, а результаты демонстрировали устойчивую регрессию производительности при повышении уровня оптимизации.

Реализация использует отсортированный Vec с бинарным поиском вместо бинарной кучи, что эффективнее для данного случая из-за требования уникальности id элементов. Ключевую роль играет функция сравнения, работающая с числами с плавающей запятой, которые известны своей сложностью в сравнении. Для анализа производительности автор использовал flamegraph, чтобы выявить разницу в поведении между уровнями оптимизации.

Nice read. Last week I wrote a blog post about two noteworthy cases of O3 being slower than O2 in C++: https://barish.me/blog/cpp-o3-slower/ In the branchy function, id is only compared if distance is equal, and since distance is a random float, this almost never happens and the

Для высокой производительности B+Tree узлы должны размещаться в памяти как единый непрерывный блок, что улучшает локальность данных и повышает вероятность попадания в кэш процессора. В C++ это требует отказа от std::vector из-за дополнительной косвенности через отдельное выделение памяти, и вместо этого используется гибкий массив (flexible array member) — техника, унаследованная из C. Массив переменной длины объявляется как последний член структуры без указания размера, что позволяет динамически выделять память под весь узел и его записи единым блоком.

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

This pattern was officially standardized in C99,No it wasn't; the C99 flexible array uses [] not [1] or [0].When using the [1] hack, you cannot use the sizeof the structure to get the offset, because it includes the [1] array.When using C99, you also cannot use sizeof to get th

Rust-разработчик взглянул на Vec<T> и обнаружил, что вместо ожидаемых трёх полей ptr, len, capacity внутри структура скрыта целая иерархия обёрток: RawVec, RawVecInner, Unique, NonNull и NonNull<T> — всё ради безопасности и гибкости. Это вызвало вопрос: зачем такая сложность, если можно было обойтись тремя полями? Ответ оказался в том, что каждый слой добавляет безопасность и абстракцию, защищая от ошибок с указателями.

• Обсуждение развивалось вокруг того, что стандартная библиотека Rust предоставляет безопасные абстракции над низкоуровневыми деталями, но при этом не скрывает их полностью, и что это влияет на то, как код на Rust выглядит и ощущается.
• Участники обсуждали, что сложность реализации Vec в стандартной библиотеке Rust отражает компромисс между безопасностью и производительностью, и что это влияет на то, как разработчики думают о системе типов и управлении памятью в Rust.
• Также обсуждались вопросы о том, как документация и обсуждение в сообществе Rust может быть улучшена, включая сравнение с C++ и обсуждение того, как язык программирования влияет на то, как мы думаем о коде.
• Участники также затронули тему того, что сложность реализации может отпугнуть новичков, но что это может быть уменьшено путем улучшения документации и обучающих материалов.
• В конце концов, обсуждение завершилось тем, что участники сошлись на том, что хотя Rust и предоставляет мощные и безопасные абстракции, это не делает его легким для новичков без качественного обучения и документации, и что это может быть улучшено.

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

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

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

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

• Участники отмечают сильные стороны Ada, такие как ограниченные числовые типы для предотвращения ошибок, выразительная система типов и удобочитаемость, но сожалеют о его недостаточном распространении вне сообщества safety-critical разработки.
• Rust ценится за безопасность памяти, фокус на надежности и растущую экосистему, но критикуется за отсутствие формальной спецификации (хотя она сейчас разрабатывается) и сложность с компилятором и асинхронностью.
• Поднимаются вопросы о различиях в подходах к строкам (Ada использует массивы символов, Rust — UTF-8), многопоточности (встроенные потоки vs. async) и индексации массивов (произвольные типы в Ada vs. словари в Rust).
• Обсуждаются практические аспекты: скорость компиляции, поддержка Unicode, необходимость спецификаций и влияние экосистемы (инструменты, библиотеки) на выбор языка.
• Упоминаются нишевые применения Ada (например, в 3D-печати) и потенциальные заимствования его функций (ограниченные типы) в другие языки, такие как Rust, C++ и Nim.

Аренная память в Rust предлагает альтернативу прямым ссылкам для структур с циклическими зависимостями, таких как двусвязные списки или графы объектов. Вместо указателей используются индексы (хэндлы) в заранее выделенном массиве (арене), что позволяет обойти ограничения системы владения Rust, сохраняя при этом детерминированное поведение и безопасность.

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

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

• Обсуждается сложность реализации двусвязных списков и циклических ссылок в Rust из-за системы владения, предлагаются решения через арены, weak pointers и изменения в языке.
• Поднимаются вопросы безопасности памяти: арены и handles могут предотвратить неопределённое поведение, но не исключают ошибки в пределах границ, что может привести к уязвимостям.
• Сравниваются подходы к управлению памятью: ручное управление через арены vs. сборка мусора, отмечаются компромиссы между производительностью, безопасностью и сложностью разработки.
• Высказываются мнения о месте Rust среди других языков: он конкурирует с C++ по производительности и безопасности, а с GC-языками — по простоте, но имеет крутую кривую обучения.
• Обсуждается необходимость и сложность добавления в Rust стабильного API для аллокаторов и других низкоуровневых возможностей для большей гибкости и контроля.

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

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

• Обсуждение затрагивает различные типы diff-алгоритмов (одномерные, многомерные, древовидные) и их применение, включая сравнение кода, JSON-структур и даже схем баз данных.
• Участники делятся инструментами для просмотра diff (например, diff2html, meld, Beyond Compare) и отмечают проблемы существующих библиотек, такие как неожиданное экранирование текста.
• Поднимаются вопросы о важности минимальности diff, семантического понимания перемещений блоков и использования метаданных для улучшения алгоритмов.
• Обсуждаются практические применения diff-алгоритмов за пределами контроля версий: в тестировании, юридической сфере, сравнении расписаний и обновлении терминальных экранов.
• Упоминаются конкретные личности (например, Джин Майерс) и работы (статья Nugroho 2019 года), а также выражаются пожелания по улучшению алгоритмов, например, для работы с перемещенными данными.

Новички в программировании часто зацикливаются на изучении структур данных и алгоритмов (DSA), потому что это проверяется на собеседованиях. Однако в реальной работе редко приходится реализовывать сложные алгоритмы вручную — вместо этого стоит понять базовые структуры, их trade-offs и основы Big O, чтобы эффективно организовывать и обрабатывать данные.

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

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

Quicksort — эффективный алгоритм сортировки, основанный на стратегии «разделяй и властвуй». Он работает, выбирая опорный элемент и разделяя массив на части: элементы меньше опорного и больше него, затем рекурсивно сортирует каждую часть. Случайный выбор опорного элемента помогает избежать худшего случая производительности, обеспечивая среднее время выполнения O(n log n).

Проект IDEA представляет алгоритмы в виде невербальных инструкций, похожих на руководства IKEA, что делает их понятными для международной аудитории. Эти материалы распространяются под лицензией Creative Commons и используются в образовательных целях, позволяя учителям и студентам визуально осваивать сложные концепции. Инициатива получила широкое освещение в медиа и академических кругах.

• Участники обсуждают эффективность объяснения алгоритма быстрой сортировки (quicksort) с помощью метафоры инструкций IKEA, отмечая, что такой подход может быть полезен как повторение, но не для первоначального изучения.
• Некоторые пользователи указывают на неточности в визуализации, например, пропуск ключевых шагов или ошибки в порядке элементов, что может привести к непониманию или неправильной реализации алгоритма.
• Поднимается вопрос о целесообразности использования quicksort по сравнению с другими алгоритмами, такими как сортировка слиянием (merge sort), из-за худшего времени выполнения в худшем случае.
• Обсуждается культурный аспект названия "KVICK SÅRT" и использование диакритических знаков для создания "IKEA-стиля", что некоторые находят неудачным или раздражающим.
• Упоминаются альтернативные способы визуализации алгоритмов, такие как диаграммы железной дороги (railroad diagrams) или венгерские народные танцы, как более эффективные или эстетичные варианты.

Алгоритм CRDT для совместного текста

Каждый символ получает уникальный id: site (идентификатор узла) и clock (локальный счётчик, увеличиваемый после каждой операции), а также parent — указатель на предыдущий символ.

• Вставка
  parent ставится на символ перед точкой вставки (null — в начало). Порядок символов задаётся прямым обходом дерева: родители идут раньше потомков.

• Сортировка при одинаковом parent
  Сначала по убыванию counter, затем по site. При вставке перед символом с тем же parent берём его counter + 1.

• Удаление
  id символа попадает в множество удалённых (tombstone). Значение можно забыть, но позиция нужна для корректного порядка.

Оптимизации

1. Последовательные вставки одного узла объединяются в блок: массовая вставка стоит как одна операция.
2. Блоки хранятся в отсортированном массиве; вставка — O(log n) без явного дерева.
3. Удаления группируются диапазонами по site и clock.

Плюсы и минусы

• Плюсы: разумный расход памяти, быстрые запросы/обновления.
• Минусы: сложная логика слияния, только рост метаданных, сборка мусора требует координации.

Интерактивный пример
Четыре пира, задержка сети, редактирование кликом. Исходник — crdt-text-buffer.js.

Полезные ссылки

• josephg.com/blog/crdts-go-brrr/ — эффективная реализация.
• archagon.net/blog/2018/03/24/data-laced-with-history/ — деревья и сборка мусора.

• Обсуждали RGA — CRDT-алгоритм для списков и текста, который Automerge раньше использовал до перехода на FugueMax.
• У RGA есть редкая проблема: при вставке элементов в обратном порядке у разных пользователей возникает чередование.
• Упомянули Eg-Walker — новый подход от Loro.dev, который вызвал интерес у участников.

Моя предыдущая статья о обобщённых структурах данных в C готовила почву к теме: структура, которая заменяет динамические массивы, даёт стабильные указатели и хорошо работает с аренными аллокаторами. Её переоткрывали много раз под разными именами: “levelwise-allocated pile” (2001), в Zig — Segmented List, частично похожая на C++ std::deque. Мне нравится название Per Vognsen — Segment Array.

Скачать мой однофайловый заголовок segment_array.h можно, подписавшись на рассылку.

Идея проста: фиксированный массив указателей на сегменты; каждый следующий сегмент вдвое больше предыдущего; новые сегменты выделяются по мере необходимости. Поскольку элементы не двигаются, указатели на них стабильны, не остаются “дыры” в арене, а доступ по индексу — за O(1).

Реализация

Структура на C:

typedef struct { u32 count; int used_segments; u8 *segments[26]; } SegmentArrayInternal;

Почему всего 26 сегментов? Из 64 бит указателя обычно реально используются 48, так что 49 сегментов уже перекрывают адресное пространство (~256 ТиБ). Я предпочитаю индекс u32 (до ~4 млрд элементов) — это даёт 32 сегмента. Ещё убираем 6 маленьких (1..32), начинаем с 64, остаётся 26 сегментов — хватает для 4 294 967 232 элементов (чуть меньше UINT32_MAX). Фиксированный массив рядом со структурой снижает риск промаха кэша.

Размеры сегментов — степени двойки: проще математика и быстрые сдвиги для индексов.

#define SMALL_SEGMENTS_TO_SKIP 6

#define log2i(X) ((u32) (8*sizeof(unsigned long long)
- __builtin_clzll((X)) - 1))

u32 capacity_for_segment_count(int segment_count) { return ((1 << SMALL_SEGMENTS_TO_SKIP) << segment_count) - (1 << SMALL_SEGMENTS_TO_SKIP); }

void *_sa_get(SegmentArrayInternal sa, u32 index, size_t item_size) { int segment = log2i((index >> SMALL_SEGMENTS_TO_SKIP) + 1); u32 slot = index - capacity_for_segment_count(segment); return sa->segments[segment] + item_sizeslot; }

log2i использует __builtin_clzll (подсчёт ведущих нулей) для быстрого вычисления номера сегмента.

Clang оптимизирует _sa_get до ~10 инструкций x86-64 (-O3), так что узким местом будет память, а не вычисления индекса. При последовательной итерации можно обходить сегменты напрямую; в segment_array.h есть макрос.

Выделение нового элемента:

u32 slots_in_segment(int segment_index) { return (1 << SMALL_SEGMENTS_TO_SKIP) << segment_index; }

void *_sa_alloc(SegmentArrayInternal *sa, size_t item_size) { if (sa->count >= capacity_for_segment_count(sa->used_segments)) { size_t segment_size = item_size * slots_in_segment(sa->used_segments); sa->segments[sa->used_segments++] = malloc(segment_size); } sa->count++; return _sa_get(sa, sa->count-1, item_size); }

Замечание: можно сделать ёмкость строго степенью двойки, если первые два сегмента одинакового размера. Код станет менее изящным, но это спасает от ~50% потерь памяти при использовании как массива бакетов в хеш-таблице со степенью двойки.

Дженерики

Я применяю технику из прошлой статьи для типобезопасного хранения любого типа. Макрос связывает тип с общей структурой:

#define SegmentArray(type)
union {
SegmentArrayInternal internal;
type *payload;
}

Дальше макросы используют payload, чтобы передавать сведения о типе…

• Обсуждается структура «сегментированный массив» (экспоненциальные сегменты), её плюсы и минусы, и сравнение с существующими решениями: std::deque, ropes, Zig std.SegmentedList, rust-array-stump, plf::colony.
• Критика терминологии: это не «массив» в классическом смысле из‑за неконтигуозной памяти; многие API ожидают сплошной/страйдовый буфер и не подойдут.
• Производительность: при локальных L1-итерациях вычислительная часть индексации может быть ощутима; для больших объёмов память становится бутылочным горлышком. Предлагаются оптимизации итерации по сегментам и замечания про clz/bsr/lzcnt и опции компилятора.
• Виртуальная память как альтернатива: резервирование большого диапазона и по мере роста коммит страниц/guard pages; отмечены плюсы на Linux (MAP_POPULATE, mremap), но плохо для embedded/WASM.
• Сравнение с deque: фиксированные блоки vs экспоненциальные, поддержка prepend, рандом-доступ есть; реализация MSVC критикуется за малый размер блока, GNU/libc++ лучше.
• Недостатки сегментов: ухудшение предвыборки/кэш-локальности при линейной итерации, отсутствие стабильной непрерывности для API, сложность с хеш-таблицами при росте (rehash), потенциальный перерасход памяти при экспоненциальных размерах.
• Предложения: настраиваемый минимальный размер сегмента, функции «склейки» мелких сегментов, разбор условий, когда экспоненциальные сегменты оправданы, и замечания о чрезмерной макротрюковости в C/C23.

I remember that when I was first learning Spanish in high school, I found a piece of (Windows) software that pelted you with a series of pairs of an infinitive and a tense, and you had to conjugate the infinitive accordingly. (Spanish conjugation typically changes the end of the